Validation slows on high number of aliases

[s1na]

Hey there! I'm using v.1.3.0 of this library to query a high number (say 2000) of the same thing:

query slots($blocknum: Long!) {
  slot0: block (number: $blocknum) {
    account(address: "...") { storage (slot: "...")}
  },
    slot1: block (number: $blocknum) {
    account(address: "...") { storage (slot: "...")}
  },
    slot2: block (number: $blocknum) {
    account(address: "...") { storage (slot: "...")}
  },
  ....
  slot2000: block (number: $blocknum) {
    account(address: "...") { storage (slot: "...")}
  }
}

And noticed this becomes way slower than splitting this query into pages of 100 each. I narrowed down the slowdown to the first loop of Validate. I'd appreciate if you could take a look and see why this is happening.

[pavelnikolov]

@s1na is this something that became slow recently? Was it more performant before? Are you repeating the same fragment 2000 times?

[s1na]

@pavelnikolov before v1.3.0 I was testing on v0.0.0-20201113091052-beb923fada29 which was also as slow. So AFAIK it's not a recent regression. Yes it's the same fragment only with different field values.

[pavelnikolov]

Do you think that we must be reusing validation? I haven't had the time to dig deeper into this issue, however, having 2000 objects being returned doesn't sound like something extremely performant. Are you displaying these on some UI or are you processing these in the backend?

[s1na]

Sorry to get back to you late on this. The problem isn't just that requesting 2000 objects is slow. Surprise is that making one query for 2000 objects is much slower than 10 queries for 200 objects. I did a profiling of our code when executing this query and the profile seems to suggest the problem lies in validateSelectionSet and specifically validateOverlap:

graphql-profile.tar.gz

Edit: hmm for some reason the svg file is not loading completely. I'll just upload the profile itself.

[s1na]

As far as I can tell this is not an issue in the graphql-go library. The specified algorithm for the OverlappingFieldsCanBeMerged rule has a quadratic complexity.

I found this great explainer article which also shares a faster algorithm. Their algo was merged in a few implementations (reference: sangria-graphql-org/sangria#12).

It's not a small change so I wanted to ask you if you'd consider deviating from spec to implement this optimization? I don't have enough understanding of it to tell if it improves the general case or only some cases.

[pavelnikolov]

I wanted to ask you if you'd consider deviating from spec to implement this optimization
No, unfortunately we don't want to deviate from the spec. You can propose a spec change. And then we could consider it. Ideally, we want to keep this library spec-compliant. Opt-in changes that do not introduce breaking changes would be welcome, though. PRs with improvements are always welcome. Thank you for posting this issue first.