4 ms·

Overfetching is a massive problem when your entity has multiple N-ary references to other entities, and those entities have multiple N-ary references to other e

Overfetching is a massive problem when your entity has multiple N-ary references to other entities, and those entities have multiple N-ary references to other entities, and those entities have multiple N-ary references to other entities. Suddenly, your frontend or API exhibits high-degree polynomial time complexity.

cjonas 4y ago
Are those references not split out as separate api "resources" that can be queried independently?
- eurasiantiger 4y ago
  That just moves the problem to the frontend. Often it can be worked around with HATEOAS at the architectural level or lazy loading, pagination, etc. in the frontend, but not always.
davedx 4y ago
Yeah this is where GraphQL (+ DataLoader or something like it) really shines. Still don’t see the need for architecting hydras like BFFs
jcparkyn 4y ago
But this is only a problem if one client _needs_ all that data at once, and another client doesn't. Otherwise you would just never return the referenced data (which isn't the type of overfetching the article is talking about).
xwowsersx 4y ago
Yeah so I'm at this point in our main service which is a rather large REST API. For certain endpoints — naturally lists of things — we run into polynomial time complexity, the N+1 queries problem. We query for a list of entities which, when serialized, queries for some child entity and on and on it goes. We've been able to stop some of the bleeding by refactoring queries to use `select_related` and `prefetch_related` (it's a Django app) so that we limit the number of queries, but this only gets us so far. I'm now at a point where I'm not sure what the next step should be. I believe caching may be the next logical step, but I've been hesitant due to concerns about the staleness problem, knowing when to bust the cache, etc. And then even if we do go the caching route, I'm unsure at what level we want to cache. Do we cache individual objects or do we cache the large, fully hydrated models (the ones that require many queries to assemble)? Then there's the problem of having to mix and match fetching objects from the cache in the context of other arbitrary DB queries that can be constructed. How do people generally go about introducing caching? Do you try to limit the scope of caching as much as possible (like to the lowest/smallest objects) and see whether that's sufficient to get the performance you want and then increase the caching surface area from there? Also, what approaches do people take from the technical side? We already use Redis for some things so I implemented a quick proof-of-concept that seemed to work in the small scale. I've also seen people use Elasticsearch to keep fully hydrated/rich models in there and then use ES as the read store. Are there merits to this approach? Crazy? Really keen to hear anyone's thoughts or guidance on this!
- eurasiantiger 4y ago
  My advice would be to avoid attempting to solve the problem by introducing a cache layer or any auxiliary query cache, and instead remove the problem at storage level by leveraging a database solution that 1) stores relationships as links 2) allows queries to resolve relationships to an arbitrary level without specifying join conditions. These two things make sure your entity resolution can happen with direct lookups instead of index lookups (or pog forbid, table scans). If you absolutely cannot do that, cache at entity resolution level. Although, it really doesn’t solve the actual problem, just makes it more bearable by offloading primary DB workload to another DB, so why not run a read replica instead?
  - xwowsersx 4y ago
    Thanks for the reply. Regarding the type of DB you referenced, what are some examples of DBs that allow relationships as links and querying to an arbitrary level? With regards to using a read replica, we do have one that we use for some queries, but that doesn't really resolve the problem with having to do many queries for certain endpoints. We can only eliminate so many queries before the backend code becomes unmanageable, because we effectively forgo any of Django's ORM in favor of our own handcrafted queries that are hard to reuse.
    - eurasiantiger 4y ago
      Potentially anything which supports Cypher or has Apache TinkerPop integration, Neo4j with GraphQL, PostgreSQL with Apache AGE, EdgeDB, SurrealDB (very fresh) and Dgraph (almost but not quite production grade).
      - xwowsersx 4y ago
        Got it, thank you. We are currently using PostgreSQL so I will look into AGE, Edge and Surreal. Any opinions on one vs the other? I guess some of that depends on which one has the best packages for Python.. Thank you!

cjonas 4y ago

Are those references not split out as separate api "resources" that can be queried independently?

eurasiantiger 4y ago
That just moves the problem to the frontend. Often it can be worked around with HATEOAS at the architectural level or lazy loading, pagination, etc. in the frontend, but not always.

davedx 4y ago

Yeah this is where GraphQL (+ DataLoader or something like it) really shines. Still don’t see the need for architecting hydras like BFFs

jcparkyn 4y ago

But this is only a problem if one client _needs_ all that data at once, and another client doesn't. Otherwise you would just never return the referenced data (which isn't the type of overfetching the article is talking about).

xwowsersx 4y ago

Yeah so I'm at this point in our main service which is a rather large REST API. For certain endpoints — naturally lists of things — we run into polynomial time complexity, the N+1 queries problem. We query for a list of entities which, when serialized, queries for some child entity and on and on it goes. We've been able to stop some of the bleeding by refactoring queries to use `select_related` and `prefetch_related` (it's a Django app) so that we limit the number of queries, but this only gets us so far. I'm now at a point where I'm not sure what the next step should be. I believe caching may be the next logical step, but I've been hesitant due to concerns about the staleness problem, knowing when to bust the cache, etc. And then even if we do go the caching route, I'm unsure at what level we want to cache. Do we cache individual objects or do we cache the large, fully hydrated models (the ones that require many queries to assemble)? Then there's the problem of having to mix and match fetching objects from the cache in the context of other arbitrary DB queries that can be constructed. How do people generally go about introducing caching? Do you try to limit the scope of caching as much as possible (like to the lowest/smallest objects) and see whether that's sufficient to get the performance you want and then increase the caching surface area from there? Also, what approaches do people take from the technical side? We already use Redis for some things so I implemented a quick proof-of-concept that seemed to work in the small scale. I've also seen people use Elasticsearch to keep fully hydrated/rich models in there and then use ES as the read store. Are there merits to this approach? Crazy? Really keen to hear anyone's thoughts or guidance on this!

eurasiantiger 4y ago
My advice would be to avoid attempting to solve the problem by introducing a cache layer or any auxiliary query cache, and instead remove the problem at storage level by leveraging a database solution that 1) stores relationships as links 2) allows queries to resolve relationships to an arbitrary level without specifying join conditions. These two things make sure your entity resolution can happen with direct lookups instead of index lookups (or pog forbid, table scans). If you absolutely cannot do that, cache at entity resolution level. Although, it really doesn’t solve the actual problem, just makes it more bearable by offloading primary DB workload to another DB, so why not run a read replica instead?
- xwowsersx 4y ago
  Thanks for the reply. Regarding the type of DB you referenced, what are some examples of DBs that allow relationships as links and querying to an arbitrary level? With regards to using a read replica, we do have one that we use for some queries, but that doesn't really resolve the problem with having to do many queries for certain endpoints. We can only eliminate so many queries before the backend code becomes unmanageable, because we effectively forgo any of Django's ORM in favor of our own handcrafted queries that are hard to reuse.
  - eurasiantiger 4y ago
    Potentially anything which supports Cypher or has Apache TinkerPop integration, Neo4j with GraphQL, PostgreSQL with Apache AGE, EdgeDB, SurrealDB (very fresh) and Dgraph (almost but not quite production grade).
    - xwowsersx 4y ago
      Got it, thank you. We are currently using PostgreSQL so I will look into AGE, Edge and Surreal. Any opinions on one vs the other? I guess some of that depends on which one has the best packages for Python.. Thank you!