Zone maps

A zone map is the smallest and largest value of a column in each block of rows. A filter such as ts >= start can’t match a block whose largest ts is below start, so Vectro doesn’t read that block at all. On data that arrives in time order (logs, orders, sensor readings, streams), “the last hour” becomes a small slice of the table instead of a scan.

Zone maps are exact: a block is skipped only when no row in it can match, so answers never change. There is nothing to create or tune.

import { Engine } from 'vectrojs';

const engine = new Engine();
const n = 5_000_000;
const start = Date.UTC(2024, 0, 1);
const orders = engine.table({
  ts: Float64Array.from({ length: n }, (_, i) => start + i * 1000),   // one order a second
  price: Float64Array.from({ length: n }, (_, i) => (i * 7919) % 1000),
});
const since = start + (n - 3600) * 1000;                             // the last hour

const best = (f) => {
  let ms = Infinity, v;
  for (let k = 0; k < 5; k++) { const t = performance.now(); v = f(); ms = Math.min(ms, performance.now() - t); }
  return `${v} in ${ms.toFixed(2)} ms`;
};

// a plain column comparison: blocks before `since` are skipped
console.log(best(() => orders.filter('ts >= since', { since }).sum('price')));
// the same rows, but `ts + 0` is an expression: every row is checked
console.log(best(() => orders.filter('ts + 0 >= since', { since }).sum('price')));

await engine.close();

Tables in memory

Each column of a table keeps the min and max of every block of 16,384 rows. They are built the first time a filter uses the column, then kept; that first build takes about 25 to 50 ms on a 10M-row column, once. Tables shorter than 65,536 rows don’t use them.

When a filter runs, Vectro finds the first and the last block that can match and runs the query over the rows between them. If that range is more than 90% of the table, it runs over the whole table as usual. Aggregates, group-bys, collect(), toRows() and top() all narrow this way.

Which filters can skip

Zone maps use the parts of a filter that compare a column with a constant, joined by &&:

Filter	Skips blocks
ts >= since (a number param)	yes
ts > t && price > 50	yes, using both parts
t0 <= ts && ts < t1	yes
ts >= '2024-06-01' (a date column against ISO text)	yes
region == 'LATAM' && qty >= 5 (a category label)	yes, when the label’s rows sit together
ts >= t || price > 99	no: an OR
ts + 0 >= t, -ts <= -t	no: an expression, not a column
price > 99.5 on unordered prices	no blocks can be ruled out

Free-text columns don’t have zone maps. Float32 tables compare in float32, so the zone check rounds exactly as the filter does.

The table this pays off on is one whose rows are ordered, or nearly ordered, by the column you filter on. If you load data in another order, sorting it once by time (table.sort('ts')) makes every later time filter cheap.

Datasets

Datasets store zone maps in the file: the min and max of every column for each chunk (4M rows) and for each block of 65,536 rows inside it, written when the dataset is written. A query first drops the chunks whose min and max rule out the filter, then, inside each chunk it keeps, reads only from the first block that can match to the last. Chunks it drops are never read from disk.

ds.lastRun shows how many chunks were read and skipped:

import { mkdtempSync, rmSync } from 'node:fs';
import { tmpdir } from 'node:os';
import { join } from 'node:path';
import { Engine } from 'vectrojs';

const dir = mkdtempSync(join(tmpdir(), 'vectro-'));
const engine = new Engine();
const n = 2_000_000;
const readings = engine.table({
  ts: Array.from({ length: n }, (_, i) => new Date(Date.UTC(2024, 0, 1) + i * 15_000)),
  sensor: Float64Array.from({ length: n }, (_, i) => i % 200),
  // values drift up over time, with noise
  value: Float64Array.from({ length: n }, (_, i) => Math.floor(i / 1000) + ((i * 7919) % 500)),
});
engine.writeDataset(join(dir, 'readings.vectro'), readings, { rowsPerChunk: 250_000 });
readings.dispose();
const ds = engine.openDataset(join(dir, 'readings.vectro'));

const show = ({ chunks, read, skipped, rows }) => ({ chunks, read, skipped, rows });

// a time filter: only the last chunk is read
console.log(ds.filter("ts >= '2024-12-01'").agg({ n: 'count()', avg: 'mean(value)' }), show(ds.lastRun));

// a filter on a column with no order: every chunk may match
console.log(ds.filter('sensor == 7').count(), show(ds.lastRun));

// top-k: after the first chunk, later blocks can't beat the 5 lowest values
console.log(ds.top(5, 'value').toRows().map((r) => r.value), show(ds.lastRun));

await ds.close();
await engine.close();
rmSync(dir, { recursive: true, force: true });

Top-k

top(k, by) on a dataset uses the zone maps of its leading sort keys (number columns). Once it holds k rows, it knows the k-th best value so far; a later block whose min (ascending) or max (descending) can’t beat or tie that value is not read. The first chunk sets the bar, so this skips most of the file when good rows turn up early. In the example, the lowest values are at the start, so top(5, 'value') reads one chunk; top(5, '-value') on the same file has to read every chunk, because each one beats the last.

In the dataset benchmark, “top 10 rows by price” read 1 chunk of 239, so it took about the same time at any size: 10 ms over 100M rows and 11 ms over a billion, against 87 ms and 827 ms for DuckDB 2.0.

Streams

Streams keep zone maps up to date as batches arrive, per block of 16,384 rows in each worker. On a live stream of 7M rows (7 workers), “last minute” and “last 10 minutes” took 0.21 to 0.25 ms, against 1.6 to 1.7 ms for a full scan (6 to 8 times faster).

How much it saves

npm run bench:zones in the Vectro repository, on an in-memory table of 10M time-ordered rows, one every 10 ms, Apple M1 Pro.

Query	With zone maps	Without	Faster
Revenue, last hour	0.68 ms	4.00 ms	5.9×
Revenue, last 6 hours	1.13 ms	3.22 ms	2.8×
One hour in the middle, EU only	0.42 ms	3.73 ms	8.8×
By region, last hour	1.16 ms	5.00 ms	4.3×
Top 10 orders, last hour	4.15 ms	5.82 ms	1.4×

The gain is largest when the filter keeps a small, contiguous part of the table. A filter that matches rows spread through the whole table runs at the speed of a normal scan; zone maps cost nothing then beyond the first build.