# What index to use with lots of duplicate values?

Let's make a few assumptions:

I have table that looks like this:

`````` a | b
---+---
a | -1
a | 17
...
a | 21
c | 17
c | -3
...
c | 22
``````

• Size of the whole table is ~ 1010 rows.

• I have ~ 100k rows with value `a` in column `a`, similar for other values (e.g. `c`).

• That means ~ 100k distinct values in column 'a'.

• Most of my queries will read all or most of the values for a given value in a, e.g. `select sum(b) from t where a = 'c'`.

• The table is written in such a way that consecutive values are physically close (either it's written in order, or we assume `CLUSTER` was used on that table and column `a`).

• The table is rarely if ever updated, we're only concerned about read speed.

• The table is relatively narrow (say ~25 bytes per tuple, + 23 bytes overhead).

Now the question is, what kind of index should I be using? My understanding is:

• BTree My issue here is that the BTree index will be huge since as far as I know it will store duplicate values (it has to, since it can't assume the table is physically sorted). If the BTree is huge, I end up having to read both the index and the parts of the table that the index points to. (We can use `fillfactor = 100` to decrease the size of the index a bit.)

• BRIN My understanding is that I can have a small index here at the expense of reading useless pages. Using a small `pages_per_range` means that the index is bigger (which is a problem with BRIN since I need to read the whole index), having a big `pages_per_range` means that I'll read a lot of useless pages. Is there a magic formula to find a good value of `pages_per_range` that takes into account those trade-offs?

• GIN/GiST Not sure those are relevant here since they're mostly used for full-text search, but I also hear that they're good at dealing with duplicate keys. Would either a `GIN` or `GiST` index help here?

Another question is, will Postgres use the fact that a table is `CLUSTER`ed (assuming no updates) in the query planner (e.g. by binary searching for the relevant start/end pages)? Somewhat related, can I just store all my columns in a BTree and drop the table altogether (or achieve something equivalent, I believe those are clustered indices in SQL server)? Is there some hybrid BTree/BRIN index that would help here?

I'd rather avoid using arrays to store my values since my query will end up less readable that way (I understand this would reduce the cost of the 23 bytes per tuple overhead by reducing the number of tuples).

• "mostly used for full-text search" GiST is used quite extensively by PostGIS. Mar 11, 2017 at 11:10

### BTree

My issue here is that the BTree index will be huge since afaict it will store duplicate values (it has too, since it can't assume the table is physically sorted). If the BTree is huge I end up having to read both the index and the parts of the table that the index points too...

Not necessarily — Having a btree index that is 'covering' will be the fastest read time, and if that is all you want (ie if you can afford the extra storage), then it is your best bet.

### BRIN

My understanding is that I can have a small index here at the expense of reading useless pages. Using a small `pages_per_range` means that the index is bigger (which is a problem with BRIN since I need to read the whole index), having a big `pages_per_range` means that I'll read a lot of useless pages.

If you can't afford the storage overhead of a covering btree index, BRIN is ideal for you, because you have clustering already in place (this is crucial for BRIN to be useful). BRIN indexes are tiny, so all the pages are likely to be in memory if you choose a suitable value of `pages_per_range`.

Is there a magic formula to find a good value of pages_per_range that takes into account those trade offs?

No magic formula, but start with `pages_per_range` somewhat less than the average size (in pages) occupied by the average `a` value. You are probably trying to minimize: (number of BRIN pages scanned)+(number of heap pages scanned) for a typical query. Look for `Heap Blocks: lossy=n` in the execution plan for `pages_per_range=1` and compare with other values for `pages_per_range` — i.e. see how many unnecessary heap blocks are being scanned.

### GIN/GiST

Not sure those are relevant here since they're mostly used for full text search, but I also hear that they're good at dealing with duplicate keys. Would either a `GIN`/`GiST` index help here?

GIN may be worth considering, but probably not GiST — however if the natural clustering really is good, then BRIN will probably be a better bet.

Here is a sample comparison between the different index types for dummy data a bit like yours:

table and indexes:

``````create table foo(a,b,c) as
from (select chr(g) a from generate_series(97,122) g) a
cross join (select generate_series(1,100000) b) b
order by a;
create index foo_btree_covering on foo(a,b);
create index foo_btree on foo(a);
create index foo_gin on foo using gin(a);
create index foo_brin_2 on foo using brin(a) with (pages_per_range=2);
create index foo_brin_4 on foo using brin(a) with (pages_per_range=4);
vacuum analyze;
``````

relation sizes:

``````select relname "name", pg_size_pretty(siz) "size", siz/8192 pages, (select count(*) from foo)*8192/siz "rows/page"
from( select relname, pg_relation_size(C.oid) siz
from pg_class c join pg_namespace n on n.oid = c.relnamespace
where nspname = current_schema ) z;
``````
```name               | size    | pages | rows/page
:----------------- | :------ | ----: | --------:
foo                | 149 MB  | 19118 |       135
foo_btree_covering | 56 MB   |  7132 |       364
foo_btree          | 56 MB   |  7132 |       364
foo_gin            | 2928 kB |   366 |      7103
foo_brin_2         | 264 kB  |    33 |     78787
foo_brin_4         | 136 kB  |    17 |    152941
```

covering btree:

``````explain analyze select sum(b) from foo where a='a';
``````
```| QUERY PLAN                                                                                                                                      |
| :---------------------------------------------------------------------------------------------------------------------------------------------- |
| Aggregate  (cost=3282.57..3282.58 rows=1 width=8) (actual time=45.942..45.942 rows=1 loops=1)                                                   |
|   ->  Index Only Scan using foo_btree_covering on foo  (cost=0.43..3017.80 rows=105907 width=4) (actual time=0.038..27.286 rows=100000 loops=1) |
|         Index Cond: (a = 'a'::text)                                                                                                             |
|         Heap Fetches: 0                                                                                                                         |
| Planning time: 0.099 ms                                                                                                                         |
| Execution time: 45.968 ms                                                                                                                       |
```

plain btree:

``````drop index foo_btree_covering;
explain analyze select sum(b) from foo where a='a';
``````
```| QUERY PLAN                                                                                                                        |
| :-------------------------------------------------------------------------------------------------------------------------------- |
| Aggregate  (cost=4064.57..4064.58 rows=1 width=8) (actual time=54.242..54.242 rows=1 loops=1)                                     |
|   ->  Index Scan using foo_btree on foo  (cost=0.43..3799.80 rows=105907 width=4) (actual time=0.037..33.084 rows=100000 loops=1) |
|         Index Cond: (a = 'a'::text)                                                                                               |
| Planning time: 0.135 ms                                                                                                           |
| Execution time: 54.280 ms                                                                                                         |
```

BRIN pages_per_range=4:

``````drop index foo_btree;
explain analyze select sum(b) from foo where a='a';
``````
```| QUERY PLAN                                                                                                                        |
| :-------------------------------------------------------------------------------------------------------------------------------- |
| Aggregate  (cost=21595.38..21595.39 rows=1 width=8) (actual time=52.455..52.455 rows=1 loops=1)                                   |
|   ->  Bitmap Heap Scan on foo  (cost=888.78..21330.61 rows=105907 width=4) (actual time=2.738..31.967 rows=100000 loops=1)        |
|         Recheck Cond: (a = 'a'::text)                                                                                             |
|         Rows Removed by Index Recheck: 96                                                                                         |
|         Heap Blocks: lossy=736                                                                                                    |
|         ->  Bitmap Index Scan on foo_brin_4  (cost=0.00..862.30 rows=105907 width=0) (actual time=2.720..2.720 rows=7360 loops=1) |
|               Index Cond: (a = 'a'::text)                                                                                         |
| Planning time: 0.101 ms                                                                                                           |
| Execution time: 52.501 ms                                                                                                         |
```

BRIN pages_per_range=2:

``````drop index foo_brin_4;
explain analyze select sum(b) from foo where a='a';
``````
```| QUERY PLAN                                                                                                                        |
| :-------------------------------------------------------------------------------------------------------------------------------- |
| Aggregate  (cost=21659.38..21659.39 rows=1 width=8) (actual time=53.971..53.971 rows=1 loops=1)                                   |
|   ->  Bitmap Heap Scan on foo  (cost=952.78..21394.61 rows=105907 width=4) (actual time=5.286..33.492 rows=100000 loops=1)        |
|         Recheck Cond: (a = 'a'::text)                                                                                             |
|         Rows Removed by Index Recheck: 96                                                                                         |
|         Heap Blocks: lossy=736                                                                                                    |
|         ->  Bitmap Index Scan on foo_brin_2  (cost=0.00..926.30 rows=105907 width=0) (actual time=5.275..5.275 rows=7360 loops=1) |
|               Index Cond: (a = 'a'::text)                                                                                         |
| Planning time: 0.095 ms                                                                                                           |
| Execution time: 54.016 ms                                                                                                         |
```

GIN:

``````drop index foo_brin_2;
explain analyze select sum(b) from foo where a='a';
``````
```| QUERY PLAN                                                                                                                         |
| :--------------------------------------------------------------------------------------------------------------------------------- |
| Aggregate  (cost=21687.38..21687.39 rows=1 width=8) (actual time=55.331..55.331 rows=1 loops=1)                                    |
|   ->  Bitmap Heap Scan on foo  (cost=980.78..21422.61 rows=105907 width=4) (actual time=12.377..33.956 rows=100000 loops=1)        |
|         Recheck Cond: (a = 'a'::text)                                                                                              |
|         Heap Blocks: exact=736                                                                                                     |
|         ->  Bitmap Index Scan on foo_gin  (cost=0.00..954.30 rows=105907 width=0) (actual time=12.271..12.271 rows=100000 loops=1) |
|               Index Cond: (a = 'a'::text)                                                                                          |
| Planning time: 0.118 ms                                                                                                            |
| Execution time: 55.366 ms                                                                                                          |
```

dbfiddle here

• So a covering index would skip reading the table altogether at the expense of disk space? Seems like a good tradeoff. I think we mean the same thing for the BRIN index by 'read the whole index' (correct me if I'm wrong), I meant scanning the whole BRIN index which I think is what's happening in dbfiddle.uk/…, no?
– foo
Mar 10, 2017 at 15:58
• @foo about the "(it has too, since it can't assume the table is physically sorted)." The physical order (cluster or not) of the table is irrelevant. The index has the values in the right order. But Postgres B-tree indexes have to store all values (and yes, multiple times). That's how they are designed. Storing each distinct value only once would be a nice feature/improvement. You could suggest it to Postgres developers (and even help implementing it.) Jack should comment, I think Oracle's implementation of b-trees does that. Mar 10, 2017 at 18:25
• @foo — you are completely correct, a scan of a BRIN index always scans the whole index (pgcon.org/2016/schedule/attachments/…, 2nd last slide) — though that isn't shown on the explain plan in the fiddle, is it? Mar 10, 2017 at 18:41
• @ypercubeᵀᴹ you can use COMPRESS on Oracle that stores each distinct prefix once per block. Mar 10, 2017 at 18:50
• @JackDouglas I read `Bitmap Index Scan` as meaning 'read the whole brin index` but maybe that's the wrong read. Oracle's `COMPRESS` looks like something that would be useful here since it would reduce the size of the B-tree, but I'm stuck with pg!
– foo
Mar 10, 2017 at 22:33

Besides btree and brin which seem the most sensible options, some other, exotic options which might be worth investigating - they might helpful or not in your case:

• `INCLUDE` indexes. They will be - hopefully - in the next major version (10) of Postgres, somewhere around September 2017. An index on `(a) INCLUDE (b)` has the same structure as an index on `(a)` but includes in the leaf pages, all the values of `b` (but unordered). Which means you can't use it for example for `SELECT * FROM t WHERE a = 'a' AND b = 2 ;`. The index might be used but while an `(a,b)` index will find the matching rows with a single seek, the include index will have to go through the (possibly 100K as in your case) values that match `a = 'a'` and check the `b` values.
On the other hand, the index is slightly less wide than the `(a,b)` index and you don't need the order on `b` for your query to calculate `SUM(b)`. You could also have for example `(a) INCLUDE (b,c,d)` which can be used for queries similar to yours that aggregate on all 3 columns.

• Filtered (partial) indexes. A suggestion that might sounds a bit crazy* at first:

``````CREATE INDEX flt_a  ON t (b) WHERE (a = 'a') ;
---
CREATE INDEX flt_xy ON t (b) WHERE (a = 'xy') ;
``````

One index for each `a` value. In your case around 100K indexes. While this sounds a lot, consider that each index will be very small, both in size (number of rows) and width (as it will store only `b` values). In all other aspects though, it (the 100K indexes together) will act as a b-tree index on `(a,b)` while using the space of a `(b)` index.
Disadvantage is that you'll have to create and maintain them yourself, each time a new value of `a` is added into the table. Since your table is rather stable, without many (or any) inserts/updates, that doesn't seem like a problem.

• Summary tables. Since the table is rather stable, you can always create and populate a summary table with the most common aggregates you'll need (`sum(b), sum(c), sum(d), avg(b), count(distinct b)`, etc). It will be small (only 100K rows) and will only have to be populated once and updated only when rows are inserted/updated/deleted on the main table.

*: idea copied from this company that runs 10 million indexes in their production system: The Heap: Running 10 Million Postgresql Indexes In Production (and counting).

• 1 is interesting but as you point out pg 10 isn't out yet. 2 does sound crazy (or at least against 'common wisdom'), I'll have a read since as you point out that could work with my almost no writes workflow. 3. wouldn't work for me, I used `SUM` as an example, but in practice my queries can't be precomputed (they're more like `select ... from t where a = '?' and ??` wjere `??` would be some other user-defined condition.
– foo
Mar 10, 2017 at 22:42
• Well, we can't help if we don't know what `??` is ;) Mar 10, 2017 at 23:16
• You mention filtered indexes. What about partitioning the table? Mar 11, 2017 at 11:16
• @jpmc26 funny, I was thinking of adding in the answer that the suggestion of filtered indexes is in a sense a form of partitioning. Partitioning might also be helpful here but I'm not sure. It would result in a lot of small indexes/tables. Mar 11, 2017 at 11:22
• I expect partial covering btree indexes to be the king of performance here, since data is almost never updated. Even if that means 100k indexes. Total index size is smallest (except for a BRIN index, but there Postgres has to read and filter heap pages additionally). Index generation can be automated with dynamic SQL. Example `DO` statement in this related answer. Mar 11, 2017 at 19:07