Compound sort keys for multi-series tables

[bluestreak01]

Summary

Support compound sort keys at the storage level, allowing tables to be ordered by N key columns followed by the designated timestamp within each partition. Range indexes provide O(1) navigation to any segment. The query engine takes full advantage of this layout — ASOF JOIN, GROUP BY, and filtered scans exploit contiguous sorted runs at each level of the key hierarchy.

Current Limitation

Tables are ordered by designated timestamp only. When multiple series (sensors, symbols, devices) are stored in a single table, rows are interleaved:

Partition 2026-01-01:
  imu       t1
  lidar     t1
  imu       t2
  gps       t1
  lidar     t2
  imu       t3
  ...

This layout means:

• Filtering by series scans through unrelated rows
• ASOF JOIN between series within the same table cannot merge-join
• Compression is poor — interleaved values from different series break delta and RLE encoding
• Users work around this by creating many tables (one per series), which doesn't scale

With Compound Sort Keys

The sort key is an ordered tuple of N columns plus the designated timestamp. Data is clustered hierarchically — each level nests within the one above.

Two-level: (sensor, ts)

CREATE TABLE joint_telemetry (
  ts TIMESTAMP,
  joint SYMBOL,
  position DOUBLE,
  velocity DOUBLE,
  torque DOUBLE
) TIMESTAMP(ts) PARTITION BY HOUR
  ORDER BY (joint, ts);

Partition 2026-01-01:
  gps    t1, t2, t3, ...     ← contiguous, sorted by ts
  imu    t1, t2, t3, ...     ← contiguous, sorted by ts
  lidar  t1, t2, t3, ...     ← contiguous, sorted by ts

Each series forms a contiguous sorted run. The query engine can seek directly to the relevant segment.

Three-level: (episode, sensor, ts)

CREATE TABLE telemetry (
  ts TIMESTAMP,
  episode_id SYMBOL,
  sensor SYMBOL,
  value DOUBLE
) TIMESTAMP(ts) PARTITION BY DAY
  ORDER BY (episode_id, sensor, ts);

Partition 2026-01-15:
  ep_0047 / force   / t1, t2, t3, ...
  ep_0047 / imu     / t1, t2, t3, ...
  ep_0047 / joints  / t1, t2, t3, ...
  ep_0048 / force   / t1, t2, t3, ...
  ep_0048 / imu     / t1, t2, t3, ...
  ep_0048 / joints  / t1, t2, t3, ...
  ...

All data for one episode is contiguous. Within an episode, each sensor is contiguous and sorted by timestamp. This enables:

Query	Behavior
All data for episode X	Read one contiguous range — sequential scan
IMU data for episode X	Seek to episode, then sensor sub-segment
ASOF JOIN across sensors within episode X	Merge join on sorted sub-segments
Export episode X as Parquet	Sequential read, minimal I/O

N-level generalization

The sort key is a general tuple (key1, key2, ..., keyN, ts). The storage engine sorts by comparator chain — no hardcoded limit on depth. Range indexes and segment metadata are maintained at each level.

-- Four-level: site → robot → sensor → ts
ORDER BY (site, robot_id, sensor, ts)

In practice, 2–3 levels cover the vast majority of use cases. Deeper keys produce finer-grained segments with diminishing returns.

Storage

The compound sort key defines the physical ordering of rows within partitions. This is a storage-level feature — column files are reordered so that rows sharing key prefix values are contiguous and internally sorted by the remaining keys and timestamp.

Aspect	Description
Partition-internal layout	Rows sorted by (key1, key2, ..., keyN, ts) within each partition
Segment hierarchy	Each level of the key produces nested segments with known offsets
Range indexes	O(1) lookup from key values to segment offset ranges (see below)
Write path	Append to WAL unsorted. Background compaction sorts into compound key order. Follows the append-then-compact model from #112.
Compression	Contiguous same-key data compresses significantly better — monotonic timestamps delta-encode well, similar value ranges improve dictionary and RLE encoding

Range Indexes

Range indexes map compound key values to contiguous offset ranges within each partition. They are the navigation structure that makes compound sort keys practical — without them, finding a segment would require binary search through the data.

Structure

For a table with ORDER BY (episode_id, sensor, ts):

Range Index (partition 2026-01-15):

Level 1 — episode_id:
  ep_0047  →  rows 0–15000,      ts_min=14:00:00, ts_max=14:42:17
  ep_0048  →  rows 15001–28000,  ts_min=14:38:05, ts_max=14:59:59

Level 2 — sensor (within each episode):
  ep_0047 / force   →  rows 0–5000
  ep_0047 / imu     →  rows 5001–10000
  ep_0047 / joints  →  rows 10001–15000
  ep_0048 / force   →  rows 15001–20000
  ep_0048 / imu     →  rows 20001–25000
  ep_0048 / joints  →  rows 25001–28000

Per segment entry: start offset, end offset, row count, ts_min, ts_max. One entry per distinct key value per level per partition.

What range indexes enable

Operation	Without range index	With range index
Seek to ep_0047/imu	Binary search through sorted data	O(1) lookup
"Does this partition contain ep_0047?"	Read data or scan	Index check, no data read
"How many rows for sensor X in episode Y?"	Count by scanning	Read from index metadata
Partition pruning by key values	Only by timestamp range	By any key column — skip partitions that don't contain the target key values
Query cost estimation	Unknown segment sizes	Exact row counts per segment

How they differ from traditional indexes

	Traditional symbol index	Range index
Maps	Value → scattered row IDs	Value → contiguous offset range
Assumes	Data is unordered	Data is sorted by compound key
Size	One entry per row per indexed value	One entry per distinct key value per partition
Use case	Point lookups in unsorted data	Segment navigation in sorted data

Range indexes are orders of magnitude smaller than traditional indexes because they exploit the sort order — only boundaries need to be recorded, not individual row positions.

When they are built

During background compaction (#112). When the compactor sorts data into (key1, key2, ..., ts) order, it emits the range index as a side product — it already knows where each segment begins and ends because it is performing the sort. Zero extra I/O cost.

For uncompacted WAL data (not yet sorted), the query engine falls back to scanning. Range indexes apply only to compacted partitions.

Query Engine

The feature ships with query engine support that exploits the compound layout. This is not optional — the storage layout without query integration would not be useful.

ASOF JOIN

Self-joins and cross-series joins within a compound-sorted table become merge operations on contiguous sorted runs:

-- Two-level: merge join on two sorted segments
SELECT *
FROM joint_telemetry AS a
ASOF JOIN joint_telemetry AS b
WHERE a.joint = 'shoulder_left'
  AND b.joint = 'elbow_left';

-- Three-level: merge join within an episode
SELECT *
FROM telemetry AS a
ASOF JOIN telemetry AS b
WHERE a.episode_id = 'ep_0047' AND a.sensor = 'imu'
  AND b.episode_id = 'ep_0047' AND b.sensor = 'force';

The engine uses range indexes to seek directly to the relevant segments and performs a linear merge. Cost is proportional to the matched segments, not the entire table.

Filtered scans

SELECT * FROM telemetry
WHERE episode_id = 'ep_0047' AND sensor = 'imu';

The engine looks up ep_0047 in the level-1 range index, then imu in the level-2 range index within that segment. Direct offset jump, no scanning through unrelated data.

Partition pruning

SELECT * FROM telemetry
WHERE episode_id = 'ep_0047';

Before reading any partition data, the engine checks each partition's level-1 range index. Partitions that don't contain ep_0047 are skipped entirely — no data read required.

GROUP BY

SELECT joint, avg(torque), max(position)
FROM joint_telemetry
WHERE ts IN '2026-01-01'
GROUP BY joint;

Each segment is aggregated independently — good cache locality, vectorization-friendly, parallelizable per segment. Segment boundaries come from the range index.

Ordering guarantee

Queries that return results ordered by a prefix of the compound key can skip sorting — the storage already provides this order.

Benefits

Benefit	Description
Fewer tables	Store hundreds of series in one table instead of one table per series
Better compression	Contiguous same-key data compresses dramatically better with delta, RLE, and dictionary encoding
Faster ASOF JOIN	Merge join on sorted segments instead of hash or scan
Faster filtered scans	Range index lookup instead of scanning entire partition
Partition pruning by key	Skip partitions that don't contain target key values without reading data
Lower I/O	Read only relevant segments from disk or object storage
Simpler data model	One table with key columns instead of hundreds of tables
Episode-native	Multi-level keys make episodes first-class — all data for an episode is one contiguous range

Use Cases

• Robotics — sensor fusion — ORDER BY (joint, ts). One table for all joint telemetry (50+ joints × 1kHz). ASOF JOIN across joints on sorted segments.
• Robotics — episode management — ORDER BY (episode_id, sensor, ts). Training data curation: find episodes by criteria, export complete multi-sensor episodes as Parquet for ML pipelines. All data for one episode is a sequential read.
• Capital markets — ORDER BY (symbol, ts). Per-symbol analytics and cross-symbol ASOF JOIN on sorted segments.
• Fleet telemetry — ORDER BY (device_id, metric, ts). One table per metric category across thousands of devices. Filter by device hits a contiguous segment.
• Multi-site operations — ORDER BY (site, robot_id, sensor, ts). Hierarchical access: all data for a site, all data for a robot within a site, specific sensor on a specific robot.

Trade-offs

• "All keys at time T" queries read across segments rather than a single localized range. Segment metadata (min/max ts per segment) mitigates this with skip logic.
• Background compaction must maintain compound ordering, adding some CPU cost during compaction.
• Key columns should be low-to-moderate cardinality (SYMBOL type). Very high cardinality keys produce many small segments.
• Deeper key hierarchies (3+ levels) produce finer-grained segments. Practical sweet spot is 2–3 levels.

Related

• Reduced write amplification with faster data visibility #112 — Reduced write amplification (provides the append-then-compact model that this feature builds on)
• Compact index storage with variable blocks and compression #115 — Compact index storage (compound sort keys reduce reliance on secondary indexes)
• Bloom filters for high-cardinality column lookups #113 — Bloom filters (complementary for high-cardinality lookups; compound sort keys solve the moderate-cardinality case)
• High-performance GROUP BY for Parquet partitions #102 — Parquet GROUP BY (Parquet row groups could align with segments for pushdown)