Choosing an index type
Indexing drives performance, but btree is not the only option. Because different index types serve different operations — one that works well for names may be useless for GIS data — PostgreSQL supports more than one index type. That flexibility raises practical questions for data warehouses: is there an alternative to btree, can indexes be made smaller, and can they be built faster?
The system table pg_am reveals which index types a given system supports. The list is not necessarily constant, since an index type can be loaded as an extension.
|
1 2 3 4 5 6 7 8 9 10 11 |
test=# SELECT * FROM pg_am; oid | amname | amhandler | amtype ------+--------+----------------------+-------- 2 | heap | heap_tableam_handler | t 403 | btree | bthandler | i 405 | hash | hashhandler | i 783 | gist | gisthandler | i 2742 | gin | ginhandler | i 4000 | spgist | spghandler | i 3580 | brin | brinhandler | i (7 rows) |
Building a fair test case
A sample table makes the comparison concrete. generate_series is the usual tool for generating large tables for testing:
|
1 2 3 4 5 6 |
test=# CREATE TABLE t_demo (id_sorted int8, id_random int8); CREATE TABLE test=# INSERT INTO t_demo SELECT id, hashtext(id::text) FROM generate_series(1, 5000000000) AS id; INSERT 0 5000000000 |
That produces 5 billion rows and a 206 GB table with two columns. The first column is ascending, holding numbers from 1 to 5 billion:
|
1 2 3 4 5 6 |
test=# d+ List of relations Schema | Name | Type | Owner | Persistence | Access method | Size | Description --------+--------+-------+-------+-------------+---------------+--------+------------- public | t_demo | table | hs | permanent | heap | 206 GB | (1 row) |
The second column holds a hash value:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
test=# SELECT * FROM t_demo LIMIT 10 OFFSET 50; id_sorted | id_random -----------+------------- 51 | 342243648 52 | -1711900017 53 | 213436769 54 | 2112769913 55 | -1318351987 56 | -19937162 57 | -299365904 58 | -1228416573 59 | 93548776 60 | 1491665190 (10 rows) |
The hash is essentially random and should be evenly distributed. The two columns let us observe how index types such as btree and BRIN behave in two common data layouts: sorted and unsorted.
Btree index creation
Starting with the PostgreSQL default configuration (only max_wal_size was raised to 100 GB), a simple btree index takes 35 minutes to create:
|
1 2 3 |
test=# CREATE INDEX idx_id ON t_demo (id_sorted); CREATE INDEX Time: 2109651,552 ms (35:09,652) |
Raising maintenance_work_mem to 1 GB and increasing the allowed number of worker processes improves on that:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
test=# SHOW maintenance_work_mem ; maintenance_work_mem ---------------------- 64MB (1 row) Time: 0,170 ms test=# SET maintenance_work_mem TO '1 GB'; SET Time: 0,181 ms test=# SET max_parallel_maintenance_workers TO 4; SET |
|
1 2 3 4 5 6 7 8 9 |
[hs@hanspc user_test]$ vmstat 2 procs -----------memory---------- ---swap-- -----io---- -system--- ------cpu----- r b swpd free buff cache si so bi bo in cs us sy id wa st 5 0 450048 235408 1800 25689472 0 2 2964 6838 21 41 9 2 88 1 0 5 0 450048 261876 1800 25650596 0 0 1225912 8 19425 8512 39 7 54 0 0 7 0 450048 257548 1800 25660116 0 0 941458 277776 19766 7638 32 7 53 7 0 1 5 450048 232476 1800 25690880 0 0 857176 411110 17791 7603 34 7 50 9 0 5 0 450048 260136 1800 25663332 0 0 756074 485380 16005 7811 28 6 53 13 0 3 4 450048 242340 1800 25679688 0 0 722454 666192 16785 8842 26 10 49 15 0 |
Monitoring with vmstat shows PostgreSQL reading and spilling hundreds of megabytes per second. Since everything cannot be sorted in memory, this is the expected behavior.
The progress monitoring infrastructure breaks the build into phases. First PostgreSQL scans the table and prepares the data for sorting, with all available cores working at full speed:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
test=# \x Expanded display is on. test=# SELECT * FROM pg_stat_progress_create_index; -[ RECORD 1 ]------+------------------------------- pid | 23147 datid | 24576 datname | test relid | 24583 index_relid | 0 command | CREATE INDEX phase | building index: scanning table lockers_total | 0 lockers_done | 0 current_locker_pid | 0 blocks_total | 27027028 blocks_done | 8577632 tuples_total | 0 tuples_done | 0 partitions_total | 0 partitions_done | 0 |
|
1 2 3 4 5 6 |
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND 38830 hs 20 0 594336 219780 12152 R 99.0 0.7 0:06.65 postgres 38831 hs 20 0 594336 219748 12120 R 99.0 0.7 0:06.65 postgres 38833 hs 20 0 594336 219920 12288 R 98.7 0.7 0:06.64 postgres 38832 hs 20 0 594336 219916 12284 R 98.3 0.7 0:06.63 postgres 23147 hs 20 0 514964 276408 149056 R 97.7 0.8 106:48.69 postgres |
Then the partial data sets are sorted. The table is too large for this to happen in memory, so data spills to disk:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
-[ RECORD 1 ]-------+------------------------------------ pid | 23147 datid | 24576 datname | test relid | 24583 index_relid | 0 command | CREATE INDEX phase | building index: sorting live tuples lockers_total | 0 lockers_done | 0 current_locker_pid | 0 blocks_total | 27027028 blocks_done | 27027028 tuples_total | 0 tuples_done | 0 partitions_total | 0 partitions_done | 0 |
Finally, data is added to the tree and the index is written to disk:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
-[ RECORD 1 ]------+--------------------------------------- pid | 23147 datid | 24576 datname | test relid | 24583 index_relid | 0 command | CREATE INDEX phase | building index: loading tuples in tree lockers_total | 0 lockers_done | 0 current_locker_pid | 0 blocks_total | 0 blocks_done | 0 tuples_total | 5000000000 tuples_done | 2005424786 partitions_total | 0 partitions_done | 0 |
The result is nearly double the indexing performance:
|
1 2 3 |
test=# CREATE INDEX idx_id ON t_demo (id_sorted); CREATE INDEX Time: 1212601.300 ms (20:12.601) |
The size of the resulting index is also worth noting:
|
1 2 3 4 5 6 |
test=# di+ List of relations Schema | Name | Type | Owner | Table | Persistence | Access method | Size | Description --------+--------+-------+-------+--------+-------------+---------------+--------+------------- public | idx_id | index | hs | t_demo | permanent | btree | 105 GB | (1 row) |
105 GB is massive, and it confirms a rough rule of thumb: an index generally needs about 25 bytes per index entry, assuming no duplicates.
A second index on the randomized column takes somewhat longer to build, because the input stream is no longer sorted:
|
1 2 3 |
test=# CREATE INDEX idx_random ON t_demo (id_random); CREATE INDEX Time: 1731088,437 ms (28:51,088) |
How btrees behave at query time
On the sorted column, query performance is striking — 10 million rows returned in 358 milliseconds:
|
1 2 3 4 5 6 7 8 9 |
test=# SELECT count(*) FROM t_demo WHERE id_sorted BETWEEN 10000000 AND 20000000; count ---------- 10000001 (1 row) Time: 358.804 ms |
The execution plan explains the result:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
test=# EXPLAIN (ANALYZE, BUFFERS) SELECT count(*) FROM t_demo WHERE id_sorted BETWEEN 10000000 AND 20000000; QUERY PLAN --------------------------------------------------------------------- Finalize Aggregate (cost=296509.46..296509.47 rows=1 width=8) (actual time=496.450..500.609 rows=1 loops=1) Buffers: shared hit=11 read=27325 -> Gather (cost=296509.24..296509.45 rows=2 width=8) (actual time=496.379..500.603 rows=3 loops=1) Workers Planned: 2 Workers Launched: 2 Buffers: shared hit=11 read=27325 -> Partial Aggregate (cost=295509.24..295509.25 rows=1 width=8) (actual time=492.621..492.622 rows=1 loops=3) Buffers: shared hit=11 read=27325 -> Parallel Index Only Scan using idx_id on t_demo (cost=0.58..284966.32 rows=4217169 width=0) (actual time=0.074..340.666 rows=3333334 loops=3) Index Cond: ((id_sorted >= 10000000) AND (id_sorted <= 20000000)) Heap Fetches: 0 Buffers: shared hit=11 read=27325 Planning: Buffers: shared hit=7 read=3 Planning Time: 0.233 ms Execution Time: 500.662 ms (16 rows) |
This is a parallel index-only scan. It is enough to scan the index without fetching from the underlying table; the existence of the row is confirmed via hint bits.
Running the same query against the random column — with the range reduced so the result set is still roughly 10 million rows — changes the picture entirely:
|
1 2 3 4 5 6 7 8 9 10 11 |
test=# EXPLAIN SELECT count(*) FROM t_demo WHERE id_random BETWEEN 10000000 AND 19000000; QUERY PLAN ------------------------------------------------------------------- Aggregate (cost=22871994.27..22871994.28 rows=1 width=8) -> Index Only Scan using idx_random on t_demo (cost=0.58..22846435.29 rows=10223592 width=0) Index Cond: ((id_random >= 10000000) AND (id_random <= 19000000)) (3 rows) |
The parallel query using more than one core is gone. Worse, the sustained I/O during the query reaches 120 MB/sec, and the runtime explodes to 5 minutes:
|
1 2 3 4 5 6 7 8 |
[hs@hanspc user_test]$ vmstat 2 procs -----------memory---------- ---swap-- -----io---- -system-- ------cpu----- r b swpd free buff cache si so bi bo in cs us sy id wa st 0 1 1377280 228168 1032 27286216 0 0 120584 314 17933 30276 2 5 86 7 0 1 0 1377280 231608 1032 27286224 0 0 121102 1069 17839 30854 2 3 88 7 0 1 1 1377280 251400 1032 27270360 0 0 121168 869 17669 30117 1 4 88 7 0 0 1 1377280 263096 1032 27254396 0 0 121674 514 17780 30695 2 2 88 7 0 0 1 1377280 236788 1032 27275712 0 0 121630 260 18403 31970 2 2 88 7 0 |
|
1 2 3 4 5 6 7 8 |
test=# SELECT count(*) FROM t_demo WHERE id_random BETWEEN 10000000 AND 19000000; count ---------- 10481155 (1 row) Time: 322747,613 ms (05:22,748) |
The cause is visible in the block counts:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
test=# EXPLAIN (ANALYZE, BUFFERS) SELECT count(*) FROM t_demo WHERE id_random BETWEEN 10000000 AND 19000000; QUERY PLAN ------------------------------------------------------------------- Aggregate (cost=22871994.27..22871994.28 rows=1 width=8) (actual time=292381.841..292381.843 rows=1 loops=1) Buffers: shared hit=6611938 read=3884860 -> Index Only Scan using idx_random on t_demo (cost=0.58..22846435.29 rows=10223592 width=0) (actual time=0.515..291336.908 rows=10481155 loops=1) Index Cond: ((id_random >= 10000000) AND (id_random <= 19000000)) Heap Fetches: 3866504 Buffers: shared hit=6611938 read=3884860 Planning Time: 1.080 ms Execution Time: 292381.934 ms (8 rows) Time: 292384.903 ms (04:52.385) |
The data is spread all over the place, so millions of 8k pages must be touched, each holding mostly rows that are not needed. The amount of data is identical in both cases — only its distribution on disk has changed.
BRIN as an alternative
BRIN indexes are often presented as the savior for warehousing workloads, but that deserves scrutiny. Creating one is fast:
|
1 2 3 |
test=# CREATE INDEX idx_brin ON t_demo USING brin (id_sorted); CREATE INDEX Time: 710549,637 ms (11:50,550) |
The size is the more convincing figure:
|
1 2 3 4 5 |
test=# SELECT pg_size_pretty(pg_relation_size('idx_brin')); pg_size_pretty ---------------- 7064 kB (1 row) |
At only 7 MB, the BRIN index saves 10 GB of disk compared with the btree. The build process also looks different — BRIN does far less sorting than a regular btree index, which means less temporary I/O and faster index creation:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
test=# SELECT * FROM pg_stat_progress_create_index; -[ RECORD 1 ]------+--------------- pid | 23147 datid | 24576 datname | test relid | 24583 index_relid | 0 command | CREATE INDEX phase | building index lockers_total | 0 lockers_done | 0 current_locker_pid | 0 blocks_total | 27027028 blocks_done | 16898015 tuples_total | 0 tuples_done | 0 partitions_total | 0 partitions_done | 0 |
Queries tell a more nuanced story:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
test=# EXPLAIN (ANALYZE, BUFFERS) SELECT count(*) FROM t_demo WHERE id_sorted BETWEEN 10000000 AND 20000000; QUERY PLAN ------------------------------------------------------------------------------------ Finalize Aggregate (cost=49930967.53..49930967.54 rows=1 width=8) (actual time=664.605..671.519 rows=1 loops=1) Buffers: shared hit=311 read=55025 -> Gather (cost=49930967.32..49930967.53 rows=2 width=8) (actual time=664.387..671.502 rows=3 loops=1) Workers Planned: 2 Workers Launched: 2 Buffers: shared hit=311 read=55025 -> Partial Aggregate (cost=49929967.32..49929967.33 rows=1 width=8) (actual time=653.953..653.955 rows=1 loops=3) Buffers: shared hit=311 read=55025 -> Parallel Bitmap Heap Scan on t_demo (cost=5390.21..49920339.39 rows=3851169 width=0) (actual time=56.944..489.563 rows=3333334 loops=3) Recheck Cond: ((id_sorted >= 10000000) AND (id_sorted <= 20000000)) Rows Removed by Index Recheck: 5546 Heap Blocks: lossy=19046 Buffers: shared hit=311 read=55025 -> Bitmap Index Scan on idx_brin (cost=0.00..3079.51 rows=9258865 width=0) (actual time=65.293..65.294 rows=541440 loops=1) Index Cond: ((id_sorted >= 10000000) AND (id_sorted <= 20000000)) Buffers: shared hit=311 read=881 Planning: Buffers: shared hit=1 Planning Time: 0.210 ms Execution Time: 671.623 ms (20 rows) |
Where the btree managed the query with just 27,000 blocks, the BRIN index needs around 55,000, which translates into more runtime. BRIN is usually a good idea for such use cases, but it is not always the magic bullet: it needs significantly less space and can be built faster, yet it does not fix every case under all circumstances.
This is not an argument that BRIN is bad — it is usually a speedup compared to btree. The point is that various setups should be compared and the best one chosen. Correlation matters as well.
