asap-executor: a columnar physical operator library (state columns, per-sample updaters) for runtimes executing the DAG #762

Problem, by example

ASAPQuery-backend executes ASAPPlanner's installed DAG with asap-executor's operators. The test case is the planner-layering PromQL examples on 2,000 series (90 minutes, 15 s samples), on a release build with perf sampling. The data plane spent 53 CPU core-seconds, and the sketch kernels were only 3–7% of that. The rest comes from the executor's row layout: a Batch is Vec<Vec<Value>>, one Vec<Value> per row.

The same work in ASAPQuery's engine, single core, same data:

The data plane must execute the DAG node by node for every query shape. No shape-matched fast path beside it is allowed. So the operators themselves must get cheaper.

Proposal: asap-executor becomes a columnar physical operator library

ASAPPlanner provides the physical operator library: one implementation per plan-node kind. The runtime's execution engine walks the DAG and calls those operators. The library also keeps a minimal single-threaded DAG runner, for the Planner's own tests and for InstallablePlan::query_time_reference.

Batch format. A batch is a set of equal-length columns plus a selection vector; a filter marks rows instead of copying them.

Batches hold up to a fixed row limit (e.g. 8,192), so memory accounting and validation are paid per batch.

State columns: how sketches are columnar. One state per group, contiguous. All states in a column share one family and one parameter set, taken from the plan.

• Exact accumulators (sum, count, min, max, last) are plain numeric columns.
• Fixed-size sketches (Count-Min, Count Sketch, HLL registers) can share one flat groups × size buffer. Merge is element-wise.
• Variable-size sketches (KLL, DDSketch, top-k heaps, UnivMon) keep one asap_sketchlib object per group, without the per-row Value wrapper.
• Stored panes are immutable Arc<StateBatch>, read by reference.

Operators. Every physical operator kind gets a columnar implementation:

A node's output is computed once per evaluation and shared through Arc.

Per-sample updaters. A public API updates one open pane's state with one sample: (family, params) → updater, with update(group, value), merge and seal. It is the same code SummaryAgg uses on a batch, so a runtime's per-sample ingestion builds byte-identical state.

Thread safety. Batches and state columns are Send + Sync, so a runtime can share stored panes across query threads.

Scope and acceptance

• Land it operator by operator. All existing executor tests, and the integration tests that execute plans, pass unchanged.
• A parity test checks each per-sample updater against the batch SummaryAgg for every summary family.
• Measured on the ASAPQuery-backend benefit harness, release build, absolute numbers:
  • pane construction approaches 2.3 µs/sample;
  • stored-state queries approach 4.1 / 24.8 / 33.5 ms on the same data;
  • the row-layout share of data-plane CPU drops well below the measured 68%.
• Out of scope: the runtime's scheduling, threads and SDS. Those live in ASAPQuery-backend.

Related

ASAPQuery-backend design-doc PR #826, sections "Execution engine: a columnar DAG executor" and "Overhead of the data plane, compared with ASAPQuery". #761 (Stage 3 cost terms for scans, per-row work and merges), #755 (installable plan and RawSampleSelector).