Skip to main content

Module ivm

Module ivm 

Source
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 a Join routes it as it would the child rows.
ArrayView
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).
ChildChange
A change to a child relationship of a node.
ClosureOutput
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 None where JS has undefined.
DeferredInput
A placeholder input for a view whose pipeline is not built yet.
Exists
Filters on whether a relationship is non-empty (exists.ts).
ExistsJoin
Set when a join feeds an EXISTS or NOT EXISTS condition (ExistsJoin in join.ts). Its parent index is kept by a JoinIndexTap at the end of the pipeline.
FanIn
Merges the branches of an OR, removing duplicates (fan-in.ts).
FanOut
Forks the where sub-graph for an OR (fan-out.ts).
FetchRequest
FetchRequest in operator.ts.
Filter
Filters through a pure predicate (filter.ts).
FilterEnd
Adapts the end of the where sub-graph back to an Input.
FilterStart
Adapts an Input to the where sub-graph (filter-operators.ts).
FlippedJoin
An inner join that fetches children first, then their parents. Outputs parents, in parent order, that have at least one related child.
FlippedJoinArgs
What FlippedJoin::new joins, and how.
GroupBy
Groups its input by columns and reduces each group, as GROUP BY does: 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.
GroupProjection
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 a groupBy() with an aggregate, its value under value_name (count, sum, …). A distinct() 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).
JoinArgs
What Join::new joins, and how.
JoinIndex
An index from join key to the parent rows that have it. Join and FlippedJoin skip the parent fetch of a child change when no indexed parent can see it.
JoinIndexTap
Keeps the parent indexes of a pipeline’s EXISTS joins equal to the rows the pipeline emits (join-index-tap.ts).
LiftField
Lifts a field of a singular child relationship onto each row.
MemorySource
A table’s rows in memory.
MemorySourceInput
A pipeline’s connection to a MemorySource.
NoFilterOutput
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.
ParentFetchBound
The bound a TakeGate caps one parent fetch of a child push at.
PipelineError
An error building or running a pipeline, with JS’s message.
ProjectedColumn
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).
SourceSchema
The schema of an operator’s output (SourceSchema in schema.ts).
Start
Where a fetch starts (Start in operator.ts).
Take
Implements limit: passes the first limit nodes 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.
TakeGate
Caps upstream parent fetches at a downstream Take’s bound.
UnionFanIn
Merges the branches of a UnionFanOut (union-fan-in.ts).
UnionFanOut
Forks a pipeline for an OR with flipped subqueries (union-fan-out.ts).
ViewEntry
A row in a materialized view, with the relationships the query asked for (Entry in view.ts).

Enums§

Basis
Whether a fetch starts at its start row or after it.
Change
A change pushed through a pipeline (change.ts).
ChangeType
The kinds of change (change-type-enum.ts).
ResultType
The result type of a view (ResultType in typed-view.ts).
SourceChange
A change to a source’s rows (source.ts).
ViewValue
A relationship in a view: several rows, at most one, or an aggregate’s value.

Constants§

LIFTED_FIELD_COLUMN
The column LiftField writes 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§

FilterInput
The where sub-graph’s input (FilterInput in filter-operators.ts).
FilterOperator
FilterOutput
The where sub-graph’s output. Filter operators have no fetch; a fetch through the sub-graph asks filter whether each node passes.
Input
An operator’s input: something that can be fetched from and pushes to an output.
InputBase
InputBase in operator.ts.
Operator
An operator in a pipeline: an input to the next and an output of the previous.
Output
An operator’s output (Output in operator.ts).
Source
A source of rows for pipelines (Source in source.ts).
SourceInput
A source’s connection to one pipeline.
TakeBoundProvider
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 value row contributes to aggregate: 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 change to parent’s relationship. 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 where compare is equal, or the first index past the elements it is greater for.
build_join_constraint
buildJoinConstraint: target_key mapped to source_row’s source_key values, or None if one is null (a null key matches nothing).
canonical_key
canonicalKey: a string key over keys, tagged by type so 1 and "1" differ.
canonical_key_of_constraint
canonical_key of a constraint’s values.
capture
Runs body, and fails with the first error an operator reported while it ran.
carries_components
carriesComponents: whether fn_’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; otherwise compareValues. 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’s a === b does for one row’s own value.
compare_values
compareValues on possibly missing values: undefined reads as null.
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 change to output if its row passes predicate; 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 change overlay to 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: valueToKey of the value for one column, the values JSON encoded for several.
group_ordering
groupOrdering: the order of a grouped query’s rows: its orderBy restricted to the group columns (its groupBy, 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 rows GroupBy emits: 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 a and b are 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; key need not be.
lazy
A stream whose elements make produces, called on the first next().
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 names that relationships lacks.
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: puts right’s relationships into left where left lacks them.
merge_sorted_streams
mergeSortedStreams: an N-way merge of streams sorted by compare. 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 message to the running capture; 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 rows filters matches, and whether anything was removed.
value
A row’s value for column; a missing column reads as null.
value_to_key
valueToKey: a string without surrogates (in UTF-16) is s and the string, any other value its JSON.
values_equal
valuesEqual on possibly missing values: undefined and null equal nothing.

Type Aliases§

BuildPipeline
Builds a DeferredInput’s pipeline.
Comparator
Orders rows (Comparator in data.ts).
GroupSchema
The columns, primary key and sort of a grouped operator’s rows.
Listener
Called with a view’s data and result type.
NodeComparator
Orders nodes.
NodeStream
A stream of nodes: what a fetch returns.
ParentPartitions
The partitions of indexed parents that share a join key, as fetch constraints; [None] for an unpartitioned index (join-index.ts).
RelationshipStream
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 undefined property 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.