Graph algorithms

The wrappers in aiq are SECURITY INVOKER, so they run as the caller and the compiled functions underneath them have to be callable by that caller too. Granting the wrapper alone produces a permission error at the first call, from a function name the caller has never heard of, so one call grants both halves.

They are off by default because the first call in a backend builds an adjacency snapshot of the graph, and that is the largest allocation this extension makes — 225 MB on a four-million-edge graph. Nothing builds it until somebody asks, and on a fresh install nobody can.

aiq.enable_graph_algorithms does not grant itself, for the obvious reason.

Related what else to size before enabling · installing the extension in a Postgres you already run

The dialect budgeted seven modes and six modifiers so that it fits in a prompt, and six new modes would have spent that budget on questions asked far less often than LOOKUP. This costs two modes and no new modifiers: DEPTH, TYPE and LIMIT already mean here exactly what they mean on GRAPH.

PATH is one mode with two arities rather than two modes, because a shortest path is the Steiner tree of two terminals — two names give the best routes, three or more give the smallest structure joining all of them.

DEPTH on RELEVANCE is refused, and the refusal is the whole argument in one error message — it ranks by how much score reaches a node, not by how many hops away it is. A caller who writes it is reaching for GRAPH, and the error says so. PATH with one name is refused for the mirror reason.

unresolved and exhausted appear on these two envelopes, each for a stated reason: the first — which LOOKUP carries too — because a dropped seed would make "no such entity" look like "nothing is related", the second because these are the two budgeted modes and a flag on the seven that cannot be truncated is a flag nobody reads.

Related the mode in the grammar reference · the seven modes it joined

This is personalised PageRank by local push. The important property is not the ranking but the locality: the walk only touches the part of the graph the mass actually reaches, so a query on a million-node graph costs what the seed's surroundings cost. Measured at four million edges it is 93 ms at the median.

It is also anytime. The unpushed mass is tracked as a residual, so running out of budget under-estimates every score and leaves the ordering intact — which is why budget_exhausted rides on every row rather than living in a second call. "Nothing else is related" and "I ran out of budget" are different answers and the shape of the result has to keep them apart.

Do not reach for this at one or two hops. The recursive walk behind GRAPH answers a depth-2 question in about a millisecond on the same graph. This earns its place when you need the order, not the neighbours.

Related `GRAPH`, for one and two hops · the `GRAPH` mode

Each edge costs 1 − ln(weight), so "shortest" means fewest hops, tie-broken by how well corroborated they are. The 0.95 subsidiary claim makes route 1 cost 2.05 rather than 2.00, which is enough to order two routes of the same length without letting a long chain of certain edges lose to a short unreliable one.

The search runs from both ends and meets in the middle. That matters most when there is no path: a one-sided search has to settle the whole component before it can say so, which on a four-million-edge graph exhausted the budget on 96 calls in 100. Two frontiers settle roughly the square root of that volume, and the single best path comes back in 8 ms.

The alternates are what cost. Asking for k=1 never runs out of budget on the graphs we have measured; asking for three hits the ceiling on about a third of calls at four million edges, and returns the best path plus however many alternates the budget bought.

as_of is accepted here and applied while the search is running rather than to the result — the only correct placement, since filtering afterwards returns the k best paths including expired edges, minus the ones that happened to be expired. This is the one read path in Percolate that honours valid_to.

Related why an empty result is usually correct

The adjacency snapshot is built through SPI as the caller, so RLS filters it at build time, and an edge whose endpoint the caller cannot see is dropped rather than walked — an edge can otherwise disclose that an invisible node exists just by being visible itself.

That snapshot is then cached in the backend, which is exactly the shape that leaks: a pooled connection handed from one tenant to the next would serve the first tenant's graph to the second. Every entry point re-checks a fingerprint — role, claims, and the tables' modification counters — and rebuilds rather than reusing somebody else's. It is asserted by behaviour rather than by reading the code: one backend, two identities, and the second must get a different snapshot.

Related the same query asked twice with different claims · querying as a superuser, and why it looks wrong

confidence is the best single path, computed as the product of the weights along it. There is no per-hop penalty, deliberately: a long chain of certain edges should not lose to a short uncertain one, which is precisely what the two answers above show.

support is the corroboration count — how many independent neighbours carry belief into that node — combined by noisy-OR. A confident number with support 0 is one path's opinion. Read together they answer how much of this rests on a model's guess, which is the question an extracted graph makes unavoidable.

The walk stops at a rank bound rather than at a confidence floor, and that is not an implementation detail: a floor bounds belief, not work. On a small-world graph a floor of 0.2 and a floor of 0.05 both reached two thirds of a million nodes, because five hops of 0.65-weight edges clear either. The walk settles in decreasing confidence, so the first k nodes it settles are the answer — which took this from 277 ms with every call over budget to 5 ms with none.

Related where extracted edges and their weights come from

This is the Steiner tree, which is NP-hard, so it is a 2-approximation rather than an answer: one multi-source walk labels every node with its nearest terminal, the connections are read off the edges that cross a boundary between two territories, a minimum spanning tree picks which to keep, and non-terminal leaves are pruned.

terminals_joined is there because a partial answer must not read as a complete one. A terminal whose neighbourhood the walk never reached is left out and counted, rather than quietly dropped.

The single-walk form replaced one walk per terminal after measuring it: at four million edges the per-terminal version spent 502 ms of a 500 ms budget and still returned a partial answer. The same call is now 130 ms and joins every terminal.

Related retrieval, which is what produces the terminals

Components is union-find, which is linear and about as cheap as a compiled graph function gets: 184 ms over 749,000 edges. The component is named by the smallest node id in it, so the name is stable across runs — a component id that moves between two runs over the same graph is not an id.

It is also the function that most needs the snapshot filter in front of it. An evidence graph records a weak opinion on every pair it ever considered, because "we looked and found nothing" is a different fact from "we never looked" — and components over all of that is one component containing everything. Build the snapshot over the relations and the weight floor you mean first:

select aiq.graph_snapshot(true, array['operated_by','subsidiary_of'], 0.6);

That filter is pushed into the build query, so the rows never arrive and are never resident — 3.8 s and 225 MB becomes 677 ms and 98 MB on a fifth of a four-million-edge table. It is also sticky: the filtered graph is what every other function walks until the next build, and every result reports the filter it ran under, so a caller can always tell which graph it just walked.

graph_induced exists for a round trip rather than for compute. A repair pass over thousands of small clusters, fetching each cluster's internal edges with its own query, is thousands of round trips for a few hundred bytes each — and one call answers all of them, because an edge internal to the union of disjoint components is internal to exactly one of them.

Related what the rest of the system costs, measured the same way

graph_reach_build runs a few passes of HyperLogLog union over the adjacency and keeps only the cardinality: four bytes per node per depth, and the query is then an array read. Read the number as an order of magnitude rather than a count — the median error is about 6% and the 95th percentile is around 22%, which is plenty for deciding whether a walk will touch thousands or millions and useless for anything that needs the figure itself.

Pass exact => true and it also runs the real traversal, which is how the two columns above ended up side by side. That is a check, not a habit: the exact count is the query the sketch exists to avoid.

The build is granted to the same role as the queries, and that was a correction. It looked like a maintenance operation to withhold — but the sketch lives in the backend that built it, over the graph that caller could see, so a sketch built by an administrator and read by a tenant comes back "estimate": null. An index only its author can use is not an index.

Related what to schedule, and what to watch

plpgsql resolves a function name when it runs, not when it is created. That is what lets the two halves install separately, and it is exactly why the failure mode is silent: a database can install cleanly, pass its surface audit, and then fail on the first call because the compiled half is older than the SQL half.

That is not an exotic state. A SQL reload does not carry a .so, so it is the normal condition of any stack that pulled a new schema without pulling a new image — the case this page's own functions are most likely to be missing in.

Three rules follow, and they are why this is a section rather than a footnote. A caller across the boundary checks first, and the check names the extension rather than raising function p8_graph_ppr does not exist, which reads as a corrupt schema. The compiled half stays pure or close to it — the parser is computation over a string, the graph functions read through SPI as the caller so row-level security still applies, and nothing across the boundary writes. And version skew is treated as a first-class state rather than an error to explain away, because two halves shipping on different rails will diverge.

The report is derived from the catalog rather than from a list somebody maintains, since a hand-written list drifts both ways at once — claiming a crossing that has gone and missing the one added last week. Deriving it caught a false positive worth keeping in mind: the first version matched aiq_parse() inside the error message several functions raise to apologise for its absence, and reported four crossings that were apologies rather than calls.

Related installing the two extensions in the right order · what to check after an upgrade

The adjacency snapshot is per backend: 225 MB at four million edges, and roughly twice that at the peak of a build. Eight concurrent callers on a 7.65 GiB machine did not produce a slow query — the OOM killer took a backend with signal 9, and Postgres did what it must when a backend dies holding shared memory: terminating any other active server processes, then recovery. One graph query took the cluster down.

Nothing in Postgres prevented it, and that is structural rather than an oversight: this memory is allocated by the extension, outside work_mem, so no existing setting sees it and the planner does not know it exists.

So there is admission control now, built from a primitive Postgres already has. A backend takes one of percolate.graph_snapshot_slots (default six) session-level advisory locks before it builds and holds it as long as it holds the snapshot — locks and memory released together when the connection ends. A backend that cannot get one is refused with a sentence telling it what is held and how to release one. Re-run at eight clients: six served, two refused, cluster alive.

It is a setting rather than a constant because the right value is a function of how much memory the machine has, and it is a superuser setting because a limit the callers it bounds can raise is not a limit. There is a second one, percolate.graph_snapshot_max_mb, that bounds a single snapshot — the two are not substitutes: the ceiling stops one graph too large for any backend, the slots stop N ordinary callers, and it was the second that took the box.

That is the same discipline as everywhere else here — turn a quiet catastrophic failure into a loud refusal — applied to the one failure on this page that was not a wrong answer but an outage.

Three ways to live with it, and the choice is operational: a small number of long-lived workers that build once, preloading at connection start, or moving the snapshot into shared memory. The measurement above promoted the third from "the natural next build" to a requirement above single-digit concurrency. Six slots is a guard rail, not a scaling story.

Every one of those figures is the call, not the algorithm, and the distinction is worth the four fields it costs. A budget measured from after the snapshot is fetched reports 96 ms of a 2,689 ms wait on a cold first call: both numbers are true of the walk, and the one an operator would build an SLO on is off by 28×. So the answer carries elapsed_ms for the call, walk_ms for the algorithm, build_ms for the snapshot, and keeps exhausted (the answer is partial) separate from over_budget (the call took longer than it was given) — opposite problems with opposite fixes.

Figures are from one run of our graph benchmark — a latency probe and a concurrency probe, neither published. Re-running moves the latency probes by 10–30% and the build probes by up to 2×, so read the ordering and the slope rather than the third digit.

Related the engine's own hot paths, measured the same way · worker pools and what to watch