Query Engine#

The query engine lives in relata-query. It parses RelataDB SQL (ANSI SQL with extensions), plans with ACL pushdown, optimizes with a cost-based join-ordering and index-selection pass, and executes against columnar, graph, vector, and full-text stores. Execution is streaming end-to-end — no intermediate result is fully materialized in memory unless it spills to disk.

Query lifecycle#

1. Parse — extract statement shape, optional PURPOSE prefix, optional AS OF temporal clause, and any graph/vector/identity operators in the projection list.
2. Purpose check — when PURPOSE '<id>' is declared, it is validated against the PurposeRegistry and recorded for audit. Purpose is optional; when absent, the engine runs normally.
3. Plan — resolve type references against the ontology, compile the principal's ACL into per-type bitmap predicates, generate a physical plan. The ACL bitmap is computed once per (principal, type) pair and cached.
4. Optimize — the cost-based optimizer picks join order, chooses scan strategy, picks hash-join build/probe sides, and applies MV rewrite when a materialized view covers the query.
5. Execute — streaming scan, hash join, aggregation, graph BFS, vector ANN, and BM25 run fused. The executor never holds the full result set in memory.
6. Assemble — result rows are packed into Arrow batches. If WITH PROVENANCE was requested, PROV-O columns are attached. An audit log entry is written.

Statement shape#

[EXPLAIN POLICY]
[PURPOSE '<id>']
SELECT <projection>
FROM <Type | TVF>
[AS OF '<timestamp>']
[WHERE <predicate>]
[ORDER BY <col [ASC|DESC]>]
[LIMIT n [AFTER '<cursor>']]
[WITH CACHE | WITH NOCACHE]
[WITH PROVENANCE]

• EXPLAIN POLICY — prints the ACL decisions the planner made for the current principal without executing. Use to debug "why can't I see this row?"
• PURPOSE '<id>' — optional. Recorded in audit; may drive policy enforcement. The engine runs without it.
• AS OF '<timestamp>' — selects the valid-time axis (what was true at that timestamp). For the system-time axis use AS OF SYSTEM TIME '<ts>'; AS OF CURRENT is sugar for both axes at NOW. See Bi-temporal reference.
• WITH PROVENANCE — attaches the prov struct of each result row, so the caller can trace every fact to its source agent and activity.
• WITH CACHE / WITH NOCACHE — overrides the default result-cache behavior for this query.
• LIMIT n AFTER '<cursor>' — keyset pagination. Cursor is opaque and stable across concurrent writes.

ACL pushdown#

Access control compiles into scan-level bitmap predicates, not a post-filter.

The budget gate prevents a pathological ACL rule from OOM-ing the reader. Rejected queries return RFC 7807 errors with the offending rule ID.

Cost-based optimizer#

The optimizer runs between planning and execution. It is not a stub or a roadmap item. It picks:

• Scan strategy — sequential scan vs. index lookup (bloom filter, range index, IdentityIndex, vector ANN).
• Join order — build/probe sides based on cardinality estimates from HLL sketches and zone maps.
• Join algorithm — hash join (default), spill-to-disk hash join for large build sides, or nested-loop for non-equi joins.
• MV rewrite — if a materialized view covers the query, rewrite to read from the MV instead of the base table.

Cardinality estimates come from HLL (HyperLogLog, approximate COUNT(DISTINCT)) and Count-Min-Sketch sketches maintained per column. Query-level access: HLL_COUNT(col) and CMS_ESTIMATE(col, value).

DataFusion bridge#

Columnar aggregation uses Apache DataFusion as a compute bridge. The planner emits a DataFusion logical plan for aggregation-heavy queries; the result is streamed back through the same Arrow batch pipeline as the native executor. DataFusion is used for its vectorized aggregation kernel, not as a SQL parser or planner — those remain in relata-query.

Execution — streaming, no full materialization#

Aggregation#

• Columnar path — used for full-table GROUP BY (no filter on the aggregate input). Vectorized over Arrow columns.
• Row path — used when the aggregate input is filtered. Row-at-a-time evaluation.
• Supported: GROUP BY + COUNT(*), SUM, MIN, MAX, AVG, COLLECT_LIST, HLL_COUNT.
• ORDER BY multi-column with ASC/DESC tiebreakers (OrderBy.tiebreakers, ast.rs:1316; applied at executor.rs:2665).

Graph execution#

The graph plane is CSR (compressed sparse row) adjacency. Two production traversal engines:

The PLL (pruned landmark labeling) distance index (crates/relata-graph/src/pll.rs) is wired into GRAPH_SSSP (when algo => 'pll', investigation_ops.rs:1938) and into GRAPH_DIJKSTRA as an undirected reachability pre-check (investigation_ops.rs:2200). PATHS_BETWEEN and default single-pair shortest-path enumeration still use bidirectional BFS / DFS over paged CSR.

10+ SQL graph operators are implemented: GRAPH_DIJKSTRA, GRAPH_LINK_PREDICT, GRAPH_SCC, GRAPH_CYCLES, GRAPH_SSSP, GRAPH_SPANNING_TREE, GRAPH_APSP, GRAPH_DIAMETER, GRAPH_SIMILARITY, GRAPH_NODE_METRIC.

The incremental degree index maintains per-node in/out degree counts as edges are written. DEGREE(node) is O(1) at query time — no CSR re-scan.

Vector search#

The primary ANN index is a custom HNSW implementation in vector.rs — not a wrapper around an external library.

Supported distance metrics: cosine (primary), L2, dot product. pgvector-compatible operators <=>, <->, <#> parse and route to the HNSW index.

search_filtered applies ACL to vector results. Adaptive pre-filter prevents the recall cliff on selective ACLs by filtering the candidate set before HNSW traversal, rather than filtering ANN output post-hoc.

Full-text search (BM25)#

The full-text engine is custom BM25 — not Tantivy. It is purpose-built for integer posting lists and token interning to fuse cleanly with the vector path.

RELATA_SEARCH_PRESET (strict / balanced / lenient, default balanced) controls edit-distance fuzzy expansion cluster-wide.

Hybrid retrieval#

BM25 and vector similarity fuse via reciprocal-rank fusion (RRF). One SELECT handles both textual relevance and semantic similarity in one pass.

SELECT id, text, score
FROM Post
WHERE BM25(text, 'financial fraud') OR VECTOR_SIMILAR(embedding, '[0.12, ...]', 0.8)
ORDER BY RRF(BM25_score, vector_score, k = 60)
LIMIT 20;

Materialized views#

CREATE MATERIALIZED VIEW ProfileEngagement
ON COMMIT
AS
SELECT author_id, COUNT(*) AS post_count, SUM(likes) AS total_likes
FROM Post
GROUP BY author_id;

RELATA_MV_MAX_ROWS (default 1,000,000) caps cached rows in an incrementally-refreshed MV. Past the cap, the MV falls back to the base table — queries still run, just slower.

Query result cache#

Result cache memoizes query results keyed by (SQL text, principal, AS OF time). Invalidation is driven by commit manifests: any commit touching a referenced table invalidates that query's cache entries. Per-query override: WITH CACHE or WITH NOCACHE.

Pattern tracker + speculative prefetch — observes query patterns and pre-fetches likely-next pages into L1 before the client asks.

Watch subscriptions#

A query can be registered as a watch subscription. The engine re-evaluates the query on every commit that touches a referenced table and pushes the diff to subscribed clients over a long-lived gRPC or HTTP stream. Watch subscriptions use the same planner and ACL path as regular queries — the result set is always policy-filtered.

Per-column bloom filters#

Each Identity-typed column has a bloom filter per Parquet row group. The planner consults the bloom before opening a row group. Point lookups on phone numbers or IBANs typically skip 90–99% of row groups before reading any data.

See also#

• Architecture Overview
• Data Model
• SQL Reference
• Hybrid Search