# GiST index

stores bounding boxes, not shapes. every spatial query is therefore two phases,
and the slow ones are slow in the second phase, not the first.

```sql
CREATE INDEX stores_geom_idx ON stores USING GIST (geom);
ANALYZE stores;
```

the `ANALYZE` is not optional. postgis statistics drive the planner's
selectivity estimates for spatial operators, and without them the planner
routinely picks a sequential scan over a perfectly good index.

## the two phases

1. **index filter.** a cheap bounding box test (`&&`, `~`, `@`) served by the
   tree. it returns a superset of candidates.
2. **exact test.** the real predicate, run on each candidate.

```
Index Scan using stores_geom_idx on stores
  Index Cond: (geom && st_expand(:point, 1000))   <- phase 1, the index
  Filter: st_dwithin(geom, :point, 1000)          <- phase 2, exact
  Rows Removed by Filter: 214                     <- the cost of a loose box
```

`Rows Removed by Filter` is the number to watch. a bounding box is a poor
approximation for a long diagonal linestring or a sprawling concave polygon: the
box can be many times the area of the shape, so phase 1 admits candidates that
phase 2 then throws away.

the fix is to make the boxes tighter by cutting the geometries up:

```sql
CREATE TABLE regions_parts AS
SELECT id, ST_Subdivide(geom, 256) AS geom FROM regions;

CREATE INDEX ON regions_parts USING GIST (geom);
```

each piece carries a box close to its own extent, so phase 1 admits far less.
you pay with more rows and a `DISTINCT` or a group by on the way out.

## the index has to match the expression

this is where most "why is my index not being used" ends. a plain `GIST (geom)`
cannot serve a query written against `geom::geography`.

```sql
-- geometry queries
CREATE INDEX ON stores USING GIST (geom);

-- geography queries, the cast is part of the index
CREATE INDEX ON stores USING GIST ((geom::geography));

-- projected queries
CREATE INDEX ON stores USING GIST (ST_Transform(geom, 31983));

-- a subset, smaller tree, only if the predicate is in every query
CREATE INDEX ON stores USING GIST (geom) WHERE active;

-- spatial plus a scalar column, needs btree_gist
CREATE EXTENSION IF NOT EXISTS btree_gist;
CREATE INDEX ON stores USING GIST (geom, tenant_id);
```

that last one matters in multi tenant schemas. without `btree_gist`, postgres
cannot put a scalar column in the same GiST index, and the planner falls back to
a bitmap AND of two separate indexes. see
[st-dwithin](../st-dwithin.md) for the cast that most often breaks this.

## GiST, SP-GiST, BRIN

| index | best for | notes |
| --- | --- | --- |
| GiST | general spatial workloads | the default, and the only one with knn `<->` |
| SP-GiST | points, evenly distributed | smaller and faster to build, no polygons |
| BRIN | huge, physically clustered tables | tiny and coarse, needs spatial ordering on disk |

BRIN only earns its place when rows are physically stored in spatial order.
`CLUSTER` on a geohash or a hilbert curve first, otherwise every block range
covers the whole extent and the index answers "maybe" for everything.

## maintenance

- **build with `CREATE INDEX CONCURRENTLY`** on a live table. the plain form
  takes an `ACCESS EXCLUSIVE` lock for the entire build.
- **GiST bloats under heavy updates.** `REINDEX CONCURRENTLY` reclaims it.
- **raise `maintenance_work_mem` before a large build.** spatial builds are
  memory hungry and spill to disk early at the default 64 MB.
- **keep postgis current.** sorted builds, from postgis 3.1 on postgres 14, are
  much faster and produce tighter trees than the old insert by insert path.