Relationship lookups are exponentially slow

[dsblank]

The gramps algorithm for finding relationships is suboptimal, and on top of that gramps-web adds a cache of every single person and family in the tree on each request (impractical for large trees). This PR fixes both problems by using a series of SQL queries and better algorithm.

The 2 Problems

Cache (memory, unbounded over time). CachePeopleFamiliesProxy, used by both /api/relations/* endpoints today, deserializes every Person and Family in the tree into full objects before answering a single query, regardless of how close the two people actually are. On a 101,518-person tree this costs roughly 700MB and multiple seconds, per uncached request. It's a local variable, not shared across requests, so nothing amortizes, the same cost is paid again and again.

Algorithm (exponential, not proportional to size). RelationshipCalculator.__apply_filter / get_relationship_distance_new enumerate every distinct path to an ancestor, not just the shortest one. Under any pedigree collapse, a normal genealogical pattern, shared distant ancestors, or simply a search that reaches past a tree's actual recorded depth, the same small set of ancestors becomes reachable through an exponentially growing number of path strings. Measured consequence: a pair connected through only 21 real ancestors took over 3 minutes and pinned a server core at 100%. It's not size-dependent either, an ordinary 7,252-person tree showed multi-second latency on a routine query, because the cost tracks pedigree-collapse density, not how many people are in the tree.

Together, these aren't edge cases: this endpoint is used on person views in both gramps-web and gramps-connect. Of course, knowing the relationship is very important for genealogy research.

Proposed Solution

Extract the ancestry graph directly from family.json_data's child_ref_list using each backend's native JSON functions (jsonb_array_elements on Postgres, json_each on SQLite), no Person/Family object construction anywhere. Hold it as a small, indexed table (child_of(parent, child, code)) and answer each query with a proper breadth-first search, every node visited once, so cost tracks distinct people, never distinct paths to them, instead of gramps-core's path-enumerating recursion. Hand the result to gramps' own, unmodified, locale-aware string formatting: only the search is replaced, not the wording.

And I know you suggested that we should avoid coding for proxies, but without doing the same optimization for the private proxy would make it impossible to compute for larger trees.

So, privacy filtering (mirroring PrivateProxyDb's three rules exactly: a private person, a private family, or a private child reference are all invisible) is a live SQL predicate, not a second precomputed graph. person.private / family.private are already plain integer columns on both backends, so there's nothing to keep in sync between a "restricted" and a "full" view, there's only ever one query, with or without one extra clause.

Status: developed thoroughly and ready for a PR

RelationResource and RelationsResource (/api/relations/<h1>/<h2> and its /all variant) both run on this path now, gramps_webapi/api/resources/relationship_graph.py plus the rewritten relations.py. All previous tests passing.

• Zero new indices on the real tables. Every lookup against person / family / event is a point lookup by handle (optionally plus treeid), already covered by each table's existing primary key. The only new index in the whole change is on the graph itself, and that table is session-scoped and ephemeral, rebuilt fresh at the start of each request, not the trigger-maintained permanent table validated separately as a future option but deliberately not shipped here.
• No schema changes at all. This is a self-contained gramps-web-api change.
• The project's own existing test suite passes. tests/test_endpoints/test_relations.py, 17/17, after this port. It caught two real bugs the whole session's own live-server testing never happened to exercise: an off-by-one in the depth cutoff, and a locale-translation gap where get_relationship_calculator() picks the right calculator class per locale but doesn't set _locale on the instance, so every string silently fell back to English regardless of the requested language.

Numbers (measured, 101,518-person tree)

	Before	After
Memory per uncached query	~700 MB	~0 (no object construction)
Typical query	10-15 s	under 1 ms
Worst case (pedigree collapse)	3+ min, pins a CPU core	under 1 ms
New tables / columns / migrations required		none

Ideally this would live in gramps in the future. Let me know and I will create the PR.

[DavidMStraub]

Indeed it's way too slow and it was unbearably slow before I added caching. The root cause is the Gramps core implementation.

I just quickly skimmed your suggestion now and I'm sure it's good, but for now just one general strategical comment: I think by identifying all the bottlenecks in Gramps core and reimplementing them in Gramps Web API, we're basically rebuilding a new Gramps core in Web API. Should this really be in scope? With all the maintenance implications?

I know, the reason we're even contemplating this is that Web API evolves much more quickly than Gramps core. But I think at some point a line has to be drawn where Web API's scope ends.

This was just a general comment, will review in detail later.

Thanks for the suggestion!

[dsblank]

I think by identifying all the bottlenecks in Gramps core and reimplementing them in Gramps Web API, we're basically rebuilding a new Gramps core in Web API. Should this really be in scope? With all the maintenance implications?

I share your concern. I don't mind putting this data structure and algorithm into a library package, possibly even under the gramps-project repo itself, for now. Then gramps DBAPI, SharedPostgreSQL, PostgreSQL, or gramps-web-api can incorporate it if they wish. We did this for gramps-object-query-language and that was very useful, being able to be shared (by a gramps addon, and gramps-web-api as well).

Let's see what that looks like.

[DavidMStraub]

But that's also a workaround and shifts the maintenance burden, but doesn't prevent drift.

I think it should be addressed at the Gramps project level, I have some ideas I need to formulate, give me a few days.

[Nick-Hall]

I'm happy with this being in core Gramps or a library owned by the Gramps project. Alternatively, you start with it in the Web API and move it later.

[dsblank]

Thanks @Nick-Hall. I'd prefer the stand-alone collection as that makes testing somewhat easier. Sound good @DavidMStraub?

[DavidMStraub]

I'll try to write up this idea ⬆️ tonight

[DavidMStraub]

... and I will not review PRs until we've aligned on a solution. Let's take that time please.

[DavidMStraub]

Took a bit longer, here it is: https://gramps.discourse.group/t/proposal-process-for-upstreaming-web-api-improvements-into-gramps-core/9940

[dsblank]

I've added:

1. gramps-sql-extensions
2. Replace RelationshipCalculator with a fast SQL-derived ancestry graph #966 - PR that uses the library. We will probably need to alter some instructions on installing without dependencies. I left the relationship tests in gramps-web, but there many more in the new repo [1]

I have a few repo's I'll propose to @Nick-Hall to moving under the gramps-project umbrella.