ZQL Engine Deep Dive

Zero’s query language (ZQL) is powered by an incremental view maintenance (IVM) engine that efficiently materializes and updates query results. This guide explores the engine’s architecture, design patterns, and implementation details.

Architecture Overview

The ZQL engine consists of three main layers:

Query Layer (packages/zql/src/query/): High-level query API and AST generation
Planner Layer (packages/zql/src/planner/): Cost-based query optimization
IVM Layer (packages/zql/src/ivm/): Incremental view maintenance execution

Data Flow

Query Builder API
      ↓
   AST (Abstract Syntax Tree)
      ↓
  Query Planner (optimization)
      ↓
 Operator Pipeline (IVM)
      ↓
Materialized View (results)

The IVM Engine

Core Concepts

The IVM engine maintains query results incrementally by processing change notifications instead of re-executing queries: Traditional approach (re-query):

// On every data change:
const results = await db.query('SELECT * FROM users WHERE ...');
// Cost: O(n) where n = table size

IVM approach (incremental):

// Initial materialization:
const results = pipeline.fetch();

// On data change:
pipeline.push({type: 'add', node: newRow});
// Cost: O(1) to O(k) where k = affected rows (typically << n)

Operator Pipeline

Queries are compiled into operator pipelines. Each operator:

Implements Input and Output interfaces (packages/zql/src/ivm/operator.ts:103)
Processes fetch requests for initial materialization
Handles push updates for incremental maintenance
Maintains internal state for efficient updates

Example pipeline:

// Query: users.where('active', true).whereExists('posts').limit(10)

Source('users')
  ↓
Filter(active = true)
  ↓
Join(posts)
  ↓
Take(10)
  ↓
Output

Operator Types

Source

Location: packages/zql/src/ivm/source.ts Purpose: Root data source, feeds data into the pipeline

interface Source {
  // Create a connection with specific ordering and filters
  connect(sort: Ordering, filters?: Condition): SourceInput;
  
  // Push changes to all connected outputs
  push(change: SourceChange): Stream<'yield'>;
}

Key features:

Multiple outputs (one per query using the table)
Applies filters and ordering
Splits edit changes when sort keys change

Filter

Location: packages/zql/src/ivm/filter.ts Purpose: Evaluates conditions and filters rows Fetch behavior:

// Forward fetch request with filter constraints
for (const node of upstream.fetch(req)) {
  if (evaluateCondition(node.row, condition)) {
    yield node;
  }
}

Push behavior:

push(change: Change): Stream<'yield'> {
  if (change.type === 'edit') {
    const oldMatch = evaluateCondition(change.oldNode.row);
    const newMatch = evaluateCondition(change.node.row);
    
    if (oldMatch && !newMatch) {
      // Row no longer matches: emit remove
      yield* output.push({type: 'remove', node: change.oldNode});
    } else if (!oldMatch && newMatch) {
      // Row now matches: emit add
      yield* output.push({type: 'add', node: change.node});
    } else if (oldMatch && newMatch) {
      // Still matches: forward edit
      yield* output.push(change);
    }
    // else: didn't match before or after, ignore
  }
}

Join

Location: packages/zql/src/ivm/join.ts Purpose: Joins parent and child data, creates hierarchical results Key insight: Zero’s joins produce hierarchical data, not flat tables:

// SQL-style flat join:
[{userId: 1, userName: 'Alice', postId: 10, postTitle: 'Hello'}]

// Zero hierarchical join:
[{
  id: 1,
  name: 'Alice',
  posts: [
    {id: 10, title: 'Hello'},
    {id: 11, title: 'World'}
  ]
}]

Fetch behavior:

fetch(req: FetchRequest): Stream<Node> {
  for (const parentNode of parent.fetch(req)) {
    // Build constraint from parent key values
    const childConstraint = buildJoinConstraint(
      parentNode.row,
      parentKey,
      childKey
    );
    
    // Fetch matching children
    const childStream = child.fetch({constraint: childConstraint});
    
    // Add relationship to parent node
    yield {
      ...parentNode,
      relationships: {
        [relationshipName]: childStream
      }
    };
  }
}

Push behavior:

// Parent changes: Check if existing children still match
// Child changes: Find affected parents and emit child changes

See packages/zql/src/ivm/join.ts:43 for full implementation.

Flipped Join

Location: packages/zql/src/ivm/flipped-join.ts Purpose: Optimized join when child table is smaller or more selective Difference from regular join:

// Regular join: Iterate parents, fetch children
for (parent of parents) {
  children = fetch(constraint: parent.key);
}

// Flipped join: Iterate children, fetch parents
for (child of children) {
  parent = fetch(constraint: child.foreignKey);
}

When to use:

Child table is much smaller than parent
Child has highly selective filters
Query has LIMIT but parent has no effective filters

The query planner (packages/zql/src/planner/) automatically chooses between regular and flipped joins based on cost estimates.

Take (Limit)

Location: packages/zql/src/ivm/take.ts Purpose: Limits output to first N rows Fetch behavior:

fetch(req: FetchRequest): Stream<Node> {
  let count = 0;
  for (const node of upstream.fetch(req)) {
    yield node;
    if (++count === limit) {
      break; // Short-circuit when limit reached
    }
  }
}

Push behavior:

// Maintains ordered buffer of current results
// Adds only if within limit
// Removes may require fetching additional rows

Union Fan-In/Out

Location: packages/zql/src/ivm/union-fan-in.ts, packages/zql/src/ivm/union-fan-out.ts Purpose: Handles OR conditions by splitting/merging data streams

// Query with OR
users.where(({or, exists}) => or(
  exists('posts'),
  exists('comments')
));

// Pipeline:
         FanOut
        /      \
  Join(posts)  Join(comments)
        \      /
         FanIn

Fan-Out: Splits single stream into multiple branches Fan-In: Merges multiple branches, deduplicates results

Change Types

Location: packages/zql/src/ivm/change.ts The IVM engine processes four types of changes:

Add Change

type AddChange = {
  type: 'add';
  node: Node; // New row and all its children
};

Represents a node (and all its children) getting added to the result.

Remove Change

type RemoveChange = {
  type: 'remove';
  node: Node; // Row to remove and all its children
};

Represents a node (and all its children) getting removed from the result.

Edit Change

type EditChange = {
  type: 'edit';
  node: Node;     // New row values
  oldNode: Node;  // Old row values
};

Represents a row value change where:

Primary key stays the same (or changes in a compatible way)
Relationships are unchanged

Edit changes may be split into remove + add when:

The row no longer passes filters
Sort order changes (relationships must be rebuilt)

See packages/zql/src/ivm/view-apply-change.ts:46 for split logic.

Child Change

type ChildChange = {
  type: 'child';
  node: Node;  // Parent node (row unchanged)
  child: {
    relationshipName: string;
    change: Change; // Descendant change
  };
};

The node’s row is unchanged, but one of its descendants changed. Allows efficient updates without re-fetching the entire subtree.

Streams and Yielding

Location: packages/zql/src/ivm/stream.ts

Stream Type

type Stream<T> = Iterable<T>;

Streams are lazy, forward-only iterables:

Consumed using for...of loops
Single-use (can’t restart after exhaustion)
Enable cleanup when iteration stops early

Yield for Responsiveness

Long-running operations can yield control:

function* fetch(req: FetchRequest): Stream<Node | 'yield'> {
  for (const node of upstream.fetch(req)) {
    // Yield control every N rows
    if (count++ % 100 === 0) {
      yield 'yield';
    }
    yield node;
  }
}

Contract:

If an input yields 'yield', caller must yield it immediately
Prevents blocking the UI thread during large operations
Allows incremental rendering and cancellation

See packages/zql/src/ivm/operator.ts:41 for yield contract details.

Query Planner

Location: packages/zql/src/planner/

Purpose

The query planner optimizes WHERE EXISTS queries by choosing optimal join execution strategies. What it optimizes:

Join direction (semi vs flipped)
Cost estimation (expected query cost)
Constraint propagation (how filters enable index usage)

Planning Algorithm

The planner uses exhaustive enumeration of join flip patterns:

// For n flippable joins, evaluate 2^n plans
for (pattern in 0...(2^n - 1)) {
  1. Reset all nodes to initial state
  2. Apply flip pattern (bit i = flip join i)
  3. Derive FO/UFO and FI/UFI from flip pattern
  4. Propagate unlimiting for flipped joins
  5. Propagate constraints backwards through graph
  6. Estimate cost forwards through graph
  7. Track best plan
}

// Restore best plan

Complexity limit: Max 9 flippable joins (512 plans) See packages/zql/src/planner/README.md for comprehensive planner documentation.

Cost Model

type ConnectionCostModel = (
  table: string,
  sort: Ordering,
  filters: Condition | undefined,
  constraint: PlannerConstraint | undefined,
) => {
  startupCost: number; // One-time setup (e.g., sorting)
  rows: number;        // Estimated rows returned
};

Cost factors:

Number of rows scanned in each table
Filter selectivity (fraction of rows passing predicates)
Join selectivity (fraction of parent rows with matching children)
Index availability (affects constraint costs)
Limit propagation (early termination)

Fan-Out Calculation

Location: packages/zql/src/planner/SQLITE_STAT_FANOUT.md Fan-out = average number of child rows per parent row Formula for semi-join selectivity:

semiJoinSelectivity = 1 - (1 - filterSelectivity)^fanOut

Example: 50% of posts are published, average 10 posts per user:

filterSelectivity = 0.5
fanOut = 10
semiJoinSelectivity = 1 - (1 - 0.5)^10 = 0.999
// 99.9% of users have at least one published post

The planner queries sqlite_stat4 and sqlite_stat1 for accurate fan-out statistics.

Storage and State

Location: packages/zql/src/ivm/operator.ts:109

Storage Interface

Operators can store internal state:

interface Storage {
  set(key: string, value: JSONValue): void;
  get(key: string, def?: JSONValue): JSONValue | undefined;
  scan(options?: {prefix: string}): Stream<[string, JSONValue]>;
  del(key: string): void;
}

Use cases:

Take operator: Stores current result set
Join operator: Caches relationship data
Custom operators: Arbitrary state management

Memory Source

Location: packages/zql/src/ivm/memory-source.ts In-memory source implementation:

class MemorySource implements Source {
  // Stores rows in memory
  // Maintains indexes for efficient constraint queries
  // Supports push updates
}

Features:

Automatic index creation based on query constraints
Efficient range queries
Used for testing and client-side sources

View Factory

Location: packages/zql/src/ivm/view.ts

View Types

type View = EntryList | Entry | undefined;
type EntryList = readonly Entry[];
type Entry = {readonly [key: string]: Value | View};

Views are hierarchical:

// Example view:
[
  {
    id: 1,
    name: 'Alice',
    posts: [  // Nested view (relationship)
      {id: 10, title: 'Hello'},
      {id: 11, title: 'World'}
    ]
  }
]

View Factory

type ViewFactory<TTable, TSchema, TReturn, T> = (
  query: Query<TTable, TSchema, TReturn>,
  input: Input,
  format: Format,
  onDestroy: () => void,
  onTransactionCommit: (cb: () => void) => void,
  queryComplete: true | ErroredQuery | Promise<true>,
  updateTTL: (ttl: TTL) => void,
) => T;

Factory creates the final view from the operator pipeline, handling:

Initial materialization
Incremental updates
Lifecycle management (cleanup)
TTL (time-to-live) tracking

Advanced Topics

Constraint Propagation

Constraints flow backwards through the pipeline to enable efficient fetches:

// Join receives constraint from output
// Translates to child constraint based on join keys
const childConstraint = {
  userId: parentRow.id  // posts WHERE userId = <parent.id>
};

Enables index usage: SELECT * FROM posts WHERE userId = ? LIMIT 1 See packages/zql/src/planner/README.md:357 for constraint flow details.

Relationship Streams

Relationships are lazy streams, not materialized arrays:

type Node = {
  row: Row;
  relationships: {
    [name: string]: Stream<Node>;
  };
};

Benefits:

Don’t fetch children unless accessed
Support infinite/large child collections
Enable streaming rendering

Trade-off: Streams are single-use (can’t iterate twice)

Debug Delegate

Location: packages/zql/src/builder/debug-delegate.ts Debug interface for tracing query execution:

interface DebugDelegate {
  logFetch?(table: string, constraint?: Constraint): void;
  logPush?(table: string, change: SourceChange): void;
}

Use for:

Understanding query execution
Debugging performance issues
Testing and validation

Performance Characteristics

Time Complexity

Operation	Initial Fetch	Push Update
Source	O(n)	O(1)
Filter	O(n)	O(1)
Join	O(n × m)	O(k) where k = affected rows
Take	O(n) up to limit	O(1) to O(log n)
Union	O(n + m)	O(1)

Space Complexity

Source: O(n) for all rows
Filter: O(1) (no state)
Join: O(n × r) where r = relationships per row
Take: O(limit) for result buffer
Union: O(n) for deduplication

Incremental Update Benefits

IVM shines when:

Changes affect small fraction of results (k much less than n)
Multiple queries over same data
UI needs real-time updates

Example: 1M users, add 1 user:

Re-query: O(1M) - scan all users
IVM push: O(1) - add one node

Implementation Patterns

Dual-State Pattern

Many components separate immutable structure from mutable planning state:

class PlannerJoin {
  // Immutable (set at construction)
  readonly #parent: PlannerNode;
  readonly #parentConstraint: Constraint;
  readonly #flippable: boolean;
  
  // Mutable (changes during planning)
  #joinType: 'semi' | 'flipped';
  
  reset(): void {
    // Reset mutable state for replanning
    this.#joinType = 'semi';
  }
}

Allows efficient plan exploration without rebuilding graph structure.

Generator-Based Streams

Use generators for lazy evaluation and cleanup:

function* fetch(req: FetchRequest): Stream<Node> {
  const stmt = db.prepare(sql);
  try {
    for (const row of stmt.iterate()) {
      yield {row, relationships: {}};
    }
  } finally {
    stmt.finalize(); // Cleanup even if iteration stops early
  }
}

Monomorphic Dispatch

For performance, avoid polymorphic shapes:

// TODO: Change to classes for monomorphic dispatch
// Currently uses discriminated unions
type Change = AddChange | RemoveChange | ChildChange | EditChange;

// Future: Use classes
class AddChange { type = 'add'; constructor(public node: Node) {} }

See packages/zql/src/ivm/change.ts:6 for optimization notes.

Next Steps

Optimize queries using Performance best practices
Debug issues with Troubleshooting techniques
Plan upgrades using Migration guides

Get Started

Core Concepts

Client Guide

Server Guide

Advanced

​ZQL Engine Deep Dive

​Architecture Overview

​Data Flow

​The IVM Engine

​Core Concepts

​Operator Pipeline

​Operator Types

​Source

​Filter

​Join

​Flipped Join

​Take (Limit)

​Union Fan-In/Out

​Change Types

​Add Change

​Remove Change

​Edit Change

​Child Change

​Streams and Yielding

​Stream Type

​Yield for Responsiveness

​Query Planner

​Purpose

​Planning Algorithm

​Cost Model

​Fan-Out Calculation

​Storage and State

​Storage Interface

​Memory Source

​View Factory

​View Types

​View Factory

​Advanced Topics

​Constraint Propagation

​Relationship Streams

​Debug Delegate

​Performance Characteristics

​Time Complexity

​Space Complexity

​Incremental Update Benefits

​Implementation Patterns

​Dual-State Pattern

​Generator-Based Streams

​Monomorphic Dispatch

​Next Steps

Build docs developers (and LLMs) love

ZQL Engine Deep Dive

Architecture Overview

Data Flow

The IVM Engine

Core Concepts

Operator Pipeline

Operator Types

Source

Filter

Join

Flipped Join

Take (Limit)

Union Fan-In/Out

Change Types

Add Change

Remove Change

Edit Change

Child Change

Streams and Yielding

Stream Type

Yield for Responsiveness

Query Planner

Purpose

Planning Algorithm

Cost Model

Fan-Out Calculation

Storage and State

Storage Interface

Memory Source

View Factory

View Types

View Factory

Advanced Topics

Constraint Propagation

Relationship Streams

Debug Delegate

Performance Characteristics

Time Complexity

Space Complexity

Incremental Update Benefits

Implementation Patterns

Dual-State Pattern

Generator-Based Streams

Monomorphic Dispatch

Next Steps