Scan: Difference between revisions

From MemCP
Jump to navigation Jump to search
No edit summary
(Refresh MemCP documentation: accuracy, operational guidance, performance profile and maintained API reference)
Line 1: Line 1:
Scan is the most important function in whole MemCP. It implements an optimized, indexed and parallelized <code>for</code> loop over items in a table.
<!-- Copyright (C) 2026 Carl-Philip Haensch -->
<!-- SPDX-License-Identifier: GPL-3.0-or-later -->
= Scan =


It represents a data local access operation where each shard can run on a different CPU core fully exploiting cache locality inside the shard. The result of each shard-local scan is then combined to a global result.
<code>scan</code>, <code>scan_order</code>, <code>scan_order_multi</code>, <code>scan_exists</code>, and transaction-bound variants are physical storage operators emitted after logical planning. Their exact generated signatures are listed under [[Storage]].


There are two variants of scan: <code>scan</code> and <code>scan_order</code>.
The physical lowerer extracts safe equality, range, IN-list, LIKE-prefix, computed-expression, ordering, and RecSet constraints. A boundary may be exact or merely a candidate superset. Candidate boundaries always retain the original SQL predicate as a residual filter.


== Unordered parallel scan + reduce: (scan schema table filterColumns filter mapColumns map reduce neutral reduce2 isOuter) ==
Column values are read in batches through encoding-specific range or multi-record fast paths. Ordered scans can combine main-index and delta ordering, propagate early stop, and use offset/limit or top-k braking when semantics and cost allow. [[RecSets]] identify records for one base relation and visibility snapshot; they do not define join multiplicity or result order. Their adaptive ranges, positive-ID lists, and bitmaps let later scans reuse a narrow domain without materializing wide rows.
Help for: scan
===
does an unordered parallel filter-map-reduce pass on a single table and returns the reduced result
Allowed nø of parameters:  6 - 10
  - schema (string|nil): database where the table is located
  - table (string|list): name of the table to scan (or a list if you have temporary data)
  - filterColumns (list): list of columns that are fed into filter
  - filter (func): lambda function that decides whether a dataset is passed to the map phase. You can use any column of that table as lambda parameter. You should structure your lambda with an (and) at the root element. Every equal? < > <= >= will possibly translated to an indexed scan
  - mapColumns (list): list of columns that are fed into map
  - map (func): lambda function to extract data from the dataset. You can use any column of that table as lambda parameter. You can return a value you want to extract and pass to reduce, but you can also directly call insert, print or resultrow functions. If you declare a parameter named '$update', this variable will hold a function that you can use to delete or update a row. Call ($update) to delete the dataset, call ($update '("field1" value1 "field2" value2)) to update certain columns.
  - reduce (func): (optional) lambda function to aggregate the map results. It takes two parameters (a b) where a is the accumulator and b the new value. The accumulator for the first reduce call is the neutral element. The return value will be the accumulator input for the next reduce call. There are two reduce phases: shard-local and shard-collect. In the shard-local phase, a starts with neutral and b is fed with the return values of each map call. In the shard-collect phase, a starts with neutral and b is fed with the result of each shard-local pass.
  - neutral (any): (optional) neutral element for the reduce phase, otherwise nil is assumed
  - reduce2 (func): (optional) second stage reduce function that will apply a result of reduce to the neutral element/accumulator
  - isOuter (bool): (optional) if true, in case of no hits, call map once anyway with NULL values


=== Characteristics ===
Application code should use SQL. Planner contributors must keep scan objects, RecSets, ORC columns, and helper tables out of the parser and logical IR. See [[Query Planner and Physical Lowering]] and the repository's <code>INVARIANTS.md</code>.


* Filter phase is parallel and uses indexes
== Reading a plan ==
* Map phase is parallel
* 1st Reduce phase is parallel
* 2nd Reduce phase is sequential (but only collect as much items as there are shards at max)


=== Examples ===
For a query such as:
The following example prints all key-value pairs in tbl1(k, v):
(scan "schema" "tbl1" '() (lambda () true) '("k" "v") (lambda (k v) (print "tbl1[" k "] = " v)))
The following example finds a value for a key:
(scan "schema" "tbl1" '(k) (lambda (k) (equal?? k "12")) '("v") (lambda (v) (print "tbl1[12] = " v)))
The following example adds all values: in tbl2(weight)
(scan "schema" "tbl2" '() (lambda () true) '("weight") + 0)
/* equivalent to: */ (scan "schema" "tbl2" '() (lambda () true) '("weight") (lambda (a b) (+ a b)) 0)


== Ordered scan+reduce: (scan_order schema table filterColumn filter sortcols sortdirs offset limit mapColumns map reduce neutral isOuter) ==
<syntaxhighlight lang="sql">
Help for: scan_order
SELECT customer_id, SUM(total)
===
FROM orders
WHERE created_at >= '2026-01-01'
does an ordered parallel filter and serial map-reduce pass on a single table and returns the reduced result
GROUP BY customer_id
ORDER BY SUM(total) DESC
Allowed nø of parameters:  10 - 13
LIMIT 20;
</syntaxhighlight>
  - schema (string): database where the table is located
  - table (string): name of the table to scan
  - filterColumns (list): list of columns that are fed into filter
  - filter (func): lambda function that decides whether a dataset is passed to the map phase. You can use any column of that table as lambda parameter. You should structure your lambda with an (and) at the root element. Every equal? < > <= >= will possibly translated to an indexed scan
  - sortcols (list): list of columns to sort. Each column is either a string to point to an existing column or a func(cols...)->any to compute a sortable value
  - sortdirs (list): list of column directions to sort. Must be same length as sortcols. false means ASC, true means DESC
  - offset (number): number of items to skip before the first one is fed into map
  - limit (number): max number of items to read
  - mapColumns (list): list of columns that are fed into map
  - map (func): lambda function to extract data from the dataset. You can use any column of that table as lambda parameter. You can return a value you want to extract and pass to reduce, but you can also directly call insert, print or resultrow functions. If you declare a parameter named '$update', this variable will hold a function that you can use to delete or update a row. Call ($update) to delete the dataset, call ($update '("field1" value1 "field2" value2)) to update certain columns.
  - reduce (func): (optional) lambda function to aggregate the map results. It takes two parameters (a b) where a is the accumulator and b the new value. The accumulator for the first reduce call is the neutral element. The return value will be the accumulator input for the next reduce call. There are two reduce phases: shard-local and shard-collect. In the shard-local phase, a starts with neutral and b is fed with the return values of each map call. In the shard-collect phase, a starts with neutral and b is fed with the result of each shard-local pass.
  - neutral (any): (optional) neutral element for the reduce phase, otherwise nil is assumed
  - isOuter (bool): (optional) if true, in case of no hits, call map once anyway with NULL values


=== Characteristics ===
the logical plan establishes filtering, grouping, ordering, and LIMIT semantics. Physical lowering can then choose a bounded date range, read only <code>created_at</code>, <code>customer_id</code>, and <code>total</code>, fuse filter/aggregation, and apply top-k braking. Use <code>EXPLAIN PHYSICAL</code> to see what was actually selected; SQL spelling alone does not force an index or RecSet.


* Filter phase is parallel and uses indexes
== Low-level callback contract ==
* Sort phase is parallel
* Map and Reduce are executed sequentially
* Map and Reduce can be pruned by <code>offset</code> and <code>limit</code>


=== Examples ===
Unordered scans can perform shard-local map/reduce work and combine partial accumulators with a second reducer. Ordered scans retain serial output order and own OFFSET/LIMIT/early stop. Update-capable callbacks receive a controlled row-update handle under the scan's transaction and locking rules. The generated [[Storage]] chapter is authoritative for parameter names and return types at the referenced commit.
Print all items from tbl3(id, weight) ordered by <code>weight DESC</code>
 
(scan "schema" "tbl3" '() (lambda () true) '("weight") '(true) 0 -1 '("id" "weight") (lambda (id weight) (print id "," weight)))
{| class="wikitable"
! Stage !! Unordered <code>scan</code> !! Ordered <code>scan_order</code>
|-
| Filter/access path || Parallel per eligible shard; may use indexes/boundaries || Parallel candidate filtering and local ordering where useful
|-
| Map || Parallel per shard || Applied in requested global order
|-
| Reduce || Shard-local partial reductions plus a final combine || Serial in output order when order affects semantics
|-
| Early stop || Cancellation or consumer stop || OFFSET/LIMIT and compatible ordered braking
|}
 
== Scheme examples ==
 
These examples illustrate the callback roles; use the exact current signatures from [[Storage]] when writing low-level code.
 
<syntaxhighlight lang="scheme">
/* resolve the current transaction and table once */
(set tx ((context "session") "__memcp_tx"))
(set tbl1 (table "schema" "tbl1"))
(set tbl2 (table "schema" "tbl2"))
 
/* print key/value pairs */
(scan tx tbl1 '() (lambda () true)
'("k" "v") (lambda (k v) (print "tbl1[" k "] = " v)))
 
/* find a key through an indexable equality predicate */
(scan tx tbl1 '("k") (lambda (k) (equal? k 12))
'("v") (lambda (v) v))
 
/* shard-local sum with neutral value */
(scan tx tbl2 '() (lambda () true)
'("weight") (lambda (weight) weight) + 0)
</syntaxhighlight>
 
An ordered scan additionally receives sort expressions/directions, OFFSET and LIMIT. Filtering and local ordering may run in parallel, but output order and order-sensitive reduction remain serial. Do not use side effects as a substitute for a reducer when result order matters. See [[RecSets]] for ordered membership intersection and progressively filtered candidate batches.

Revision as of 11:59, 28 August 2026

Scan

scan, scan_order, scan_order_multi, scan_exists, and transaction-bound variants are physical storage operators emitted after logical planning. Their exact generated signatures are listed under Storage.

The physical lowerer extracts safe equality, range, IN-list, LIKE-prefix, computed-expression, ordering, and RecSet constraints. A boundary may be exact or merely a candidate superset. Candidate boundaries always retain the original SQL predicate as a residual filter.

Column values are read in batches through encoding-specific range or multi-record fast paths. Ordered scans can combine main-index and delta ordering, propagate early stop, and use offset/limit or top-k braking when semantics and cost allow. RecSets identify records for one base relation and visibility snapshot; they do not define join multiplicity or result order. Their adaptive ranges, positive-ID lists, and bitmaps let later scans reuse a narrow domain without materializing wide rows.

Application code should use SQL. Planner contributors must keep scan objects, RecSets, ORC columns, and helper tables out of the parser and logical IR. See Query Planner and Physical Lowering and the repository's INVARIANTS.md.

Reading a plan

For a query such as:

<syntaxhighlight lang="sql"> SELECT customer_id, SUM(total) FROM orders WHERE created_at >= '2026-01-01' GROUP BY customer_id ORDER BY SUM(total) DESC LIMIT 20; </syntaxhighlight>

the logical plan establishes filtering, grouping, ordering, and LIMIT semantics. Physical lowering can then choose a bounded date range, read only created_at, customer_id, and total, fuse filter/aggregation, and apply top-k braking. Use EXPLAIN PHYSICAL to see what was actually selected; SQL spelling alone does not force an index or RecSet.

Low-level callback contract

Unordered scans can perform shard-local map/reduce work and combine partial accumulators with a second reducer. Ordered scans retain serial output order and own OFFSET/LIMIT/early stop. Update-capable callbacks receive a controlled row-update handle under the scan's transaction and locking rules. The generated Storage chapter is authoritative for parameter names and return types at the referenced commit.

Stage Unordered scan Ordered scan_order
Filter/access path Parallel per eligible shard; may use indexes/boundaries Parallel candidate filtering and local ordering where useful
Map Parallel per shard Applied in requested global order
Reduce Shard-local partial reductions plus a final combine Serial in output order when order affects semantics
Early stop Cancellation or consumer stop OFFSET/LIMIT and compatible ordered braking

Scheme examples

These examples illustrate the callback roles; use the exact current signatures from Storage when writing low-level code.

<syntaxhighlight lang="scheme"> /* resolve the current transaction and table once */ (set tx ((context "session") "__memcp_tx")) (set tbl1 (table "schema" "tbl1")) (set tbl2 (table "schema" "tbl2"))

/* print key/value pairs */ (scan tx tbl1 '() (lambda () true) '("k" "v") (lambda (k v) (print "tbl1[" k "] = " v)))

/* find a key through an indexable equality predicate */ (scan tx tbl1 '("k") (lambda (k) (equal? k 12)) '("v") (lambda (v) v))

/* shard-local sum with neutral value */ (scan tx tbl2 '() (lambda () true) '("weight") (lambda (weight) weight) + 0) </syntaxhighlight>

An ordered scan additionally receives sort expressions/directions, OFFSET and LIMIT. Filtering and local ordering may run in parallel, but output order and order-sensitive reduction remain serial. Do not use side effects as a substitute for a reducer when result order matters. See RecSets for ordered membership intersection and progressively filtered candidate batches.

Retrieved from "https://www.memcp.org/index.php?title=Scan&oldid=354"