OverlappingFieldsCanBeMerged is slow

[redhead]

OverlappingFieldsCanBeMerged can be very slow when many fragments in the query.
Scala implementation resolved it by optimizing the algorithm.

See sangria-graphql-org/sangria#12.

Can we do something similar in graphql-java?

[bbakerman]

Can we do something similar in graphql-java?

of course we can - its an open source project and you can you submit a PR to get this started.

[redhead]

It doesn't follow the spec, so I'm asking if it's the way to go.

I may do it once I will get some free time.

[bbakerman]

Are you saying that way the sangria team solved the performance problem was to not follow spec?

if so can you expand on that and help us understand what they did and how it deviates?

I read that issue but there is a lot of reverse engineering involved and it would be great to get a head start on that

[redhead]

I didn't read it very much into details, but they looked at the algorithm defined by the spec regarding overlapping-fields-can-be-merged, and introduced some optimizations to it (some caching, and some function call refactorings so they don't check things more than needed).

Currently, it is in "experimental" and providing a way how to replace the original validator with the optimized one using their API for validators. Which is not possible in graphql-java if I saw correctly. So the spec algorithm is still the default one, but there is a way to replace it.

See also
(short comment) sangria-graphql-org/sangria#12 (comment)
(details in blog post) https://tech.xing.com/graphql-overlapping-fields-can-be-merged-fast-ea6e92e0a01

[redhead]

Bump.

We would like to sort this our for our application, as it's imposing quite a big performance hit for our API.

[andimarek]

@redhead can you provide us with some profiling results?

[redhead]

I kind of wanted to start a discussion about it first, so I can't give you profiling results of the rewritten algorithm (I can of the current state).

Also, as it's not following the spec's pseudocode, I wasn't sure you would be ok of merging it at all.

[redhead]

This is the state now. As you can see, even constructing quite a big SQL select and running it on the DB server was faster than OverlappingFieldsCanBeMerged.isAlreadyChecked

[andimarek]

How big was the query you are running? Can maybe share it? Thanks

[redhead]

The query is big (2k lines), it's because we are doing a global search query which can potentially return any type of our app model entity. Because of that, it consists of a lot of inline fragments for "casting" to the right GQL type of the app model entity. Most of the entities don't have a common denominator interface to make it consise.

The gist of it is here, it was edited for clarity and to hide our business domain:

query GlobalSearch {
  _search(size: 10, filter: "foobar") {
    edges {
      node {
        gid
        type
        publishedVersion {
          ... on FooType {
            name
            _ancestors {
              gid
              type
              ancestorVersion {
                ... on AType {
                  name
                  _draftType
                }
                ... on BType {
                  label
                  _draftType
                }
              }
            }
          }
          ... on BarType {
            name
            _ancestors {
              gid
              type
              ancestorVersion {
                ... on XType {
                  label
                  _draftType
                }
                ... on YType {
                  yName
                  _draftType
                }
                ... on ZType {
                  zName
                  _draftType
                }
              }
            }
          }

          #################
          ## ...
          ## THIS CAN GO ON LIKE THIS HUNDRED OF TIMES
          ## ...
          #################

        }
      }
    }
    pageInfo {
      hasNextPage
      endCursor
    }
    totalCount
  }
}

[redhead]

Please have a look into the sangria bug report (though written in scala, it probably follows the same algorithm):
sangria-graphql/sangria#296

and the query they reported was:
https://gist.github.com/objmagic/3c881449fcdb3a812a371b86bfa5a3c9

[redhead]

(I had to delete my previous post from today as it wasn't fully valid.)

I took a chance to try to rewrite the algorithm from Scala (sangria) implementation to graphql-java. As you can see, it went quite well:

I have a dirty WIP code of the new algorithm rewritten from scala., All the tests from OverlappingFieldsCanBeMergedTest are passing except for these cases:

1. the error messages are not exactly the same (could be more or less of them, as they can be reported case by case)
2. types that cannot be resolved according to the schema are ignored (fields' types that are unknown in validator are not considered for the validation - they always pass)

[davidcurrie]

+1 for giving this some serious consideration. I'm looking at a Java profile where, of the 3.8s of CPU time spent in the GraphQL endpoint, 3.2s is spent in OverlappingFieldsCanBeMerged.leaveSelectionSet.

[andimarek]

hi,

we are planning to address this issue via #2495

Special thanks to @redhead: we really appreciate the effort you put in, but ultimately we could not accept a scala version of the algorithm from a longterm maintainability POV. But we implemented the same algorithm based on the xing article.

We are planning to replace the current validation completely with the more performant one.

Andi

[redhead]

Thanks a lot. It looks great.

[andimarek]

merged now and will be part of 17.0