Principles and Optimization of 5 PostgreSQL Indexes (btree,hash,gin,gist,and brin)

Note: This article contains links to Chinese blog articles.

The above methods require certain adjustments to the program (of course if the user already has a PostgreSQL technology stack, modifications will be minimal). See below for an example.

Let’s assume a user uses multiple columns to indicate different attributes, and each attribute matches the value range of certain TAGs.

<code>create table user_tags(uid int8 primary key, lab1 int, lab2 text, lab3 timestamp, lab4 text, lab5 interval, lab6 json);</code>

The user's original tag and statistical inquiry may look like this:

Continuous queries like between and, need to be converted into hash queries. While this makes programming more complicated, it could also provide the most optimal performance.

Does PostgreSQL provide a better method?

The answer is yes. Solutions are created for the lazy, and the lazy thereby drive progress!

You can refer to the following articles to learn more about PostgreSQL solutions.

1.Use bitmapand, bitmapor, and any index to tag people.

<a href="https://github.com/digoal/blog/blob/master/201706/20170607_02.md">Multi-field queries with any combination of conditions (without modeling) - best practices for real-time tagging in milliseconds</a>

2.Use the varbitx extension to tag people.

<a href="https://github.com/digoal/blog/blob/master/201705/20170502_01.md">Introduction to the Alibaba Cloud RDS for PostgreSQL varbitx extension and real-time image applications</a>

Let’s see how it works in scenarios with continuous queries, equality queries, and queries with multiple combinations of conditions.

Create a TAG table

Insert a batch of data

Data model

Analyze table statistics

Check the hash degree for each column

Based on the above statistical information, we should create btree indexes for a unique column, and create gin indexes (inverted indexes) for a loose column to achieve the best effect.

In order to enable common types to support gin, we need to create the btree_gin extension.

Query testing shows that queries on any combination of c1 and c6 are very efficient .

So let’s create btree indexes for the other columns. The n_distinct values of the other columns indicate that the values in these columns are basically unique, so we are going to create btree indexes, which allows us to precisely locate the value we need.

Create brin indexes for columns in good linear correlation. Principles and selection of indexes will be detailed later.

Queries on combinations of multiple columns are very efficient.

The performance of queries on arbitrary conditions can be significantly improved by filtering data with bitmapAnd and bitmapOr and by using multiple indexes Operational principles are as follows:

How do I select an index? This will be detailed later.

I used GIN multi-column compound indexes in the above example, but there is actually another way around the issue. We can convert multiple columns into an array, and create array indexes (PostgreSQL expression indexes)

1.How can multiple columns be converted into an array?

2.Array expression indexes

Example

3.How to hit array expression indexes?

When the query condition is consistent with the expression of the index, it is hit.

<b>1.When to choose btree?</b>

B-tree indexes are suitable for columns with better selection properties (value of n_distinct is very big, or =-1), or there is a high proportion of unique values.

<b>2.When to choose gin?</b>

Contrary to btree indexes, GIN indexes are more efficient if the columns have poor selection properties.

In addition, as GIN indexes are inverted indexes, they are very appropriate for queries on combinations of multi-value elements, e.g. array, full-text search, token, etc.

As interfaces for GIN indexes are open, you can customize your GIN indexes according to the individual characteristics of your data. It supports more data types, e.g.similarity between images, text similarity, etc.

<b>3.When to choose gist?</b>

GIST is a generalized index interface belonging to PostgreSQL. It is appropriate for various data types, particularly heterogeneous types, e.g. geometry index, spatial index, range index, etc.

Refer to the following for the principles of GIST indexes:

<a href="https://github.com/digoal/blog/blob/master/201612/20161231_01.md">Getting started with complicated fuzzy search - PostgreSQL unique skills - I. Principles and technical background of GIN, Gist, SP-GiST, and RUM indexes</a>

<b>4.When to choose hash?</b>

Hash indexes are useful if you are only dealing with equality queries, and the length of the indexed columns is very long, more than 1/3 of the database block length. PostgreSQL 10 hash indexes will generate WAL. To ensure reliability, it also supports stream replication.

Hash indexes are not recommended for PostgreSQL versions earlier than version 10, as rebuilding is required after a crash and prior versions do not support stream replication.

<b>5.When to choose brin?</b>

BRIN indexes can be used when the data and stack storage are linearly correlated.

A BRIN index is a block range index. It stores the atomic information (max value, min value, average value, null ratio, COUNT, etc.) of each data block (or consecutive data blocks).

It is particularly suitable for range scans.

<b>1.btree</b>

Supports sorting, “&gt;=”, “&lt;=”, “=”, “in”, “&gt;”, “&lt;” and other queries.

<b>2.HASH</b>

Supports “=” queries.

<b>3.GIN</b>

Supports different query demands based on different data types.

For example, if the data is made up of arrays intersection and "Contains" queries are most appropriate.

<b>4.GIST</b>

For example, if the data is spatial, appropriate query types include distance, KNN, "Contains", intersection, Left, and Right.

<b>5.BRIN</b>

Supports range queries, and “=” queries

The above explains how to select an index type, but does not mention how to optimize your indexes. In reality, the efficiency of an index is heavily reliant on data distribution.

For example

<a href="https://github.com/digoal/blog/blob/master/201404/20140426_01.md">Statistical principles and solutions to heap scan IO enlargement arising from Index order scan - PostgreSQL index scan enlarge heap page scans when index and column correlation small</a>

Therefore, the efficiency of our index queries can be greatly improved if our data is redistributed according to the characteristics of index scans.

For example, bitmap index scan (read in the order of Block Ids) can be used in PostgreSQL to reduce discrete IO.

1.btree data distribution optimization

Better linear correlation makes scanning and returning multiple data records more efficient.

2.Optimizing hash data distribution

3.Optimizing gin data distribution

For normal data, better linear correlation makes scanning and returning multiple data records more efficient.

For multi-value data (e.g. array, full-text searches, TOKENs), queries are more efficient the more the elements are concentrated (e.g. in element concentration analysis, where the x axis is the row number and the y axis is the element value, the more the data is concentrated).

It is usually not easy to achieve element concentration, but we have several methods to aggregate data. 1. Sort and restructure data based on the frequency of the elements. When users search frequently occurring terms, fewer blocks need to be searched and the IO enlargement is reduced. 2. Sort based on the value (of the count of searched elements x the hit number), and aggregate data in a descending order from the element that ranks first.

(The above methods might be a bit difficult to understand. I will publish an article that specifically addresses data restructuring optimization of GIN later.)

<a href="https://github.com/digoal/blog/blob/master/201706/20170612_05.md">Index scan optimization - data restructuring optimization of GIN (aggregated by element) - imagine you are playing a multi-stage rubric's cube</a>

4.Optimizing gist data distribution

For spatial data, queries are more efficient the more the elements are concentrated (e.g. when data is consecutively distributed by geohash).

5.Optimizing brin data distribution

6.Optimizing data distribution for multi-column compound indexes

For multi-column compound indexes, the efficiency is dependent on the index type, and the above requirements are applicable.

One more condition: the better the linear correlation between multiple columns, the higher the efficiency.

To learn how to calculate linear correlation between multiple columns, see:

<a href="https://github.com/digoal/blog/blob/master/201604/20160403_01.md">Use PostgreSQL to calculate the linear correlation between fields of any type</a>

Data distribution has another benefit in that it significantly increases the compression ratio for column storage.

<a href="https://github.com/digoal/blog/blob/master/201604/20160404_01.md">A simple algorithm to help IoT and financial users cut data storage costs by 98% with PostgreSQL and Greenplum</a>

<a href="https://github.com/digoal/blog/blob/master/201702/20170221_01.md">Application of PostgreSQL GIN single column concentration index</a>

<a href="https://github.com/digoal/blog/blob/master/201702/20170205_01.md">The best sword for the best man - equivalent searches on random combinations of fields - exploration on PostgreSQL multi-array expansion of B-tree indexes (GIN)</a>

<a href="https://github.com/digoal/blog/blob/master/201702/20170204_01.md">PostgreSQL - GIN index principles</a>

<a href="https://github.com/digoal/blog/blob/master/201305/20130516_01.md">PostgreSQL 9.3 pg_trgm improve support multi-bytes char and gist,gin index for reg-exp search</a>

<a href="https://github.com/digoal/blog/blob/master/201612/20161225_01.md">Marketing to trillions of people in milliseconds - database design for real-time recommendations systems with trillions of user tags</a>