GiST Indexes for Range and Exclusion Queries #

A booking system checks “is this room free between these two timestamps?” with WHERE room_id = $1 AND NOT (ends_at <= $2 OR starts_at >= $3). The plan reads every booking for the room and filters. Separately, two users occasionally double-book the same slot, because the check and the insert are not atomic. A range column with a GiST index solves both: the overlap test becomes an index probe, and an exclusion constraint makes double-booking impossible.

GIN and GiST are introduced in specialized index types (GIN/GiST). This page covers the range side of GiST.

The Index Condition #

B-trees order values along one dimension, which is why a two-sided overlap test cannot be a bounded index scan, as discussed in join filter in nested loops without an index. GiST is a framework for indexes over types with no total order: each internal entry holds a bounding predicate covering its subtree, so a search descends only the branches that could contain matches.

For range types — tstzrange, daterange, int4range and friends — the built-in GiST operator class supports:

Two ways to get a range column: store one directly, or generate it from existing bounds:

ALTER TABLE bookings ADD COLUMN during tstzrange
  GENERATED ALWAYS AS (tstzrange(starts_at, ends_at, '[)')) STORED;
CREATE INDEX CONCURRENTLY bookings_during_gist ON bookings USING gist (room_id, during);

Including room_id in the GiST index requires the btree_gist extension, which provides operator classes so scalar columns can participate. That combination is what makes both the query and the constraint efficient.

An exclusion constraint uses the same index to enforce a rule across rows:

CREATE EXTENSION IF NOT EXISTS btree_gist;
ALTER TABLE bookings ADD CONSTRAINT bookings_no_overlap
  EXCLUDE USING gist (room_id WITH =, during WITH &&);

It reads as: no two rows may have equal room_id and overlapping during. PostgreSQL enforces it with the index, atomically, under concurrency.

Four steps to an indexable overlap rule Four stages. Two timestamp columns hold the bounds. A generated range column combines them. A GiST index on room_id and the range makes overlap queries indexable. An exclusion constraint over the same index prevents overlapping rows for one room. starts_at, ends_at plain timestamp columns during (generated) tstzrange, stored GiST index room_id + during EXCLUDE constraint no overlaps per room btree_gist lets the scalar room_id join the GiST index

Annotated EXPLAIN Evidence #

Before, with two comparisons:

EXPLAIN (ANALYZE, BUFFERS)
SELECT 1 FROM bookings
WHERE room_id = 41
  AND starts_at < '2026-09-20 12:00+00' AND ends_at > '2026-09-20 10:00+00';
Index Scan using bookings_room_starts_idx on bookings  (actual time=0.05..18.4 rows=1 loops=1)
  Index Cond: ((room_id = 41) AND (starts_at < '2026-09-20 12:00:00+00'::timestamptz))
  Filter: (ends_at > '2026-09-20 10:00:00+00'::timestamptz)
  Rows Removed by Filter: 41208
  Buffers: shared hit=1204
-- the second bound is a filter: every earlier booking for the room is examined

After, with a range and GiST:

EXPLAIN (ANALYZE, BUFFERS)
SELECT 1 FROM bookings
WHERE room_id = 41 AND during && tstzrange('2026-09-20 10:00+00', '2026-09-20 12:00+00');
Index Scan using bookings_during_gist on bookings  (actual time=0.03..0.03 rows=1 loops=1)
  Index Cond: ((room_id = 41) AND (during && '["2026-09-20 10:00:00+00","2026-09-20 12:00:00+00")'::tstzrange))
  Buffers: shared hit=4
Execution Time: 0.05 ms
-- both dimensions in the index condition; four buffers

And the constraint doing its job:

INSERT INTO bookings (room_id, during) VALUES (41, tstzrange('2026-09-20 11:00+00','2026-09-20 13:00+00'));
ERROR:  conflicting key value violates exclusion constraint "bookings_no_overlap"
DETAIL:  Key (room_id, during)=(41, ["2026-09-20 11:00:00+00","2026-09-20 13:00:00+00")) conflicts with
         existing key (room_id, during)=(41, ["2026-09-20 10:00:00+00","2026-09-20 12:00:00+00")).
Three signals the range index is working Three items are annotated. A Filter line on the second bound shows a B-tree could only bound one side. An Index Cond containing the overlap operator shows GiST handling both bounds. The exclusion constraint error shows the rule enforced atomically. Filter: (ends_at > …) Rows Removed: 41208 B-tree bounds only one side Index Cond: (… AND during && '[…)') GiST handles the overlap conflicting key … exclusion constraint enforced under concurrency the same index serves the query and the constraint

Step-by-Step Resolution #

  1. Add the range column as a generated column so it cannot drift from the bounds, choosing inclusivity deliberately — '[)' (inclusive start, exclusive end) is right for time intervals.

  2. Install btree_gist if the query also filters on scalar columns such as room_id.

  3. Create the GiST index concurrently, with the equality column first:

    CREATE INDEX CONCURRENTLY bookings_during_gist ON bookings USING gist (room_id, during);

  4. Rewrite queries to use range operators — && for overlap, @> for containment — so the index condition covers the whole test.

  5. Add the exclusion constraint once existing data is clean; the build fails on existing overlaps, which is a data-quality finding rather than an obstacle.

  6. Handle the constraint violation in the application as a retry or a user-facing conflict message; it replaces a check-then-insert race.

  7. Measure index size and build time. GiST indexes are larger and slower to build than B-trees; on very large tables consider partitioning by time so each partition’s index stays manageable.

One availability check With a B-tree on room_id and starts_at the check reads 1,204 buffers and takes 18.4 milliseconds because the second bound is a filter. With the GiST range index it reads 4 buffers and takes 0.05 milliseconds. On a room with 200 thousand historical bookings the B-tree version grows to 94 milliseconds while the GiST version is unchanged. B-tree, 41k bookings 18.4 ms B-tree, 200k bookings 94 ms GiST range index 0.05 ms the GiST cost does not grow with the room's history

Before and After #

-- BEFORE: two comparisons on a B-tree
Index Cond: (room_id = 41 AND starts_at < …)  Filter: (ends_at > …)  Rows Removed: 41208   18.4 ms

-- AFTER: generated range column + GiST index + exclusion constraint
Index Cond: (room_id = 41 AND during && '[…)')  Buffers: shared hit=4                      0.05 ms

Where GiST is the wrong tool #

GiST is not a general replacement for B-trees. For plain equality and ordered range scans on scalar columns, a B-tree is smaller, faster and supports index-only scans more readily. GiST indexes are lossy for some operator classes, meaning the executor rechecks conditions against the heap — visible as Rows Removed by Index Recheck — and they cost more to build and maintain.

Use GiST when the question is genuinely multi-dimensional or non-orderable: ranges, geometric containment, nearest-neighbour ordering (ORDER BY point <-> :target LIMIT 10, which GiST supports natively), and full-text search where the index must be small rather than fast. For equality-heavy JSON containment queries, GIN is the better fit, compared in when to use GIN over B-tree.

SP-GiST is worth knowing about for non-balanced structures such as quadtrees and radix trees; for range types it can outperform GiST on some workloads. Both are worth benchmarking on real data before committing, because their relative cost depends heavily on how values are distributed.

Common Pitfalls #

Comparing bounds instead of using range operators. Only one bound can be an index condition. Diagnostic signal: a Filter on the second bound. Fix: a range column and &&.

Forgetting btree_gist. Scalar columns cannot join a GiST index without it. Diagnostic signal: error creating the index or the constraint. Fix: create the extension.

Inclusive end bounds. '[]' ranges make adjacent bookings overlap at the boundary. Diagnostic signal: spurious conflicts between back-to-back slots. Fix: use '[)'.

Adding the constraint to dirty data. The build fails on existing overlaps. Diagnostic signal: constraint creation error naming two rows. Fix: find and resolve overlaps first with a self-join on &&.

Frequently Asked Questions #

How do I index a query that checks for overlapping time ranges? #

Store the interval as a range column, index it with GiST — including any scalar filter columns via the btree_gist extension — and write the query with the overlap operator so the whole condition becomes an index condition.

What is an exclusion constraint? #

A constraint enforced by an index that forbids rows whose specified columns relate to each other in a given way, such as equal room and overlapping time range. It provides atomic enforcement that a check-then-insert in the application cannot.

Is GiST slower than B-tree? #

For plain scalar equality and ordered ranges, yes: GiST indexes are larger, build more slowly and can require rechecks. GiST wins where B-trees cannot work at all, such as overlap, containment and nearest-neighbour queries.

Up: Specialized Index Types (GIN/GiST)