Architecture implementation archive

Architecture implementation archive

These are detailed sections moved out of architectural chapters, preserved from repository commit f5e786f. They are historical text, not current API documentation. Some describe earlier pull-shell APIs, fixed-i64 aggregation, Robin Hood layouts, or proposals that have since changed. Consult the current implementation pages and source map in AGENTS.md before using a signature, source path, or status claim.

aggregation.md

Source map

Area	Source
Logical aggregate operator and output schema	qdb/ops/aggregate.{h,cpp}
Physical planning	qdb/exec/planner.cpp
Key type and ABI layout construction	qdb/kernel/aggregate_key.{h,cpp}
Generated hash, equality, reducers and entry wrappers	qdb/kernel/gen.{h,cpp}
Oz loading and final AST composition	qdb/kernel/lib.{h,cpp}
LLVM JIT setup and callable kernel wrappers	qdb/kernel/compiler.{h,cpp}
Generic production Oz kernels	qdb/kernel/aggregation/*.oz
External Qumir types and allocator functions	qdb/modules/qumirdb.cpp
Allocator and f64 bit helper implementations	qdb/modules/qumirdb_runtime.{h,cpp}
Runtime pipeline breaker	qdb/exec/aggregate_exec.{h,cpp}
Kernel-level tests	test/test_aggregation.cpp
End-to-end execution tests	test/test_aggregate.cpp

Concrete key representation

BuildAggregateKeyDescriptor maps logical group columns to a fixed-width key:

• one group column: Key is that column's type directly;
• multiple group columns: Key is a generated named struct such as AggKey_k1_i64_k2_f64;
• generated struct fields are named key_0, key_1, and so on;
• Qumir's struct layout supplies the C ABI padding implicitly;
• each descriptor records source column index, offset, size, and alignment.

Supported layout leaves are integers, f64, bool, and recursively nested structs. The current CompileAggregate validation is narrower: each selected group column must itself be an integer or f64. Recursive struct hashing is already implemented and tested, but is not yet exposed by that production validation path.

Owned key arrays are byte-addressed in the external ABI. HashTable.Keys and HashTable.GroupKeys are <ptr u8> plus HashTable.KeySize. A generic Oz function casts them locally to <ptr Key> only after Key is specialized. This keeps the C++ ABI independent of the query's key type.

HashTable ABI and memory ownership

QumirDbModule exposes a 104-byte HashTable struct. Its important fields are:

Field	Type	Purpose
Keys	u8*	probe keys, Capacity * KeySize bytes
Dist	i64*	probe distance, -1 means empty
SlotId	i64*	stable dense slot for each probe entry
GroupKeys	u8*	dense keys
AggBuffers	i64**	one dense state array per reducer
Capacity	i64	power-of-two table capacity
Size	i64	number of groups
NumAggs	i64	reducer count
KeySize	i64	concrete key size in bytes

Scratch, Scratch2, QueryKey, and NumKeys are retained in the current ABI but are not used by the production table path.

Ownership is split intentionally:

• TRuntimeAggregate owns a zero-initialized 104-byte header for one query execution;
• aht_init and aht_rehash allocate internal arrays through the registered qdb_alloc external function;
• aht_destroy releases those arrays through qdb_free;
• C++ owns the finalized output arrays and their TRowSet lifetime.

The allocator functions currently wrap malloc/free. A future query-owned allocator can replace this implementation without changing the typed generic kernel boundary; allocator context propagation is not designed yet.

Production and staged Oz files

Only these files are currently composed by CompileAggregate:

• robin_hood_rehash_generic.oz
• aggregation_hashtable_generic.oz
• aggregation_finalize_states.oz

Other files under qdb/kernel/aggregation are staged components, focused examples, or earlier integration layers used by test/test_aggregation.cpp. In particular, key_ops_i64.oz is a test/reference implementation; production hash and equality helpers are generated from the query type AST.

Extension points

The main type-generic extension points are already isolated:

• add a supported leaf type in key layout, hash generation, and equality generation together;
• relax CompileAggregate validation when recursively structured group columns are ready for the input/output ABI;
• replace generated built-in reducer bodies with reducer functions carried by the logical aggregation node;
• generalize aggregate state buffers beyond i64;
• introduce a query context and query-owned allocator without changing the opaque byte storage used for concrete keys.

Any new key type must preserve all three contracts: fixed ABI layout, matching hash/equality semantics, and typed projection during finalize.

join.md

Source map

Area	Source
Logical join operator and output schema	qdb/ops/join.{h,cpp}
Physical planning	qdb/exec/planner.cpp
Runtime executor and output materialization	qdb/exec/join_exec.{h,cpp}
Join key descriptor	qdb/kernel/join_key.{h,cpp}
Generated join process/probe/finalize AST	qdb/kernel/join_gen.{h,cpp}
Residual predicate AST generation	qdb/kernel/gen.{h,cpp}
JIT compilation and C++ callable ABI	qdb/kernel/compiler.{h,cpp}
Generic Oz join table/update code	qdb/kernel/join/*.oz
Shared hash table ABI	qdb/modules/qumirdb.cpp
Runtime tests	test/test_join_exec.cpp
Kernel tests	test/test_join_kernel.cpp
Planner tests	test/test_join_planner.cpp

Runtime data structures

TRowStore owns retained input batches for one join side. Stored rows are addressed by a packed TRowId:

row_id = (batch_idx << 32) | row_idx

kNullRowId == -1 marks absent rows for outer-join null padding and for semi/anti builder pairs where the non-emitted side is ignored.

TJoinOutputBuilder stores (left_row_id, right_row_id) pairs and later gathers output columns from LeftRows_ and RightRows_. This is used when both sides of a pair are retained.

Probe-only streaming uses a different materialization path. The streamed row does not have a stable TRowStore entry, so TRuntimeJoin drains the kernel pair buffer immediately into owned output TRowSets and queues them in ReadyOutput_. The stream batch can then be released safely.

Hash tables and pair buffers

Join reuses the generic HashTable external ABI used by aggregation, but with join-specific dense buffers:

AggBuffers[0] = bucket row count per dense slot
AggBuffers[1] = bucket row capacity per dense slot
AggBuffers[2] = bucket data pointer, stored as i64

Each side has its own HashTable buffer:

LeftTable_
RightTable_

The kernel emits matches into a PairBuffer containing adjacent left/right row-id pairs:

Data[2*i + 0] = left row id
Data[2*i + 1] = right row id

The pair buffer grows in Oz code and is destroyed by the compiled kernel library. C++ resets only Count after draining.

Kernel split

TKernelCompiler::CompileJoin composes one complete Qumir AST per entry point:

1. generated key type declarations;
2. generated rh_hash(Key) and rh_key_equal(Key, Key);
3. generic join library from qdb/kernel/join/*.oz;
4. generated entry wrappers for the concrete query.

The compiled TJoinKernels ABI contains:

Entry	Purpose
Init(table, capacity)	Initialize one side's hash table
ProcessLeft(own, opp, batch, batch_idx, pairs, left_store, right_store)	Probe right, emit matches, insert left rows
ProcessRight(own, opp, batch, batch_idx, pairs, left_store, right_store)	Probe left, emit matches, insert right rows
ProbeLeftStream(build, batch, batch_idx, pairs, left_store, right_store)	Probe right/build table with a left stream batch; no insert
ProbeRightStream(build, batch, batch_idx, pairs, left_store, right_store)	Probe left/build table with a right stream batch; no insert
InsertKeyOnly(own, opp, batch, batch_idx, pairs)	Build a key-existence table for non-residual semi/anti
FinalizeAntiSemi(own, opp, pairs)	Scan left table and emit semi/anti left row ids
FinalizeOuter(own, opp, pairs)	Scan own side and emit rows with no opposite match
DestroyTable(table)	Free table allocations
DestroyPairs(pairs)	Free pair-buffer allocation

The generic Oz helper jt_probe_and_emit does the common probe and pair emit. jt_emit_and_insert calls it first, then inserts the current row into the own-side table. Probe-only wrappers call only jt_probe_and_emit.

This split is deliberate: the expensive and type-specialized key extraction is generated once per side, while the generic table code remains shared.

logical_plan_build.md

Source map

Area	Source
Builder	qdb/plan/build.{h,cpp} (BuildPlan → BuildQuery → BuildSelect)
Operators	qdb/plan/ops/{source,filter,project,aggregate,join,window}.{h,cpp}
Expression clone (CTE inlining)	qdb/plan/clone_expr.{h,cpp}
Conjunct splitting	qdb/plan/passes/flatten_conjucts.{h,cpp}

join_reorder.md

Source map

Area	Source
Pass	qdb/plan/passes/join_order.{h,cpp} (ReorderJoins)
Conjunct/disjunct splitting	qdb/plan/passes/{flatten_conjucts,flatten_disjuncts,factor_conjuncts}.cpp

predicate_pushdown.md

Source map

Area	Source
Pass	qdb/plan/passes/equijoin.{h,cpp} (ExtractEquiJoins)
Equivalence classes	qdb/utils/union_find.h
Conjunct/disjunct splitting	qdb/plan/passes/{flatten_conjucts,flatten_disjuncts,factor_conjuncts}.cpp
Free-variable detection	qdb/plan/passes/unbound_vars.{h,cpp}

decorrelation.md

Source map

Area	Source
EXISTS/IN → semi/anti	qdb/plan/build.cpp (AsDecorrelation, DecorrelateExists, DecorrelateIn)
Scalar subqueries	qdb/plan/build.cpp (ExtractScalarSubqueries, CollectLocalColumns)
Subquery AST node	qdb/sql/ast.h (TSubqueryExpr, kind Exists/In/Scalar)

dispatch.md

Runtime shell model

The runtime shell kinds are intentionally small:

TRuntimeSource

TRuntimeUnaryStreamingKernel
  child.Next(rowset)
  kernel/process(rowset)
  return rowset

TRuntimeUnaryBlockingKernel
  process(child, out)
  return out

TRuntimeBinaryKernel
  owns left child
  owns right child
  exposes output type

TRuntimeJoin is currently the concrete binary shell for equi-join modes. It shares the same state and output machinery across inner, semi, anti, and outer joins, with mode-specific dispatch methods:

TRuntimeJoin::Next
  EnsureInit
  DrainReadyOutput
  if residual semi/anti -> NextResidualSemiAnti
  if semi/anti          -> NextSemiAnti
  if outer              -> NextOuter
  otherwise             -> NextInner

This is still one binary runtime shell. The mode methods are control-flow policies over the same retained row stores, hash tables, pair buffer, compiled kernel bundle, and output builder.

JS dispatcher target

A JS dispatcher can be modeled as an interpreter over a physical runtime graph:

RuntimePlan
  nodes:
    id
    kind: source | unary_stream | unary_block | binary_join | limit | ...
    children: [ids]
    output_schema
    shell_config
    kernel_bundle_id

KernelBundleRegistry
  id -> compiled entrypoint table

Dispatcher
  next(node_id) -> RowSetHandle | end

For example:

next(filter_node):
  input = next(child)
  if input == end: return end
  call filter_kernel(input)
  return input

next(join_node):
  state = get_join_state(join_node)
  return join_next(state)

The dispatcher needs a faithful implementation of the shell state machines, not knowledge of SQL expressions or generated Oz ASTs.

What is already enough

The current lowering work already provides the major prerequisites:

• compute operators have typed kernel specs;
• filter/project/aggregate/join build kernels from specs;
• generic unary streaming and unary blocking shells exist;
• binary ownership is isolated in TRuntimeBinaryKernel;
• join mode dispatch is now explicit and localized in small methods;
• join residual predicates run inside kernels, including semi/anti cases;
• hash/probe/update logic is in Oz source modules rather than JS/C++ dispatch.

This makes a JS dispatcher realistic if C++ continues to provide:

• physical planning or a serialized RuntimePlan;
• kernel compilation and a kernel bundle registry;
• rowset/state allocation primitives.

What still stays in the dispatcher

A JS dispatcher would still need to implement real runtime policy:

• pull order and EOF transitions;
• blocking-vs-streaming boundaries;
• rowset retain/release discipline;
• output batch draining;
• join symmetric/probe-only transitions;
• semi/anti and outer finalization timing;
• sort/top-sort state policy.

This is expected. Moving these policies into kernels would make kernels own query graph execution, which is not the goal.

Remaining uncertainty

The largest remaining modeling questions are not ABI questions:

• whether join policy should remain one binary_join shell or split into binary_join_inner, binary_join_semi_anti, and binary_join_outer;
• whether sort/top-sort should expose a more explicit state-policy descriptor;
• whether source and sink nodes should use the same next(node) protocol in JS, or be host callbacks;
• whether runtime plans should reference logical operator names or only shell kinds plus kernel bundle ids;
• whether kernel specs are sufficient as the serialized plan format, or whether they should remain compiler input only and produce a smaller runtime config.

scheduler_runtime.md

Task Nodes

Task node	Input shape	Output shape	Used by physical nodes	State owner	Why it exists
TSourceTask	none	one lane	Source	TSchedulerSourceState	Pulls rowsets from ISource; parquet scans can be split into independent row-group range sources.
TUnaryTask	one lane	one lane	Filter, Project, cross residual filter, cross scalar forwarding	TUnaryStreamingKernelState or trivial state	Streaming one-rowset-in/one-rowset-out stage. Keeps partitioning unchanged.
TBlockingTask	one lane	one lane	Aggregate, Limit, Sort, TopSort, late lookup	operator-specific processor state	Drains input until enough state exists to emit output.
TBinaryBlockingTask	two lanes	one lane	equi-join, cross join	TInnerJoinProcessor or TCrossJoinProcessor	Coordinates two input streams and emits joined rowsets.
TMergeTask	N lanes	one lane	partitioned Sort, partitioned TopSort, late materialization	TMergeProcessor or operator-specific state	Reads several input lanes and emits one output stream.
THashShuffleTask	one lane	many lanes through THashShuffleConnection	grouped aggregate, window, and equi-join repartition	per-task hash scratch and output buffers	Computes row hashes and routes rows to partition lanes.
TSinkTask	one lane	none	final sink	caller-owned ISink alias	Writes final rowsets and releases them.

Operator Lowering

Physical operator	Lowered task pattern	Connections	Kernels/processors	Notes
Source	one TSourceTask per scan lane	parent output connection	none	Parquet source may split row groups into several lane-local sources.
Filter	child lanes -> TUnaryTask per lane	one-to-one child input	filter kernel	Selection is detached before crossing the output connection.
Project	child lanes -> TUnaryTask per lane	one-to-one child input	optional project kernel	Identity columns are references; computed columns are materialized into owned buffers.
Limit	child -> one TBlockingTask	one-to-one if one child lane, otherwise gather	TLimitProcessor	Global limit/offset is intentionally single-lane.
Aggregate, ungrouped/global	child -> one aggregate task, or optional cascade	one-to-one or gather; cascade uses partial tasks -> gather -> combine task	aggregate kernels	Cascade is off by default for cheap aggregates.
Aggregate, grouped	either child lanes -> repartition -> complete aggregate, or statistics-selected local partial aggregate -> repartition -> final aggregate	one-to-one into each local phase, hash-shuffle at the repartition boundary	group hash + partial/final aggregate kernels	Partial and final are distinct executable stages. Parent usually gathers final partitions later if needed.
Sort, one input lane	child -> one sort task	one-to-one	sort processor + optional radix kernel	Full blocking sort.
Sort, many input lanes	local sort per lane -> merge task	one-to-one run connections	local sort + merge processor	Produces one globally sorted stream.
TopSort, one input lane	child -> one top-sort task	one-to-one	top-sort processor + optional radix kernel	Keeps local top-K only.
TopSort, many input lanes	local top-sort per lane -> merge -> limit	one-to-one run connections	top-sort + merge + limit	Implements top-sort over partitions -> merge -> limit.
Late materialization	rows after LIMIT -> optional broadcast -> lookup tasks by column range -> merge	gather or one-to-one, optional broadcast, then one result lane per lookup task	Parquet row lookup	Lookup tasks stay in the scheduler pool. They share the open Parquet file reader.
Equi-join, single partition	left/right -> one binary join task	two one-to-one inputs	join kernels	Fast path skips hash-shuffle and join-hash kernels.
Equi-join, partitioned	left/right -> shuffle tasks -> join task per partition	two one-to-one inputs, two hash-shuffle connections	join hash + join kernels	Both sides use the same partition count, so matching keys land in the same join lane.
Keyless inner join	vector side + scalar side -> cross tasks	vector one-to-one; scalar one-to-one or gather -> broadcast	TCrossJoinProcessor; residual uses filter kernel	Scalar side is buffered, then paired with each vector lane.
Final sink	producers -> TSinkTask	one-to-one if one lane, otherwise gather	none	RunPlanIntoSink appends the sink node after lowering.

Current Dispatch Summary

Category	Already kernelized	Still mostly C++ dispatch/state
Per-row expression evaluation	filter predicates, computed project columns, join residuals	selection ownership after filter
Hashing	join key hash, group key hash	shuffle routing, batching, materialization
Aggregation	hash table update/finalize kernels	processor lifecycle, output sizing/gather
Join	hash table probe/insert/finalizers	two-input pull policy, row stores, pair draining, output gather
Sort	radix key sorting for supported key types	comparator fallback, row store, merge, top-K state
Scan/sink	none in scheduler kernels	source/sink implementations

This means a JS scheduler can be designed around the current graph model, but a pure JS dispatcher would still need exported native adapters for aggregate, join, shuffle materialization and sort/merge unless those state machines are split into explicit ABI objects.

Generic Task Machines

Task node	Persistent state	Main transition loop	Output ownership
TSourceTask	Finished flag, source state	If output cannot accept, return BLOCKED_OUTPUT; otherwise call Source->Next(rowSet). On data, push rowset and return OK; on EOF, finish output and return FINISHED.	Source returns an owned/refcounted TRowSet; task transfers it to the output connection.
TUnaryTask	current input rowset, HasInput, InputFinished, OutputFinished, unary state	Fetch one input if none is held. On NO_DATA, return NEED_DATA; on input finish, finish output. Otherwise run Code.Process(state,rowSet), push transformed rowset, return OK.	Holds one input rowset across retries; releases it in destructor if still held.
TSinkTask	Finished flag, sink alias	Fetch one input. On NO_DATA, return NEED_DATA; on finish, return FINISHED; on rowset, call sink writer, release rowset, return OK.	Consumes and releases fetched rowsets.
TBlockingTask	pending output rowset, HasOutput, OutputFinished, blocking processor state	First flush pending output if any. Then call Code.Process(state,input,output). If processor returns OK, remember output and return OK; if FINISHED, finish output.	Processor fills one output rowset at a time; task owns pending output until pushed.
TBinaryBlockingTask	pending output rowset, HasOutput, OutputFinished, binary processor state	Same as TBlockingTask, but calls Code.Process(state,left,right,output) and the processor drives two input ports.	Same pending-output ownership as blocking task.
TMergeTask	pending output rowset, HasOutput, OutputFinished, merge state and input ports	Same pending-output shell as blocking task; processor reads all run inputs, then emits merged rowsets.	Same pending-output ownership as blocking task.
THashShuffleTask	hash buffer, per-destination buffers, pending rowsets, pending index, OutputFinished	Push pending outputs first. Otherwise fetch input; on data, hash/scatter into destination buffers and push ready outputs; on input finish, flush all buffers, push pending, finish the source lane.	Either emits selection-view rowsets retaining the input, or materialized rowsets with owned buffers.

Operator Processor Machines

These are the SQL-level machines currently hidden behind generic task nodes. For a JS runtime, each row in this table is either JS code or a native/WASM node adapter.

Physical node	Generic task	Processor state	State machine	Compiled kernels used
Filter	TUnaryTask	reusable selection buffer	For each rowset, resize selection, point rowSet.Selection at it, call filter dispatch with the input selection, then detach selection before crossing a connection.	CompileFilter
Project	TUnaryTask	none beyond closure metadata	For each rowset, retain input, allocate owned buffers for computed columns, call project dispatch, build output column array mixing input columns and computed columns.	optional CompileProject
Limit	TBlockingTask	skipped/emitted counters	Fetch rowsets until enough rows are skipped/emitted; produce selection-view rowsets; finish when limit reached or input finishes.	none
Aggregate	TBlockingTask	aggregate hash table, done flag, output buffers inside processor	On first use init hash table; for each input rowset call update dispatch; on EOF measure groups, allocate output buffers, call finalize, emit output, then finish/destroy.	aggregate dispatch/measure/finalize
Sort	TBlockingTask	row store, row-id vector, cursor, optional radix scratch	Drain all input rowsets into row store; sort row ids by keys; emit gathered output batches by cursor.	optional radix sort dispatch
TopSort	TBlockingTask	bounded top-K state, scratch buffers, cursor	For each input rowset, keep only local top-K candidates; after EOF emit gathered sorted top-K batches.	optional radix sort dispatch
Merge	TMergeTask	one row store per run, finished flags, merged row-id vector, cursor	Drain all sorted run inputs; merge run row ids by the same sort comparator; emit gathered output batches.	none directly; local sorts may use radix kernels
Equi-join	TBinaryBlockingTask	left/right row stores, two hash tables, pair buffer, ready output queue, join mode flags	Fetch from both sides, store batches, call process-left/right kernels, drain pair buffer into output rowsets; after one side finishes, stream/probe or finalize depending on join type.	join init/process/probe/finalize/destroy kernels
Cross join	TBinaryBlockingTask	right row store, optional left row store, output builder, drain flags	Drain/buffer right side, then stream left rowsets and pair each selected left row with every buffered right row; residual is a separate filter stage.	none for cross itself; residual uses filter kernel
Hash shuffle	THashShuffleTask	hash scratch, per-partition buffered row lists, pending outputs	For each input rowset, compute row hashes, route selected rows to partitions, flush partition buffers by row/byte thresholds, materialize when needed.	join hash or group hash

Kernel bundle	Compiler entry	ABI shape	Called by	Purpose
Filter	CompileFilter	void(TRowSet&, const uint8_t* inputSelection)	TUnaryTask via MakeFilterProcess	Fill rowSet.Selection for one input batch. Rows outside inputSelection get 0 and are not evaluated.
Project	CompileProject	void(TRowSet*, void** outBuffers)	TUnaryTask via MakeProjectProcess	Compute non-identity projection columns; identity columns stay zero-copy references.
Aggregate	CompileAggregate	Dispatch(ht,batch,arg,op), Measure, Finalize	TBlockingTask through TAggregateProcessor	Maintain per-group hash table and emit grouped aggregate output.
Join	CompileJoin	init, process-left/right, stream-probe, finalizers, destroy	TBinaryBlockingTask through TInnerJoinProcessor	Symmetric hash join, semi/anti, outer finalization, residual filtering inside join kernel where supported.
Join hash	CompileJoinHash	bool(TRowSet*, uint64_t*)	THashShuffleTask, TRuntimeFilterTask	Compute one hash per selected row for join-side partitioning and runtime filters.
Group hash	MakeGroupKeyHash	bool(TRowSet*, uint64_t*)	THashShuffleTask	Compute one hash per selected row for grouped aggregate partitioning.
Sort radix	CompileRadixSortComposite, CompileRadixSortCompositeNullable	key arrays + index/work/count buffers	TSortProcessor, TTopSortProcessor	Fast index sorting for radix-sortable key columns.

Runtime piece	JS can own today in principle	Requires C++/WASM adapter	Why
Graph topology	yes	no	Nodes, edges, lanes and debug names are plain structural data.
Scheduling policy	yes	no	Scheduler consumes only task results and graph edges.
OneToOne / Gather / Broadcast queues	yes	maybe	Semantics are simple rowset queues plus finish flags. Need exact TRowSet ownership ABI.
HashShuffleConnection	yes	yes	Queue semantics are simple, but shuffle task currently performs C++ selection/materialization.
Source task	partial	yes	Parquet scan and ISource are C++ objects today. JS can schedule it, but scan implementation remains native/WASM.
Filter/project task	yes	yes	JS can call WASM kernels and manage rowset buffers if TRowSet ownership is exported.
Aggregate task	partial	yes	Dispatch/measure/finalize are kernels, but TAggregateProcessor owns hash table lifecycle and output assembly in C++.
Join task	partial	yes	Kernels are compiled, but row stores, pair buffer draining, outer/semi finalization orchestration and materialization are C++.
Sort/merge/top-sort task	partial	yes	Radix kernels are compiled, but row store, comparator fallback, merge and output gather are C++.
Sink task	yes	maybe	Depends on the target sink; null/text sinks are simple, external sinks need adapters.

The architectural blocker is not kernel dispatch: the compiled kernel handles are already separated from scheduler task execution. The blocker is that several operator processors still combine three responsibilities in C++:

1. Stateful operator protocol (Add, Finish, Next, two-input fetch loops).
2. Rowset ownership and materialization (Retain/Release, private destroy payloads, selection detaching, string/nullable output assembly).
3. Calls into compiled kernels.

A JS runtime over WASM kernels becomes smooth when these state machines are either exported as native/WASM operator adapters, or their data/state ABI is made explicit enough for JS to own them directly.

kernel-compilation-phases.md

Consumers

• Physical graph JSON attaches kernel artifacts to semantic task groups by ExecStageId. Scheduler-only plumbing has separate monotonically assigned task:<id> groups; debug strings are display-only.
• BuildExecPlan collapses physical lanes and contracts plumbing using stable stage/input IDs, producing an exporter-neutral typed DAG.
• The exec JSON codec indexes kernels by ExecStageId; stage entrypoints and physical graph artifacts therefore refer to kernels emitted by the same scheduler lowering. Sort stages take radixKeys directly from retained kernel metadata. Nothing is lowered or compiled twice.

optimizations.md

Reproducing the plans

QDB_DUMP_PASSES=1 ./build/bin/qdb --sql --data <dir> -i q.sql   # plan after every pass
./build/bin/qdb --sql --verbose --data <dir> -i q.sql           # logical + runtime plan + scheduler graph

All examples below use four tiny Parquet tables:

table	columns	rows
t	a int64, b string, c int64	6
u	a int64, d string	4
v	a int64, e int64	3
big	a int64, c int64	40 rows in 4 row groups

Plans are printed by PrintPlanTree (qdb/plan/plan_print.cpp); source paths are shortened here. rows≈/cost≈ annotations appear once EstimateStats has run, and are elided below where they are not the point.

6. Not yet in master

• Aggregate hash-table pre-sizing from NDV — sizes the Robin Hood table from group-key NDVs instead of growing from 4, and moves the string hash/copy primitives into the runtime. On branch todo-aggregate-presizing, pending the review findings recorded there.

scan_parallelism.md

DuckDB comparison

Inspected the local DuckDB checkout at commit 044a04a7cd39e6e8235f756597ae42dde084e5e5 and checked the corresponding upstream implementation. For one Parquet file, its source concurrency limit is the number of row groups (at least one). Multiple files allow the scheduler's full concurrency. The pipeline then applies source, intermediate-operator and sink limits and caps the result at threads. It launches one pipeline task per allowed thread. This path does not use projected bytes or a rows-per-task threshold to choose the Parquet task count.

Row groups are assigned dynamically: a task receives the next group from the shared file state and can request another after finishing. A larger work pool therefore does not require a larger number of pipeline tasks. The relevant code is ParquetMultiFileInfo::MaxThreads and ParquetReader::TryInitializeScan and Pipeline::TryGetMaxThreads and LaunchScanTasks.

Native DuckDB tables have a size-based source limit: floor(total_rows / row_group_size) + 1, followed by the same pipeline and thread caps. The default native row-group size is 122,880 rows. They also assign row groups dynamically rather than pinning a range to each task. See DataTable::MaxThreads, the default row-group size, and RowGroupCollection::NextParallelScan.

DuckDB's ordinary in-memory hash join merges local build collections into one hash table and probes that table concurrently. It does not use qdb's dense graph of scan-to-join queues. Its initial radix partition count is 16 below 100 threads and 32 otherwise; these partitions are distinct from pipeline tasks. For an external join, it can increase the radix bits when the largest partition will not fit in the memory reservation, except in a heavily skewed case. The repartition estimate aims at one quarter of the reservation per partition. See PhysicalHashJoin::Finalize and JoinHashTable::SetRepartitionRadixBits.

Dynamic row-group assignment is a separate possible improvement for qdb. It would help balance row-group work while keeping scan and shuffle lane counts bounded. The current automatic mode keeps static ranges and chooses their count from source size and downstream join fan-in.

late_materialization.md

CLI and Browser

These CLI options control the rule:

--late-materialization=auto|off
--late-materialization-max-rows <n>
--late-materialization-min-savings <factor>

auto is the default. The default maximum is 100 rows. The default minimum cost factor is 2.0. With --verbose, QDB prints the planner decision and its byte estimates.

The browser runtime has no source lookup task. Plan export turns late materialization off for browser plans.

string_values.md

Generated type helpers

The AST generator must recursively produce helpers for the concrete pair of types:

rh_hash(LookupKey) -> i64
rh_hash(StoredKey) -> i64
rh_key_equal(StoredKey, LookupKey) -> bool
rh_key_equal(StoredKey, StoredKey) -> bool
key_owned_bytes(LookupKey) -> i64
key_clone_owned(LookupKey, <ptr u8>) -> StoredKey

Both hash overloads must use the same byte hash and struct combiner. Equality must compare lengths first and then bytes. Composite helpers recurse through nested fields and ignore generated padding.

key_clone_owned is recursive and type-directed. Fixed-width leaves are copied directly. String leaves copy bytes into successive slices of one caller-provided block and construct OwnedString handles pointing into those slices.

The first implementation should use a small, stable Oz byte hash with fixed test vectors. A faster hash can replace it later only with deliberate compatibility and performance testing. Hash values are process-local table details; they are not persisted.

Owned byte storage

Each new group receives one contiguous byte slice containing all string leaves of its key. Generated clone code sets each OwnedString.Data into that slice.

Slices come from a table-owned chunked arena. Chunks start at 4 KiB and grow geometrically up to 2 MiB; a request larger than that receives an exactly sized chunk. Each chunk has a 24-byte {magic, capacity, used} header and allocations bump the used offset. The magic distinguishes arena chunks from foreign or legacy registry entries before their allocator fields are read; a mismatch fails allocation without modifying the registry. This turns the allocation cost from one allocation per unique string-bearing group into roughly one allocation per arena chunk.

Only the most recent chunk accepts new slices. If a request does not fit, its remaining tail is not revisited; this keeps allocation constant-time at the cost of up to roughly 2x fragmentation for adversarial sizes. Ordinary short string keys leave much smaller tails.

The table owns a registry of chunk bases. aht_destroy delegates its cleanup to the shared owned_arena_destroy lifecycle helper, so allocation ownership has one destruction path across aggregation and join kernels. Rehash copies OwnedString handles and never clones or frees their bytes. If insertion fails after allocation, the most recent slice is rewound; an empty chunk may remain registered for reuse.

The registry reuses the three previously unused 8-byte scratch slots in HashTable: OwnedBlocks, OwnedBlockCount, and OwnedBlockCapacity at offsets 40, 48, and 56. The table ABI therefore remains 104 bytes.

Allocation must happen only after borrowed lookup reports a miss. A failure during allocation or insertion must leave the table logically unchanged and return an error.