Query Planning & Performance

patinaDB compiles each query into a streaming operator tree (the “Op tree”), picks a physical access path for every entry point, and — on skewed data — uses a statistics catalog and a cost model to choose between competing plans. This chapter shows how to read what the planner chose and which fast paths make a query cheap.

Reading EXPLAIN and PROFILE

EXPLAIN renders the chosen plan without running the query; PROFILE runs it and prefixes the elapsed time.

$ patinadb ./mygraph.db query "EXPLAIN MATCH (p:Person {name: 'Ada'}) RETURN p"
plan: 'Project items=1 distinct=false return_star=false
  MatchScan required=[[entry](p:Person) → PropertyIndex[name] = est.1]
'

Read the tree bottom-up: the MatchScan is the leaf that produces rows, and each line above consumes them. The arrow annotation is the access path and its estimated cardinality — here a PropertyIndex[name] = est.1 point lookup on the value index (one estimated row), not a full label scan.

A range predicate with an ORDER BY that a value index can serve turns into a sorted seek and emits a Physical: footer naming the executed access path:

$ patinadb ./mygraph.db query \
    "EXPLAIN MATCH (r:Reader) WHERE r.age > 40 RETURN r.name ORDER BY r.age"
plan: 'Project items=1 distinct=false return_star=false
  MatchScan required=[[entry](r:Reader) → PropertyIndex[age] SORTED SCAN ASC est.2]
Physical:
  entry.range_seek
'

The Physical: footer is the single source of truth for the executed access path — the same registry drives both the EXPLAIN render and the executor, so EXPLAIN cannot lie about which path runs. Common footer names:

The statistics catalog

The planner keeps a lazy, cached statistics catalog derived from the value index — per label a vertex count, and per property the present count, distinct-value count (NDV), min/max, and a small equi-depth histogram. Inspect it with CALL patinadb.stats:

$ patinadb ./mygraph.db query "CALL patinadb.stats('Person')"

For the imported Person data (3 nodes) this yields, per property:

The catalog is invalidated automatically by writes (it is tagged with each label’s write generation), computed on demand, cached, and — because statistics only change which plan runs, never the result — never replicated across a cluster. Each node computes its own.

Cost-based selection

Two things use the catalog:

1. Entry-point selection. For a skewed EQ predicate (a value with many rows) or a range predicate, the estimator tightens its guess using the catalog (present_count / NDV, or histogram interpolation) instead of a pessimistic whole-label count. That can move the entry point of a multi-node pattern to the genuinely cheapest node.

2. Physical-rule ranking. When both a covering compound index and a selective single-property seek apply to the same node, the planner ranks them by an estimated Cost { rows, io } rather than static priority — so a non-selective compound index correctly loses to a selective single-property seek. When the cost model overrides the default pick, EXPLAIN’s footer says so (entry.cost_override: …).

3. Join ordering. A multi-pattern comma-MATCH is reordered so the most selective pattern drives the join and the intermediate result stays small (a bounded Selinger DP for ≤ 8 patterns, greedy above that). Connectivity is preserved, so the reorder never introduces a cartesian product the written order avoided.

Because an inner join’s result is a multiset independent of join order, and a different access path over the same data returns the same rows, cost-based planning changes only speed, never results. A query without ORDER BY already returns rows unordered; one with ORDER BY post-sorts.

Fast paths that make queries cheap

The executor recognizes a number of shapes and serves them without a full scan or a blocking sort. You don’t opt into these — they fire automatically when the shape and the available indexes match. The Physical: footer tells you which fired.

The advisor

When a traversal + ORDER BY target.prop LIMIT k shape could be served by an edge-sorted index but none exists, both EXPLAIN and the advisor procedure tell you exactly which index to create:

$ patinadb ./mygraph.db query \
    "EXPLAIN MATCH (c:Company {name:'Acme'})<-[:WORKS_AT]-(p:Person)
             RETURN p ORDER BY p.age DESC LIMIT 3"
plan: 'Limit skip=0 count=3
  Project items=1 distinct=false return_star=false
    Sort keys=1
      MatchScan required=[(c:Company) -[entry](p:Person) → PropertyIndex[age] SORTED SCAN DESC est.3]
Physical:
  limit.bounded_topk
Advice: CREATE EDGE SORTED INDEX FOR (m:Person)<-[:WORKS_AT]-() ON m.age  (would serve this ORDER BY … LIMIT via edge_sorted_topk instead of a fan-out top-K)
'

The same suggestion is available programmatically:

$ patinadb ./mygraph.db query \
    "CALL patinadb.advisor('MATCH (c:Company {name:\"Acme\"})<-[:WORKS_AT]-(p:Person) RETURN p ORDER BY p.age DESC LIMIT 3') YIELD suggestion"
suggestion: 'CREATE EDGE SORTED INDEX FOR (m:Person)<-[:WORKS_AT]-() ON m.age'

Creating that index flips the plan to limit.edge_sorted_topk and the advice disappears. See Edge-Sorted Indexes.

Bounded-memory guards

Blocking operators (aggregate input, non-top-K ORDER BY, UNION-distinct, and hash-join build sides) are capped at PATINADB_MAX_AGG_ROWS (default 5,000,000). Past the cap they raise a clear, actionable error instead of an OOM — the default is far above any normal query, so below it the result is byte-identical. See Configuration and Caching & Memory Tuning for the RAM budget model, and Cache Observability & Tuning for the read-cache hit rates that make repeated hot queries cheap.