Scan: Difference between revisions

From MemCP
Jump to navigation Jump to search
(Created page with "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. There are two variants of scan: <code>scan</code> and <code>scan_order</code>. == (scan schema table filterColumns filter mapColumns map reduce neutral reduce2 isOuter) == Help for: scan === does an unordered parallel filter-map-reduce pass on a single table and returns the reduced result Allowed nø of parameters...")
 
(Refresh MemCP documentation: accuracy, operational guidance, performance profile and maintained API reference)
 
(4 intermediate revisions by 2 users not shown)
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 =


There are two variants of scan: <code>scan</code> and <code>scan_order</code>.
<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]].


== (scan schema table filterColumns filter mapColumns map reduce neutral reduce2 isOuter) ==
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.
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


== (scan_order schema table filterColumn filter sortcols sortdirs offset limit mapColumns map reduce neutral 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_order
 
===
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>.
 
does an ordered parallel filter and serial map-reduce pass on a single table and returns the reduced result
== Reading a plan ==
 
Allowed nø of parameters:  10 - 13
For a query such as:
 
  - schema (string): database where the table is located
<pre>
  - table (string): name of the table to scan
SELECT customer_id, SUM(total)
  - filterColumns (list): list of columns that are fed into filter
FROM orders
  - 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
WHERE created_at >= '2026-01-01'
  - 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
GROUP BY customer_id
  - sortdirs (list): list of column directions to sort. Must be same length as sortcols. false means ASC, true means DESC
ORDER BY SUM(total) DESC
  - offset (number): number of items to skip before the first one is fed into map
LIMIT 20;
  - limit (number): max number of items to read
</pre>
  - 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.
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.
  - 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
== Low-level callback contract ==
  - isOuter (bool): (optional) if true, in case of no hits, call map once anyway with NULL values
 
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.
 
{| 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.
 
<pre>
/* 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)
</pre>
 
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.

Latest revision as of 12:14, 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: 

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

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. 

/* 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)

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=401"