Geospatial and Time-Series Data Questions

Direct answer

Do not try to index the petabyte. Build a narrow trip-starts table (one row per trip: ID, start time, start latitude/longitude and a start-cell key), partition it by start hour, and sort the data inside each partition by a spatial cell key such as a precision-6 geohash. A query then prunes on two axes before reading anything: the time predicate selects one hour's partition, and the cell predicate (start_cell IN the 9 cells around the point) lets the engine skip every file or block (the physical chunk a partition is split into on disk, called a file in an open table format such as Iceberg or Delta, or a block in a warehouse's own storage; both are pruned the same way) whose min/max cell range cannot match. Only the remaining candidates get the exact 500 m distance check. The costs are a derived column computed at write time, a periodic re-sort (compaction) of recently written partitions, and a small duplicate table; in return, the bytes scanned per query drop by several orders of magnitude.

How warehouses make "without a full scan" possible

Key terms.

• Columnar storage stores each column separately, so a query reading 5 columns of a 100-column table reads only those 5.
• Partition pruning: the table is split into partitions by a column (here, start hour); a filter on that column skips whole partitions.
• Clustering / sort order and zone maps: inside a partition, data is written in files or blocks, and the engine keeps each block's minimum and maximum per column (a zone map, also called min/max statistics). If rows are sorted by a key, a filter on that key skips every block whose range excludes it. BigQuery clustering, Snowflake clustering keys, Redshift sort keys and the sort orders of open table formats (a metadata layer over plain data files that tracks each file's schema, partitions and per-column min/max statistics, so a query engine can plan which files to read without opening them) such as Apache Iceberg and Delta Lake (which manage Parquet columnar files) are all versions of this.
• A geohash turns a location into a string where each extra character is a smaller cell and nearby points usually share a prefix, so sorting by it keeps nearby trips in the same blocks.

The trick is to turn a 2D spatial predicate into a 1D key the engine can prune on, because zone maps work on one column at a time: min/max on latitude and longitude separately prunes poorly (a thin latitude band spans the whole planet in longitude).

The design

Tables.

trip_starts partitioned by start_ts truncated to the hour (or by day with hour as the leading sort key if the engine caps partition counts: most engines slow down or refuse to plan a query once a table has too many partitions, commonly somewhere in the thousands), then sorted by (start_geohash6, start_ts).

Query shape.

SELECT t.trip_id, t.start_ts
FROM trip_starts t
WHERE t.start_ts >= TIMESTAMP '2026-06-12 17:00:00'
  AND t.start_ts <  TIMESTAMP '2026-06-12 18:00:00'
  AND t.start_geohash6 IN (:c1, :c2, :c3, :c4, :c5, :c6, :c7, :c8, :c9)
  AND ST_DWITHIN(ST_GEOGPOINT(t.start_lon, t.start_lat),
                 ST_GEOGPOINT(:lon, :lat), 500);

(ST_GEOGPOINT and ST_DWITHIN are BigQuery's spellings; each warehouse has equivalents.) A search on only the point's own cell would miss a trip that started a few metres away but just across a cell edge, so the query expands to a 3x3 block: the point's precision-6 geohash cell and its 8 neighbours, computed by the client. A precision-6 cell is about 0.61 km tall everywhere and, at 40 degrees latitude, about 0.94 km wide (360 / 2^15 degrees of longitude times cos(latitude)), so a 500 m circle around any point inside the centre cell stays inside the 3x3 block; the general rule is that a 3x3 block only fully covers the search circle when the radius is no larger than the cell's shortest side. The width is 1.222 km times cos(latitude), which drops below 500 m above about 65.8 degrees latitude; beyond that the client should switch to precision 5.

Worked example: bytes scanned

Inputs (stated assumptions, not measurements): 3 years of history in trips totalling 1 PB; 20,000,000 trips per day; trip_starts rows of about 60 bytes compressed.

With the hour partition selected and blocks sorted by geohash, the 9 target cells are a tiny slice of a global service's cells, so the engine reads the one or few blocks whose cell ranges overlap them. Estimate: a compacted 50 MB hourly partition typically lands in on the order of 10 to 20 files of a couple of megabytes each; because file order follows the geohash sort, the 9 adjacent target cells usually fall inside one file, occasionally two if they straddle a file boundary, so the engine reads on the order of a few megabytes instead of 50 MB, and many orders of magnitude less than a petabyte. Exact numbers depend on the engine's block size, so measure them with the engine's "bytes processed" figure on a real query rather than trusting this estimate.

Wider windows scale linearly: a one-week window reads 168 hourly partitions, still pruned by cell within each.

Trade-offs: latency vs storage vs write-time work

The committed option wins because it serves both the time and the space predicate with the engine's cheapest mechanism (block skipping) and costs almost nothing to store. The write-time price is clustering maintenance: rows arriving late or out of order land in new, unsorted files, which widens their min/max ranges and silently degrades pruning. Schedule compaction that re-sorts each partition once it stops receiving writes (for example 24 hours after the hour closes), and monitor the bytes-scanned trend for a fixed benchmark query.

Pitfalls

• Sorting by latitude then longitude looks spatial but prunes badly, because every longitude sits inside a narrow latitude band.
• Cell key without the exact check returns false positives up to the block's corners; the ST_DWITHIN refinement is required for correctness.
• Wrapping the column in a function (WHERE ST_GEOHASH(point) IN ... computed at query time) defeats pruning; the key must be a stored column.
• Time zones: partition on UTC and convert analyst input, or a local-time "one hour" straddles two partitions.
• What would change the design: if analysts mostly asked city-level or polygon questions rather than 500 m point questions, cluster by city_id then time instead; if the dominant query were "trips passing near a point" rather than starting there, index route cells (a trip-to-cells table) instead of start cells.

Direct answer

A relational database like Postgres is built to store, update and join individual rows correctly; a time-series database (TSDB) is built for one very specific shape of data: huge volumes of timestamped measurements that are appended once, never updated, read back as ranges and aggregates over time, and deleted wholesale when they age out. Because it can assume that shape, a TSDB stores each series as a compressed stream (on the order of 1 to 2 bytes per point, against about 84 bytes per point measured below for a plain indexed Postgres table), expires old data by dropping whole blocks, and answers "average over the last hour, per service" without touching individual rows. So metrics go in the TSDB, and orders, users, configuration and anything you update or join goes in Postgres.

How the two are built differently

Key terms. A series is one metric for one source, such as CPU usage for host web-3; a series is a list of (timestamp, value) points. Labels (or tags) are the key-value pairs that identify it (host="web-3", region="eu"). Retention is how long data is kept before deletion.

Why the compression actually works, in five points. Take a CPU metric scraped every 15 seconds, at timestamps 0, 15, 30, 45 and 60 seconds, with values 42.0, 42.0, 43.5, 43.5 and 43.5. The raw deltas between timestamps are 15, 15, 15, 15; from the second delta onward the delta-of-delta (the change in that delta) is 0, 0, 0, because the interval never changes, and this scheme encodes a delta-of-delta of 0 as a single bit. For the values, XOR-ing each one with the one before it: 42.0 XOR 42.0 is 0 (identical numbers have identical bits, so every bit cancels out), encoded as a single bit; 43.5 XOR 43.5 is 0 again for the last two points. Only the one real change, 42.0 XOR 43.5, is non-zero: bit for bit it comes out to 0x0000c00000000000, which has 16 leading zero bits, 46 trailing zero bits, and just 2 bits of real information sandwiched between them, so the scheme stores a short header plus those 2 bits (well under 20 bits total) instead of a fresh 64-bit value. Three of the four points in this tiny run cost 1 bit each and the one real change costs a few bits, against 64 bits apiece stored raw: that is where the 1.37-bytes-per-point average below comes from, not a black box.

Worked example: the storage difference, measured

One million metric samples stored the "obvious" way in Postgres 16 (timestamp, series ID, value, plus an index on series and time so range queries are fast):

CREATE TABLE metrics_rows (ts timestamptz NOT NULL, series_id int NOT NULL, value double precision NOT NULL);
INSERT INTO metrics_rows
SELECT timestamptz '2026-01-01' + (i/100) * interval '15 seconds', i % 100, (i % 1000)::float8
FROM generate_series(0, 999999) i;
CREATE INDEX metrics_rows_series_ts ON metrics_rows (series_id, ts);
VACUUM ANALYZE metrics_rows;
SELECT pg_relation_size('metrics_rows'), pg_indexes_size('metrics_rows'), pg_total_relation_size('metrics_rows');

52183040|31563776|83787776

That is 52.2 bytes per sample for the table plus 31.6 bytes for the index: 83.8 bytes per sample. The raw information is 16 bytes (an 8-byte timestamp and an 8-byte value); the rest is per-row overhead and indexing. Facebook's Gorilla paper (a published engineering write-up describing an in-memory TSDB; the delta-of-delta and XOR scheme walked through above is what it introduced, and most modern TSDBs copied it) reported an average of about 1.37 bytes per point with that scheme. At that ratio:

About 61 times less storage, before any downsampling, for a modest 100,000-series fleet scraped every 15 seconds. (The Postgres figure is measured above; the 1.37 bytes is the paper's reported average on Facebook's data, so your ratio will vary with how noisy your values are.)

What goes where, concretely

Logs are a third case: they are time-oriented but consist of text events with many unique fields, so they go in a log store (Elasticsearch, a full-text search engine, or its open-source fork OpenSearch; Loki, a log-aggregation tool that indexes only the labels and keeps the text itself cheap to store; or a columnar warehouse), not in either of these. Prometheus-style TSDBs deliberately store only numbers.

Trade-offs and the middle option

• TimescaleDB (a Postgres extension that partitions a table into time chunks and compresses older chunks column-wise) is the right choice when the time-series data must be joined with relational data using SQL, or when the team wants one database to operate. It closes most of the storage gap with compression, at the cost of running and tuning Postgres at metrics volume.
• A dedicated TSDB wins for infrastructure and application metrics at fleet scale: the monitoring ecosystem (scrapers, alerting rules, Grafana, the dashboarding tool most teams use to chart this data) is built around it, and it should keep working when your main database is the thing that is down.
• The weakness of a TSDB is everything outside its shape: no transactions, no joins, poor at high-cardinality identifiers (a label per user ID creates one series per user and exhausts memory), and awkward for correcting historical data.
• Recommendation for the colleague: metrics in the TSDB, business entities in Postgres, logs in a log store, and use exemplars (individual raw requests a monitoring tool attaches to a metric point as a sample) or trace IDs (identifiers that let you follow one request across every service it touched) to link a spike on a graph to the specific requests behind it.

Direct answer

First measure where the tail latency comes from (index lookup, reading chunks, the compressed blocks of consecutive samples a time-series engine actually stores and reads off disk, decoding, aggregation, or one slow shard among many, a shard being one partition of the data and the node that serves it, so a query spanning many shards waits on whichever one is slowest), because the fix differs for each. The biggest wins for aggregations over thousands of series (a series is one metric name plus one exact set of labels, the key/value tags such as service="checkout" attached to it) are almost always: pre-aggregate (recording rules, continuous aggregates, a warehouse or TSDB feature that keeps a rollup automatically up to date as new raw rows arrive rather than a job you schedule yourself, or rollups so the query reads 50 series instead of 20,000), read coarser data for long ranges (5-minute or 1-hour rollups), split and cache query results by time, and cut fan-out stragglers (fan-out: sending one query out to many shards or series in parallel; a straggler is the one shard that answers much slower than the rest and so decides the whole query's latency) with hedged requests. Index and partition tuning come next. Each of these costs little storage compared with the raw data.

Tail latency means the slow end of the latency distribution, usually p99 (99th percentile: 1 in 100 queries is slower). A rollup (downsampled table) stores one aggregated point per series per interval (for example a 5-minute min, max, sum and count) instead of every raw sample. A recording rule is a query the TSDB (time-series database) runs on a schedule, storing its result as a new, much smaller series.

Step 1: diagnose before optimising

Break one slow query into stages using the engine's query statistics (Prometheus-compatible engines and ClickHouse both expose per-query stats such as series touched, samples or rows read, and bytes read):

Why fan-out makes the tail worse: if each of n shards is independently slow 1% of the time (p = 0.01), the query waits for the slowest shard, so

With 50 shards, about 39.5% of queries hit at least one shard's p99. With 10 shards it is 9.6%. A per-shard 1-in-100 event now hits roughly 2 in 5 queries.

Step 2: schema

• Cut cardinality (cardinality: the number of distinct series a metric produces, driven by how many distinct label-value combinations exist). Drop labels no dashboard groups by (pod UID, request ID, full URL path). Fewer series means fewer index entries and chunks to open.
• Pre-aggregate the hot query. If a dashboard always shows sum by (service) (rate(http_requests_total[5m])) (read: for each service, the average per-second rate of the http_requests_total counter over the trailing 5 minutes, summed across every series for that service), store that as a recording rule or continuous aggregate. 20,000 series collapse to 50.
• Keep rollups mergeable: store sum and count (and min and max), never only a pre-computed average, so you can combine rollups correctly across hosts and intervals.

Step 3: query rewriting

• Replace regex matchers (path=~".*", a label matcher that pattern-matches against every value of the path label instead of picking one exact value, so the engine has to check it against every series) with equality matchers on low-cardinality labels.
• Aggregate as early as possible (sum by (service) inside the subquery, not after joining).
• Align the query step (in PromQL, the spacing between the evaluated points a query returns, for example one point every 30 seconds) to the rollup interval, and align start and end times to step boundaries, so identical dashboards produce identical, cacheable queries.
• Pick the resolution from the range: a 7-day panel does not need 15-second samples on an 800-pixel-wide chart.

Step 4: storage engine

• Time partitioning so the planner opens only the partitions in range.
• Inverted index from label value to series IDs (Prometheus-style postings lists: the per-label-value list of which series IDs carry that label, the same idea a search engine uses to find every document containing a given word), or a sort key starting with the grouping columns (ClickHouse ORDER BY (metric, service, ts)) so matching rows are contiguous.
• Tiered resolutions: raw for the last few days, 5-minute rollups for weeks, 1-hour rollups for a year. The query layer routes by range.
• Bigger, compacted blocks so a 7-day query opens a handful of files rather than hundreds.

Step 5: caching and fan-out control

• Split long queries by day and cache each day's result; only the current, still-changing day is recomputed on refresh.
• Chunk and index caches (memcached, a widely used in-memory key-value cache, or local SSD) in front of object storage.
• Hedged requests: if a shard has not answered by its p95 latency, send the same request to a replica and take whichever answers first. This targets exactly the straggler math above, at the cost of a few percent extra load.
• Per-query limits (max series, max samples) so one runaway query cannot starve everyone else's tail.

Worked example

A dashboard panel: sum by (service) (rate(http_requests_total[5m])) over 7 days, matching 20,000 series scraped every 15 s.

• Raw samples read: 20,000 × (7 × 86,400 / 15) = 806.4 million samples.
• From a 5-minute rollup: 20,000 × (7 × 86,400 / 300) = 40.32 million, a 20x reduction.
• From a recording rule producing 50 per-service series at 5-minute resolution: 50 × 2,016 = 100,800 points, 8,000 times fewer than raw.

Storage cost of the recording rule: 50 extra series, against the 20,000 it summarises, a 0.25% increase. That is why pre-aggregation is the first lever, not the last.

Trade-offs and pitfalls

• Rollups lose detail. A 5-minute average hides a 20-second spike; keep max in the rollup and keep raw data for recent incident debugging.
• Recording rules only help known queries. Ad-hoc exploration still hits raw data, so pair them with query limits.
• Caching the latest interval returns stale data; exclude the most recent few minutes from the cache or give it a short TTL (time-to-live).
• Hedging doubles load on an overloaded cluster if the slowness is global rather than one straggler; cap hedges as a small percentage of requests.
• Common wrong turn: adding more shards. That spreads storage but, by the formula above, can make the tail worse for fan-out queries.

Direct answer

remote_write is a Prometheus setting that streams every sample Prometheus scrapes (scraping: Prometheus pulling the current value of each metric from a target on a timer, rather than the target pushing to it), in near real time, to an external HTTP endpoint such as Thanos Receive, Grafana Mimir, Cortex or VictoriaMetrics, four open-source systems that all fill the same role (accept remote_write traffic and store it long-term), so pick whichever your team can operate; they are largely interchangeable here. remote_read is the reverse direction: Prometheus asks a remote endpoint for the raw samples that match some label selectors (a filter such as service="checkout" that picks out which series to return, the same syntax you write inside {...} in a query) and a time range, then evaluates the PromQL (Prometheus's own query language) query itself. You use them to get retention beyond one server's disk, a global view across many Prometheus servers, and durability that survives losing a node. I prefer a remote TSDB (time-series database, defined below) when history has to outlive a single server or queries have to span clusters; I prefer several independent Prometheus servers when each team's queries and alerts are local and a few weeks of history is enough.

A few terms first. A TSDB (time-series database) stores values indexed by time. A series is one metric plus one exact set of labels, for example http_requests_total{service="checkout", code="500"}. A sample is one (timestamp, value) point in a series. The WAL (write-ahead log) is the append-only file Prometheus writes every sample to before it builds its on-disk blocks.

How remote_write works

flowchart LR
  T[Scrape targets] --> P[Prometheus]
  P --> W[(Local WAL + TSDB)]
  W --> Q[Remote-write queue shards]
  Q -->|snappy protobuf over HTTP| R[(Remote TSDB)]
  R --> O[(Object storage)]
  G[Grafana] --> R

• Each remote_write destination gets its own queue that reads from the WAL, batches samples and sends them as snappy-compressed protocol buffers (protobuf: a compact binary encoding for structured data, smaller and faster to parse than JSON; Snappy is a fast compression algorithm layered on top of it) over HTTP. Remote Write 1.0 is the stable protocol; 2.0 is an experimental spec you opt into with protobuf_message: io.prometheus.write.v2.Request.
• The queue fans out over parallel shards (concurrent senders). queue_config defaults in the current docs: capacity 10000 samples buffered per shard, min_shards 1, max_shards 50, max_samples_per_send 2000, batch_send_deadline 5s. Prometheus scales shards up and down between min and max from observed throughput.
• write_relabel_configs lets you drop or rewrite series before they leave the server. This is the main cost lever: you rarely need every high-cardinality debug series in long-term storage.
• Agent mode (--agent flag) runs Prometheus as a scrape-and-forward agent: it keeps only a WAL, sends everything by remote_write, and cannot be queried or evaluate rules locally. It fits edge clusters that should not hold state.

How remote_read works

• Prometheus sends selectors and a time range to the remote endpoint, gets raw samples back, and runs all PromQL evaluation locally. The docs call out the consequence: every sample the query touches must be loaded into the querying Prometheus first, so a long-range query over many series can exhaust its memory.
• read_recent defaults to false: for time ranges the local TSDB should fully cover, Prometheus does not ask the remote at all.
• required_matchers restricts the remote to queries that include specific label matchers, and filter_external_labels (default true) adds this server's external labels (fixed key/value labels, set once in this server's own config rather than coming from any scrape, such as cluster or replica, that get attached to every series this server exposes so a downstream system can tell which server data came from) as selectors.
• In practice most teams query the remote system's own PromQL API (Thanos Querier, Mimir's query frontend) from Grafana instead of remote_read, because those engines evaluate queries in a distributed way.

Use cases and what each buys you

Worked example: when one server stops being enough

A platform has 1,000,000 active series scraped every 15 s.

• Ingest rate: 1,000,000 / 15 = 66,667 samples/s.
• The Prometheus storage docs estimate 1 to 2 bytes per sample on disk. Per day that is 66,667 × 86,400 × 1 to 2 B = 5.76 to 11.52 GB/day.
• The default local retention is 15 days: 86 to 173 GB. Fine on one server.
• The capacity team wants 1 year: 2.1 to 4.2 TB on a single server's disk, where losing that disk loses the year, and every year-long query loads its raw samples into one process. This is the point where a remote TSDB backed by object storage is the right call.

Sizing the remote_write queue for the same server: at full batches of 2,000 samples, 66,667 / 2,000 = 33.3 requests/s. If one request takes 100 ms round trip (an assumption; measure yours), one shard can send 10 requests/s, so about 4 shards keep up, well under the default ceiling of 50. The docs state shard memory is proportional to shards × (capacity + max_samples_per_send) samples, and say the defaults (10,000 + 2,000 = 12,000 samples per shard) keep that under 2 MB per shard; that 2 MB figure is the Prometheus project's own stated bound, not something derived here from a bytes-per-sample assumption. It is a different, much larger per-sample cost than the roughly 1 to 2 bytes per sample used above for on-disk storage: a sample waiting in the queue is a live Go value with its label set and pointers attached, not the compressed on-disk encoding, which is why 12,000 in-flight samples cost under 2 MB (roughly 170 bytes each) while the same 12,000 samples compressed on disk, at 1 to 2 bytes each, would cost roughly two orders of magnitude less. The docs also recommend capacity at 3 to 10 times max_samples_per_send.

Pitfalls

• Outages longer than about 2 hours lose data on the remote side. Prometheus compacts its local head block (the in-memory, still-open portion of the TSDB) into a persistent 2-hour block by default, and once a block is written it truncates the matching WAL segments; the remote_write queue can only retry samples still sitting in the WAL, so once the endpoint has been down long enough for that 2-hour compaction to happen, whatever it had not yet sent is truncated away with it. The docs say failures are retried without loss unless the endpoint stays down for more than 2 hours; after that the WAL is compacted and unsent samples are gone from the remote copy. Alert on the lag between the newest sample written to the WAL and the newest sample the remote acknowledged (the remote-write lag metrics), not just on HTTP errors.
• Memory growth. Remote write caches series ID to label mappings for every series in the WAL, plus the shard buffers. Budget extra RAM before enabling it on a large server.
• Egress (the cost of data leaving your network to reach the remote endpoint, which most cloud providers bill separately from compute) and ingest cost scale with cardinality. Sending every label combination to a paid backend is where bills explode. Use write_relabel_configs to drop unused series.
• Missing external labels. Without a cluster and replica label on each server, the remote cannot tell two clusters' up series apart or deduplicate an HA pair.
• Alerting through the remote path. Keep critical alerts evaluated on the local Prometheus (or a highly available ruler, the component, run standalone in systems like Mimir or Cortex, that evaluates alerting and recording rules independently of any single Prometheus server) so a remote-storage incident does not silence your paging.
• Heavy remote_read queries can take down the Prometheus that issued them, since it holds all raw samples in memory.

Remote TSDB vs multiple Prometheus servers

My default recommendation for a growing organisation: one Prometheus (or HA pair) per cluster doing scraping and local alerting, remote_write to one horizontally scalable remote TSDB for long-term and global queries. What flips it: a small organisation with one cluster and 30-day needs should not take on the operational cost of a distributed TSDB at all.

Direct answer

A purpose-built TSDB like Prometheus indexes series: an inverted index maps each label pair (such as service="checkout") to a sorted list of the series that carry it, and within each series the data is already in time order, so a time range is just "which chunks overlap". A columnar store like ClickHouse indexes row ranges: data is sorted by a key you choose, and a sparse primary index keeps one entry per block of 8,192 rows (a "granule"), plus optional data-skipping indexes that store small summaries (min/max, a set of values, or a bloom filter, a compact structure that can say a value is definitely NOT in a block but can only ever say it MIGHT be in one, never guaranteeing a match: it produces false positives, flagging a block that turns out not to contain the value, but never a false negative, so it never skips a block that actually does) per block. For time-range aggregations use time partitioning plus a sort key ending in time; for tag lookups use an inverted index (TSDB) or a sort key starting with the tag (columnar); for high-cardinality filters use a bloom-filter skip index in columnar, and keep unbounded values out of TSDB labels entirely.

TSDB: inverted index over series

In the Prometheus block format, the index file has a symbol table (every distinct label string stored once, referenced elsewhere by a small integer ID instead of repeating the text, which keeps the postings lists below compact), a series section (each series' labels plus references to its compressed chunks with their min and max timestamps) and postings: for each label name and value, a monotonically increasing list of series references (each next ID in the list is larger than the last, which is what lets the merge-intersect below run in a single linear pass instead of needing to re-sort). A query like http_requests_total{service="checkout", code="500"} intersects the postings lists. A tiny model of it:

# A tiny inverted index in the style of a TSDB block: label pair -> sorted series IDs
series = {
    1: {"__name__": "http_requests_total", "service": "checkout", "code": "200"},
    2: {"__name__": "http_requests_total", "service": "checkout", "code": "500"},
    3: {"__name__": "http_requests_total", "service": "search",   "code": "500"},
    4: {"__name__": "http_requests_total", "service": "search",   "code": "200"},
    5: {"__name__": "cpu_seconds_total",   "service": "checkout", "code": "none"},
}
postings = {}
for sid in sorted(series):
    for k, v in series[sid].items():
        postings.setdefault((k, v), []).append(sid)   # stays sorted: IDs added in order

def intersect(a, b):
    """Merge-intersect two sorted lists in O(len(a) + len(b))."""
    i = j = 0; out = []
    while i < len(a) and j < len(b):
        if a[i] == b[j]:
            out.append(a[i]); i += 1; j += 1
        elif a[i] < b[j]:
            i += 1
        else:
            j += 1
    return out

q = [("__name__", "http_requests_total"), ("service", "checkout"), ("code", "500")]
result = postings[q[0]]
print(q[0], result)
for pair in q[1:]:
    print(pair, postings[pair])
    result = intersect(result, postings[pair])
print("matching series:", result, series[result[0]])

Output:

('__name__', 'http_requests_total') [1, 2, 3, 4]
('service', 'checkout') [1, 2, 5]
('code', '500') [2, 3]
matching series: [2] {'__name__': 'http_requests_total', 'service': 'checkout', 'code': '500'}

Because the lists are sorted, the intersection is a linear merge. Time is handled at two levels: each block covers a known time span (2 hours when first written, larger after compaction), and each chunk records its min and max time, so a range query only decompresses overlapping chunks.

InfluxDB 1.x and 2.x use the same idea (the TSI, time series index, mapping tags to series). InfluxDB 3 moved to Parquet files on object storage, which puts it closer to the columnar model below.

Columnar: sparse primary index plus skip indexes

This ClickHouse script loads 10 million rows (1,000 hosts, one row per host per second for about 2.8 hours), sorted by (host, ts), with a bloom-filter skip index on the high-cardinality trace_id. Run with clickhouse local --multiquery < file.sql (tested on 24.10):

CREATE TABLE samples (
    -- LowCardinality(String) dictionary-encodes the column: each distinct string is stored once
    -- and referenced by a small integer, which pays off here because only 1,000 distinct hosts
    -- repeat across 10 million rows.
    host     LowCardinality(String),
    trace_id String,
    ts       DateTime('UTC'),
    value    Float64,
    INDEX trace_bf trace_id TYPE bloom_filter(0.01) GRANULARITY 1
) ENGINE = MergeTree
PARTITION BY toDate(ts)
ORDER BY (host, ts);

INSERT INTO samples
SELECT concat('host-', toString(number % 1000)),
       hex(cityHash64(number)),
       toDateTime('2026-03-01 00:00:00', 'UTC') + intDiv(number, 1000),
       number % 97
FROM numbers(10000000);

OPTIMIZE TABLE samples FINAL;

SELECT count() AS parts, sum(rows) AS total_rows, sum(marks) AS marks FROM system.parts WHERE table = 'samples' AND active
FORMAT PrettyCompactMonoBlock;

EXPLAIN indexes = 1
SELECT avg(value) FROM samples
WHERE host = 'host-42' AND ts >= '2026-03-01 01:00:00' AND ts < '2026-03-01 02:00:00';

EXPLAIN indexes = 1
SELECT count() FROM samples WHERE trace_id = hex(cityHash64(1234567));

Output, excerpted (... marks omitted lines; in the omitted Min-Max and Partition sections every query reads 1221/1221 granules):

   ┌─parts─┬─total_rows─┬─marks─┐
1. │     1 │   10000000 │  1222 │
   └───────┴────────────┴───────┘
...
      Parts: 1 | Granules: 1
...
        PrimaryKey
          Keys:
            host
            ts
          Condition: and((ts in (-Inf, 1772330399]), and((ts in [1772326800, +Inf)), (host in [\'host-42\', \'host-42\'])))
          Parts: 1/1
          Granules: 1/1221
          Search Algorithm: binary search
...
         Parts: 1 | Granules: 13
...
           PrimaryKey
             Condition: true
             Parts: 1/1
             Granules: 1221/1221
           Skip
             Name: trace_bf
             Description: bloom_filter GRANULARITY 1
             Parts: 1/1
             Granules: 13/1221

Reading it:

• 10,000,000 / 8,192 = 1,220.7, so 1,221 granules; the index has one mark per granule (a mark is the index's one recorded entry per granule: the row number and file offset where that granule starts, letting ClickHouse jump straight to it instead of scanning from the beginning), plus a final mark, hence 1,222. That is the "sparse" part: 1,222 entries index 10 million rows.
• Query 1 (one host, one hour, 3,600 rows): the primary key narrows to 1 of 1,221 granules by binary search on (host, ts). Partition and min-max pruning did nothing here because all data is on one day; on a table with many days they would discard whole days first.
• Query 2 (one trace ID, a value not in the sort key): the primary index cannot help (Condition: true), but the bloom filter rules out all but 13 of 1,221 granules. One granule really contains the value; the others are expected false positives from the 1% rate the index was built with (1% of 1,221 is about 12).

Which structure for which query

Trade-offs

• Inverted index cost grows with series count. Postings and the in-memory head index are proportional to active series, so a label with millions of values degrades the whole TSDB, not just queries on that label.
• Sparse index cost is nearly fixed, but it only helps filters on the leading sort-key columns. A filter on the third sort column after two high-cardinality ones barely prunes; that is why skip indexes exist, and why they must be measured: a bloom filter on a value present in every granule costs space and saves nothing.
• Choosing the sort key is choosing your fast queries. (host, ts) makes per-host queries cheap and "all hosts, last minute" a scan of every host's range; (ts, host) inverts that. Pick the dominant query, and serve the other with a projection (a second, automatically maintained copy of the table stored with a different sort order, so a query that does not match the primary ORDER BY can still hit a sorted copy instead of scanning) or a rollup.