Spatial Index Tuning for Provenance Queries

Part of: Storage, Indexing & Query Optimization

Provenance queries have a characteristic shape that generic indexing advice ignores. A compliance officer asking “which lineage events touched this parcel between two dates” issues a query that filters on both a geometry and a time range, then walks derivation edges. If the planner cannot cheaply prune the audit table by bounding box and timestamp first, that query degrades into a sequential scan over millions of immutable lineage rows — acceptable for an ad-hoc report, fatal for an interactive audit dashboard bound by a service-level agreement. Tuning the spatial and temporal indexes behind these access patterns is what keeps evidence retrieval fast enough to be usable under scrutiny.

This guide, part of the Storage, Indexing & Query Optimization section, focuses on PostGIS index selection and tuning for lineage workloads. It assumes you have already laid out an audit table following the PostGIS lineage schema design guidance and now need those tables to answer spatial-temporal provenance queries within a bounded latency budget. We cover when to reach for GiST, SP-GiST, or BRIN, how composite and covering indexes collapse multi-column filters, how to read EXPLAIN ANALYZE output, and how planner statistics decide whether your carefully built index is ever used at all.

The provenance access patterns worth indexing

Before creating any index, characterize the queries that carry an SLA. In a lineage audit table, four patterns dominate. The first is a spatial containment or overlap filter — “events whose footprint intersects this jurisdiction” — expressed with the && bounding-box operator and refined by ST_Intersects. The second is a temporal range — “events between two valid_from timestamps” — which on an append-only table correlates strongly with physical row order. The third is the combination of both, which is the hard case and the one that most benefits from deliberate index design. The fourth is exact-key lookup by dataset UUID, served by an ordinary B-tree.

Indexing is a trade, not a free win. Every index you add slows the high-frequency writes that lineage ingestion generates and consumes storage that must itself be retained. The goal is the minimal index set that turns your SLA-bound read patterns into index scans while leaving write throughput acceptable. That balance is why index type matters: a BRIN index costs a fraction of a GiST index to maintain and store, and on the right column it answers range queries almost as well.

GiST, SP-GiST, and BRIN for spatial and temporal columns

PostGIS ships three access methods relevant here, each suited to a different data distribution.

• GiST is the default and correct choice for the geometry column. It builds a balanced tree of bounding boxes, so overlap queries with && prune the table efficiently regardless of how rows are physically ordered. Use it for polygon footprints and any geometry where extents overlap.
• SP-GiST partitions space rather than bounding it, which makes it strong for large collections of non-overlapping points — think sample locations or sensor coordinates — where a quadtree-style partition is tighter than GiST’s overlapping boxes. It is a targeted optimization, not a default.
• BRIN (Block Range INdex) stores only the min/max value per block range. It is tiny and cheap to maintain, and it shines on columns whose values track physical storage order — precisely the case for a valid_from timestamp in an append-only, immutable lineage table where new rows arrive in time order. On a well-ordered column BRIN answers range queries at a small fraction of a B-tree’s size; on a randomly ordered column it is useless.

The pairing that serves most spatial-temporal provenance queries is a GiST index on the geometry and a BRIN index on the timestamp. The planner combines them with a bitmap AND, prefiltering by bounding box and time block range before the expensive exact predicates run.

Prerequisites

• PostGIS 3.4+ on PostgreSQL 15+ with the postgis extension installed.
• A lineage audit table with a geom geometry(Geometry, 4326) column and a valid_from timestamptz column, populated with a representative row volume.
• ANALYZE run at least once so the planner has statistics, and permission to run EXPLAIN ANALYZE.
• Ability to run CLUSTER or control insertion order if you intend to rely on BRIN.
• A short list of the SLA-bound queries you are tuning for, captured as parameterized SQL.

Step-by-step

1. Baseline the query before indexing

Never tune blind. Capture the current plan and timing so you can prove an index helped. EXPLAIN (ANALYZE, BUFFERS) shows the chosen scan, estimated versus actual rows, and heap buffer reads.

EXPLAIN (ANALYZE, BUFFERS)
SELECT event_id, dataset_uuid, valid_from
FROM lineage_audit
WHERE geom && ST_MakeEnvelope(-71.2, 42.2, -70.9, 42.5, 4326)
  AND valid_from >= '2026-01-01' AND valid_from < '2026-04-01';

A Seq Scan node with a large actual-rows count and high buffer reads is your evidence that an index is warranted.

2. Build the spatial GiST index

Create a GiST index on the geometry column. The && operator in the query is what makes this index eligible; it performs the bounding-box prefilter that cheaply discards non-overlapping rows before ST_Intersects runs the exact test.

CREATE INDEX idx_lineage_geom_gist
    ON lineage_audit USING gist (geom);

3. Build the temporal BRIN index

Add a BRIN index on valid_from. Because the audit table is append-only, rows already arrive in timestamp order, so each block range has a tight min/max and the index prunes date ranges effectively. The pages_per_range parameter controls granularity — smaller ranges mean tighter pruning at the cost of a slightly larger index.

CREATE INDEX idx_lineage_ts_brin
    ON lineage_audit USING brin (valid_from) WITH (pages_per_range = 64);

4. Consider a composite or covering index for hot lookups

For the exact-key pattern, a covering B-tree lets the query return from the index alone via an index-only scan, avoiding heap reads. INCLUDE carries the payload columns without making them part of the search key.

CREATE INDEX idx_lineage_uuid_cover
    ON lineage_audit (dataset_uuid) INCLUDE (valid_from, event_id);

5. Refresh statistics, then re-check the plan

Indexes are only used if the planner’s cost estimates favor them, and those estimates come from table statistics. Run ANALYZE, then re-run the EXPLAIN ANALYZE from step 1 and confirm the plan now shows a Bitmap Index Scan on your GiST and BRIN indexes combined under a BitmapAnd.

ANALYZE lineage_audit;

The tuning GiST and BRIN indexes for lineage how-to works a full before/after measurement of exactly this pair, including how to pick fillfactor and pages_per_range.

Configuration reference

Measuring Before and After, Honestly

Index tuning generates more confident wrong conclusions than almost any other database work, because the measurement is easy to get wrong in ways that flatter the change.

Cache state dominates the first run. A query timed immediately after creating an index runs against a buffer cache warmed by the index build itself, and will look dramatically faster than the same query on a cold cache. Run each variant several times, discard the first, and compare medians — or use EXPLAIN (ANALYZE, BUFFERS) and compare buffer counts rather than wall-clock time, which is less sensitive to what else the machine is doing.

Test data must have production’s shape, not its size. A million synthetic rows with uniformly distributed extents will show a GiST index performing beautifully, because uniform distribution is the easy case. Real lineage extents cluster hard — most agencies process one metropolitan area far more often than anywhere else — and an index that looks fine on uniform data can degrade badly on clustered data. Sample real extents rather than generating them.

The query you time must be the query that runs. Timing a hand-written variant with literal values misses the effect of parameter binding, which changes plan selection in PostgreSQL through generic-plan caching. Test with the same prepared-statement shape the application uses, and check whether a generic plan is being chosen for a query whose selectivity varies widely by parameter.

Record the before-and-after numbers alongside the migration that adds the index, in the commit message or the migration file itself. Six months later, when someone asks whether an index is still earning its write cost, the original measurement is the only thing that makes the question answerable — and pairing it with the current pg_stat_user_indexes scan count turns a debate into an arithmetic problem rather than a matter of anyone’s recollection about which queries used to be slow, which is the form these discussions otherwise take and the main reason speculative indexes survive on a table for years after the query that motivated them was rewritten or removed entirely.

Reading the Plan Before Adding an Index

Work through these in order, because each earlier answer changes the meaning of the later ones. The most common outcome is the third: a query whose plan shows a healthy index scan and which is still slow because the executor is reading megabytes of jsonb payload to satisfy a SELECT * that never examines it. No index change helps, and adding one wastes write throughput to fix a problem that a column list solves.

The second row deserves particular attention on recursive queries, because it is the one people try to fix with indexing and cannot. WITH RECURSIVE plans once and reuses that plan for every iteration, so a cardinality estimate correct at depth one is applied unchanged at depth six where the row count is orders of magnitude larger. The remedy is to bound the recursion — a depth column with an explicit limit — rather than to keep adding indexes the planner was already using correctly.

Common failure modes & mitigations

When to Add an Index, and When Not To

The inverted read/write ratio is what makes lineage indexing different from indexing an analytical table. Each additional index is maintained on every insert, and inserts happen continuously while the queries the index serves may run monthly. A schema carrying nine indexes because each seemed reasonable in isolation can spend more time maintaining them than writing the rows.

Audit pg_stat_user_indexes quarterly and drop indexes with zero scans. Speculative indexes accumulate because dropping one feels riskier than keeping it, but an index that has never been scanned is pure write cost — and if a future query needs it, creating it concurrently takes minutes. Keep the ones the plan actually chooses, and treat the statistics view as the arbiter rather than anyone’s recollection of which queries matter.

Compliance & governance alignment

Fast, predictable retrieval is itself a control objective: an audit is only defensible if the evidence can be produced within the response time regulators or contracts require. Index tuning is how you meet the availability and timeliness expectations that sit alongside the retention rules described in the object storage WORM retention guide.

Treat index design as an ongoing discipline rather than a one-time setup. As lineage volumes grow and query patterns shift, re-baseline with EXPLAIN ANALYZE, prune indexes that no SLA query exercises, and keep statistics fresh so the planner’s choices continue to match the access patterns your audits actually depend on.

Frequently Asked Questions

Related

• Tuning GiST and BRIN Indexes for Lineage — the measured tuning procedure
• PostGIS Lineage Schema Design — the tables these indexes cover
• Spatial Partitioning for Lineage Tables — pruning before indexing
• Storage, Indexing & Query Optimization — reading a lineage execution plan
• Part of: Storage, Indexing & Query Optimization