Graph Index

QueryIndexingJoinsGraph

Stable On by default · production-ready

What it is

Most joins between related tables — customers → orders, orders → order_lines — repeat the same shape over and over. A hash join rebuilds a hash table from scratch every time. The Join-Graph remembers the relationship instead: the engine keeps hot relationships warm and serves selective joins along them near-instantly, without rebuilding join state on every run.

There are two ways to get one:

• Automatic — on by default. The engine captures a Join-Graph edge as a byproduct of running an eligible join, and reuses it on the next run. Nothing to declare.
• Declared — CREATE GRAPH INDEX pins a relationship you know is hot. A declared edge is eagerly built, never evicted, survives restart, and unlocks the navigational serve fast-path for selective lookups along it.

Why it matters

• Navigational serve — a selective join over a declared graph index (… JOIN … WHERE <join key> = <value>) is answered directly from the remembered relationship, materializing only the matching rows. Neither side of the join is even scanned. A repeated relationship join is answered as a microsecond-scale lookup of just the matching rows, no matter how large the tables grow.
• Zero maintenance to adopt — the automatic layer needs no DDL and no tuning; it warms itself from your workload and stays within a fixed memory budget.
• Correct by construction — every fast-path is freshness-checked. If a write touched either table since the cache was built, the query transparently falls back to a correct hash / sort-merge join. A stale row can never be served.

flowchart LR
  classDef q    fill:#1f2640,stroke:#7c5cff,color:#e8eaf0
  classDef idx  fill:#1f2640,stroke:#00d4ff,color:#e8eaf0
  classDef hit  fill:#1f2640,stroke:#4ade80,color:#4ade80

  Q["SELECT … FROM customers c<br/>JOIN orders o ON c.id = o.customer_id<br/>WHERE c.id = 42"]:::q
  Q --> IDX["Graph Index (declared)"]:::idx
  IDX --> HIT["Only customer 42's orders<br/>returned — neither table<br/>scanned"]:::hit

The automatic Join-Graph

The automatic layer is on by default — there is nothing to create. As eligible joins run, the engine captures the relationship as a byproduct of running the join and serves it back on subsequent runs. It only publishes an edge when the parent side’s keys are provably unique (a real foreign-key → primary -key shape); if neither side is unique, the query runs a one-time sort-merge and no (potentially wrong) edge is cached.

Captured edges live under a fixed memory budget (256 MiB by default). When the budget is full, the least-recently-used non-declared edges are evicted — the Join-Graph never grows without bound or slows the running system to warm a cache. A write to either table drops that relationship’s edge, so freshness is automatic.

You can turn the automatic layer off if you want fully deterministic planning:

aetheriusd --disable-join-graph      # or set AETHERIUS_DISABLE_JOIN_GRAPH=1

Declaring a Graph Index

CREATE GRAPH INDEX pins one or more relationships (LINKS) between a parent column and a child column. A declared edge is eagerly built, marked non-evictable, persisted in the catalog, and — crucially — enables the navigational serve fast-path.

CREATE GRAPH INDEX customer_orders ON LINKS (
  customers(id) -> orders(customer_id) CARDINALITY '1:N'
);

-- Several relationships in one graph index:
CREATE GRAPH INDEX order_graph ON LINKS (
  customers(id) -> orders(customer_id)   CARDINALITY '1:N',
  orders(id)    -> order_lines(order_id) CARDINALITY '1:N'
);

DROP GRAPH INDEX customer_orders;

Each link reads parent(key) -> child(foreign key). The syntax rules:

• Cardinality is required and must be '1:1' or '1:N' (a '1:1' declares the child key unique too). 'N:M' is not supported.
• Link keys are single-column and must be an integer axis (BIGINT / TIMESTAMP). A composite link key is rejected.
• Creation is strict and all-or-nothing: every table and column must resolve, and the declared cardinality is verified against the live data. A '1:1' with duplicate keys, or a non-unique parent, fails the statement and names the offending key — the index is never created in a state it can’t honour.

Navigational serve: which queries hit the fast-path

The fast-path routes a single inner equi-join over a declared edge where one side carries a selective predicate on the join key and the other is a plain scan. The predicate can be:

Predicate	Example
Point	WHERE c.id = 42
Range	WHERE c.id BETWEEN 10 AND 20, WHERE c.id >= 100, < <= > >=
IN-list	WHERE c.id IN (7, 42, 99) — served as N disjoint point lookups, unioned

-- Served navigationally from the declared graph index:
SELECT c.tier, o.id, o.total
FROM   customers c
JOIN   orders o ON c.id = o.customer_id
WHERE  c.id = 42;

Keys must be integer literals. NOT IN, non-equi joins, multi-way joins, and predicates on non-key columns are not eligible — they run the normal plan and return the same result. As with every index here, when the fast-path can’t serve (no cache yet, a recent write, or an unsupported shape) the query transparently drains to a correct hash / sort-merge join.

NULL join keys are skipped exactly as a hash join skips them, so results match the relational join semantics byte-for-byte.

Restart & freshness

A declared graph index’s definition survives a restart (it re-arms from the catalog); its derived acceleration cache does not — it is rebuilt automatically on the first navigational query after restart, then served. Because every serve is freshness-checked, a cache that is still warming never serves a stale answer.

Under a burst of concurrent first-queries, only one query pays the rebuild cost; the others take the (correct) fallback to a normal join in the meantime — no thundering-herd of redundant rebuilds.

Evolving: incremental maintenance

Today a write to a member table invalidates the relationship’s cache, and the next read rebuilds it. Incremental cache maintenance — keeping the cache current without a full rebuild — is in development. It is not yet active on the serving path; the stable, supported behaviour is invalidate-and-rebuild, always freshness-checked for correctness.

Observability

Every live edge — automatic or declared — is visible in a system view:

SELECT * FROM system.join_graph;
-- edge | declared | parent_rows | child_rows | bytes | hits | last_used_epoch

EXPLAIN annotates an eligible join with the strategy it chose and whether the cache was warm:

JoinStrategy: JoinGraph(edge=customers:id<->orders:customer_id, cached=yes)

Key concepts

Term	What it means
Edge	A remembered relationship between two (table, column) endpoints.
Declared vs. automatic	Declared edges (CREATE GRAPH INDEX) are eager, non-evictable, restart-persistent, and enable navigational serve. Automatic edges are learned, budget-bounded, and LRU-evictable.
Navigational serve	Answering a selective relationship join directly from the remembered relationship, materializing only matching rows — neither table is scanned.
Freshness guarantee	A cache serves only when it is provably current; if either table changed since it was built, the query transparently runs a normal join — a stale result is never served.

Advanced Indexing (PTI) →

The broader CREATE INDEX surface and covering aggregates.

Graph-Relational Duality →

Query the same data as tables or as a graph.

Native Graph Traversal →

Traverse relationships natively in SQL.

Adaptive Query Execution →

How the planner picks join strategies at runtime.