How the Query Planner Works

This chapter is the structured reference for the patinaDB query planner. It is written for application developers and operators who write Cypher and read EXPLAIN and PROFILE. It explains which stage makes each decision, what inputs that stage uses, and which settings change the outcome. With it you should be able to predict the plan for a query and explain it.

Query Planning & Performance keeps the detailed, feature-by-feature notes. This chapter links to it where that chapter has more detail.

Two rules hold throughout:

• Plans never change results. Every alternative described here returns the same rows. Row order is the same wherever ORDER BY defines it. Without ORDER BY, row order is unspecified and can differ between plans and between cluster nodes. Statistics only choose plans; they never filter rows, and they are never replicated. Different access paths can visit different records, so which storage error a damaged record raises, and when, can depend on the plan.
• The RFC 0042 cost model and operators are on by default. Since 2026-10-17 the cost model (join), factorized execution and the auto modes of worst-case optimal joins and the CSR adjacency cache are the shipped defaults (#1442). The reference planner, with heuristic rules over cardinality estimates, remains: it decides wherever the cost model declines or keeps it by margin, and setting all four switches to off restores it exactly (see Specialised operators and switches).

The pipeline at a glance

A read query passes through these stages, in this order:

Read this table as two halves. Everything up to the plan cache is decided once per query text and then reused. Everything in the execution row is decided again on every run, using the current statistics.

Figure 1. The pipeline. The plan cache stores the rewritten operator tree; the entry choice (with the A2 entry-decision cache, introduced in RFC 0042 A6), fast paths and operator admission are decided on every execution.

The plan cache

The plan cache holds the operator tree after the access-path rewrite. That tree fixes the join order and the per-step hash or nested-loop choice.

• Scope. One cache per process holds up to 512 plans, keyed per database, and evicts the least recently used. There is no setting for its size. PATINADB_PLAN_CACHE=off (also 0, false or no) disables it, together with literal normalization.

• Key. A plan is reused only for the same normalized text. User parameters ($personId) are kept by name, so every value of $personId shares one plan.

• Literals. Literals are replaced by internal parameters. Normalization is skipped, and the plan is keyed by the exact text, when:

  • the query has two or more MATCH steps that reach join reordering;
  • the text contains comments, backticks or non-ASCII characters;
  • the normalized text does not parse.

• Decided per execution, not cached.

  • the entry node and the access path of each MatchScan;
  • the order of a multi-pattern MatchScan;
  • all fast paths, limit rules and aggregate specialisations;
  • parallel admission and the auto modes.

• Invalidation. Cached plans are dropped by:

  • any DDL, such as CREATE INDEX or CREATE EDGE SORTED INDEX;
  • clearing the graph (restore, snapshot install, reset);
  • DROP DATABASE.

  Under PATINADB_COST_MODEL=join, an accepted degree-catalog publication for the same database also makes the cached plan rebuild on its next lookup. Refused refreshes, ordinary data writes and publications in another database do not trigger this rebuild. Reference/entry plans retain their previous policy. Parameter values still share a plan; parameter-sensitive join planning remains a limitation between replans.

• EXPLAIN and PROFILE plan afresh. They never read the plan cache. If the data or the statistics have changed since a query was first cached, EXPLAIN can therefore show a different join order from the one the cached plan executes. Under PATINADB_COST_MODEL=join, the decisions show a plan.cache … chosen=built line, which records the schema epoch the join decisions were made under.

The L3 result cache, which stores whole result tables, is separate; see Cache memory budget.

The plan.cache wording in the example below reflects this publication policy; the original example fixture and the other recorded decisions are unchanged.

Entry node and direction

Each MatchScan starts at one node of its path, the entry node, and expands from there in both directions. This choice is made again on every execution.

Figure 2. Entry choice. The margin depends on the provenance of the cheapest candidate’s inputs; the details follow in the two sections below.

Reference rules (fallback)

The reference selector decides wherever the entry cost model declines a pattern or keeps its pick by margin, and everywhere when PATINADB_COST_MODEL=off. It applies these rules in order:

1. UUID shortcut. A node constrained by an id equality (id(n) = $id, elementId(n) = …) is the entry, without estimating anything else.
2. Single node. A pattern with one node starts there.
3. Sort hint. If ORDER BY names a property of a node in the pattern, that node is the entry. The exception is when its estimate is at least 10 times the cheapest node’s estimate (integer ratio, both estimates positive).
4. Minimum cardinality. Otherwise the labelled node with the smallest estimate wins.
   • Ties go to the leftmost node.
   • The walk stops at the first estimate of 1 or less.
   • Unlabelled nodes are never estimated.
5. Direction check. For chains of 3 to 9 nodes the planner can then switch to the other endpoint. This applies only when every node has exactly one label and no properties, and every relationship has a fixed length and one type. If the two endpoint estimates are within 2× of each other, it samples up to 32 anchors per hop and direction, with one shared 16,384-edge budget. There is no setting for this step.

The node estimates come from these rules (constants as in the source; they are heuristics, not measured optima):

The first label is the primary label. Label counts, value indexes and compound indexes are keyed by it. A label that a node holds only as a secondary label (for example Post in CREATE (:Message:Post)) is not counted by the label index. The reference selector then falls back to the total vertex count. In the example dataset this is why (:Comment) is estimated at est rows=31070, the whole graph, instead of 20,000.

Once the entry node is chosen, the access path for it is the first rule that applies, in this priority order:

Priority is fixed with one exception. When both a compound index and a single-property index apply, they are compared on an estimated rows + io cost. If the cost beats the priority order, the Physical: footer says so with an entry.cost_override: … line (see Cost-based selection).

The entry cost model (PATINADB_COST_MODEL=entry)

With PATINADB_COST_MODEL=entry (or join, the default, which includes it), the minimum cardinality rule (step 4) and the direction check (step 5) are replaced, for eligible patterns, by a whole-path cost in calibrated nanoseconds.

• Eligible patterns. Fixed-length paths with at least one relationship, where every relationship has exactly one type. Patterns with an id constraint, variable-length relationships, shortestPath, untyped or type-alternative relationships, and patterns with a sort hint keep the reference rules. So do patterns whose estimates are not finite, and patterns whose planning scratch memory is refused.

• What is priced. Every labelled node competes as the entry. Each candidate costs:

  • its entry access (seek or scan);
  • for every entry row, the expansion of both sides of the path, including label checks and property reads at each hop;
  • the construction of the cross product of both sides.

  The hop sizes come from the degree catalog, using the mean degree for the (relationship type, direction, anchor label, other label) group. Filters are assumed independent.

• Regimes. The primitive costs were measured on one host (A2-cal v1, #1442). A hop is priced as “warm L2” only when the entry cache is enabled, its expected list fits the L2 admission cap (at most 8,192 edges), and the working set fits the level cap. Otherwise it is priced as “warm redb”. The cold regime is never chosen automatically.

• Keyed consumers. Some operators repeat work per run of one binding. Today this is only the count over independent OPTIONAL one-hop branches. For those, the expected number of runs times the per-run cost is added as entry.cost.consumer.

• Adoption margin. The model’s choice replaces the reference entry only when the predicted advantage clears a margin that depends on the inputs:

  • Exact inputs: no margin; the cheapest candidate is used.
  • Sampled degrees: the larger of 1.1× and the spread of the candidates’ estimated output rows.
  • Missing or stale degrees (Default, Stale): 2×.

  Ties keep the reference entry. These margins are unverified policy choices, not confidence intervals.

• Missing statistics. If a degree group is missing or stale, the model uses a cached legacy fan-out or a default of 1. It also asks for one bounded background refresh, which runs on a single worker:

  • budget PATINADB_DEGREE_STATS_EDGE_BUDGET, default 1,000,000 directional edges; 0 disables the refresh;
  • a 120-second deadline;
  • a 5-second retry backoff per database.

  The query that triggered the refresh does not wait for it. The refresh= field of entry.cost reports what happened, for example started, not needed, single flight or cache budget refusal. A refusal means the entry cache is disabled, or the stats.degree region has less than the 256-group minimum left. A 2 GiB node fits the sample (#1442). So the default cost model does not need a manual CALL patinadb.stats.degrees(): the first queries of a shape plan with the fallback, later ones with the sample once it is published. The sample is node-local RAM, lost on restart, and costs a bounded edge sample plus one pass over all vertices on a background thread. Join orders chosen before it arrived stay in the plan cache until a schema change or eviction (see The plan cache); entry choices are re-priced when the catalog changes.

• It needs the entry cache. The degree catalog lives in a region of the entry cache. A server enables the entry cache by default (PATINADB_CACHE_LIMIT=40%). Embedded use enables it only when PATINADB_CACHE_LIMIT is set. Without it, every degree lookup falls back to Default and the refresh is refused. This is the same IC2-shaped query run embedded without a cache limit:

  entry.cost _:["Person"] - ["KNOWS"]:Undirected - friend:["Person"] - ["HAS_CREATOR"]:Inbound - message:["Message"]: chosen=node[0] (est rows=1.931123270035404) (est ns=4155.373289255539) over node[2] (est rows=1.931123270035404) (est ns=844442.8018863855) over node[4] (est rows=60) (est ns=25337715.354519267); minimum calibrated primitive ns; dominant=entry access; warm redb default, L2 only within list and working-set caps; A1 population mean or legacy-default cache-only fallback; refresh=cache budget refusal; independent filters; constants A2-cal v1 #1442; Default; repeats=3

All values and their side effects are listed in Entry and join cost model.

Joins

Which patterns become a join

Before any ordering, lowering folds patterns that share an endpoint into a single path. For example, (a)-[:R]->(b), (b)-[:S]->(c) becomes one path (a)-[:R]->(b)-[:S]->(c). Patterns stay separate when:

• a pattern is OPTIONAL or binds a named path;
• both patterns contain a relationship and come from different MATCH clauses;
• the shared variable is an interior node of either path (branches and stars stay separate);
• two patterns share both endpoints but use disjoint relationship types. They stay a two-key join instead of becoming one closed walk (LSQB Q2’s shape; see Closed paths and endpoint joins).

Separate MATCH clauses lower together like comma patterns. The exceptions are an OPTIONAL clause, a clause with its own WHERE or dynamic pattern properties, and a clause with two or more relationship patterns. Patterns that remain separate form a join chain.

Reference join planner (fallback)

The reference join planner orders joins when join costing declines or is switched off.

1. Seed. The pattern with the smallest base estimate starts the chain; ties go to the first pattern. The base estimate is the smallest node estimate in the pattern. A pattern that touches a variable bound by an enclosing seed counts as 1.

2. Order. Up to 8 patterns use a Selinger-style dynamic program that minimises the sum of intermediate result sizes. Above 8 patterns, a greedy order is used.

   • A connected join step is estimated as max(prefix, base), a foreign-key assumption. It does not use fan-out.
   • A disconnected step is estimated as prefix × base.
   • Connected patterns always come before disconnected ones. The planner never adds a cartesian product that the query did not already force.
   • Finally, patterns that are anchored on two or more bound nodes, or that close a cycle on a bound node, are moved forward.

3. Strategy per step. A step becomes a seeded nested loop (Apply) when it is connected and either:

   • anchored as above; or
   • a point probe applies (one hop, or every interior node bound) and the nested-loop cost prefix × seek beats a scan of the right side.

   The right side must have at least 1,000 estimated rows, except when the whole step is evaluated per outer row. Every other step is a hash join (Join kind=hash); the right side is the build side.

4. Cartesian products. A keyless join fails with a resource error once it would emit more than PATINADB_CARTESIAN_CAP rows (default 10,000).

5. Semi-join pruning. In supported shapes, the hash table of a join is passed as a membership filter into a later traversal. That traversal then skips vertices that cannot join (up to 8 keys).

6. Partial COUNT. An ungrouped count(*) over a keyed hash-join chain is rewritten into per-side grouped counts. These are joined on the keys and summed as products. In EXPLAIN this shows as a Join of two Aggregate group_by=… inputs, as in Example C.

Hash and cartesian joins emit combined rows on demand (#1468), preserving left scan order and right bucket/scan order, including duplicates. Under an active query memory context, new row backing and recursive scalar copies are admitted before allocation against the existing query/transaction budgets. A memory refusal terminates output with ResourceExhausted. The cartesian cardinality gate still checks the complete product before emitting any row. Probe key containers, recursive scalar copies and edge-formatting scratch also reserve before allocation (#1469). Their credit stays with the current probe and releases on advancing, exhaustion, error or early iterator drop, rather than accumulating in delivery. Missing bindings retain their skip semantics. Keyed build tables also admit their hash allocation, fresh composite keys and bucket storage (#1470), including old/new capacity overlap during growth. Shared membership filters retain the same table owner; the last owner releases its credit. Existing input row payloads are moved or shared, not re-accounted as new table payload. Join input collectors reserve slot capacity before growing (#1471), including old/new allocation overlap. Cartesian iterators keep both input permits until drop; keyed build releases its collector after handoff. Collection can fail its memory budget before the product cardinality is known. No new switch is introduced. Shared seed/import selection and APPLY/OPTIONAL merges now use the same fallible copier (#1473). Unique owned entries move; shared entries require an admitted recursive copy. CALL import visibility and first-binding precedence remain unchanged. Refusals propagate through reader, writer, predicate and COUNT/EXISTS callers. A governed APPLY iterator checks its original query memory context on every advance, including within the current seed. Copied payload credit stays with query delivery, including discarded temporary copies. Original row producers and other copy sites remain separate limitations, so this is not a complete join memory bound. The keyed emitter probes its immutable bucket per output row; its throughput impact has not been measured.

OPTIONAL MATCH never joins the chain. It becomes a LeftJoin that seeds each optional pattern from every left row. Under a query memory context, its input, clause extensions, results and memoized candidate row-slot buffers reserve capacity before growth/copy (#1472). Sort input and correlated/rooted MATCH candidate and accumulator containers use the same owner. Concurrently live containers count together; completed output keeps its credit through iterator/result lifetime. A refusal propagates through the existing resource-error path. Identity/SKIP filtering, clause-level WHERE and NULL extension, duplicate order and count/deadline guards are unchanged. The existing limits therefore may reject work previously admitted with uncounted buffers. Optional memo keys/table storage and recursive row/model producers remain separate limitations. No new knob or measured throughput claim.

Cost-based join ordering (PATINADB_COST_MODEL=join)

join adds degree-aware join costing on top of entry:

• Search.

  • Up to 10 relations: a Pareto (cost, rows) subset dynamic program. It gives up and falls through when a frontier would need more than 8 states.
  • Up to 32 relations: an interval dynamic program over the greedy order.
  • Above 32: greedy.

  These limits are unverified policy. The search is left-deep and adds no cartesian products.

• Pricing. For each step, a hash join (build + probe + row construction) is compared with a seeded nested loop (seeks plus expansion per outer row), in the same calibrated nanoseconds as the entry model. No new operator is introduced.

• Guard. The reference plan is priced in the same model. The search result is adopted only if it is predicted to be faster by more than 1.1× (when both prices come from exact statistics) or 2× (otherwise). The reference plan is also kept when:

  • every pattern is edge-free;
  • a pattern closes a cycle, meaning a node variable repeats inside one pattern. A cycle spread over several comma patterns does not count;
  • an input cannot be modelled: shortest paths, variable-length or multi-type relationships;
  • the reference price is not finite, or planning scratch memory is refused;
  • the reference executes as a partial COUNT and the search result would not. The audit then says kept reference: it executes as a partial COUNT ….

On the LSQB, SF1 and Velr suites that were checked (#1442), the guard keeps the reference plan everywhere (RFC 0042, Increments A3). Treat join as an experiment that reports its reasoning, not as a tuning knob.

Statistics

Notes:

• Generations. A generation advances once per dirty label or relationship type at each storage synchronisation, not once per written row.
• Where statistics live. Statistics are kept in RAM only. The cache holds at most 4,096 entries or 4 MiB, is cleared completely when it overflows, and is lost on restart. Each cluster node computes its own statistics; they are never replicated.
• Estimates vs guarantees. Every number here is an estimate. Statistics are never used to prove that a row is absent or to skip a check that results depend on.
• CALL patinadb.stats(label?) shows exact, freshly computed values, including secondary-label holders. It is not a view of the planner’s cached (possibly stale, primary-label-only) entries, so its numbers can differ from the estimates in EXPLAIN.

The degree catalog

CALL patinadb.stats.degrees(edgeBudget?) builds the RFC 0042 A1 degree catalog and returns one row per (relationship type, direction, anchor label, other label) group. Both labels include secondary labels. Here is an excerpt from the example dataset:

edge_type | direction | anchor_label | other_label | edges | anchors | population | p50 | p99 | max | heavy_hitters | provenance | sample_edges | sample_anchors
  …
HAS_CREATOR | in | Person | Message | 30000 | 1000 | 1000 | 15 | 110 | 110 | [16 entries] | exact | 30000 | 1000
  …
KNOWS | in | Person | Person | 6500 | 1000 | 1000 | 7 | 9 | 9 | [16 entries] | exact | 6500 | 1000
KNOWS | out | Person | Person | 6500 | 1000 | 1000 | 7 | 7 | 155 | [16 entries] | exact | 6500 | 1000

How to read a row:

• anchors counts anchors with at least one edge, while population includes zero-degree anchors.
• p50 and p99 are upper bounds of log₂ buckets.
• heavy_hitters lists up to 16 high-degree candidates with their exact observed degrees. The cost model uses an exact heavy-hitter degree only for a literal UUID seed; for anything else it uses the mean.
• Exact vs sampled. Without an argument, the budget is PATINADB_FANOUT_RECOMP_MAX_EDGES. If both directions of the graph fit the budget, the pass is exact. Otherwise it samples 256 evenly spaced UUID ranges, assuming uniformly distributed UUIDs. sampled counts are then extrapolated, max is only the observed maximum, and groups that the sample missed are absent rather than proven empty.
• Population. The population counts come from a full vertex scan, which the edge budget does not bound.
• Failure. An exhausted budget, more than 4,096 groups, or a deadline fails the call and keeps the previous catalog.
• Freshness. A group counts as stale for the entry and join models as soon as any of its three generations (relationship type, anchor label, other label) has moved. Factorized admission uses a looser rule: it refreshes when the generations have moved by more than max(64, population / 100).
• Storage. The catalog is stored only when the entry cache is enabled (see above). Planner paths never block on building it; they request the background sample described in The entry cost model.

Specialised operators and switches

All five are read once per process; restart after changing them. --check-config validates their values and prints the effective mode of the four RFC 0042 switches, marking defaults. Note that PATINADB_WCOJ rejects Boolean aliases: at runtime true and 1 mean off.

Defaults (since 2026-10-17, #1442). Unset or empty means the default in the table. An explicitly set value keeps the meaning it had before the defaults changed: off selects the reference path, and so does any value outside a switch’s grammar (--check-config rejects those). To run the reference planner and executor exactly as before, set all four to off:

PATINADB_COST_MODEL=off PATINADB_FACTORIZE=off PATINADB_WCOJ=off PATINADB_CSR=off

The default was chosen from the server comparison in Measured effects: Velr 0.544, LSQB 0.878, SF1 0.995 of all-off. PATINADB_QUERY_THREADS stays 1.

What auto means. Under auto, an operator engages only where it has its own cost admission, and only when PATINADB_COST_MODEL is entry or join. Without a cost model, auto behaves exactly like off. Operators without a cost admission (anti-intersection, the cyclic join, CSR shortest paths and CSR fixed hops) need an explicit on.

Figure 3. Switch map. “Uncosted” means the operator engages wherever its structural checks pass; “inert” means an auto mode without a cost model.

Prerequisites that decline silently. Factorized execution, sorted intersections and the cyclic join run only under a query memory scope:

• On a server, Bolt reads get one from the memory governor.
• Embedded code gets one from Dataset::query_table_read_with_memory.

Without a scope, PROFILE reports agg.factorized aggregate: chosen=flat over factorized; query memory scope required and the reference operator runs.

Factorized execution (PATINADB_FACTORIZE)

Factorized operators work on a fixed path that splits at an interior pivot into two independent branches. Instead of building every combination of the two branches, they read each branch once per pivot.

• Grouped aggregates (B2).
  • Aggregates: count(*), count(x) and count(DISTINCT …), with group keys on the pivot or on the branch end nodes.
  • Exact-integer sum, min and max on a general path, but only with the cost model off.
  • Branches may share a relationship type only if they reach the pivot through it in the same way. Relationship uniqueness is then checked per pivot at run time.
• B3–B5. DISTINCT over the pivot plus one branch, top-k within a factor, and cross-branch =/<> counts by inclusion–exclusion. A degenerate factor flattens back to the ordinary operator, before any output. The details are in Factor consumers.
• Admission.
  • With the cost model off, every proven shape engages (forced; meant for tests and measurement).
  • With the cost model on, only the per-pivot count path is cost-admitted. It is admitted when 700 · F > 1.5 · (1000 + 300 · W + 30 · F) ns, where F is the estimated flat rows and W the walked elements per pivot, taken from the degree catalog. The weights were fitted on one host and are indicative (#1442). Missing or refresh-due degree evidence keeps the flat aggregate. SUM/MIN/MAX and join shapes are not costed and stay flat.
  • B3–B5 have no cost admission. They engage whenever the switch is on and their structural checks pass.

The same Velr-A1-shaped query (“pairs of authors whose comments reply to the same post”), first with PATINADB_FACTORIZE=on alone and then with the cost model and auto modes on as well:

  agg.factorized pivot=4 (per-pivot key multisets; runtime witness proof for shared relationship types; runtime admission)
  …
  agg.factorized aggregate: chosen=factorized over flat; selected; cached pivot count=Some(0); cached first-hop means=[Some(2.0), Some(2.0)]; PATINADB_COST_MODEL records its estimate separately; Cached; repeats=1

  agg.factorized pivot=4 (per-pivot key multisets; runtime witness proof for shared relationship types; runtime admission)
  …
  agg.factorized aggregate: chosen=flat (est rows=4) (est cost=2800) over factorized (est rows=4) (est cost=2320); cost model per pivot: flat rows=4.00, walk elements=4.00, flat=2800ns, factorized=2320ns, margin=1.5; Cached; repeats=1

Both runs return the same five rows. On this graph each post has two comments, so F = 4 flat rows per pivot against W = 4 walked elements. That fails the margin, and the cost model keeps the flat aggregate. The grouped count MATCH (p:Person)-[:KNOWS]->(q:Person)<-[:HAS_CREATOR]-(m:Message) RETURN q.lastName AS name, count(*) AS n ORDER BY name LIMIT 3 pivots at q. It has F = 195 against W = 36.5 and is admitted:

  agg.factorized pivot=2 (per-pivot key multisets; runtime admission)
  …
  agg.factorized aggregate: chosen=factorized (est rows=195) (est cost=17800) over flat (est rows=195) (est cost=136500); cost model per pivot: flat rows=195.00, walk elements=36.50, flat=136500ns, factorized=17800ns, margin=1.5; Cached; repeats=2

Worst-case optimal joins (PATINADB_WCOJ)

• C0, closing probe (expand.into). When the last hop of a pattern returns to an already bound node, the executor can probe that one edge instead of scanning the whole adjacency and filtering. The closing relationship must be unnamed, single-typed and without properties. Under auto the probe is chosen when the cached list length or the catalog degree makes a full scan dearer than one seek; unknown degrees keep the scan.
• C1, sorted intersection (expand.intersect). For c in N(a) ∩ N(b) shapes (triangles, mutual friends), the executor merges two UUID-sorted neighbour lists instead of expanding and filtering. Under auto, each candidate samples at most 256 keys per side. The intersection is used only when the binary plan’s intermediate result exceeds the output and the binary plan costs more than 1.5× the intersection. Sampling stops for a hop after 32 candidates whose expected gains do not pay for it, and resumes on every 64th. The anti-intersection for NOT (a)--(c) runs only with on.
• C2, cyclic join (join.wcoj). Connected cyclic regions with at least three fixed, typed relationships (up to 16 vertex variables and 16 relationships) run as a leapfrog join over the adjacency. Named or property-filtered relationships join it as binary probes. OPTIONAL, variable-length paths, derived inputs and scans with ordering promises keep the reference execution. Runs only with on; there is no cost admission yet.
• Triangle entry (entry.intersect). With auto and a cost model, a homogeneous undirected triangle may be entered at the node that gives C1 its complete prefix.

Limitations: Experimental cyclic joins require explicit activation.

CSR adjacency cache (PATINADB_CSR)

The CSR is a derived, read-only, in-memory copy of one relationship type’s adjacency in one direction. It is built in the background from the stored trees and is never written to disk or replicated.

• When it is used. Until a CSR is built, and for any anchor written since the build, the existing reader is used. A CSR more than a quarter dirty is rebuilt.
• Memory. Its share is one ninth of the decoded entry-cache levels’ allowance; the four existing levels keep two ninths each. With on, that share is reserved at start-up. With auto, it is reserved only once the CSR cache exists.
• auto. Only deduplicating variable-length traversals (BFS), where count(DISTINCT …) or similar makes path multiplicity irrelevant, are cost-admitted. The expected expansions must save more than twice the dense-id lookups plus a 1/4096 share of the build scan; this policy is unverified. Shortest paths keep the reference reader.
• on. Also enables shortest paths and single-type fixed hops (D2).

EXPLAIN neither builds nor reports a CSR. Only PROFILE shows traversal.source:

  csr.admission deduplicated BFS: chosen=csr candidate; degree/visits versus amortized build and lookup; uncertified caches still decline; Structural; repeats=1
  traversal.source "KNOWS" reverse=false: chosen=csr over l2/redb; clean anchor at compatible snapshot; Exact; repeats=225
  traversal.source "KNOWS" reverse=true: chosen=csr over l2/redb; clean anchor at compatible snapshot; Exact; repeats=225

In the same auto run, the C1 intersection’s sorted domains also consulted the CSR and requested its build (not built, then background build in progress in Example D). That run had no csr.admission decision for the triangle query. That excerpt was captured before the CSR auto containment: in the current source, auto admits only the deduplicating BFS, and intersection domains stay on the reference reader without requesting a build. They read the CSR only with PATINADB_CSR=on.

Parallel execution (PATINADB_QUERY_THREADS)

With a thread cap above 1, eligible read-only scans, fixed traversals, mergeable aggregates (not sum/avg), bounded top-k, sorted DISTINCT and seeded Apply can run as morsels on the query pool. Results and their order keep the serial contract. Admission depends on the cost model:

• Cost model off. A scan or traversal goes parallel only above PATINADB_PAR_AGG_MIN_ROWS estimated rows (default 100,000, unverified).
• Cost model on (A4). A plan goes parallel only when its estimated serial work exceeds 4 × (400 µs dispatch + 265 ns per morsel + 1.4 ns per row), and the parallel version is also cheaper. Some cases need more:
  • aggregates grouped by an entity add about 1 µs of serial work per group;
  • row-producing pipes still also need the row floor;
  • a serial specialisation (path count, covering input) keeps priority unless the parallel plan is four times cheaper.
• Always.
  • Workers must be idle (parallel.load in the access profile).
  • Deferred-prefix pruning always keeps priority.
  • Edge morsels split a first hop only when its actual average fan-out reaches PATINADB_PAR_FANOUT_MIN_EDGES (default 50,000).

A two-hop grouped count (MATCH (a:Person)-[:KNOWS]-(b:Person)-[:KNOWS]-(c:Person) RETURN c.lastName AS name, count(*) AS n) with PATINADB_QUERY_THREADS=4. With the cost model off, the row floor compares the entry estimate (1,000) with 100,000 and stays serial:

      [2] MatchScan required=[(a:Person) -(b:Person) -(c:Person)] rows=377064 est=1000 q-error=377.064
  …
  parallel.admission traversal rows: chosen=serial over parallel (est rows=1000); max label estimate >= floor 100000; entry=1000; Cached; repeats=2

With PATINADB_COST_MODEL=join, the calibrated work estimate is compared with the overhead and the pool admits four threads:

      [2] MatchScan required=[(a:Person) -(b:Person) -(c:Person)] rows=377064 est=169000 q-error=2.231
  …
  parallel.admission calibrated work: chosen=parallel (est rows=169000) (est cost=2830130.3734979997) over serial (est rows=169000) (est cost=8780502.616999999); serial_ns > 4 * overhead_ns=635004.719248; effective_threads=4; morsels=4; A2-cal v1, unverified margin; Cached; repeats=2
  …
  parallel.admission pool load: chosen=parallel over serial; idle=8/8; requested cap=4; admitted cap=4; Exact; repeats=1
  …
  parallel.load: admitted, idle 8/8, threads 4

More detail is in Day-2 operations and the PATINADB_QUERY_* rows of Configuration.

Fast paths

These run automatically, without a switch:

• Limit rules. Rules for ORDER BY … LIMIT are tried in this priority order, and the walk is recorded as limit.rule:
  1. edge_sorted_topk (needs an edge-sorted index);
  2. spatial_knn;
  3. reverse_probe, which is cost-compared against the fan-out top-k;
  4. bounded_topk, an O(k) heap;
  5. window.
• Path counts. agg.disjoint_path_count and agg.grouped_disjoint_path_count count fixed paths that split into branches with disjoint relationship types, without building cross-product rows.
• Optional counts. agg.independent_optional_count handles count(*) over up to 8 independent optional one-hop branches.
• Covering input. agg.covering (PATINADB_READ_COVERING, default on) applies to broad integer aggregates of at least 4,096 estimated rows.
• Whole-query counts. Label, filtered and grouped count scans.

The full list is in Fast paths that make queries cheap.

Reading Decisions: in EXPLAIN and PROFILE

EXPLAIN returns a plan string. In order, it contains:

• the operator tree, read bottom-up;
• Storage: and property-layout lines;
• an optional Physical: footer with planned rules and cost lines;
• Decisions:;
• optional Advice: and Warning [...] lines.

PROFILE runs the query and also returns elapsed_ms. Its plan string adds:

• Planned access (before execution): and the same planned tree;
• Executed operators (query thread): with actual row counts;
• Decisions (executed):, the decisions taken during this execution;
• the executed aggregate access, the resolved property storage and the storage request counts.

Each decision line has this form:

  <point> <subject>: chosen=<alternative> [(est rows=…)] [(est ns|cost=…)] over <alternative> …; <reason>; <provenance>; repeats=<n>

• point: the decision family. Examples are entry.node, entry.access, entry.cost, join.order, limit.rule, agg.factorized, parallel.admission and traversal.source.
• subject: what was decided. This is usually the pattern, with labels and directions, or a step such as step 1.
• chosen / over: the chosen alternative first, then the rejected ones. Priority walks stop at their winner, so later alternatives may be missing.
• estimates: est ns is used for entry.cost and for decisions whose reason starts with calibrated ns; other estimates are in the selector’s own units (est cost). They are estimates, not timings.
• reason: the rule or the margin that decided.
• provenance: where the inputs came from.
  • Exact: a fresh, exact statistic.
  • Sampled { size }: sampled evidence.
  • Cached: a value reused from a cache or catalog.
  • Histogram: column histogram interpolation.
  • Stale: an outdated statistic.
  • Default: no statistic; a fallback value was used.
  • Structural: a rule with no numeric estimate.
• repeats: how often the same point, subject and choice recurred.
  • Seeded and nested executions repeat decisions.
  • The estimates shown are from the first occurrence.
  • At most 128 distinct decisions are kept.

In Executed operators, [n] is the preorder index of the executed plan, and rows= counts rows actually pulled from that operator. A LIMIT can leave its input only partly consumed. rows=unobserved (bypassed/fused) marks an operator that a fast path replaced or fused. A MatchScan (and, under PATINADB_COST_MODEL=join, a join) also shows its estimate and its q-error: the larger of estimate/actual and actual/estimate, with zero counted as one. What the estimate means depends on the mode:

• Cost model off. The MatchScan estimate is the entry node’s estimate, not the path’s output. A multi-hop scan therefore shows a large q-error even when the plan is right.
• Cost model on. The estimate is the chosen entry’s predicted output rows from entry.cost, which is directly comparable to rows=.

A large q-error shows where an estimate was wrong. It does not mean the plan was wrong. Worker-internal rows are not shown.

The examples below are real output from an in-process release build of this source on the generated example dataset (1,000 persons, 30,000 messages; #1442). Lines marked … are omitted. The query texts are the SF1 Interactive and LSQB texts from crates/patinadb/src/plan/exec/ldbc_pins/ (IC2, IC9) and ldbc_pins/parallel_admission.rs (LSQB). The row counts are logical work on a toy graph and are no performance measurement.

Example A: an IC2-style friends’ messages page

MATCH (:Person {id: $personId})-[:KNOWS]-(friend:Person)<-[:HAS_CREATOR]-(message:Message)
WHERE message.creationDate <= $maxDate
RETURN friend.id AS personId, friend.firstName AS personFirstName, friend.lastName AS personLastName,
       message.id AS postOrCommentId, coalesce(message.content, message.imageFile) AS postOrCommentContent,
       message.creationDate AS postOrCommentCreationDate
ORDER BY postOrCommentCreationDate DESC, toInteger(postOrCommentId) ASC
LIMIT 20

EXPLAIN with every switch off (personId = 1):

Limit skip=0 count=20
  Sort keys=2
    Project items=6 distinct=false return_star=false
      MatchScan required=[[entry](_:Person) -(friend:Person) -(message:Message) → PropertyIndex[id] = est.1]
Storage: native (allocated database fits detected RAM at open)
Vertex property storage: owner-key directory; canonical values <= 256 serialized bytes inline, wider values in property/owner payload table; automatic physical routing, existing query access operators retained
Physical:
  limit.bounded_topk
  parallel.topk: serial: query thread cap is one
  parallel.frontier: serial: query thread cap is one
Decisions:
  entry.node _:["Person"] - ["KNOWS"]:Undirected - friend:["Person"] - ["HAS_CREATOR"]:Inbound - message:["Message"]: chosen=node[0] (est rows=1); minimum cardinality; stop at <=1; unlabelled nodes skipped; Default; repeats=3
  entry.direction admission: chosen=fallback; shape, cardinality separation or sampling unavailable; retain pivot; Structural; repeats=3
  entry.access None: chosen=property_value_index; static priority; no complete cost comparison; Structural; repeats=3
  limit.rule edge_sorted_topk: chosen=declined; priority walk; stop at first applicable rule; Structural; repeats=2
  limit.rule spatial_knn: chosen=declined; priority walk; stop at first applicable rule; Structural; repeats=2
  limit.rule reverse_probe: chosen=declined; priority walk; stop at first applicable rule; Structural; repeats=2
  limit.rule bounded_topk: chosen=applicable; priority walk; stop at first applicable rule; Structural; repeats=2

• entry.node … chosen=node[0] (est rows=1): the id index equality gives an estimate of 1. The walk stops there, so the other nodes are never estimated.
• entry.access … property_value_index: the entry is a point lookup on the value index (PropertyIndex[id] = est.1 in the tree).
• limit.rule: no edge-sorted index covers this sort, so the walk ends at bounded_topk, a 20-row heap instead of a full sort.

With PATINADB_COST_MODEL=join and the degree catalog loaded, the same EXPLAIN prices all three entries:

Decisions:
  entry.cost.hops _:["Person"] - ["KNOWS"]:Undirected - friend:["Person"] - ["HAS_CREATOR"]:Inbound - message:["Message"] node[0]: chosen=estimate (est rows=376.5690376569038) (est cost=38508.96192405824); right[0] scanned=13.000 output=13.000 check_ns=8.933533 record_probes=0 regime=warm L2; right[1] scanned=390.000 output=376.569 check_ns=8.933533 record_probes=0 regime=warm L2; ; Exact; repeats=3
  entry.cost.hops _:["Person"] - ["KNOWS"]:Undirected - friend:["Person"] - ["HAS_CREATOR"]:Inbound - message:["Message"] node[2]: chosen=estimate (est rows=376.56903765690384) (est cost=3045511.749845188); left[0] scanned=13000.000 output=13.000 check_ns=8.933533 record_probes=0 regime=warm L2; right[0] scanned=30000.000 output=28966.849 check_ns=8.933533 record_probes=0 regime=warm L2; ; Exact; repeats=3
  entry.cost.hops _:["Person"] - ["KNOWS"]:Undirected - friend:["Person"] - ["HAS_CREATOR"]:Inbound - message:["Message"] node[4]: chosen=estimate (est rows=376.5690376569038) (est cost=40711683.6658395); left[0] scanned=28966.849 output=28966.849 check_ns=8.933533 record_probes=0 regime=warm L2; left[1] scanned=376569.038 output=376.569 check_ns=8.933533 record_probes=0 regime=warm L2; ; Exact; repeats=3
  entry.cost _:["Person"] - ["KNOWS"]:Undirected - friend:["Person"] - ["HAS_CREATOR"]:Inbound - message:["Message"]: chosen=node[0] (est rows=376.5690376569038) (est ns=38508.96192405824) over node[2] (est rows=376.56903765690384) (est ns=3045511.749845188) over node[4] (est rows=376.5690376569038) (est ns=40711683.6658395); minimum calibrated primitive ns; dominant=expansion; warm redb default, L2 only within list and working-set caps; A1 population mean or legacy-default cache-only fallback; refresh=not needed; independent filters; constants A2-cal v1 #1442; Exact; repeats=3
  entry.access None: chosen=property_value_index; static priority; no complete cost comparison; Structural; repeats=3

• entry.cost.hops shows, for each candidate, the scanned and accepted rows per hop, the label-check cost and the regime (warm L2). For node[0], 13 KNOWS neighbours are expected (the mean undirected degree), then 390 messages, 376.6 of which pass the date filter.
• The cost model picks the same entry as the reference. Every input is Exact, so no margin applies.

PROFILE then shows how far the estimate was off:

Executed operators (query thread):
  [0] Limit skip=0 count=20 rows=20
    [1] Sort keys=2 rows=unobserved (bypassed/fused)
      [2] Project items=6 distinct=false return_star=false rows=unobserved (bypassed/fused)
        [3] MatchScan required=[(:Person) -(friend:Person) -(message:Message)] rows=5300 est=376.5690376569038 q-error=14.074

Person 1 is one of ten hubs in the dataset, with 155 outgoing KNOWS edges. The catalog’s mean degree cannot see that, hence the q-error of 14. Only a literal UUID seed would use the exact heavy-hitter degree. The plan is still the best one available: a point entry followed by expansion.

Example B: IC9 and an edge-sorted index

IC9 collects friends and friends of friends, then pages their messages by date. Without a covering index, PROFILE with every switch off shows the seeded Apply expanding HAS_CREATOR once per friend:

Executed operators (query thread):
  [0] Retain keep=[personId,personFirstName,personLastName,commentOrPostId,commentOrPostContent,commentOrPostCreationDate] rows=20
    [1] Limit skip=0 count=20 rows=20
      [2] Sort keys=2 rows=unobserved (bypassed/fused)
        [3] Project items=7 distinct=false return_star=false rows=unobserved (bypassed/fused)
          [4] Apply imports=[] scope=InheritOuter rows=17550
            [5] Retain keep=[friend,message] rows=565
              [6] Unwind binding=friend rows=unobserved (bypassed/fused)
                [7] Aggregate group_by=0 aggs=1 rows=1
                  [8] Filter rows=2344
                    [9] MatchScan required=[(root:Person) -(friend:Person)] rows=2344 est=1 q-error=2344.000
            [10] MatchScan required=[(friend:_) -(message:Message)] rows=unobserved (bypassed/fused)
  …
  traversal.source fixed ["HAS_CREATOR"] reverse=true: chosen=redb over csr over l2; CSR off or auto (fixed hops require on); Exact; repeats=565
  …
Resolved vertex property storage (query thread; logical resolutions, not physical I/O; workers/caches/buffers may bypass):
  inline=42100 canonical bytes=241541; external=0 canonical bytes=0

After CREATE EDGE SORTED INDEX FOR (m:Message)<-[:HAS_CREATOR]-() ON m.creationDate (run on a copy of the dataset), the limit.edge_sorted_topk rule applies. The ordered frontier then merges the friends’ date-sorted edge lists. The HAS_CREATOR traversal reader is entered 20 times instead of 565 (see repeats):

Physical:
  limit.edge_sorted_topk
  …
Executed operators (query thread):
  [0] Retain keep=[personId,personFirstName,personLastName,commentOrPostId,commentOrPostContent,commentOrPostCreationDate] rows=20
    [1] Limit skip=0 count=20 rows=20
      [2] Sort keys=2 rows=unobserved (bypassed/fused)
        [3] Project items=7 distinct=false return_star=false rows=unobserved (bypassed/fused)
          [4] Apply imports=[] scope=InheritOuter rows=unobserved (bypassed/fused)
            [5] Retain keep=[friend,message] rows=565
              [6] Unwind binding=friend rows=unobserved (bypassed/fused)
                [7] Aggregate group_by=0 aggs=1 rows=1
                  [8] Filter rows=2344
                    [9] MatchScan required=[(root:Person) -(friend:Person)] rows=2344 est=1 q-error=2344.000
            [10] MatchScan required=[(friend:_) -(message:Message)] rows=unobserved (bypassed/fused)
  …
  traversal.source fixed ["HAS_CREATOR"] reverse=false: chosen=redb over csr over l2; CSR off or auto (fixed hops require on); Exact; repeats=20
  …
Resolved vertex property storage (query thread; logical resolutions, not physical I/O; workers/caches/buffers may bypass):
  inline=92 canonical bytes=506; external=0 canonical bytes=0

The Apply is now fused (unobserved), and 92 property resolutions replace 42,100. These are logical counts from one run each, not timings. The q-error of 2,344 on [9] compares the entry estimate (1, the id lookup) with the 2,344 rows that the KNOWS*1..2 expansion produced. With the cost model off, that is expected. The cost model would not change it either, because it does not price variable-length paths.

Example C: an LSQB-style count

LSQB Q2 with PATINADB_COST_MODEL=join:

MATCH (person1:Person)-[:KNOWS]-(person2:Person),
  (person1)<-[:HAS_CREATOR]-(comment:Comment)-[:REPLY_OF]->(post:Post)-[:HAS_CREATOR]->(person2)
RETURN count(*) AS count

Planned access (before execution):
Project items=1 distinct=false return_star=false
  Aggregate group_by=0 aggs=1
    Join kind=hash keys=[person1,person2]
      left:
        Aggregate group_by=2 aggs=1
          MatchScan required=[[entry](person1:Person) -(person2:Person) → LabelScan ⚠ (no matching index) est.1000]
      right:
        Aggregate group_by=2 aggs=1
          MatchScan required=[(person1:Person) -(comment:Comment) -(post:Post) -[entry](person2:Person) → LabelScan ⚠ (no matching index) est.1000]
  …
Executed operators (query thread):
  [0] Project items=1 distinct=false return_star=false rows=1
    [1] Aggregate group_by=0 aggs=1 rows=1
      [2] Join kind=hash keys=[person1,person2] rows=269
        [3] Aggregate group_by=2 aggs=1 rows=13000
          [4] MatchScan required=[[entry](person1:Person) -(person2:Person) → LabelScan ⚠ (no matching index) est.1000] rows=13000 est=13000 q-error=1.000
        [5] Aggregate group_by=2 aggs=1 rows=20000
          [6] MatchScan required=[(person1:Person) -(comment:Comment) -(post:Post) -[entry](person2:Person) → LabelScan ⚠ (no matching index) est.1000] rows=20000 est=20000 q-error=1.000
Decisions (executed):
  join.strategy step 1: chosen=Hash (est rows=31070) over NestedLoop (est rows=1000); connected and anchored/probe eligible; otherwise hash; Structural; repeats=1
  join.order bases=[1000.0, 31070.0]: chosen=[0, 1] (est rows=31070) (est cost=32070); DP (cap 8), anchored priority; Default; repeats=1
  …
  join.order person1:["Person"] - ["KNOWS"]:Undirected - person2:["Person"] | person1:[] - ["HAS_CREATOR"]:Inbound - comment:["Comment"] - ["REPLY_OF"]:Outbound - post:["Post"] - ["HAS_CREATOR"]:Outbound - person2:[]; relations=2; guard: chosen=reference [0, 1] (est rows=260) (est ns=34999058.497517996) over subset DP [1, 0] (est rows=403.90999999999997) (est ns=33889480.401324295); calibrated ns; kept reference: predicted advantage below 1.1x; Exact; repeats=1
  plan.cache join planning epoch: chosen=built; schema_epoch=0; retained decisions; data writes retain plans; new degree catalogs replan; Cached; repeats=1

How to read it:

• The join. The two patterns share both endpoints but use disjoint relationship types, so they stay separate join inputs.
• The rewrite. The partial COUNT rewrite turned the hash join into a join of two grouped counts: 13,000 and 20,000 grouped rows meet in 269 key matches.
• The reference decisions. join.order (DP over 2 patterns) and join.strategy (hash) were made by the reference planner. bases=[1000.0, 31070.0] shows the secondary-label fallback for the second pattern.
• The guard. The join.order … guard line is the A3 search. It found a different order 3% cheaper, which is below the 1.1× margin for exact inputs, so the reference order was kept.
• The cache entry. plan.cache … chosen=built records the schema epoch of these decisions.
• Estimate quality. Both MatchScan estimates have a q-error of 1.000. Under the cost model they are the predicted output rows from the degree catalog. With the switches off, the same scans show the label-count entry estimate of 1,000.

A keyed consumer looks like this. These lines are from LSQB Q7 under PATINADB_COST_MODEL=entry:

  entry.cost.consumer _:["Tag"] - ["HAS_TAG"]:Inbound - message:["Message"] - ["HAS_CREATOR"]:Outbound - creator:["Person"] node[0]: chosen=keyed runs (est cost=18684342.197546996); message:LIKES runs=30000.000 ns_per_run=305.783; message:REPLY_OF runs=30000.000 ns_per_run=317.028; ; Exact; repeats=1
  …
  entry.cost.consumer _:["Tag"] - ["HAS_TAG"]:Inbound - message:["Message"] - ["HAS_CREATOR"]:Outbound - creator:["Person"] node[2]: chosen=keyed runs (est cost=18684342.197546996); message:LIKES runs=30000.000 ns_per_run=305.783; message:REPLY_OF runs=30000.000 ns_per_run=317.028; ; Exact; repeats=1
  …
  entry.cost.consumer _:["Tag"] - ["HAS_TAG"]:Inbound - message:["Message"] - ["HAS_CREATOR"]:Outbound - creator:["Person"] node[4]: chosen=keyed runs (est cost=18684342.197546996); message:LIKES runs=30000.000 ns_per_run=305.783; message:REPLY_OF runs=30000.000 ns_per_run=317.028; ; Exact; repeats=1
  …
  entry.cost _:["Tag"] - ["HAS_TAG"]:Inbound - message:["Message"] - ["HAS_CREATOR"]:Outbound - creator:["Person"]: chosen=node[0] (est rows=30000) (est ns=29063112.205906995) over node[2] (est rows=30000) (est ns=38630507.417546995) over node[4] (est rows=30000) (est ns=29369677.606546998); minimum calibrated primitive ns; dominant=keyed consumer; warm redb default, L2 only within list and working-set caps; A1 population mean or legacy-default cache-only fallback; refresh=not needed; independent filters; keyed-consumer runs priced; constants A2-cal v1 #1442; Exact; repeats=1

Example D: a triangle count under WCOJ

MATCH (a:Person)-[:KNOWS]-(b:Person)-[:KNOWS]-(c:Person)-[:KNOWS]-(a)
RETURN count(*) AS triangles

With COST_MODEL=join WCOJ=auto CSR=auto FACTORIZE=on, under a query memory scope:

Executed operators (query thread):
  [0] Project items=1 distinct=false return_star=false rows=1
    [1] Aggregate group_by=0 aggs=1 rows=1
      [2] MatchScan required=[(a:Person) -(b:Person) -(c:Person) -(a:_)] rows=26760 est=338000 q-error=12.631
  …
  entry.cost a:["Person"] - ["KNOWS"]:Undirected - b:["Person"] - ["KNOWS"]:Undirected - c:["Person"] - ["KNOWS"]:Undirected - a:[]: chosen=node[2] (est rows=338000) (est ns=22099296.471) over node[0] (est rows=338000) (est ns=82355575.995) over node[4] (est rows=338000) (est ns=23492927.619); minimum calibrated primitive ns; dominant=row construction; warm redb default, L2 only within list and working-set caps; A1 population mean or legacy-default cache-only fallback; refresh=not needed; independent filters; constants A2-cal v1 #1442; Default; repeats=1
  entry.intersect homogeneous triangle: chosen=node[0]; calibrated closing-domain candidate beats binary expansion; complete prefix required; Structural; repeats=1
  …
  expand.intersect bounded closing domains: chosen=intersect (est rows=13) (est cost=3120.355953) over binary (est rows=182) (est cost=6236.583665); left=Some(Exact(13.0)); right=Some(Exact(14.0)); closing=14 (homogeneous proxy); lower bounds must win over their open tails; Sampled { size: 256 }; repeats=11410
  traversal.source "KNOWS" reverse=false: chosen=l2/redb over csr; not built; Exact; repeats=22820
  traversal.source "KNOWS" reverse=true: chosen=l2/redb over csr; background build in progress; Exact; repeats=22820
  expand.intersect two-hop closing domain: chosen=intersect over binary; auto cost admitted; sorted domains; Structural; repeats=11410
  expand.into closing degree: chosen=scan; cached domain length or catalog degree versus one seek; unknown retains scan; Structural; repeats=36430
  …
  expand.into closing degree: chosen=probe; cached domain length or catalog degree versus one seek; unknown retains scan; Structural; repeats=6644
  expand.into repeated binding: chosen=probe over scan; auto cost admitted; fixed bound target; Structural; repeats=6644
  expand.intersect bounded closing domains: chosen=binary (est rows=2080) (est cost=7658.041013999999) over intersect (est rows=13) (est cost=10437.203915000002); left=Some(Exact(13.0)); right=Some(Exact(160.0)); closing=160 (homogeneous proxy); lower bounds must win over their open tails; Sampled { size: 256 }; repeats=1590

• entry.cost would start at b (node[2]). entry.intersect then overrides this to a, which gives the intersection its complete prefix.
• expand.intersect bounded closing domains is the per-candidate sampling decision. With 13 and 14 neighbours the intersection wins. Against a hub with 160 neighbours, the binary plan wins. Both appear, with their own repeats.
• expand.into … probe is the C0 closing probe, admitted where the degree makes a scan dearer than one seek.

With WCOJ=on the cyclic join takes the whole pattern, and the MatchScan becomes unobserved:

Executed operators (query thread):
  [0] Project items=1 distinct=false return_star=false rows=1
    [1] Aggregate group_by=0 aggs=1 rows=1
      [2] MatchScan required=[(a:Person) -(b:Person) -(c:Person) -(a:_)] rows=unobserved (bypassed/fused)
  …
  join.wcoj variable order / (domain, conditional) estimates: [(Some("a"), Some(1000.0), Some(1000.0)), (Some("b"), Some(1000.0), Some(13.0)), (Some("c"), Some(1000.0), Some(0.16899999999999998))]: chosen=leapfrog over binary; completed base adjacency join; Cached; repeats=1

All three runs (off, auto, on) returned 26,760 triangles.

Practical guidance

Make the planner’s job easy

• Use parameters. Parameters share one cached plan and keep plan-build cost off the hot path. Literals are normalized too, but not in queries with two or more MATCH clauses or with comments. Remember that every value of a parameter shares the join order built for the first one.
• Label the anchor and its neighbours. Unlabelled nodes are skipped as entry candidates. Put the most selective label first when you create nodes, because only the primary label has exact counts and value indexes. A label used only as a secondary label is estimated as the whole graph.
• Filter on indexed properties of labelled nodes.
  • Equality, range and STARTS WITH on a property of a node’s primary label can seek the label-scoped value index (see the data model); the IC9 plan of Example B shows (message:Message) → PropertyIndex[creationDate] < est.30000 although the dataset declares no index on creationDate.
  • Declare a compound index for equality plus range or sort combinations.
  • Declare an edge-sorted index for “traversal, then ORDER BY target.prop LIMIT k”. EXPLAIN prints an Advice: line with the exact DDL when such an index would apply.
• Paginate with keys, not deep SKIP. WHERE n.p > $cursor ORDER BY n.p LIMIT k seeks to the cursor. SKIP n still has to walk past n qualifying rows. See Planning note for filtered pages.
• Keep comma patterns connected. A pattern that shares no variable becomes a cartesian product, capped at 10,000 rows by default.
• Avoid literal-only differences in big multi-MATCH queries. Such queries are cached per exact text, so each literal variant builds its own plan.

Diagnosing a slow plan, step by step

1. EXPLAIN first. Check the [entry] marker and the access path of every MatchScan. Warning signs:
   • LabelScan ⚠ (no matching index), or AllVertices ⚠;
   • estimates of est.∞ or of the whole graph (secondary-label fallback);
   • Join without keys (a cartesian product).
2. Read Decisions:. Find the entry.node or entry.cost line for the slow pattern. Default or Stale provenance means the planner had no usable statistics. Check the limit.rule walk and any Advice: line.
3. PROFILE.
   • Compare rows= with est= for every MatchScan and join; the largest q-error is usually the culprit.
   • Check whether expensive operators are unobserved (a fast path engaged), or carry large repeats (seeded per outer row).
   • The traversal.source lines show whether adjacency came from l2, redb or csr.
4. Fix the input before the knob. Add the label, the index or the parameter. Rewrite the query so the selective pattern is connected to the rest.
5. Then try a switch on a test system, comparing PROFILE output and timing with and without it. The RFC 0042 switches are on by default, so the comparison is usually against off.

Known limitations

• The reference join estimate ignores fan-out, and cached join orders are never re-validated (see The plan cache).
• The cost model assumes independent filters and uses mean degrees. Correlated paths and hubs reached through non-literal seeds can be misestimated, as in Example A.
• Statistics are primary-label only, except for the degree catalog.
• The RFC 0042 switches are on by default since 2026-10-17; the measured gain is suite-level, and single queries can be slower (see Measured effects). See Limitations, in particular the sections on cyclic joins and factorized operators.

Measured effects

These are the joint switch-matrix results recorded in RFC 0042 (docs/rfcs/0042-query-engine-modernisation.md, section “Joint switch matrix”, #1442). The ratios are geometric means of warm medians, relative to every switch off; below 1 is faster. They come from a shared host with documented disturbances. Treat them as indicative. They are not a qualification and not a promise for your workload.

allauto is COST_MODEL=join FACTORIZE=on WCOJ=auto CSR=auto. In the same runs:

• FACTORIZE carried most of the Velr gain (A1 0.09).
• WCOJ gave LSQB Q3 0.80–0.81.
• SF1 IC2 stayed 8–18% slower with the cost model, with an identical plan. The targeted IC2 line-2 timing was 9.86 ms off against 12.04 ms allauto: per-query cost-model work, not a plan change. The A2 entry-decision cache below removed it. With it, allauto against off gave Velr 0.544, LSQB 0.878 and SF1 0.995, IC2 0.82/0.81 and IC14 0.80/0.71 (3 rounds; RFC 0042 A6). IC10, IC11 line 3 and IC12 line 3 stayed 3–10% slower (IC11 line 3 at 1.10).
• The maintainer adopted allauto as the default on 2026-10-17 on this result (#1442).

Per case, the A6 comparison that the default was adopted on looks like this. Darker bars changed by at least 3% in the same direction in every round; lighter bars did not.

Figure 4a. Velr per case. A1, A4, A6 and A8 are the cases that RFC 0042 attributes to FACTORIZE (indicative, #1442).

Figure 4b. LSQB per case: Q3, Q4, Q5 and Q8 are faster; no case is consistently slower (indicative, #1442).

Figure 4c. SF1 per case: IC2 and IC14 are faster; IC8 line 3, IC10, IC11 and IC12 line 3 are consistently 3–10% slower (indicative, #1442).

Figure 4d. Leave-one-out on the earlier, pre-fix binary: removing FACTORIZE costs Velr most. The three combined-switch regressions that RFC 0042 records for this run (LSQB Q4 and Q7, SF1 IC8) were fixed afterwards; compare the table above (indicative, #1442).

Planning budget

With a cost model on, the entry model runs every time a pattern is executed, because the entry choice is not part of the cached plan. Three mechanisms keep that cheap without changing any decision (RFC 0042 A6, #1442):

• Catalog reuse. The degree catalog is decoded once per transaction and published catalog, and each label and relationship-type generation is read once.
• Exact pruning. Candidates are priced in ascending order of a lower bound: rows × non-empty sides × one seek. A candidate whose bound already exceeds the best estimate is skipped. EXPLAIN and PROFILE still price and show every candidate.
• A2 entry-decision cache (introduced in RFC 0042 A6). A completed A2 choice is reused by later executions of the same pattern with the same parameter values.
  • The cache holds up to 64 entries per process, within the governor-visible planner.entries cap of min(Q/16, 4 MiB) estimated bytes (#1467). Q is the auxiliary cache quantum after native/CSR adjustments. PATINADB_CACHE_LIMIT=0 disables reuse; there is no separate A2 switch.
  • On a fill, pattern and parameter ownership is estimated and reserved before copying. Oversize keys, values exceeding the 128-level sizing traversal, and function/expression AST literals without a layout model skip this optional cache. The query still uses the ordinary entry planner. Hits retain exact key comparison and snapshot validation without repeating the sizing walk. The byte model includes live construction and evicted-but-pinned readers; it is not an exact allocator or RSS bound.
  • Cache contention causes a miss or skipped fill, so planning uses the ordinary cost model. Snapshot metadata is validated outside the global cache mutex (#1466); every existing dependency check still applies.
  • An entry is reused only while the schema, the statistics, the published degree catalog and every label/relationship-type generation the choice read are unchanged.
  • Transactions that wrote, snapshot views, EXPLAIN/PROFILE and runs that requested a statistics refresh do not use it.
  • A valid hit skips entry costing; validating its metadata still performs reads (RFC 0042 A6). Native READY and generation readers now decode borrowed bytes (#1474), avoiding their owned value copy while keeping all these reads and dependency checks. Overlay reads retain their existing fallback, and buffered own writes can still copy during lookup. No new contention or query-throughput measurement is claimed.

A budget gate that skipped the cost model for cheap-looking queries was measured and not adopted. It judged each inner pattern alone, so a query with an expensive pattern comprehension lost the model’s better entry. See RFC 0042 A6.

Appendix: the example dataset

The outputs above were produced on a graph generated by these statements, executed in order on an empty embedded database. The EXPLAIN and PROFILE runs used PATINADB_CACHE_LIMIT=1GiB, except the one shown without a cache limit. Example D and the factorized, CSR and parallel excerpts also ran under a 2 GiB query memory scope. Each switch combination was a separate process. Every process except the edge-sorted-index run (switches off) ran CALL patinadb.stats.degrees() first.

CREATE INDEX ON :Person(id);
CREATE INDEX ON :Tag(id);
CREATE INDEX ON :Country(id);
CREATE INDEX ON :City(id);
UNWIND range(1, 5) AS i CREATE (:Place:Country {id: i, name: 'country' + toString(i)});
UNWIND range(1, 25) AS i MATCH (co:Country {id: (i % 5) + 1}) CREATE (:Place:City {id: 100 + i, name: 'city' + toString(i)})-[:IS_PART_OF]->(co);
UNWIND range(1, 1000) AS i MATCH (c:City {id: 100 + (i % 25) + 1}) CREATE (:Person {id: i, firstName: ['Chau', 'Ali', 'Jun', 'Eva'][i % 4], lastName: 'L' + toString(i % 17), creationDate: 1300000000000 + i * 1000000})-[:IS_LOCATED_IN]->(c);
MATCH (a:Person) UNWIND [5, 10, 15, 29, 61] AS d MATCH (b:Person {id: ((a.id + d - 1) % 1000) + 1}) CREATE (a)-[:KNOWS {creationDate: 1300000000000 + a.id * d}]->(b);
MATCH (a:Person) WHERE a.id <= 10 UNWIND range(1, 150) AS d MATCH (b:Person {id: ((a.id + d * 3 + 100) % 1000) + 1}) CREATE (a)-[:KNOWS {creationDate: 1300000000000 + d}]->(b);
UNWIND range(1, 40) AS i CREATE (:Tag {id: i, name: 'tag' + toString(i)});
MATCH (p:Person) UNWIND [0, 17] AS k MATCH (t:Tag {id: ((p.id + k) % 40) + 1}) CREATE (p)-[:HAS_INTEREST]->(t);
MATCH (p:Person) UNWIND range(1, 10) AS k CREATE (:Message:Post {id: p.id * 100 + k, creationDate: 1300000000000 + (p.id * 37 + k * 1009) * 100000, content: 'post ' + toString(k)})-[:HAS_CREATOR]->(p);
MATCH (m:Post) WITH m MATCH (t:Tag {id: (m.id % 40) + 1}) CREATE (m)-[:HAS_TAG]->(t);
MATCH (m:Post) UNWIND [3, 11] AS d MATCH (p:Person {id: ((m.id * d) % 1000) + 1}) CREATE (c:Message:Comment {id: m.id * 10 + d, creationDate: m.creationDate + d * 1000, content: 'comment'})-[:HAS_CREATOR]->(p), (c)-[:REPLY_OF]->(m);
MATCH (c:Comment) WITH c MATCH (t:Tag {id: (c.id % 40) + 1}) CREATE (c)-[:HAS_TAG]->(t);
MATCH (m:Message) WHERE m.id % 3 = 0 WITH m MATCH (p:Person {id: ((m.id * 13) % 1000) + 1}) CREATE (p)-[:LIKES]->(m);

KNOWS offsets 5, 10 and 15 form triangles. Persons 1–10 each get 150 extra outgoing KNOWS edges (hubs). Message is the primary label of every post and comment.