Statements and execution plans

Each statement compiles once into a step chain that runs in the order it is written, chosen from the statement's shape and the catalog, never from data statistics.

KDBS has no cost-based query planner. When a statement is parsed, it is compiled into a step chain: an ordered list of steps, one per table access, run in the order the statement is written. The access method for each step is chosen from the statement’s shape and from what the catalog holds (indexes, Cabins). It is never chosen from row counts or data statistics. So a statement’s plan does not change as a table grows, and you can predict its cost from its text.

How it works

From text to steps

 SQL text ──▶ parser ──────────────▶ step compiler ─────────────▶ step VM
              • fingerprint           • names → table/column ids   • runs steps in order
                (pattern_id)          • one access kind per step    on the session's core
              • execution class       • predicates attached

The parser reads the statement once. While it reads, it replaces each literal value with a placeholder and hashes the result. This hash is the statement’s pattern_id: WHERE id = 42 and WHERE id = 7 have the same pattern_id. The parser also tags the statement with an execution class: PointSelect, RangeSelect or JoinSelect.
The step compiler resolves every table and column name to an internal id, and picks one access kind per step. After this, execution performs no name lookups.
The step VM runs the chain front to back, as a nested loop: for each row a step produces, the next step runs.

Step kinds

Step	What it does	Chosen when
`Lookup`	Descends the B+ tree to one key	`WHERE <pk> = <value>`
`Range`	Walks the leaves between two keys	`<pk> BETWEEN <low> AND <high>`
`Probe`	Descends to a key produced by an earlier step	A join or correlated subquery keyed on a table’s primary key
`IndexProbe`	Reads a secondary index, then the rows it names	Equality on an indexed column
`CabinProbe`	Reads a Cabin’s entries for an observed value	Equality on a column with a Cabin, and no index
`FilterScan`	Reads every row, keeps those that match an equality	Equality on a column with no index and no Cabin
`Scan`	Reads every row	No usable predicate
`Exists` / `NotExists`	Stops at the first match / proves there is none	`EXISTS`, `IN`, `NOT EXISTS`, `NOT IN` subqueries

For an equality on a non-key column, the order of preference is fixed: secondary index, then Cabin, then filter scan. Other comparisons are checked as filters on the step that reads the rows; for example, WHERE id < 3 runs as a Scan with a filter.

Joins run in written order

The tables in FROM ... JOIN ... are read in the order written. Nothing reorders them. A join on the inner table’s primary key becomes a Probe. Any other equi-join is still allowed: it becomes a scan of the inner table with the ON condition checked per row.

When a join’s inner side has no index, no Cabin and no filter of its own, the engine builds an in-memory map of the inner rows during the first outer row’s read, and later outer rows look up the map. This does not change which table drives the join or the order of the rows returned. The map lives for one statement. ANALYZE marks such a step build, and join_build_max_rows = 0 turns it off.

Subqueries

Subqueries are allowed only in predicate position (WHERE), up to 4 levels deep.

An uncorrelated subquery runs once, before the outer chain.
A correlated subquery runs once per outer row, where it is written. A correlated subquery on a primary key costs what a join step costs.
The engine never rewrites a correlated subquery into a join.

What may change the order

Three things are allowed, and none of them changes which rows a statement returns:

ORDER BY sorts the output after every step has run. Rows the sort does not distinguish keep their written order. ORDER BY <primary key> ASC is dropped at compile time, because rows already come out in key order.
Equality propagation. From a.x = b.y and b.y = 5, the compiler adds a.x = 5, so the step on a can use it as a key. It only adds conditions, never removes or reorders them. ANALYZE prints such conditions as derived.
The join build described above.

Examples

A primary-key equality is one Lookup:

kdbs> ANALYZE SELECT * FROM passengers WHERE id = 2
analyze rows=1 class=PointSelect steps=1 examined=1 pages=1 opens=1 pattern_id=0x40a5b5e4e01959eb fetch_id=0x9b8e7707127bd8d4
class=PointSelect steps=1 hoisted=0
step 0 Lookup passengers key=2
  filter 0:0.0 = 2
project * (4 column(s) of step 0)
step 0 Lookup passengers opens=1 examined=1 matched=1 sel=100% pages=1

The same statement with id = 3 has the same pattern_id (0x40a5b5e4e01959eb), because only the literal changed.

A join keyed on passengers.id scans tickets (written first) and probes passengers once per ticket:

kdbs> ANALYZE SELECT p.name, t.seat FROM tickets AS t JOIN passengers AS p ON p.id = t.passenger_id
analyze rows=9 class=JoinSelect steps=2 examined=18 pages=10 opens=10 pattern_id=0x76d381c022f662a fetch_id=0xa2ac65820beb7ff2
class=JoinSelect steps=2 hoisted=0
step 0 Scan tickets AS t
step 1 Probe passengers AS p key=0:0.2
  filter 0:1.0 = 0:0.2
project p.name=0:1.1, t.seat=0:0.3
step 0 Scan tickets AS t opens=1 examined=9 matched=9 sel=100% pages=1
step 1 Probe passengers AS p opens=9 examined=9 matched=9 sel=100% pages=9

An equality on name is a FilterScan while the column has no index:

kdbs> ANALYZE SELECT * FROM passengers WHERE name = 'Park Jiho'
analyze rows=1 class=JoinSelect steps=1 examined=8 pages=1 opens=1 pattern_id=0x4a30f64aef21b46b fetch_id=0xd233d3fa77d83084
class=JoinSelect steps=1 hoisted=0
step 0 FilterScan passengers
  filter 0:0.1 = 'Park Jiho'
project * (4 column(s) of step 0)
step 0 FilterScan passengers opens=1 examined=8 matched=1 sel=12% pages=1

After CREATE INDEX ix_name ON passengers(name), the same statement uses the index. The plan changed because the catalog changed, not because the data did:

kdbs> ANALYZE SELECT * FROM passengers WHERE name = 'Park Jiho'
analyze rows=1 class=JoinSelect steps=1 examined=1 pages=2 opens=1 pattern_id=0x4a30f64aef21b46b fetch_id=0xd233d3fa77d83084
class=JoinSelect steps=1 hoisted=0
step 0 IndexProbe passengers
  filter 0:0.1 = 'Park Jiho'
project * (4 column(s) of step 0)
step 0 IndexProbe passengers opens=1 examined=1 matched=1 sel=100% pages=2 index_scanned=1 index_resolved=1

Ordering by the primary key adds nothing; ordering by another column adds a sort line:

kdbs> ANALYZE SELECT * FROM flights ORDER BY base_fare DESC
analyze rows=4 class=JoinSelect steps=1 examined=4 pages=1 opens=1 sorted=4 pattern_id=0x50bd515e8d5e2129 fetch_id=0xf4cdd401d8f181c6
class=JoinSelect steps=1 hoisted=0
step 0 Scan flights
project * (8 column(s) of step 0)
sort 0:0.7 desc
step 0 Scan flights opens=1 examined=4 matched=4 sel=100% pages=1

What it guarantees

The plan does not depend on data size. The same statement shape over the same catalog compiles to the same chain at any table size.
The written order is the execution order, and it is the order rows come back in when there is no ORDER BY. So LIMIT n OFFSET m without ORDER BY is well defined: rows [m, m+n) of the unlimited result.
A statement does not run away. A statement that touches more than max_rows_touched rows (default 100,000,000) fails with ResourceExhausted. A sort that would hold more than sort_max_rows rows fails instead of spilling or truncating.
A refusal names its position. A form the engine does not run is refused with the byte position of the offending token, and says whether it is not built yet (NOT_IMPLEMENTED) or not supported by design (UNSUPPORTED).

What it costs

You choose the join order. A join written with the large table first runs that way. Put the table that narrows the result first, and join to the others by primary key where you can.
The engine cannot skip its own index on a tiny table, the way a cost-based planner would.
A sorted LIMIT reads every matching row. The sort must see all of them before it knows the first. OFFSET reads and discards the rows it skips; for deep pages, use a key condition such as WHERE id > <last seen> LIMIT n.

The grammar is small. WHERE takes AND-joined conditions only: no OR, no NOT over an expression, no parenthesized nesting. There are no CTEs, derived tables, outer joins, window functions or HAVING. IN takes a subquery, not a value list.

kdbs> SELECT * FROM passengers LEFT JOIN tickets ON tickets.passenger_id = passengers.id
                               ^
ERR NOT_IMPLEMENTED retryable=0 outer joins are not supported: 'LEFT' at byte 25; only inner equi-joins (JOIN ... ON) are available

Fingerprints and the workload

Each statement has two fingerprints, both printed by ANALYZE:

pattern_id is the whole shape with literals removed.
fetch_id is the shape without its select list, so SELECT a ... and SELECT COUNT(*) ... over the same FROM ... WHERE share one. SHOW PATTERNS lists statements by fetch_id.

From the second time the same shape runs with the same arguments, the engine records which rows it found, as a Waystone trail, and later runs can use the trail to skip a key lookup. A trail is advisory: it can make a statement faster or slower, never change its result. See Waystone trails.

How to observe it

Command	Shows
`ANALYZE <select>`	The chain that ran: class, each step’s access kind, rows examined and matched, pages read, sorts, `pattern_id` and `fetch_id`
`SHOW ACCESS`	How often each table was accessed by each access kind and column set
`SHOW PATTERNS`	The statement shapes the database has received

After the examples above (the id = 3 statement left out), on a fresh sandbox:

kdbs> SHOW ACCESS
access_shapes=8
kind=Lookup rel=airlines columns=[id] uses=3 last_seen=1227680216613158
kind=Lookup rel=flights columns=[id] uses=3 last_seen=1227680226720382
kind=Lookup rel=passengers columns=[id] uses=9 last_seen=1227680230773009
kind=Scan rel=tickets columns=[] uses=1 last_seen=1227680231250469
kind=Probe rel=passengers columns=[id] uses=1 last_seen=1227680231250469
kind=FilterScan rel=passengers columns=[name] uses=1 last_seen=1227680231574458
kind=IndexProbe rel=passengers columns=[name] uses=1 last_seen=1227680236203745
kind=Scan rel=flights columns=[] uses=1 last_seen=1227680236582346

The airlines and flights lookups, and eight of the nine passengers lookups, are foreign-key checks made when the sample flights and tickets rows were loaded.

A FilterScan row is a statement that asked for a few rows and had to read all of them: the shape an index or a Cabin would fix.

Limitations

ANALYZE takes SELECT only. A write cannot be analyzed.
Functions are limited. DATE(ts) and NOW() are allowed only as one side of a WHERE comparison, and such a comparison never becomes a key or an index range. Expressions are allowed in UPDATE ... SET values, but not in a select list or in INSERT ... VALUES.
No implicit type conversion. A literal must be written in the compared column’s own form (n = 20, not n = '20'). A mismatch is refused at compile time.
Aggregates are not allowed inside subqueries, and ORDER BY over grouped output is refused.