Expand description
Incremental view maintenance (packages/zql/src/ivm): the operators a
query’s pipeline is built from, the memory source they read, and the view
that materializes their output.
A pipeline is a graph of reference-counted operators on one thread. Each
operator holds its inputs strongly and its outputs weakly, so the view at
the end of a pipeline owns it; a push that reaches a released output is
dropped. Operators take &self and keep their state in cells, borrowed
only between calls to other operators: a push can fetch back through the
operator that pushed it.
Fetches are lazy streams, like JS’s generators: a fetch reads operator and source state when its first row is pulled, not when it is created.
Structs§
- Aggregate
- Reduces the rows of a relationship per parent, or of a whole query, to
an aggregate: one row per group key,
{...groupKey, _0_value}, so aJoinroutes it as it would the child rows. - Array
View - A materialized view of a pipeline’s output (
array-view.ts). - Cap
- A count-based limit for EXISTS subqueries that needs no order: it tracks
membership by primary key (
cap.ts). - Child
Change - A change to a child relationship of a node.
- Closure
Output - Routes an input’s pushes to closures, as JS operators do with object literals. The operator owns it: inputs hold their outputs weakly.
- Constraint
- Keys keep insertion order, like the JS object: a memory source builds its
index sort from it. A value is
Nonewhere JS hasundefined. - Deferred
Input - A placeholder input for a view whose pipeline is not built yet.
- Exists
- Filters on whether a relationship is non-empty (
exists.ts). - Exists
Join - Set when a join feeds an EXISTS or NOT EXISTS condition (
ExistsJoininjoin.ts). Its parent index is kept by aJoinIndexTapat the end of the pipeline. - FanIn
- Merges the branches of an OR, removing duplicates (
fan-in.ts). - FanOut
- Forks the
wheresub-graph for an OR (fan-out.ts). - Fetch
Request FetchRequestinoperator.ts.- Filter
- Filters through a pure predicate (
filter.ts). - Filter
End - Adapts the end of the
wheresub-graph back to anInput. - Filter
Start - Adapts an
Inputto thewheresub-graph (filter-operators.ts). - Flipped
Join - An inner join that fetches children first, then their parents. Outputs parents, in parent order, that have at least one related child.
- Flipped
Join Args - What
FlippedJoin::newjoins, and how. - GroupBy
- Groups its input by columns and reduces each group, as
GROUP BYdoes: one row per combination of the columns’ values,{...columns, _0_key, _0_value}, with a sum or average’s components. A distinct is a GroupBy with a count, whose value a view doesn’t show. - Group
Projection - Turns the rows of a
GroupBy, or of the source a synced client reads them from, into the rows a view shows: the group columns under the query’s names and, for agroupBy()with an aggregate, its value undervalue_name(count,sum, …). Adistinct()shows no value, so an edit, which only moves its count, doesn’t reach the view. - Join
- Joins a parent and a child input into hierarchical output: each parent
node gets a relationship streaming its children (
join.ts). - Join
Args - What
Join::newjoins, and how. - Join
Index - An index from join key to the parent rows that have it.
JoinandFlippedJoinskip the parent fetch of a child change when no indexed parent can see it. - Join
Index Tap - Keeps the parent indexes of a pipeline’s EXISTS joins equal to the rows
the pipeline emits (
join-index-tap.ts). - Lift
Field - Lifts a field of a singular child relationship onto each row.
- Memory
Source - A table’s rows in memory.
- Memory
Source Input - A pipeline’s connection to a
MemorySource. - NoFilter
Output - Never constructed: the type behind
no_filter_output. - Node
- A row flowing through a pipeline, plus its relationships. Relationships are generated lazily as they are read.
- Parent
Fetch Bound - The bound a
TakeGatecaps one parent fetch of a child push at. - Pipeline
Error - An error building or running a pipeline, with JS’s message.
- Projected
Column - A group column as a view shows it: its name in the view and in the input.
- Relationships
- A node’s relationships, in insertion order like a JS object’s keys. Nodes carry a handful at most, so lookups are linear.
- Skip
- Sets where the pipeline starts: no row before the bound is output
(
skip.ts). - Source
Schema - The schema of an operator’s output (
SourceSchemainschema.ts). - Start
- Where a fetch starts (
Startinoperator.ts). - Take
- Implements
limit: passes the firstlimitnodes of its input and keeps a bound, the last accepted row, to decide on pushes (take.ts). Counts globally or per value of a partition key. - Take
Gate - Caps upstream parent fetches at a downstream
Take’s bound. - Union
FanIn - Merges the branches of a
UnionFanOut(union-fan-in.ts). - Union
FanOut - Forks a pipeline for an OR with flipped subqueries (
union-fan-out.ts). - View
Entry - A row in a materialized view, with the relationships the query asked
for (
Entryinview.ts).
Enums§
- Basis
- Whether a fetch starts at its start row or after it.
- Change
- A change pushed through a pipeline (
change.ts). - Change
Type - The kinds of change (
change-type-enum.ts). - Result
Type - The result type of a view (
ResultTypeintyped-view.ts). - Source
Change - A change to a source’s rows (
source.ts). - View
Value - A relationship in a view: several rows, at most one, or an aggregate’s value.
Constants§
- LIFTED_
FIELD_ COLUMN - The column
LiftFieldwrites the destination’s field into. A space can’t start an identifier, so it never collides with a real column. - MULTI_
CONSTRAINT_ CHUNK_ SIZE - The most entries in one batched parent fetch (
flipped-join.ts).
Traits§
- Filter
Input - The
wheresub-graph’s input (FilterInputinfilter-operators.ts). - Filter
Operator - Filter
Output - The
wheresub-graph’s output. Filter operators have nofetch; a fetch through the sub-graph asksfilterwhether each node passes. - Input
- An operator’s input: something that can be fetched from and pushes to an output.
- Input
Base InputBaseinoperator.ts.- Operator
- An operator in a pipeline: an input to the next and an output of the previous.
- Output
- An operator’s output (
Outputinoperator.ts). - Source
- A source of rows for pipelines (
Sourceinsource.ts). - Source
Input - A source’s connection to one pipeline.
- Take
Bound Provider - Provides
Take’s bound to upstream operators (take-gate.ts).
Functions§
- aggregate_
source_ schema aggregateSourceSchema: the columns and primary key of the rows an aggregate emits, from its input’s columns and its group key. A top-level aggregate has no group key, so its one row is keyed by_0_key.- aggregate_
value aggregateValue: the valuerowcontributes toaggregate: its field, or the JSON leaf at the path when it is one the function takes (a number for sum and avg, a number or string for min and max), else null.- apply
- Applies
changetoparent’srelationship. Returns whether the tree changed (JS returns the same entry when it did not). - assert_
not_ synthetic_ column assertNotSyntheticColumn.- assert_
ordering_ includes_ pk assertOrderingIncludesPK.- binary_
search binarySearch(high, compare)(shared/src/binary-search.ts): the index wherecompareis equal, or the first index past the elements it is greater for.- build_
join_ constraint buildJoinConstraint:target_keymapped tosource_row’ssource_keyvalues, orNoneif one is null (a null key matches nothing).- canonical_
key canonicalKey: a string key overkeys, tagged by type so1and"1"differ.- canonical_
key_ of_ constraint canonical_keyof a constraint’s values.- capture
- Runs
body, and fails with the first error an operator reported while it ran. - carries_
components carriesComponents: whetherfn_’s rows carry the sum and count.- compare_
aggregate_ values compareAggregateValues: numbers before strings, as in JS and SQLite, for the leaves of a JSON path; otherwisecompareValues. Values JS can’t compare, such as the objects of a json column without a path, fail the query as JS’s throw does. Equal values compare equal first, as JS’sa === bdoes for one row’s own value.- compare_
values compareValueson possibly missing values:undefinedreads asnull.- constraint_
contains_ partition_ key constraintContainsPartitionKey.- constraint_
matches_ partition_ key constraintMatchesPartitionKey: the constraint is on exactly the partition key, or neither is set.- create_
predicate createPredicate(condition)for a condition without subqueries.- empty
- A stream with no elements.
- empty_
aggregate_ value emptyAggregateValue.- filter_
push - Pushes
changetooutputif its row passespredicate; an edit whose row enters or leaves the predicate becomes an add or a remove. - from_
vec - A stream of
elements. - generate_
with_ overlay generateWithOverlay: applies the in-flight child changeoverlayto a sorted child stream, so a parent that has yet to receive the change sees the children as they were.- generate_
with_ overlay_ unordered generateWithOverlayUnordered: the overlay for an unordered child stream. Removed rows go first; added rows are suppressed by primary key.- group_
key groupKey: a group’s_0_key, which also keys its state:valueToKeyof the value for one column, the values JSON encoded for several.- group_
ordering groupOrdering: the order of a grouped query’s rows: itsorderByrestricted to the group columns (itsgroupBy, or the columns a count of distinct combinations groups by), then the rest of them ascending.- group_
source_ schema groupSourceSchema: the columns, primary key and sort of the rowsGroupByemits: the group columns, the group’s key (_0_key) and the aggregate’s payload, with a sum or average’s row count (_0_rows).- has_
failed - Whether an operator reported an error to the running
capture. Where JS’s throw would unwind, a source stops pushing. - identical
- JS
===on possibly missing values. Arrays and objects are never identical, since rows are decoded fresh. - is_
in_ parent_ fetch - Whether one of the parent fetches of a push yields
row. - is_
invertible isInvertible: a change to one row moves the result by a fixed delta.- is_
join_ match - is_same
- Whether
aandbare the same object, as JS’s===on operators. - is_
synthetic_ column isSyntheticColumn: the columns the aggregate operators add to a row.- js_
string - JS
String(value)for JSON values. - key_
matches_ primary_ key keyMatchesPrimaryKey. The primary key is sorted;keyneed not be.- lazy
- A stream whose elements
makeproduces, called on the firstnext(). - make_
add_ empty_ relationships makeAddEmptyRelationships(schema)(change).- make_
comparator makeComparator(order, reverse).- maybe_
split_ and_ push_ edit_ change maybeSplitAndPushEditChange.- merge_
empty - Adds an empty stream for each of
namesthatrelationshipslacks. - merge_
fetches mergeFetches: merges sorted branch streams, uniting the relationships of a row that several branches yield (the first branch wins a conflict).- merge_
filters - The request’s filter and the operator’s own, ANDed.
- merge_
relationships mergeRelationships: putsright’s relationships intoleftwhereleftlacks them.- merge_
sorted_ streams mergeSortedStreams: an N-way merge of streams sorted bycompare. The stream of the node emitted last is pulled again only when the next node is asked for, as the JS generator does on resume. Ties go to the earlier stream.- no_
filter_ output - A weak filter output that upgrades to nothing.
- no_
output - A weak reference that upgrades to nothing, for an input whose output is not set yet.
- primary_
key_ constraint_ from_ filters primaryKeyConstraintFromFilters: the primary key lookup the filters amount to, if they do.- pull_
simple_ and_ components pullSimpleAndComponents: the top-level AND conjuncts that are simple.- push_
accumulated_ changes pushAccumulatedChanges(push-accumulated.ts): pushes the single change that the changes collected from an OR’s branches amount to.- push_
witness_ deltas - The row stays, but gained (
add) or lost (remove) every witness in its branch relationships: one child change per witness. - read_
parent_ fetch_ bounds - Reads the bounds for a child push’s parent fetches before they start.
- report
- Reports
messageto the runningcapture; the first one wins. Outside one (a pipeline driven directly) the error goes to stderr, and the operator yields nothing. - row_
equals_ for_ compound_ key - transform_
filters transformFilters: a condition without subqueries that matches a superset of the rowsfiltersmatches, and whether anything was removed.- value
- A row’s value for
column; a missing column reads asnull. - value_
to_ key valueToKey: a string without surrogates (in UTF-16) issand the string, any other value its JSON.- values_
equal valuesEqualon possibly missing values:undefinedandnullequal nothing.
Type Aliases§
- Build
Pipeline - Builds a
DeferredInput’s pipeline. - Comparator
- Orders rows (
Comparatorindata.ts). - Group
Schema - The columns, primary key and sort of a grouped operator’s rows.
- Listener
- Called with a view’s data and result type.
- Node
Comparator - Orders nodes.
- Node
Stream - A stream of nodes: what a fetch returns.
- Parent
Partitions - The partitions of indexed parents that share a join key, as fetch
constraints;
[None]for an unpartitioned index (join-index.ts). - Relationship
Stream - A relationship of a node: a stream of its child nodes, made each time it is read.
- Row
- A row: column name to value. A missing column reads as absent, as an
undefinedproperty does in JS. Rows are shared, not copied, as they flow through a pipeline. - RowPredicate
- Whether a row passes a filter.
- Stream
- A stream of values, pulled once.