Status
Proposed
Date
2026-06-05
Context
The query compiler picks a join order from a fixed strategy for each query type and from coarse selectivity labels in the ontology. Each label marks a filter as high or low selectivity. Flat chains start from the edge table, and foreign key (FK) star queries start from the center node.
The labels hide large differences. A string filter on a column with tens of thousands of distinct values gets the same label as one on a column with three.
Profiling showed the cost of this. When the compiler replaced filter-only common table expressions (CTEs) with joins, rows read on code graph queries dropped by 70%. That gain was luck, because the new shape happened to suit that query. For a different filter combination, the old shape might have been better. Without cardinality data, which counts rows and distinct values, the compiler cannot make this choice on purpose.
The compiler already supports several join strategies:
| Strategy | Entry point | When used |
|---|---|---|
| FK star | Center node | All hops use an FK to the same center |
| Flat chain | Edge table | Default for edge-based queries |
| Single node | Node table | No edges |
The gap is strategy selection. With row counts and value distributions per column and namespace, the compiler can pick the entry point and join order with the smallest intermediate results.
Decision
The compiler orders joins by cost, with column statistics that ClickHouse maintains on insert.
The compiler estimates the rows that each valid join order reads and picks the cheapest one.
Query types affected
Join ordering applies to every query that joins two or more tables, so only bare single-node searches are out of scope.
| Query type | Tables joined | Current join strategy |
|---|---|---|
| Traversal, single hop | One edge and one or two nodes | Edge first, then join the nodes |
| Traversal, multiple hops | N edges and N+1 nodes | Edge first, then join each hop in sequence |
| Aggregation | Same as traversal, with grouping | Same as traversal |
| FK star | Center node and N target nodes, no edges | Center first through FK columns |
| Neighbors | One center node and one edge scan | Center first |
| Path finding | Two anchor nodes and recursive edge CTEs | Anchor CTEs, then edge expansion |
The planner is the plan pass of the compiler. For a single-hop traversal, it starts from the edge table or from the more selective node. For multiple hops, the direction of each hop matters. For an FK star, the planner joins the smallest target first to narrow the result early. For neighbors, the planner scans the center or the edges, based on center filters beyond the pinned IDs. Path finding keeps its recursive structure. Its anchor selection is still a join ordering choice: which endpoint expands first, and how to split forward and backward depth.
Statistics
We keep three types of statistics, each in its own ClickHouse table that merges aggregate states:
| Statistic | Covers | Key |
|---|---|---|
| Value frequency | Booleans, enums, and strings with few distinct values | Table, column, traversal path, and value |
| Token frequency | Strings with more distinct values | Table, column, traversal path, and token |
| Equi-depth histogram | Integers, timestamps, dates, and floats | Table, column, traversal path, and bucket |
The ontology property types decide the category of each column at load time, so nobody lists columns by hand. The statistics skip UUID columns, because their selectivity is always one row. They also skip virtual columns and columns that cannot be filtered.
One materialized view per node table fires on insert and writes aggregate states to the statistics tables. The view counts distinct entities per value or bucket with a HyperLogLog sketch, which gives an approximate distinct count. The sketch ignores duplicate values, so the old row versions that node tables keep after an update do not inflate counts.
Deleted rows still contribute to the statistics. We accept this error, because exact counts need a periodic batch job with a deduplicating scan. For join ordering, the error is negligible.
Statistics are partitioned by traversal path, the namespace path stored on each row, so each namespace has its own statistics. Entities without a traversal path, such as users and runners, use an empty partition key for global statistics. The total row count of an entity comes from the histogram of its ID column.
A ClickHouse dictionary, an in-memory lookup table, sits over the statistics tables. It refreshes every few minutes and answers lookups in less than a millisecond.
Cardinality estimation
The planner estimates the rows that remain after filters:
estimated rows = total rows * product(selectivity of each filter)Each filter type gets its selectivity from one statistic:
| Filter | Statistic | Selectivity |
|---|---|---|
| Equality | Value frequency | Count of the value divided by total rows |
| Set membership | Value frequency | Sum of the matching value counts divided by total rows |
| Range comparison | Histogram | Sum of the buckets in range divided by total rows |
| Substring, prefix, or suffix match | Token frequency | Count of the token divided by total rows, with a fixed default |
| Null check | Value frequency | Count of null values divided by total rows, with a fixed default |
| No filter | None | One |
| Pinned IDs | None | Number of pinned IDs, capped at total rows, divided by total rows |
| ID range | Histogram | Sum of the buckets in range divided by total rows |
The planner multiplies the selectivity values of filters on the same node. This independence assumption is standard in PostgreSQL, MySQL, and other query planners. Correlated filters, such as a city of Paris and a country of France, give overestimates. Most filter columns in the Orbit ontology are independent.
The planner estimates join output with the FK join formula:
join output = left rows * right rows / max(distinct left keys, distinct right keys)For an edge-to-node join, the key is the node ID on one side and the source or target ID on the edge. The histogram table gives the number of distinct key values.
In this example query, the user is pinned and the merge requests have a branch filter:
Query: a traversal from a user with pinned node ID 1, through AUTHORED to merge requests on the main source branch, through IN_PROJECT to projects.
Statistics for one namespace:
Merge requests: 82,000 rows, 4,200 distinct source branches
AUTHORED edges from users: about 500,000 rows
Projects: 200 rows
Ordering 1: User, edges, merge requests, edge, project
1 user, about 6 edges, about 6 merge requests, 1 project lookup
Total work: about 13 rows
Ordering 2: Merge requests, edges, user, edge, project
About 20 merge requests, about 20 edges, 1 user, 1 project lookup
Total work: about 42 rows
The planner picks ordering 1.Join order selection
The planner lists the join orderings that the declared ontology relationships allow. It estimates the intermediate row count at each step and picks the ordering with the lowest estimated total.
The query language caps the number of nodes and relationships, so the search space is small. Brute-force evaluation takes less than a microsecond, and no dynamic programming is necessary. The compiler must be able to start a flat chain from either a node or an edge.
Pipeline placement
The Orbit query pipeline runs these stages in order: security, compilation, the ClickHouse query, extraction, authorization, redaction, hydration, and output. The stats fetch runs after security and before compilation. At that point, Orbit has these inputs:
- The traversal paths that the user can access
- The parsed query, with its node entities and filters
- The ontology, which loads at startup
The compiler needs the statistics during its plan pass, before it emits SQL. The fetch is one dictionary lookup, or a small batch, for the node tables of the query in the traversal paths of the user. An in-process cache keeps results for a few minutes, keyed by table, column, and traversal path. Most requests get their statistics from the cache with no ClickHouse round trip. Orbit passes the statistics to the compiler as a map from table and column to the statistics of that column.
A statistics section in the schema configuration declares the table names and dictionary settings. The same section sets the histogram bucket count, the top token count, the partition key, and the excluded columns.
Benefits of this approach
Queries with several filtered nodes get the cheapest estimated join order instead of a fixed strategy. The planner can skip narrowing CTEs when statistics show that a filter does not narrow much. Measured numbers replace the high and low selectivity labels. Code graph queries over files, definitions, or imported symbols benefit most. Their tables are large, and their filter selectivity varies widely.
Consequences
- Schema migrations must create and drop the statistics tables, views, and dictionary with the graph tables.
- Each node table gets one materialized view, and each view fires on every insert, which adds write amplification.
- Statistics for deleted entities stay slightly inflated until the HyperLogLog sketches are rebuilt.
Why not the alternatives
Table part metadata only
ClickHouse part metadata gives approximate global row counts with no new infrastructure. It has no namespace scope, no distinct counts per column, and no value distributions. Join ordering depends on filter selectivity as well as table size, so this is too coarse.
Periodic batch job
A batch job could use deduplicating scans for exact statistics. It adds a scheduler, failure handling, and staleness windows. Materialized views are simpler and maintain themselves.
Inline subquery at query time
Statistics computed before each query are too slow. An exact distinct count over a deduplicated node table is itself a full table scan, which is the cost we want to avoid.
One statistic type with distinct counts and row counts
This covers equality and set membership filters. It cannot estimate range or text filter selectivity. Three types cover all query language filters with little additional complexity.