Principles and Applications of the Index Types Supported by PostgreSQL

Background

PostgreSQL supports a wide range of features:

1. Open data interfaces that allow PostgreSQL to support a wide range of different data types. Apart from those supported by traditional databases, it also supports GIS, JSON, RANGE, IP, ISBN, image characteristics, chemistry, DNA and a host of others. Users can also expand support for more data types based on their actual business needs.
2. Open operator interfaces that allow PostgreSQL to support not only common operators but also extensional operators, including distance, logical operators (And, Or, Not), image similarity, and geometric , etc. Users can also expand support for more operators based on their actual business needs.
3. An open external data source interface allows PostgreSQL to support a wide range of different external data sources. You can read and write MySQL, redis, mongo, oracle, sqlserver, hive, www, hbase, ldap, and many other data sources with the FDW interface.
4. An open language interface allows PostgreSQL to support the use of almost any programming language in the world, including plpython, plperl, pljava, plR, plCUDA, and plshell, as database functions and scripts. Users can expand the languages to be supported by PostgreSQL through the language handler.
5. Open index interfaces allow PostgreSQL to support extensive indexes, such as btree, hash, gin, gist, sp-gist, brin, bloom, rum, zombodb, and bitmap (greenplum extend). Users can choose different indexes based on different data and query types.
6. PostgreSQL also supports BitmapAnd and BitmapOr optimization methods internally, and supports the merger of scanning operations on multiple indexes, so as to more efficiently access data on multiple indexes.

PostgreSQL has different index interfaces for different data types and business scenarios. Let's introduce the principles and application scenarios for each index.

I. B-tree

Principle

In-depth Introduction to PostgreSQL B-Tree Index Structure

Application scenarios

B-tree indexes are applicable to all data types. They can be used in sorting as well as greater than, less than, equals, greater than or equal to, less than or equal to searches.

If we use indexes in combination with Recursive Query, we can also achieve rapid searches for sparse codes.

PostgrSQL - a few applications of recursive SQL - thoughts of geeks and normal persons

Example

postgres=# create table t_btree(id int, info text);  
CREATE TABLE  
postgres=# insert into t_btree select generate_series(1,10000), md5(random()::text) ;  
INSERT 0 10000  
postgres=# create index idx_t_btree_1 on t_btree using btree (id);  
CREATE INDEX  
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from t_btree where id=1;  
                                                          QUERY PLAN                                                             
-------------------------------------------------------------------------------------------------------------------------------  
 Index Scan using idx_t_btree_1 on public.t_btree  (cost=0.29..3.30 rows=1 width=37) (actual time=0.027..0.027 rows=1 loops=1)  
   Output: id, info  
   Index Cond: (t_btree.id = 1)  
   Buffers: shared hit=1 read=2  
 Planning time: 0.292 ms  
 Execution time: 0.050 ms  
(6 rows)

II. Hash

Principle

src/backend/access/hash/README

（hash index entries store only the hash code, not the actual data value, for each indexed item. ）

Application scenarios

A hash index stores the hash of the value of the indexed field, and only supports equality queries.

Hash indexes are particularly useful in scenarios where you have very long VALUE fields (an index page of the B-tree indexes needs to store at least 3 Entries, so B-tree indexes do not support very long VALUE fields). For example, when users need to run “Equal To” searches on extremely long strings, it is recommended to use the Hash indexes.

Example

postgres=# create table t_hash (id int, info text);  
CREATE TABLE  
postgres=# insert into t_hash select generate_series(1,100), repeat(md5(random()::text),10000);  
INSERT 0 100  
  
-- Using a B-tree index will return an error, as the length exceeds 1/3 of the index page.
postgres=# create index idx_t_hash_1 on t_hash using btree (info);  
ERROR:  index row size 3720 exceeds maximum 2712 for index "idx_t_hash_1"  
HINT:  Values larger than 1/3 of a buffer page cannot be indexed.  
Consider a function index of an MD5 hash of the value, or use full text indexing.  
  
postgres=# create index idx_t_hash_1 on t_hash using hash (info);  
CREATE INDEX  
  
postgres=# set enable_hashjoin=off;  
SET  
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from t_hash where info in (select info from t_hash limit 1);  
                                                             QUERY PLAN                                                                
-------------------------------------------------------------------------------------------------------------------------------------  
 Nested Loop  (cost=0.03..3.07 rows=1 width=22) (actual time=0.859..0.861 rows=1 loops=1)  
   Output: t_hash.id, t_hash.info  
   Buffers: shared hit=11  
   ->  HashAggregate  (cost=0.03..0.04 rows=1 width=18) (actual time=0.281..0.281 rows=1 loops=1)  
         Output: t_hash_1.info  
         Group Key: t_hash_1.info  
         Buffers: shared hit=3  
         ->  Limit  (cost=0.00..0.02 rows=1 width=18) (actual time=0.012..0.012 rows=1 loops=1)  
               Output: t_hash_1.info  
               Buffers: shared hit=1  
               ->  Seq Scan on public.t_hash t_hash_1  (cost=0.00..2.00 rows=100 width=18) (actual time=0.011..0.011 rows=1 loops=1)  
                     Output: t_hash_1.info  
                     Buffers: shared hit=1  
   ->  Index Scan using idx_t_hash_1 on public.t_hash  (cost=0.00..3.02 rows=1 width=22) (actual time=0.526..0.527 rows=1 loops=1)  
         Output: t_hash.id, t_hash.info  
         Index Cond: (t_hash.info = t_hash_1.info)  
         Buffers: shared hit=6  
 Planning time: 0.159 ms  
 Execution time: 0.898 ms  
(19 rows)  

III. Gin

Principle

A gin index is an inverted index that stores the value or value element of the indexed field, as well as the list or tree of the row.

(col_val:(tid_list or tid_tree), col_val_elements:(tid_list or tid_tree))

PostgreSQL - GIN index principles

The best sword for the best man - equivalent searches on arbitrary combinations of fields - exploring PostgreSQL multi-array expansion of B-tree indexes (GIN)

Application scenarios

1. Gin indexes are applicable to searches on values with multi-value data types, such as array, full-text search, and token. Gin indexes support multiple searches for different types of data, including intersection, contains, greater than, left, and right.)
2. When user data is relatively sparse and the user wishes to search for a value, B-tree_gin may be adapted to support any data type supported by B-tree. (Supports B-tree operators)
3. When a user needs to search by random columns, gin allows the creation of independent index fields in multiple columns, and supports the merger of bitmapAnd and bitmapOr to quickly return data for random column search requests.

Example

1.Search over multi-value data

postgres=# create table t_gin1 (id int, arr int[]);  
CREATE TABLE  
  
postgres=# do language plpgsql 
$$
  
postgres$# declare  
postgres$# begin  
postgres$#   for i in 1..10000 loop  
postgres$#     insert into t_gin1 select i, array(select random()*1000 from generate_series(1,10));  
postgres$#   end loop;  
postgres$# end;  
postgres$# 
$$
;  
DO  
postgres=# select * from t_gin1 limit 3;  
 id |                    arr                      
----+-------------------------------------------  
  1 | {128,700,814,592,414,838,615,827,274,210}  
  2 | {284,452,824,556,132,121,21,705,537,865}  
  3 | {65,185,586,872,627,330,574,227,827,64}  
(3 rows)  
  
postgres=# create index idx_t_gin1_1 on t_gin1 using gin (arr);  
CREATE INDEX  
  
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from t_gin1 where arr && array[1,2];  
                                                       QUERY PLAN                                                          
-------------------------------------------------------------------------------------------------------------------------  
 Bitmap Heap Scan on public.t_gin1  (cost=8.93..121.24 rows=185 width=65) (actual time=0.058..0.207 rows=186 loops=1)  
   Output: id, arr  
   Recheck Cond: (t_gin1.arr && '{1,2}'::integer[])  
   Heap Blocks: exact=98  
   Buffers: shared hit=103  
   ->  Bitmap Index Scan on idx_t_gin1_1  (cost=0.00..8.89 rows=185 width=0) (actual time=0.042..0.042 rows=186 loops=1)  
         Index Cond: (t_gin1.arr && '{1,2}'::integer[])  
         Buffers: shared hit=5  
 Planning time: 0.208 ms  
 Execution time: 0.245 ms  
(10 rows)  
  
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from t_gin1 where arr @> array[1,2];  
                                                     QUERY PLAN                                                        
---------------------------------------------------------------------------------------------------------------------  
 Bitmap Heap Scan on public.t_gin1  (cost=7.51..9.02 rows=1 width=65) (actual time=0.022..0.022 rows=0 loops=1)  
   Output: id, arr  
   Recheck Cond: (t_gin1.arr @> '{1,2}'::integer[])  
   Buffers: shared hit=5  
   ->  Bitmap Index Scan on idx_t_gin1_1  (cost=0.00..7.51 rows=1 width=0) (actual time=0.020..0.020 rows=0 loops=1)  
         Index Cond: (t_gin1.arr @> '{1,2}'::integer[])  
         Buffers: shared hit=5  
 Planning time: 0.116 ms  
 Execution time: 0.044 ms  
(9 rows) 

2.Search over single-value sparse data

postgres=# create extension btree_gin;  
CREATE EXTENSION  
postgres=# create table t_gin2 (id int, c1 int);  
CREATE TABLE  
postgres=# insert into t_gin2 select generate_series(1,100000), random()*10 ;  
INSERT 0 100000  
postgres=# create index idx_t_gin2_1 on t_gin2 using gin (c1);  
CREATE INDEX  
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from t_gin2 where c1=1;  
                                                         QUERY PLAN                                                            
-----------------------------------------------------------------------------------------------------------------------------  
 Bitmap Heap Scan on public.t_gin2  (cost=84.10..650.63 rows=9883 width=8) (actual time=0.925..3.685 rows=10078 loops=1)  
   Output: id, c1  
   Recheck Cond: (t_gin2.c1 = 1)  
   Heap Blocks: exact=443  
   Buffers: shared hit=448  
   ->  Bitmap Index Scan on idx_t_gin2_1  (cost=0.00..81.62 rows=9883 width=0) (actual time=0.867..0.867 rows=10078 loops=1)  
         Index Cond: (t_gin2.c1 = 1)  
         Buffers: shared hit=5  
 Planning time: 0.252 ms  
 Execution time: 4.234 ms  
(10 rows)

3.Search over multiple random columns

postgres=# create table t_gin3 (id int, c1 int, c2 int, c3 int, c4 int, c5 int, c6 int, c7 int, c8 int, c9 int);  
CREATE TABLE  
postgres=# insert into t_gin3 select generate_series(1,100000), random()*10, random()*20, random()*30, random()*40, random()*50, random()*60, random()*70, random()*80, random()*90;  
INSERT 0 100000  
postgres=# create index idx_t_gin3_1 on t_gin3 using gin (c1,c2,c3,c4,c5,c6,c7,c8,c9);  
CREATE INDEX  
  
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from t_gin3 where c1=1 or c2=1 and c3=1 or c4=1 and (c6=1 or c7=2) or c8=9 or c9=10;  
                                                                                              QUERY PLAN                                                                                                 
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------  
 Bitmap Heap Scan on public.t_gin3  (cost=154.03..1364.89 rows=12286 width=40) (actual time=1.931..5.634 rows=12397 loops=1)  
   Output: id, c1, c2, c3, c4, c5, c6, c7, c8, c9  
   Recheck Cond: ((t_gin3.c1 = 1) OR ((t_gin3.c2 = 1) AND (t_gin3.c3 = 1)) OR (((t_gin3.c4 = 1) AND (t_gin3.c6 = 1)) OR ((t_gin3.c4 = 1) AND (t_gin3.c7 = 2))) OR (t_gin3.c8 = 9) OR (t_gin3.c9 = 10))  
   Heap Blocks: exact=834  
   Buffers: shared hit=867  
   ->  BitmapOr  (cost=154.03..154.03 rows=12562 width=0) (actual time=1.825..1.825 rows=0 loops=1)  
         Buffers: shared hit=33  
         ->  Bitmap Index Scan on idx_t_gin3_1  (cost=0.00..83.85 rows=9980 width=0) (actual time=0.904..0.904 rows=10082 loops=1)  
               Index Cond: (t_gin3.c1 = 1)  
               Buffers: shared hit=6  
         ->  Bitmap Index Scan on idx_t_gin3_1  (cost=0.00..9.22 rows=172 width=0) (actual time=0.355..0.355 rows=164 loops=1)  
               Index Cond: ((t_gin3.c2 = 1) AND (t_gin3.c3 = 1))  
               Buffers: shared hit=8  
         ->  BitmapOr  (cost=21.98..21.98 rows=83 width=0) (actual time=0.334..0.334 rows=0 loops=1)  
               Buffers: shared hit=13  
               ->  Bitmap Index Scan on idx_t_gin3_1  (cost=0.00..7.92 rows=42 width=0) (actual time=0.172..0.172 rows=36 loops=1)  
                     Index Cond: ((t_gin3.c4 = 1) AND (t_gin3.c6 = 1))  
                     Buffers: shared hit=6  
               ->  Bitmap Index Scan on idx_t_gin3_1  (cost=0.00..7.91 rows=41 width=0) (actual time=0.162..0.162 rows=27 loops=1)  
                     Index Cond: ((t_gin3.c4 = 1) AND (t_gin3.c7 = 2))  
                     Buffers: shared hit=7  
         ->  Bitmap Index Scan on idx_t_gin3_1  (cost=0.00..14.38 rows=1317 width=0) (actual time=0.124..0.124 rows=1296 loops=1)  
               Index Cond: (t_gin3.c8 = 9)  
               Buffers: shared hit=3  
         ->  Bitmap Index Scan on idx_t_gin3_1  (cost=0.00..12.07 rows=1010 width=0) (actual time=0.102..0.102 rows=1061 loops=1)  
               Index Cond: (t_gin3.c9 = 10)  
               Buffers: shared hit=3  
 Planning time: 0.272 ms  
 Execution time: 6.349 ms  
(29 rows)  

IV. Gist

Principle

GiST stands for Generalized Search Tree.

It is a balanced, tree-structured access method that acts as a base template in which to implement arbitrary indexing schemes.

B-trees, R-trees and many other indexing schemes can be implemented in GiST.

Getting started with complicated fuzzy search - PostgreSQL unique skills - I. Principles and technical backgrounds of GIN, Gist, SP-GiST, and RUM indexes

Application scenarios

GiST is a generalized index interface. You can use GiST to create B-tree, R-tree and other index structures.

Different types of indexes support different indexed searches. For example:

1. The geometry index type supports location searches (Contain, Intersection, Top, Bottom, Left, Right, etc.), and sorting by distance.
2. The range type supports location searches (Contain, Intersection, Left, Right, etc.).
3. The IP type supports location searches (Contain, Intersection, Left, Right, etc.).
4. The spatial type (PostGIS) supports location searches (Contain, Intersection, Top, Bottom, Left, Right, etc.), and sorting by distance.
5. The scale type supports sorting by distance.

Performance of PostgreSQL for querying neighboring geographical locations among tens of billions of data entries

Example

1.Searching with a geometry index

postgres=# create table t_gist (id int, pos point);  
CREATE TABLE  
postgres=# insert into t_gist select generate_series(1,100000), point(round((random()*1000)::numeric, 2), round((random()*1000)::numeric, 2));  
INSERT 0 100000  
postgres=# select * from t_gist  limit 3;  
 id |       pos         
----+-----------------  
  1 | (325.43,477.07)  
  2 | (257.65,710.94)  
  3 | (502.42,582.25)  
(3 rows)  
postgres=# create index idx_t_gist_1 on t_gist using gist (pos);  
CREATE INDEX  
  
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from t_gist where circle '((100,100) 10)'  @> pos;  
                                                       QUERY PLAN                                                         
------------------------------------------------------------------------------------------------------------------------  
 Bitmap Heap Scan on public.t_gist  (cost=2.55..125.54 rows=100 width=20) (actual time=0.072..0.132 rows=46 loops=1)  
   Output: id, pos  
   Recheck Cond: ('<(100,100),10>'::circle @> t_gist.pos)  
   Heap Blocks: exact=41  
   Buffers: shared hit=47  
   ->  Bitmap Index Scan on idx_t_gist_1  (cost=0.00..2.53 rows=100 width=0) (actual time=0.061..0.061 rows=46 loops=1)  
         Index Cond: ('<(100,100),10>'::circle @> t_gist.pos)  
         Buffers: shared hit=6  
 Planning time: 0.147 ms  
 Execution time: 0.167 ms  
(10 rows)  
  
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from t_gist where circle '((100,100) 1)' @> pos order by pos <-> '(100,100)' limit 10;  
                                                              QUERY PLAN                                                                 
---------------------------------------------------------------------------------------------------------------------------------------  
 Limit  (cost=0.28..14.60 rows=10 width=28) (actual time=0.045..0.048 rows=2 loops=1)  
   Output: id, pos, ((pos <-> '(100,100)'::point))  
   Buffers: shared hit=5  
   ->  Index Scan using idx_t_gist_1 on public.t_gist  (cost=0.28..143.53 rows=100 width=28) (actual time=0.044..0.046 rows=2 loops=1)  
         Output: id, pos, (pos <-> '(100,100)'::point)  
         Index Cond: ('<(100,100),1>'::circle @> t_gist.pos)  
         Order By: (t_gist.pos <-> '(100,100)'::point)  
         Buffers: shared hit=5  
 Planning time: 0.092 ms  
 Execution time: 0.076 ms  
(10 rows)

2.Sorting with a scale index

postgres=# create extension btree_gist;  
CREATE EXTENSION  
  
postgres=# create index idx_t_btree_2 on t_btree using gist(id);  
CREATE INDEX  
  
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from t_btree order by id <-> 100 limit 1;  
                                                                QUERY PLAN                                                                   
-------------------------------------------------------------------------------------------------------------------------------------------  
 Limit  (cost=0.15..0.19 rows=1 width=41) (actual time=0.046..0.046 rows=1 loops=1)  
   Output: id, info, ((id <-> 100))  
   Buffers: shared hit=3  
   ->  Index Scan using idx_t_btree_2 on public.t_btree  (cost=0.15..408.65 rows=10000 width=41) (actual time=0.045..0.045 rows=1 loops=1)  
         Output: id, info, (id <-> 100)  
         Order By: (t_btree.id <-> 100)  
         Buffers: shared hit=3  
 Planning time: 0.085 ms  
 Execution time: 0.076 ms  
(9 rows)  

V. SP-GiST

Principle

SP-GiST is an abbreviation for space-partitioned GiST.

SP-GiST supports partitioned search trees, which facilitate development of a wide range of different non-balanced data structures, such as quad-trees, k-d trees, and radix trees (tries).

The common feature of these structures is that they repeatedly divide the search space into partitions that need not be of equal size.

Searches that are well matched to the partitioning rule can be very fast.

Similar to GiST, SP-GiST is a generic index interface. The difference is that the SP-GiST uses spatial partitioning, which allows SP-GiST to better support unevenly distributed data structures, such as quad-trees, k-d trees, and radis trees.

《Space-partitioning trees in PostgreSQL》

《SP-GiST for PostgreSQL User Manual》

Application scenarios

1. The geometry index type supports location searches (Contain, Intersection, Top, Bottom, Left, Right, etc.), and sorting by distance.
2. The range type supports location searches (Contain, Intersection, Left, Right, etc.).
3. The IP type supports location searches (Contain, Intersection, Left, Right, etc.).

Example

1. Searching with a range index

postgres=# create table t_spgist (id int, rg int4range);  
CREATE TABLE  
  
postgres=# insert into t_spgist select id, int4range(id, id+(random()*200)::int) from generate_series(1,100000) t(id);  
INSERT 0 100000  
postgres=# select * from t_spgist  limit 3;  
 id |   rg      
----+---------  
  1 | [1,138)  
  2 | [2,4)  
  3 | [3,111)  
(3 rows)  
  
postgres=# set maintenance_work_mem ='32GB';  
SET  
postgres=# create index idx_t_spgist_1 on t_spgist using spgist (rg);  
CREATE INDEX  
  
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from t_spgist where rg && int4range(1,100);  
                                                       QUERY PLAN                                                          
-------------------------------------------------------------------------------------------------------------------------  
 Bitmap Heap Scan on public.t_spgist  (cost=2.55..124.30 rows=99 width=17) (actual time=0.059..0.071 rows=99 loops=1)  
   Output: id, rg  
   Recheck Cond: (t_spgist.rg && '[1,100)'::int4range)  
   Heap Blocks: exact=1  
   Buffers: shared hit=6  
   ->  Bitmap Index Scan on idx_t_spgist_1  (cost=0.00..2.52 rows=99 width=0) (actual time=0.043..0.043 rows=99 loops=1)  
         Index Cond: (t_spgist.rg && '[1,100)'::int4range)  
         Buffers: shared hit=5  
 Planning time: 0.133 ms  
 Execution time: 0.111 ms  
(10 rows)  
  
postgres=# set enable_bitmapscan=off;  
SET  
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from t_spgist where rg && int4range(1,100);  
                                                             QUERY PLAN                                                                
-------------------------------------------------------------------------------------------------------------------------------------  
 Index Scan using idx_t_spgist_1 on public.t_spgist  (cost=0.28..141.51 rows=99 width=17) (actual time=0.021..0.051 rows=99 loops=1)  
   Output: id, rg  
   Index Cond: (t_spgist.rg && '[1,100)'::int4range)  
   Buffers: shared hit=8  
 Planning time: 0.097 ms  
 Execution time: 0.074 ms  
(6 rows)  

VI. BRIN

Principle

A BRIN index is a block range index. It is different from other indexes, such as B-tree indexes, in that a BRIN index does not store information by row number. Rather, it stores the statistical information of each data block or each consecutive data block. The result is that a BRIN index requires much less space than other indexes, and has very low impact on the process of writing, updating, and deleting data.

BRIN indexes are lossy, and perform particularly well when the values of the indexed columns are strongly correlated with the physical storage.

Taking chronological data for example, BRIN indexes would perform very well on Equals and Range searches if created based on the time or serial fields.

Application scenarios

BRIN (block range index) index

The cutting-edge technology of PostgreSQL for IoT - creating an index (BRIN Index) a fraction of the normal size

PostgreSQL aggregates storage and BRIN indexes - searching high throughput data on highly concurrent behavior and tracks

How to ensure chronologically linear storage when writing in parallel to heap tables with PostgreSQL - BRIN index optimization

Example

postgres=# create table t_brin (id int, info text, crt_time timestamp);  
CREATE TABLE  
postgres=# insert into t_brin select generate_series(1,1000000), md5(random()::text), clock_timestamp();  
INSERT 0 1000000  
  
postgres=# select ctid,* from t_brin limit 3;  
 ctid  | id |               info               |          crt_time            
-------+----+----------------------------------+----------------------------  
 (0,1) |  1 | e48a6cd688b6cc8e86ee858fa993b31b | 2017-06-27 22:50:19.172224  
 (0,2) |  2 | e79c335c679b0bf544e8ba5f01569df7 | 2017-06-27 22:50:19.172319  
 (0,3) |  3 | b75ec6db320891a620097164b751e682 | 2017-06-27 22:50:19.172323  
(3 rows)  
  
  
postgres=# select correlation from pg_stats where tablename='t_brin' and attname='id';  
 correlation   
-------------  
           1  
(1 row)  
  
postgres=# select correlation from pg_stats where tablename='t_brin' and attname='crt_time';  
 correlation   
-------------  
           1  
(1 row)  
  
postgres=# create index idx_t_brin_1 on t_brin using brin (id) with (pages_per_range=1);  
CREATE INDEX  
postgres=# create index idx_t_brin_2 on t_brin using brin (crt_time) with (pages_per_range=1);  
CREATE INDEX  
  
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from t_brin where id between 100 and 200;  
                                                       QUERY PLAN                                                          
-------------------------------------------------------------------------------------------------------------------------  
 Bitmap Heap Scan on public.t_brin  (cost=43.52..199.90 rows=74 width=45) (actual time=1.858..1.876 rows=101 loops=1)  
   Output: id, info, crt_time  
   Recheck Cond: ((t_brin.id >= 100) AND (t_brin.id <= 200))  
   Rows Removed by Index Recheck: 113  
   Heap Blocks: lossy=2  
   Buffers: shared hit=39  
   ->  Bitmap Index Scan on idx_t_brin_1  (cost=0.00..43.50 rows=107 width=0) (actual time=1.840..1.840 rows=20 loops=1)  
         Index Cond: ((t_brin.id >= 100) AND (t_brin.id <= 200))  
         Buffers: shared hit=37  
 Planning time: 0.174 ms  
 Execution time: 1.908 ms  
(11 rows)  
  
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from t_brin where crt_time between '2017-06-27 22:50:19.172224' and '2017-06-27 22:50:19.182224';  
                                                                                       QUERY PLAN                                                                                          
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------  
 Bitmap Heap Scan on public.t_brin  (cost=59.63..4433.67 rows=4474 width=45) (actual time=1.860..2.603 rows=4920 loops=1)  
   Output: id, info, crt_time  
   Recheck Cond: ((t_brin.crt_time >= '2017-06-27 22:50:19.172224'::timestamp without time zone) AND (t_brin.crt_time <= '2017-06-27 22:50:19.182224'::timestamp without time zone))  
   Rows Removed by Index Recheck: 2  
   Heap Blocks: lossy=46  
   Buffers: shared hit=98  
   ->  Bitmap Index Scan on idx_t_brin_2  (cost=0.00..58.51 rows=4494 width=0) (actual time=1.848..1.848 rows=460 loops=1)  
         Index Cond: ((t_brin.crt_time >= '2017-06-27 22:50:19.172224'::timestamp without time zone) AND (t_brin.crt_time <= '2017-06-27 22:50:19.182224'::timestamp without time zone))  
         Buffers: shared hit=52  
 Planning time: 0.091 ms  
 Execution time: 2.884 ms  
(11 rows)  

VII. Rum

Principle

https://github.com/postgrespro/rum

RUM is a Postgres Pro Enterprise extension that serves as an enhanced version GIN index and is perfect for full-text search.

Enhancements include:

1. A RUM index stores the positional information of lexems. So, when calculating the ranking, RUM does not need to query back in the table (required for GIN indexes).
2. RUM supports phrase searches, which are not supported by GIN.
3. A RUM index allows the user to store field values apart from the ctid (line number) in the posting tree, e.g. the timestamp.

As a result, a RUM index supports not only the full-text searches supported by GIN indexes, but also calculating and sorting by the similarity of texts. It also supports positional matching, e.g. (for Fast and Furious, we can do the matching with “Fast” <2> “Furious”, which can not be achieved with GIN indexes).

Positional information is as follows:

postgres=# select to_tsvector('english', 'hello digoal');
     to_tsvector      
----------------------
 'digoal':2 'hello':1
(1 row)

postgres=# select to_tsvector('english', 'hello i digoal');
     to_tsvector      
----------------------
 'digoal':3 'hello':1
(1 row)

postgres=# select to_tsvector('english', 'hello i am digoal');
     to_tsvector      
----------------------
 'digoal':4 'hello':1
(1 row)

postgres=# select to_tsquery('english', 'hello <1> digoal');
      to_tsquery      
----------------------
 'hello' <-> 'digoal'
(1 row)

postgres=# select to_tsquery('english', 'hello <2> digoal');
      to_tsquery      
----------------------
 'hello' <2> 'digoal'
(1 row)

postgres=# select to_tsquery('english', 'hello <3> digoal');
      to_tsquery      
----------------------
 'hello' <3> 'digoal'
(1 row)

postgres=# select to_tsvector('hello digoal') @@ to_tsquery('english', 'hello <1> digoal');
 ?column? 
----------
 t
(1 row)

postgres=# select to_tsvector('hello digoal') @@ to_tsquery('english', 'hello <2> digoal');
 ?column? 
----------
 f
(1 row)

postgres=# select to_tsvector('hello i digoal') @@ to_tsquery('english', 'hello <2> digoal');
 ?column? 
----------
 t
(1 row)

Application scenarios

Full-text search with PostgreSQL is way too fast - RUM index interface (Pandora box)

Getting started with complicated fuzzy search - PostgreSQL unique skills - I. Principles and technical backgrounds of GIN, Gist, SP-GiST, and RUM indexes

Application of PostgreSQL in combination with cosine and linear relational algorithms in fields of text, images, arrays, and similarities - Analysis of RUM and Smlar in 3 application scenarios

Example

postgres=# create table rum_test(c1 tsvector);  
CREATE TABLE  
  
postgres=# CREATE INDEX rumidx ON rum_test USING rum (c1 rum_tsvector_ops);  
CREATE INDEX  
  
$ vi test.sql  
insert into rum_test select to_tsvector(string_agg(c1::text,',')) from  (select (100000*random())::int from generate_series(1,100)) t(c1);  
  
$ pgbench -M prepared -n -r -P 1 -f ./test.sql -c 50 -j 50 -t 200000  
  
postgres=# explain analyze select * from rum_test where c1 @@ to_tsquery('english','1 | 2') order by c1 <=> to_tsquery('english','1 | 2') offset 19000 limit 100;  
                                                               QUERY PLAN                                                                  
-----------------------------------------------------------------------------------------------------------------------------------------  
 Limit  (cost=18988.45..19088.30 rows=100 width=1391) (actual time=58.912..59.165 rows=100 loops=1)  
   ->  Index Scan using rumidx on rum_test  (cost=16.00..99620.35 rows=99749 width=1391) (actual time=16.426..57.892 rows=19100 loops=1)  
         Index Cond: (c1 @@ '''1'' | ''2'''::tsquery)  
         Order By: (c1 <=> '''1'' | ''2'''::tsquery)  
 Planning time: 0.133 ms  
 Execution time: 59.220 ms  
(6 rows)  
  
postgres=# create table test15(c1 tsvector);  
CREATE TABLE  
postgres=# insert into test15 values (to_tsvector('jiebacfg', 'hello china, i''m digoal')), (to_tsvector('jiebacfg', 'hello world, i''m postgresql')), (to_tsvector('jiebacfg', 'how are you, i''m digoal'));  
INSERT 0 3  
postgres=# select * from test15;  
                         c1                            
-----------------------------------------------------  
 ' ':2,5,9 'china':3 'digoal':10 'hello':1 'm':8  
 ' ':2,5,9 'hello':1 'm':8 'postgresql':10 'world':3  
 ' ':2,4,7,11 'digoal':12 'm':10  
(3 rows)  
postgres=# create index idx_test15 on test15 using rum(c1 rum_tsvector_ops);  
CREATE INDEX  
postgres=# select *,c1 <=> to_tsquery('hello') from test15;  
                         c1                          | ?column?   
-----------------------------------------------------+----------  
 ' ':2,5,9 'china':3 'digoal':10 'hello':1 'm':8     |  16.4493  
 ' ':2,5,9 'hello':1 'm':8 'postgresql':10 'world':3 |  16.4493  
 ' ':2,4,7,11 'digoal':12 'm':10                     | Infinity  
(3 rows)  
postgres=# explain select *,c1 <=> to_tsquery('postgresql') from test15 order by c1 <=> to_tsquery('postgresql');  
                                   QUERY PLAN                                     
--------------------------------------------------------------------------------  
 Index Scan using idx_test15 on test15  (cost=3600.25..3609.06 rows=3 width=36)  
   Order By: (c1 <=> to_tsquery('postgresql'::text))  
(2 rows)

GIN VS RUM

GIN

postgres=# create table t_gin_1 (id int, ts tsvector);
CREATE TABLE
postgres=# insert into t_gin_1 values (1, to_tsvector('hello digoal')),(2, to_tsvector('hello i digoal')),(3, to_tsvector('hello i am digoal'));
INSERT 0 3
postgres=# create index idx_t_gin_1_1 on t_gin_1 using gin (ts);
CREATE INDEX
postgres=# explain select * from t_gin_1 where ts @@ to_tsquery('english', 'hello <1> digoal');
                       QUERY PLAN                       
--------------------------------------------------------
 Seq Scan on t_gin_1  (cost=0.00..1.04 rows=1 width=36)
   Filter: (ts @@ '''hello'' <-> ''digoal'''::tsquery)
(2 rows)

postgres=# set enable_seqscan=off;
SET
postgres=# explain select * from t_gin_1 where ts @@ to_tsquery('english', 'hello <1> digoal');
                                 QUERY PLAN                                 
----------------------------------------------------------------------------
 Bitmap Heap Scan on t_gin_1  (cost=4.50..6.01 rows=1 width=36)
   Recheck Cond: (ts @@ '''hello'' <-> ''digoal'''::tsquery)
   ->  Bitmap Index Scan on idx_t_gin_1_1  (cost=0.00..4.50 rows=1 width=0)
         Index Cond: (ts @@ '''hello'' <-> ''digoal'''::tsquery)
(4 rows)

postgres=# explain (analyze,verbose,timing,costs,buffers) select * from t_gin_1 where ts @@ to_tsquery('english', 'hello <1> digoal');
                                                      QUERY PLAN                                                      
----------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on public.t_gin_1  (cost=4.50..6.01 rows=1 width=36) (actual time=0.029..0.030 rows=1 loops=1)
   Output: id, ts
   Recheck Cond: (t_gin_1.ts @@ '''hello'' <-> ''digoal'''::tsquery)
   Rows Removed by Index Recheck: 2
   Heap Blocks: exact=1
   Buffers: shared hit=4
   ->  Bitmap Index Scan on idx_t_gin_1_1  (cost=0.00..4.50 rows=1 width=0) (actual time=0.018..0.018 rows=3 loops=1)
         Index Cond: (t_gin_1.ts @@ '''hello'' <-> ''digoal'''::tsquery)
         Buffers: shared hit=3
 Planning time: 0.106 ms
 Execution time: 0.061 ms
(11 rows)

RUM

postgres=# create table t_gin_1 (id int, ts tsvector);
CREATE TABLE
postgres=# insert into t_gin_1 values (1, to_tsvector('hello digoal')),(2, to_tsvector('hello i digoal')),(3, to_tsvector('hello i am digoal'));
INSERT 0 3
postgres=#  create index idx_t_gin_1_1 on t_gin_1 using rum (ts rum_tsvector_ops);
CREATE INDEX
postgres=# explain select * from t_gin_1 where ts @@ to_tsquery('english', 'hello <1> digoal');
                       QUERY PLAN                       
--------------------------------------------------------
 Seq Scan on t_gin_1  (cost=0.00..1.04 rows=1 width=36)
   Filter: (ts @@ '''hello'' <-> ''digoal'''::tsquery)
(2 rows)

postgres=# set enable_seqscan =off;
SET
postgres=# explain select * from t_gin_1 where ts @@ to_tsquery('english', 'hello <1> digoal');
                                  QUERY PLAN                                  
------------------------------------------------------------------------------
 Index Scan using idx_t_gin_1_1 on t_gin_1  (cost=2.00..4.01 rows=1 width=36)
   Index Cond: (ts @@ '''hello'' <-> ''digoal'''::tsquery)
(2 rows)

postgres=# explain (analyze,verbose,timing,costs,buffers) select * from t_gin_1 where ts @@ to_tsquery('english', 'hello <1> digoal');
                                                          QUERY PLAN                                                           
-------------------------------------------------------------------------------------------------------------------------------
 Index Scan using idx_t_gin_1_1 on public.t_gin_1  (cost=2.00..4.01 rows=1 width=36) (actual time=0.049..0.049 rows=1 loops=1)
   Output: id, ts
   Index Cond: (t_gin_1.ts @@ '''hello'' <-> ''digoal'''::tsquery)
   Buffers: shared hit=3
 Planning time: 0.288 ms
 Execution time: 0.102 ms
(6 rows)

VII. Bloom

Principle

Bloom provides a PostgreSQL index access method based on the Bloom filter structure. A bloom index is lossy, and it can collect the results set (excluding results that do not meet the conditions, and select those that meet the conditions from the rest of the results). Therefore, a secondary check is required. Bloom indexes support equality queries on arbitrary column combinations.

A Bloom index stores signatures. A larger signature requires larger space, but it also means more accurate exclusion. Of course, there are pros and cons to this method.

CREATE INDEX bloomidx ON tbloom USING bloom (i1,i2,i3)
       WITH (length=80, col1=2, col2=2, col3=4);

The length of each signature is represented in bits. The default is 80 bits, and the maximum is 4096 bits.

col1 - col32 respectively refer to the number of bits generated for each index column. The default is 2 bits and maximum is 4095 bits.

Bloom provides an index access method based on Bloom filters.

A Bloom filter is a space-efficient data structure that is used to test whether an element is a member of a set. In the case of an index access method, it allows fast exclusion of non-matching tuples via signatures whose size is determined at index creation.

This type of index is most useful when a table has many attributes and queries test arbitrary combinations of them.

Application scenarios

Bloom indexes are useful for queries on arbitrary combinations of multiple columns

Cutting-edge technology of PostgreSQL 9.6 – a single Bloom algorithm index to support queries on arbitrary combinations of columns

Example

=# CREATE TABLE tbloom AS  
   SELECT  
     (random() * 1000000)::int as i1,  
     (random() * 1000000)::int as i2,  
     (random() * 1000000)::int as i3,  
     (random() * 1000000)::int as i4,  
     (random() * 1000000)::int as i5,  
     (random() * 1000000)::int as i6  
   FROM  
  generate_series(1,10000000);  
SELECT 10000000  
=# CREATE INDEX bloomidx ON tbloom USING bloom (i1, i2, i3, i4, i5, i6);  
CREATE INDEX  
=# SELECT pg_size_pretty(pg_relation_size('bloomidx'));  
 pg_size_pretty  
----------------  
 153 MB  
(1 row)  
=# CREATE index btreeidx ON tbloom (i1, i2, i3, i4, i5, i6);  
CREATE INDEX  
=# SELECT pg_size_pretty(pg_relation_size('btreeidx'));  
 pg_size_pretty  
----------------  
 387 MB  
(1 row)  
  
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;  
                                                        QUERY PLAN  
---------------------------------------------------------------------------------------------------------------------------  
 Bitmap Heap Scan on tbloom  (cost=178435.39..178439.41 rows=1 width=24) (actual time=76.698..76.698 rows=0 loops=1)  
   Recheck Cond: ((i2 = 898732) AND (i5 = 123451))  
   Rows Removed by Index Recheck: 2439  
   Heap Blocks: exact=2408  
   ->  Bitmap Index Scan on bloomidx  (cost=0.00..178435.39 rows=1 width=0) (actual time=72.455..72.455 rows=2439 loops=1)  
         Index Cond: ((i2 = 898732) AND (i5 = 123451))  
 Planning time: 0.475 ms  
 Execution time: 76.778 ms  
(8 rows)  

IX. Zombodb

Principle

ZomboDB is a PostgreSQL extension that allows you to create indexes that use Elasticsearch (“ES”).

https://github.com/zombodb/zombodb

Application scenarios

Combining with ES allows the creation of a search engine that uses the SQL interface, as well as transparent data searches.

Example

-- Install the extension:  
  
CREATE EXTENSION zombodb;  
  
-- Create a table:  
  
CREATE TABLE products (  
    id SERIAL8 NOT NULL PRIMARY KEY,  
    name text NOT NULL,  
    keywords varchar(64)[],  
    short_summary phrase,  
    long_description fulltext,   
    price bigint,  
    inventory_count integer,  
    discontinued boolean default false,  
    availability_date date  
);  
  
-- insert some data  
-- Index it:  
  
CREATE INDEX idx_zdb_products   
          ON products   
       USING zombodb(zdb('products', products.ctid), zdb(products))  
        WITH (url='http://localhost:9200/', shards=5, replicas=1);  
  
-- Query it:  
  
SELECT *   
  FROM products   
 WHERE zdb('products', ctid) ==> 'keywords:(sports,box) or long_description:(wooden w/5 away) and price < 100000';  

X. Bitmap

Principle

A Bitmap index is the index interface of Greenplum, similar to GIN. The difference is that the KEY of a bitmap index is the value of the index column, while the VALUE of a bitmap is BIT (each BIT matches a line) rather than list of row numbers or a tree.

Greenplum best practices - when to use Bitmap indexes

Application scenarios

When the number of unique values of a field is between 100 and 100,000 (bitmap is not recommended if the number is beyond this range), if the number of records in the table is very big and it does not change frequently (or AO table), then using Bitmap indexes is probably your best option. Bitmap indexes can allow you to quickly search for multiple values or a single value. We only need to perform bit operations on or compute the Bitmap of the row numbers to obtain the final Bitmap, and then retrieve the results from lines based on that.

Similar to B-tree indexes, Bitmap indexes support equals, greater than, smaller than, greater than or equal to, and smaller than or equal to searches.

Example

postgres=# create table t_bitmap(id int, info text, c1 int);
NOTICE:  Table doesn't have 'DISTRIBUTED BY' clause -- Using column named 'id' as the Greenplum Database data distribution key for this table.
HINT:  The 'DISTRIBUTED BY' clause determines the distribution of data. Make sure column(s) chosen are the optimal data distribution key to minimize skew.
CREATE TABLE
postgres=# insert into t_bitmap select generate_series(1,1000000), 'test', random()*1000;
INSERT 0 1000000
postgres=# create index idx_t_bitmap_1 on t_bitmap using bitmap(c1);
CREATE INDEX
postgres=# explain analyze select * from t_bitmap where c1=1;
                                       QUERY PLAN                                       
----------------------------------------------------------------------------------------
 Gather Motion 3:1  (slice1; segments: 3)  (cost=0.00..200.27 rows=1 width=13)
   Rows out:  0 rows at destination with 3.769 ms to end, start offset by 0.250 ms.
   ->  Index Scan using idx_t_bitmap_1 on t_bitmap  (cost=0.00..200.27 rows=1 width=13)
         Index Cond: c1 = 1
         Rows out:  0 rows (seg0) with 0.091 ms to end, start offset by 3.004 ms.
 Slice statistics:
   (slice0)    Executor memory: 115K bytes.
   (slice1)    Executor memory: 273K bytes avg x 3 workers, 273K bytes max (seg0).
 Statement statistics:
   Memory used: 128000K bytes
 Total runtime: 4.110 ms
(11 rows)

postgres=# explain analyze select * from t_bitmap where c1<=10;
                                       QUERY PLAN                                       
----------------------------------------------------------------------------------------
 Gather Motion 3:1  (slice1; segments: 3)  (cost=0.00..200.27 rows=1 width=13)
   Rows out:  0 rows at destination with 2.952 ms to end, start offset by 0.227 ms.
   ->  Index Scan using idx_t_bitmap_1 on t_bitmap  (cost=0.00..200.27 rows=1 width=13)
         Index Cond: c1 <= 10
         Rows out:  0 rows (seg0) with 0.055 ms to end, start offset by 3.021 ms.
 Slice statistics:
   (slice0)    Executor memory: 115K bytes.
   (slice1)    Executor memory: 273K bytes avg x 3 workers, 273K bytes max (seg0).
 Statement statistics:
   Memory used: 128000K bytes
 Total runtime: 3.278 ms
(11 rows) 

XI. Varbitx

Principle

Varbitx is an extension pack for Alibaba Cloud RDS that has function interfaces of extensive bit types. Varbitx is actually not an index interface, but it can replace and produce the same effect as Bitmap indexes when used in conjunction with PostgreSQL.

Application scenarios

Introduction to the Alibaba Cloud RDS for PostgreSQL varbitx extension and real-time image application scenarios

Creation of a real-time image recommendation system based on Alibaba Cloud RDS PostgreSQL

PostgreSQL (varbit, roaring bitmap) VS pilosa (bitmap library)

Example

Omitted. Please refer to contents above.

XII. Partial indexes

PostgreSQL allows users to create partial indexes. For example, if your business only cares about active users, you can create indexes for only active users.

Example

create table test(id int, info text, crt_time timestamp, active boolean);  
  
create index idx_test_id on test(id) where active;  
  
select * from test where active and id=?;  -- Partial indexes can be used  

XIII. Expression indexes

Another unique feature in PostgreSQL is expression indexes. Expression indexes are great for scenarios where the user data needs to be converted before the search can be run. For example, when geographic coordinates submitted by certain devices do not conform to the Chinese national standard, we need to convert them into Chinese coordinates to run the search.

We can create expression indexes specifically for these fields, and build the conversion process into the expression, which can also be used in searches.

create table t_express (id int, pos geometry);  
  
create index idx_t_express_1 on t_express using gist ( ( ST_Transform(pos, 26986) ) );  
  
select * from t_express order by ST_Transform(pos, 26986) <-> ST_Transform(ST_GeomFromText('POINT(108.50000000001 22.8)', 4326), 26986) limit 10;  

XIV. Internal inspection index storage

https://www.postgresql.org/docs/9.6/static/pageinspect.html

You can read the contents of the index pages in the pageinspect module.

Example

test=# SELECT * FROM bt_page_stats('pg_cast_oid_index', 1);  
-[ RECORD 1 ]-+-----  
blkno         | 1  
type          | l  
live_items    | 256  
dead_items    | 0  
avg_item_size | 12  
page_size     | 8192  
free_size     | 4056  
btpo_prev     | 0  
btpo_next     | 0  
btpo          | 0  
btpo_flags    | 3  
  
test=# SELECT * FROM bt_page_items('pg_cast_oid_index', 1);  
 itemoffset |  ctid   | itemlen | nulls | vars |    data  
------------+---------+---------+-------+------+-------------  
          1 | (0,1)   |      12 | f     | f    | 23 27 00 00  
          2 | (0,2)   |      12 | f     | f    | 24 27 00 00  
          3 | (0,3)   |      12 | f     | f    | 25 27 00 00  
          4 | (0,4)   |      12 | f     | f    | 26 27 00 00  
          5 | (0,5)   |      12 | f     | f    | 27 27 00 00  
          6 | (0,6)   |      12 | f     | f    | 28 27 00 00  
          7 | (0,7)   |      12 | f     | f    | 29 27 00 00  
          8 | (0,8)   |      12 | f     | f    | 2a 27 00 00  
  
test=# SELECT * FROM brin_page_items(get_raw_page('brinidx', 5),  
                                     'brinidx')  
       ORDER BY blknum, attnum LIMIT 6;  
 itemoffset | blknum | attnum | allnulls | hasnulls | placeholder |    value       
------------+--------+--------+----------+----------+-------------+--------------  
        137 |      0 |      1 | t        | f        | f           |   
        137 |      0 |      2 | f        | f        | f           | {1 .. 88}  
        138 |      4 |      1 | t        | f        | f           |   
        138 |      4 |      2 | f        | f        | f           | {89 .. 176}  
        139 |      8 |      1 | t        | f        | f           |   
        139 |      8 |      2 | f        | f        | f           | {177 .. 264}