Execution & Performance

Basalt's query engine is engineered from the ground up for power users with super-large vaults ($\ge 25,000$ notes). In traditional JS-based environments, querying tens of thousands of notes locks the main thread, causing typing lag, frame drops, and heavy Garbage Collection pauses.

Basalt offloads query compilation, filtering, and aggregation to native Rust in crates/basalt-tables, delivering sub-15ms response times even under heavy loads.

The Execution Pipeline

Every DQL query passes through a five-stage compilation and execution pipeline:

┌────────────────────────────────────────────────────────┐
│ 1. AST Parsing & Projection Analysis                   │
│    Extracts exact frontmatter keys required            │
├────────────────────────────────────────────────────────┤
│ 2. Predicate & Source Push-Down                        │
│    Filters candidates via memory indexes before clone  │
├────────────────────────────────────────────────────────┤
│ 3. Row Materialization & WHERE Evaluation              │
│    Applies predicates using Null-safe 3VL logic        │
├────────────────────────────────────────────────────────┤
│ 4. Transformation & Aggregation                        │
│    Bounded FLATTEN expansion & single-pass grouping    │
├────────────────────────────────────────────────────────┤
│ 5. Ordering & Pagination                               │
│    Schwartzian transform sort & Top-K priority queue   │
└────────────────────────────────────────────────────────┘

---

Architectural Optimizations

1. Predicate & Source Push-Down

In naive implementations, a query engine clones metadata for all 25,000 vault notes before filtering. For a query matching #project-alpha (which might only exist in 30 notes), 24,970 heap allocations would be wasted.

Basalt evaluates the FROM clause directly against the vault's in-memory inverted tag index, link graph, and folder trie:

• Notes failing the source predicate are eliminated immediately.
• Only matching candidates have their frontmatter materialized into PageRow structs.

2. Projection Analysis

Before building row objects, the compiler inspects the query to extract the exact set of frontmatter keys requested across the SELECT, WHERE, SORT, GROUP BY, and FLATTEN clauses. Unreferenced properties are ignored, minimizing memory footprint and string allocations.

3. Schwartzian Transform Sorting

Standard sorting algorithms call the comparison closure $O(N \log N)$ times. For 25,000 notes, this means roughly 375,000 repeated AST evaluations of expressions like file.mtime or custom_rank + 1.

Basalt applies the Schwartzian Transform:

1. Evaluates the sort expression once per row in $O(N)$ time into a contiguous Vec<(TypedValue, usize)>.
2. Sorts the compact key-index pairs.
3. Reorders the materialized rows based on the sorted indices.

4. Top-K Streaming Heap Selection

When a query contains LIMIT k (e.g. SORT file.mtime DESC LIMIT 10), sorting all 25,000 candidates is unnecessary. Basalt feeds evaluated keys into a bounded binary heap (priority queue) of size $k$.

• Complexity drops from $O(N \log N)$ to $O(N \log k)$.
• Executes in under 4ms across 25,000 notes.

5. Three-Valued Logic (3VL) & Total Type Ordering

In JavaScript, unexpected type coercion (such as "10" < 2) frequently creates subtle bugs. Basalt uses a canonical total ordering across all TypedValue variants:

Null < Boolean < Number < Text < Date < Array < Object

Comparisons against missing or Null fields adhere to strict three-valued logic, ensuring consistent and predictable sorting across heterogeneous note metadata.

---

Benchmark Metrics

Query execution is continuously verified against Criterion benchmarks at 25k-note vault scale:

Benchmark	Query Scenario	25k Note Target
dql_scan_and_filter	TABLE file.name, status WHERE status = "active"	≤ 5ms
dql_sort_limit	SORT date DESC LIMIT 20	≤ 4ms
dql_flatten_group	Multi-level FLATTEN tags and GROUP BY category	≤ 15ms