RecSets - Revision history

Wikiservice: Refresh MemCP documentation: accuracy, operational guidance, performance profile and maintained API reference

2026-08-28T10:13:52Z

Refresh MemCP documentation: accuracy, operational guidance, performance profile and maintained API reference

← Older revision		Revision as of 12:13, 28 August 2026
Line 21:		Line 21:
	The essential implementation is deliberately small:		The essential implementation is deliberately small:

	<~~syntaxhighlight lang="go"~~>		<pre>
	type recSet struct {		type recSet struct {
	tx *TxContext		tx *TxContext
Line 37:		Line 37:
	count int64		count int64
	}		}
	</~~syntaxhighlight~~>		</pre>

	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.		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.
Line 81:		Line 81:
	This keeps late materialization intact. Creating <code>WHERE tenant_id = 7 AND state = 'open'</code> 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.		This keeps late materialization intact. Creating <code>WHERE tenant_id = 7 AND state = 'open'</code> 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.

	<~~syntaxhighlight lang="scheme"~~>		<pre>
	(begin		(begin
	(define tx ((context "session") "__memcp_tx"))		(define tx ((context "session") "__memcp_tx"))
Line 91:		Line 91:
	(and (equal? tenant 7) (equal? state "open")))))		(and (equal? tenant 7) (equal? state "open")))))
	(recset_count open_orders))		(recset_count open_orders))
	</~~syntaxhighlight~~>		</pre>

	The low-level example illustrates the operator contract. SQL users should normally write the predicate in SQL and inspect the optimizer's decision with <code>EXPLAIN PHYSICAL</code>.		The low-level example illustrates the operator contract. SQL users should normally write the predicate in SQL and inspect the optimizer's decision with <code>EXPLAIN PHYSICAL</code>.
Line 99:		Line 99:
	Passing a RecSet as the input of <code>scan_recset</code> adds another condition without revisiting rows outside the existing membership:		Passing a RecSet as the input of <code>scan_recset</code> adds another condition without revisiting rows outside the existing membership:

	<~~syntaxhighlight lang="scheme"~~>		<pre>
	(define recent_open		(define recent_open
	(scan_recset tx open_orders		(scan_recset tx open_orders
	'("created_at")		'("created_at")
	(lambda (created_at) (>= created_at cutoff))))		(lambda (created_at) (>= created_at cutoff))))
	</~~syntaxhighlight~~>		</pre>

	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.		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.
Line 114:		Line 114:
	The pseudo-column <code>$recset_contains</code> supplies a closure bound to the current row. It tests one or more same-table RecSets without exposing physical record IDs:		The pseudo-column <code>$recset_contains</code> supplies a closure bound to the current row. It tests one or more same-table RecSets without exposing physical record IDs:

	<~~syntaxhighlight lang="scheme"~~>		<pre>
	(scan tx orders		(scan tx orders
	'("$recset_contains" "total")		'("$recset_contains" "total")
Line 123:		Line 123:
	(lambda (sum id) (+ sum id))		(lambda (sum id) (+ sum id))
	0)		0)
	</~~syntaxhighlight~~>		</pre>

	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 <code>$recset_contains</code> parameters are supported when a filter needs independent sets.		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 <code>$recset_contains</code> parameters are supported when a filter needs independent sets.
Line 129:		Line 129:
	== Set algebra, in parallel ==		== Set algebra, in parallel ==

	<~~syntaxhighlight lang="scheme"~~>		<pre>
	(define visible (recset_intersect (list tenant_rows active_rows)))		(define visible (recset_intersect (list tenant_rows active_rows)))
	(define either (recset_union (list starred_rows recent_rows)))		(define either (recset_union (list starred_rows recent_rows)))
	(define allowed (recset_difference (list visible blocked_rows muted_rows)))		(define allowed (recset_difference (list visible blocked_rows muted_rows)))
	(define other_visible_rows (recset_not visible))		(define other_visible_rows (recset_not visible))
	</~~syntaxhighlight~~>		</pre>

	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.		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.
Line 146:		Line 146:
	<code>recset_project_join</code> 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:		<code>recset_project_join</code> 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:

	<~~syntaxhighlight lang="scheme"~~>		<pre>
	(define permitted_links		(define permitted_links
	(scan_recset tx access_links		(scan_recset tx access_links
Line 164:		Line 164:
	(lambda (rows row) (append rows (list row)))		(lambda (rows row) (append rows (list row)))
	'() false)		'() false)
	</~~syntaxhighlight~~>		</pre>

	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.		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.
Line 172:		Line 172:
	For repeated scalar membership checks, <code>recset_key_index</code> builds an immutable lookup closure over one or more columns:		For repeated scalar membership checks, <code>recset_key_index</code> builds an immutable lookup closure over one or more columns:

	<~~syntaxhighlight lang="scheme"~~>		<pre>
	(define contains_document		(define contains_document
	(recset_key_index tx permitted_documents '("id")))		(recset_key_index tx permitted_documents '("id")))

	(contains_document 12345)		(contains_document 12345)
	</~~syntaxhighlight~~>		</pre>

	== Ordering, LIMIT, and adaptive batches ==		== Ordering, LIMIT, and adaptive batches ==
Line 215:		Line 215:
	Use these views when investigating a plan:		Use these views when investigating a plan:

	<~~syntaxhighlight lang="sql"~~>		<pre>
	EXPLAIN IR SELECT ...;		EXPLAIN IR SELECT ...;
	EXPLAIN REORDER SELECT ...;		EXPLAIN REORDER SELECT ...;
	EXPLAIN PHYSICAL SELECT ...;		EXPLAIN PHYSICAL SELECT ...;
	</~~syntaxhighlight~~>		</pre>

	<code>EXPLAIN PHYSICAL</code> 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.		<code>EXPLAIN PHYSICAL</code> 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.

Wikiservice: Refresh MemCP documentation: accuracy, operational guidance, performance profile and maintained API reference

2026-08-28T09:59:20Z

Refresh MemCP documentation: accuracy, operational guidance, performance profile and maintained API reference

New page

= RecSets: compact, parallel record-set processing =

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

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: <code>scan</code>, <code>scan_batch</code>, <code>scan_order</code>, <code>scan_order_multi</code>, and <code>scan_exists</code> 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:

<syntaxhighlight lang="go">
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
}
</syntaxhighlight>

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:

{| class="wikitable"
! Representation !! Layout !! Best fit !! Membership and combination
|-
| Ranges || Sorted <code>(base, count)</code> pairs || Long runs, full/empty shards, or a nearly full set with a few holes || Range lookup; linear range sweeps
|-
| Positive IDs || Sorted, deduplicated <code>uint32</code> 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 ==

<code>scan_recset</code> uses the normal MemCP scan machinery rather than walking every row blindly:

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

This keeps late materialization intact. Creating <code>WHERE tenant_id = 7 AND state = 'open'</code> 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.

<syntaxhighlight lang="scheme">
(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))
</syntaxhighlight>

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

=== Narrowing an existing RecSet ===

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

<syntaxhighlight lang="scheme">
(define recent_open
(scan_recset tx open_orders
'("created_at")
(lambda (created_at) (>= created_at cutoff))))
</syntaxhighlight>

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 <code>GetValueRange</code>; 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 <code>$recset_contains</code> supplies a closure bound to the current row. It tests one or more same-table RecSets without exposing physical record IDs:

<syntaxhighlight lang="scheme">
(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)
</syntaxhighlight>

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 <code>$recset_contains</code> parameters are supported when a filter needs independent sets.

== Set algebra, in parallel ==

<syntaxhighlight lang="scheme">
(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))
</syntaxhighlight>

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.

<code>recset_not</code> 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 <code>NOT predicate</code> when NULL/UNKNOWN is possible.

== Projecting membership through a join ==

<code>recset_project_join</code> 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:

<syntaxhighlight lang="scheme">
(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)
</syntaxhighlight>

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, <code>recset_key_index</code> builds an immutable lookup closure over one or more columns:

<syntaxhighlight lang="scheme">
(define contains_document
(recset_key_index tx permitted_documents '("id")))

(contains_document 12345)
</syntaxhighlight>

== Ordering, LIMIT, and adaptive batches ==

A RecSet itself is unordered. <code>scan_order</code> 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. <code>EXPLAIN PHYSICAL</code> can report the adaptive RecSet boundary and runtime alternatives such as <code>ordered_inverse_recset</code> and <code>ordered_base_membership</code>.

For an ORDER BY/LIMIT query whose expensive acceptance condition lives on another relation, <code>scan_order_batch_accept</code> preserves order without evaluating the whole candidate domain. It draws an initial ordered RecSet of <code>OFFSET + LIMIT</code> 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:

{| class="wikitable"
! 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 <code>IN</code>/<code>NOT IN</code> and general three-valued logic are handled before truth-only Boolean set identities are applied.

Use these views when investigating a plan:

<syntaxhighlight lang="sql">
EXPLAIN IR SELECT ...;
EXPLAIN REORDER SELECT ...;
EXPLAIN PHYSICAL SELECT ...;
</syntaxhighlight>

<code>EXPLAIN PHYSICAL</code> 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 <code>$update</code> 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 <code>scan_order</code>; include a unique tie-breaker when stable pagination matters.

== Low-level operator map ==

{| class="wikitable"
! Operator !! Purpose
|-
| <code>scan_recset</code> || Build from a table or narrow an existing RecSet.
|-
| <code>recset_count</code> || Return stored membership cardinality.
|-
| <code>recset_union</code> / <code>recset_intersect</code> || Combine same-table memberships.
|-
| <code>recset_difference</code> / <code>recset_not</code> || Subtract sets or complement against visible rows.
|-
| <code>recset_project_join</code> || Project distinct keys into a target-table RecSet.
|-
| <code>recset_key_index</code> || Build an immutable scalar/composite-key membership closure.
|-
| <code>$recset_contains</code> || Test current-row membership inside a scan predicate.
|-
| <code>scan_order_batch_accept</code> || 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]].