RecSets

RecSets: compact, parallel record-set processing

Verified against commit c42e19eba on 27 August 2026. RecSets are an internal physical execution mechanism. Applications normally use SQL and let the optimizer choose them.

A RecSet is a query-local subset of one MemCP table. Instead of materializing complete rows, it records the physical record IDs that currently qualify. The result remains table-shaped: scan, scan_batch, scan_order, scan_order_multi, and scan_exists can consume it as a source while retaining columnar reads, indexes, transaction visibility, and parallel shard execution.

This separation is valuable on large relations. A cheap predicate can identify a narrow working set once; expensive residual predicates, correlated access checks, joins, projections, ordering, and aggregation then operate only on those candidates. Millions of base rows need not become millions of Scheme lists or wide temporary rows.

What a RecSet represents

A RecSet contains membership, not result rows:

• it belongs to exactly one base table and one transaction/visibility context;
• it has set semantics: no duplicates and no join multiplicity;
• it carries no result order;
• it is query-local and is neither persisted nor a stable public record-ID format;
• it can be an exact set of TRUE rows or a safe candidate superset followed by a residual predicate.

The essential implementation is deliberately small:

type recSet struct {
	tx     *TxContext
	table  *table
	shards []recSetShard
	count  int64
}

type recSetShard struct {
	shard    *storageShard
	kind     recSetRepresentation
	universe uint32
	data     []uint32
	used     uint32
	count    int64
}

Each shard owns its own record-ID universe. This mirrors MemCP's storage layout and makes construction and set algebra naturally parallel without sharing a global bitmap or exposing record IDs across shards.

Adaptive representation

One fixed representation would waste memory for either sparse or dense sets. Every RecSet shard therefore chooses among three forms:

Representation	Layout	Best fit	Membership and combination
Ranges	Sorted (base, count) pairs	Long runs, full/empty shards, or a nearly full set with a few holes	Range lookup; linear range sweeps
Positive IDs	Sorted, deduplicated uint32 record IDs	A small, scattered result	Sorted membership lookup; linear list merge/intersection
Bitmap	One bit per record-ID position	Dense or highly fragmented membership	Direct bit test and word-wise Boolean operations

There is intentionally no separate “full”, “empty”, or negative representation. An empty shard is zero ranges; a full shard is one range; “everything except a few holes” is a small number of ranges. A fragmented set eventually becomes a bitmap.

For orientation, an uncompressed bitmap for a one-million-position shard needs approximately 125 kB. A positive-ID result uses four bytes per hit before slice overhead, and a range uses eight bytes per run. The builder chooses according to the observed shape rather than a SQL selectivity guess. Immutable search-index RecSets have an additional compressed form: their positive IDs and ranges can themselves use MemCP's packed integer storage, and their small interface can intersect a mutable query-local RecSet in place.

One-pass adaptive construction

The builder starts with ranges. More than three isolated singleton runs indicate sparse, non-clustered data and trigger conversion to a positive list. If the compact representation exceeds the bitmap budget, it escalates to a bitmap.

The filter predicate is evaluated exactly once per candidate record ID. A representation change copies already collected IDs or ranges; it never repeats the scan or replays Scheme predicates. This matters because a predicate may include decoded column values, JIT/interpreter work, search-index checks, or an expensive correlated condition. After construction, range and positive results are copied into right-sized slices so a small result does not keep the worst-case bitmap allocation alive.

Ranges are also split at the immutable-main/delta boundary. Consumers can then bulk-read a main-storage run without accidentally spanning into transaction deltas.

Building a RecSet in the scan/filter path

scan_recset uses the normal MemCP scan machinery rather than walking every row blindly:

1. extract equality, range, LIKE/search, computed, and RecSet boundaries from the filter;
2. order useful boundaries and derive index limits;
3. schedule eligible shards in parallel;
4. prepare only the columns named by the filter and optimize its Scheme procedure;
5. read index candidates in batches of up to 1,024 record IDs;
6. apply transaction/deletion visibility and the residual predicate once;
7. feed qualifying IDs to the adaptive shard builder.

This keeps late materialization intact. Creating WHERE tenant_id = 7 AND state = 'open' as a RecSet needs the filter columns, but it does not have to decode payload, JSON, or text columns that are only required by a later projection.

(begin
	(define tx ((context "session") "__memcp_tx"))
	(define orders (table "shop" "orders"))
	(define open_orders
		(scan_recset tx orders
			'("tenant_id" "state")
			(lambda (tenant state)
				(and (equal? tenant 7) (equal? state "open")))))
	(recset_count open_orders))

The low-level example illustrates the operator contract. SQL users should normally write the predicate in SQL and inspect the optimizer's decision with EXPLAIN PHYSICAL.

Narrowing an existing RecSet

Passing a RecSet as the input of scan_recset adds another condition without revisiting rows outside the existing membership:

(define recent_open
	(scan_recset tx open_orders
		'("created_at")
		(lambda (created_at) (>= created_at cutoff))))

For a very sparse input, MemCP walks its IDs directly. For a broader input, it combines the exact RecSet boundary with other index/search boundaries before reading residual columns. This is the intended pattern for “cheap selective predicate first, expensive predicate second”, including ACL or search conditions with their own subscans.

When scanning a RecSet, consecutive visible main-storage IDs are coalesced into runs. Each required column is fetched for the whole run with GetValueRange; visibility remains row-specific, while column decoding becomes batched and cache-friendly. Delta rows use their transaction-aware delta path.

Membership inside another scan

The pseudo-column $recset_contains supplies a closure bound to the current row. It tests one or more same-table RecSets without exposing physical record IDs:

(scan tx orders
	'("$recset_contains" "total")
	(lambda (contains total)
		(and (contains open_orders) (> total 1000)))
	'("id")
	(lambda (id) id)
	(lambda (sum id) (+ sum id))
	0)

The closure caches the current RecSet and its shard entry, avoiding a repeated shard search for successive membership calls. If an exact RecSet boundary already proves the membership condition, the scan can provide an always-true closure instead of probing it again. Multiple $recset_contains parameters are supported when a filter needs independent sets.

Set algebra, in parallel

(define visible (recset_intersect (list tenant_rows active_rows)))
(define either  (recset_union (list starred_rows recent_rows)))
(define allowed (recset_difference (list visible blocked_rows muted_rows)))
(define other_visible_rows (recset_not visible))

Union, intersection, and difference require operands from the same table. Sorted range/list invariants allow linear two-pointer or N-way sweeps; bitmap pairs use word operations. Mixed representation pairs have specialized implementations instead of expanding everything into one common row list.

Each shard combination is independent and runs through MemCP's bounded fan-out scheduler. Results are sorted back into deterministic shard order after parallel completion. This lets Boolean work over millions of record positions use available cores while keeping synchronization out of the inner membership loop.

recset_not deserves special attention: it constructs the currently visible table universe and subtracts the input. It does not merely invert raw bits, because that could resurrect deleted rows or rows invisible to the transaction. At SQL level, a RecSet complement is also not automatically equivalent to NOT predicate when NULL/UNKNOWN is possible.

Projecting membership through a join

recset_project_join reads distinct source keys from one RecSet and creates a RecSet over matching rows of another table. This is useful for EXISTS/IN carriers, ACL links, tags, and search-result relations:

(define permitted_links
	(scan_recset tx access_links
		'("user_id")
		(lambda (user_id) (equal? user_id current_user))))

(define permitted_documents
	(recset_project_join tx permitted_links
		'("document_id") documents '("id")))

(scan_order tx permitted_documents
	'() (lambda () true)
	'("created_at" "id") '(< <)
	0 0 50
	'("id" "title")
	(lambda (id title) (list id title))
	(lambda (rows row) (append rows (list row)))
	'() false)

Composite source/target keys are supported. At execution time the operator knows the actual number of distinct source keys and target rows per shard. It chooses between indexed point probes and a dense target scan. A single integral key can use an O(1) hash membership test during the dense scan; generic composite keys use sorted tuples and binary lookup.

The current cost constants were calibrated with production-shaped A/B fixtures. One recorded case projected about 80,000 integral keys through 1.84 million target rows in roughly 8 ms on the calibration machine, while another case with 105 keys and 22 indexed target shards favored point probes. These are decision-model observations, not portable latency guarantees; hardware, encodings, shard layout, visibility state, and surrounding query work matter.

For repeated scalar membership checks, recset_key_index builds an immutable lookup closure over one or more columns:

(define contains_document
	(recset_key_index tx permitted_documents '("id")))

(contains_document 12345)

Ordering, LIMIT, and adaptive batches

A RecSet itself is unordered. scan_order applies an index/order from the base table and intersects it with RecSet membership. Depending on cardinality, index span, and LIMIT, the execution kernel can:

• drive the base ordered index and test RecSet membership;
• translate sparse RecSet IDs into ordered index positions and sort those positions;
• iterate the RecSet directly when no useful ordering is required.

The crossover is calibrated by a benchmark with 800,000 rows, RecSet cardinalities from 16 to 720,000, bounded and unbounded scans, and both distributed and adversarial late hits. EXPLAIN PHYSICAL can report the adaptive RecSet boundary and runtime alternatives such as ordered_inverse_recset and ordered_base_membership.

For an ORDER BY/LIMIT query whose expensive acceptance condition lives on another relation, scan_order_batch_accept preserves order without evaluating the whole candidate domain. It draws an initial ordered RecSet of OFFSET + LIMIT candidates, asks a batch function to return an exact accepted subset, and doubles subsequent disjoint batches until enough rows are accepted or the source is exhausted. The accepted RecSet is used as a mask against the already ordered vector, so it is not rescanned in physical-ID order.

This is especially useful for ordered document/search/ACL queries: project a candidate batch to the access relation, filter it in parallel, project accepted membership back, and stop once the requested page is complete.

How the optimizer uses RecSets

RecSets appear only during physical lowering. The logical planner first establishes joins, domains, SQL truth semantics, grouping, ordering, and multiplicity. The physical cost model can then compare:

Choice	Often attractive when
Direct indexed probe	The driving side is small and each lookup is selective.
RecSet carrier	A filtered domain is reused, projected, combined, or much narrower than the base relation.
Prepared key/group table	Keys or aggregate results need relational reuse and more than membership.
Dense fused scan	Most rows are visited once and building a reusable carrier would add work.
Ordered RecSet iterator	An existing membership domain must be consumed in base-table order or with a small LIMIT.

Candidate RecSets do not permit the optimizer to drop correctness checks. Approximate LIKE/full-text boundaries and other safe supersets retain their residual SQL predicate. Nullable IN/NOT IN and general three-valued logic are handled before truth-only Boolean set identities are applied.

Use these views when investigating a plan:

EXPLAIN IR SELECT ...;
EXPLAIN REORDER SELECT ...;
EXPLAIN PHYSICAL SELECT ...;

EXPLAIN PHYSICAL exposes membership-carrier choices and runtime access alternatives for projected and ordered RecSets. A remaining roadmap item is richer tracing for why the same RecSet domain was built or reused and for the exact ordered-iterator mode chosen at runtime.

Operational and correctness limits

• Do not retain a RecSet as application state or persist its physical IDs.
• Algebra operands must refer to the same table; projected joins deliberately return a new target-table RecSet.
• A RecSet is tied to its transaction/visibility context. Batch-accept callbacks must return a same-table, same-transaction subset.
• Scanning a RecSet for reads is supported; mutation callbacks such as $update are rejected on a RecSet source.
• Cancellation is checked before shard work is scheduled. Once entered, one shard's RecSet build runs atomically.
• Set cardinality is not SQL row cardinality after a one-to-many join, and membership does not retain duplicate keys.
• Ordered output needs scan_order; include a unique tie-breaker when stable pagination matters.

Low-level operator map

Operator	Purpose
scan_recset	Build from a table or narrow an existing RecSet.
recset_count	Return stored membership cardinality.
recset_union / recset_intersect	Combine same-table memberships.
recset_difference / recset_not	Subtract sets or complement against visible rows.
recset_project_join	Project distinct keys into a target-table RecSet.
recset_key_index	Build an immutable scalar/composite-key membership closure.
$recset_contains	Test current-row membership inside a scan predicate.
scan_order_batch_accept	Filter progressively larger ordered candidate RecSets before LIMIT.

The generated Storage reference is authoritative for exact signatures. For the surrounding execution architecture see Scan, Query Planner and Physical Lowering, Columnar Storage, Data Auto Sharding and Auto Indexing, and Parallel Computing.