SP-GiST Partitioned Search Structures and BRIN for Physically Correlated Huge Tables

Learning outcomes

ServiceHub's next two workloads look unrelated: network-address lookup and an append-heavy event history with tens of millions of potential rows. The first can benefit from a search structure that recursively partitions a key space; the second may not need one index entry per row at all if event time is naturally correlated with heap location. SP-GiST and BRIN solve these different physical problems.

1. SP-GiST partitions a search space

SP-GiST means space-partitioned GiST. Unlike B-tree's fixed balanced ordered-tree model, SP-GiST is infrastructure for partitioned structures such as radix trees (tries), quad-trees, and k-d trees. The operator class determines how values are partitioned and searched. This can fit data whose natural search space is prefix-, point-, or range-like.

SELECT opc.opcname,       opc.opcintype::regtype AS input_type,       opc.opcdefaultFROM pg_opclass AS opcJOIN pg_am AS am ON am.oid = opc.opcmethodWHERE am.amname = 'spgist'ORDER BY input_type::text, opc.opcname;

The exact built-in list is evidence from your server. Do not copy an operator class name from another PostgreSQL major or extension without verifying it exists.

SP-GiST and GiST are both extensible indexing frameworks, but their physical ideas differ. GiST organizes entries through a balanced-tree interface driven by operator-class penalty, union, and consistency logic; SP-GiST supports recursively partitioned spaces that need not be balanced in the same way. Neither framework is automatically preferable. Start with the operators your query uses, then inspect which operator classes implement those operators and what shape of data they are designed to partition.

2. A prefix-style network search lab

PostgreSQL's network types already model address/subnet semantics more accurately than plain text. We can use a built-in SP-GiST class when available and compare it with a query whose operator is supported by the class.

DROP TABLE IF EXISTS app.ch10_network_lab;CREATE TABLE app.ch10_network_lab (    endpoint_id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,    addr inet NOT NULL,    site text NOT NULL);INSERT INTO app.ch10_network_lab(addr, site)SELECT ('10.' || (g % 200) || '.' || ((g / 200) % 250) || '.' || ((g % 250) + 1))::inet,       'site-' || (g % 50)FROM generate_series(1,100000) AS g;ANALYZE app.ch10_network_lab;CREATE INDEX ch10_network_spgist_idxON app.ch10_network_lab USING spgist(addr inet_ops);

EXPLAIN (ANALYZE, BUFFERS, SETTINGS)SELECT count(*)FROM app.ch10_network_labWHERE addr << inet '10.42.0.0/16';

PostgreSQL 18 supplies the SP-GiST inet_ops operator class for inet, including subnet-containment operators such as <<. Expect an SP-GiST index/bitmap path when the predicate is selective enough. The earlier catalog query is still the operational check: verify the class on the exact server rather than assuming an extension or older major has the same catalog state.

3. BRIN mental model: summarize heap block ranges

BRIN means Block Range Index. Instead of storing a conventional search entry for each row, a BRIN operator class stores summary information for groups of physically adjacent heap pages. With a min/max class, a time range whose pages contain only old timestamps can be skipped when a query asks for recent timestamps. BRIN is intentionally lossy: qualifying block ranges are read and candidate tuples are rechecked.

4. Build correlated and randomized twins

DROP TABLE IF EXISTS app.ch10_event_corr;CREATE TABLE app.ch10_event_corr (    event_id bigint NOT NULL,    occurred_at timestamptz NOT NULL,    payload text NOT NULL);INSERT INTO app.ch10_event_corrSELECT g,       timestamptz '2026-01-01 00:00+00' + g * interval '5 seconds',       repeat(md5(g::text), 2)FROM generate_series(1,300000) AS g;ANALYZE app.ch10_event_corr;SELECT attname, correlationFROM pg_statsWHERE schemaname='app' AND tablename='ch10_event_corr'  AND attname IN ('event_id','occurred_at');

DROP TABLE IF EXISTS app.ch10_event_random;CREATE TABLE app.ch10_event_random ASSELECT * FROM app.ch10_event_corrORDER BY random();ANALYZE app.ch10_event_random;SELECT attname, correlationFROM pg_statsWHERE schemaname='app' AND tablename='ch10_event_random'  AND attname IN ('event_id','occurred_at');

The correlation statistic is not a “BRIN score,” but it is useful evidence about the relationship between column order and physical heap order. The correlated table should have an occurred_at correlation close to an ordered layout, while the randomized twin should be much weaker.

5. Create comparable BRIN indexes

CREATE INDEX ch10_event_corr_brin_idxON app.ch10_event_corr USING brin(occurred_at)WITH (pages_per_range = 32, autosummarize = on);CREATE INDEX ch10_event_random_brin_idxON app.ch10_event_random USING brin(occurred_at)WITH (pages_per_range = 32, autosummarize = on);SELECT c.relname AS index_name,       pg_size_pretty(pg_relation_size(c.oid)) AS index_sizeFROM pg_class AS cWHERE c.oid IN (  'app.ch10_event_corr_brin_idx'::regclass,  'app.ch10_event_random_brin_idx'::regclass);

pages_per_range is a precision/size tradeoff: smaller ranges store more summaries and can prune more precisely, but grow the BRIN index and summarization work. There is no universal “best 32 pages” value; this is a lab value chosen to make the mechanism visible.

That tradeoff differs fundamentally from B-tree. B-tree normally carries an entry for each indexed row (subject to implementation optimizations such as deduplication), whereas BRIN deliberately summarizes a physical region. Consequently, a tiny BRIN can be useful on a huge append-ordered table even when its predicate must recheck heap tuples. The relevant question is not “which index is smaller?” but whether the summary can exclude enough block ranges for the workload while keeping write and maintenance overhead appropriate.

SELECT c.relname,       c.relpages,       pg_size_pretty(pg_relation_size(c.oid)) AS bytesFROM pg_class AS cWHERE c.oid IN (  'app.ch10_event_corr'::regclass,  'app.ch10_event_corr_brin_idx'::regclass)ORDER BY c.relname;

relpages is planner/catalog metadata and may lag until maintenance updates it; pg_relation_size() reports the current main-fork byte size. Use them as complementary evidence rather than assuming either is a direct measure of query benefit.

6. Same predicate, different physical evidence

EXPLAIN (ANALYZE, BUFFERS, SETTINGS)SELECT count(*)FROM app.ch10_event_corrWHERE occurred_at >= timestamptz '2026-01-18 00:00+00'  AND occurred_at <  timestamptz '2026-01-18 01:00+00';

EXPLAIN (ANALYZE, BUFFERS, SETTINGS)SELECT count(*)FROM app.ch10_event_randomWHERE occurred_at >= timestamptz '2026-01-18 00:00+00'  AND occurred_at <  timestamptz '2026-01-18 01:00+00';

On the correlated heap, BRIN can eliminate many page ranges whose min/max timestamp cannot overlap the requested hour. On the randomized heap, many ranges may contain both very early and very late timestamps, so the summaries prune little. Look at the actual plan, heap blocks, bitmap/lossy behavior, and rows removed by recheck rather than claiming a fixed speedup.

7. Summarization and unsummarized ranges

BRIN summaries are created for block ranges. Newly extended ranges may be unsummarized until vacuum/autosummarize or an explicit summarization function processes them. autosummarize queues summarization when the next range begins; it is not an instantaneous per-row guarantee.

SELECT brin_summarize_new_values('app.ch10_event_corr_brin_idx');SELECT brin_summarize_new_values('app.ch10_event_random_brin_idx');

This function is useful for a controlled diagnostic. In normal operations, combine autovacuum health, insertion pattern, and autosummarize policy instead of calling it after every batch by habit.

8. Wrong approach: BRIN because the table is large

Size alone is insufficient. A 2 TB table with randomly distributed values can be a poor candidate for a min/max BRIN on that random column. Conversely, a very large append-only event table with tight timestamp-to-heap correlation can get useful pruning from a tiny BRIN. Workload selectivity matters too: a query that legitimately needs 60% of the table may be better served by a sequential/parallel scan even with excellent correlation.

Likewise, SP-GiST is not “a faster GiST.” It is a different framework for partitioned search structures and is useful only when an available operator class's partitioning semantics match the operators in the workload.

9. Production judgment and cleanup

For huge append-heavy tables, assess BRIN with physical correlation, selectivity, pages-per-range, summarization health, and actual heap blocks visited. For SP-GiST, start with the available operator classes and supported operators. Keep B-tree available when exact scalar range/order semantics and point lookups justify the larger per-row structure.

DROP TABLE IF EXISTS app.ch10_event_random;DROP TABLE IF EXISTS app.ch10_event_corr;DROP TABLE IF EXISTS app.ch10_network_lab;

Authoritative references

Index behavior depends on PostgreSQL major version, operator class, collation, statistics, data distribution, visibility, and workload. Use the documentation for the exact major you operate.

• PostgreSQL 18 — SP-GiST Indexes
• PostgreSQL 18 — BRIN Indexes
• PostgreSQL 18 — CREATE INDEX / BRIN storage parameters
• PostgreSQL 18 — Planner Statistics / correlation