Postgres Indexing

How Data(Records) are stored in Postgres?

Tables are stored in the Postgres heap. They are stored as physical files in a database with each table stored as a separate file. The maximum size of a file in Postgres is 1GB. A table with a records size greater than 1GB will maintain more files. Files in turn consist of a collection of pages. The page has headers and items. Max page(Block) size is 8KB, and as the number of records increases more pages will be appended to the file. To fetch a record from the database, records are searched(and fetched) sequentially from files (searched through pages). As more and more data is appended to the database, more pages will be added to files and search will become slow.

Postgres never stores data in a sorted(Ascending/Descending) way. The main reason behind this whenever we delete rows from a table, space is created(Vaccum) and new rows can be appended to that freed space.

Indexing in Postgres:

With the addition of more and more records in the table, querying of data will become slow(with sequential search) and ultimately hamper customer experience by increasing the response time.

Indexes provide us with a way to optimize searching by decreasing the disk search(I/O Comparisons). Indexes are physical storage on Postgres heap same as regular tables.

How to optimize the query execution time?

Postgres provides indexes to optimize the query execution time. Indexes are special objects stored in Postgres as files that help optimize query execution time by maintaining the reference to actual records(rows) in the database.

With indexed columns, we get the page info(tuple location) from the index and ultimately we can directly fetch data from the corresponding page(pages) and execution time and comparisons are reduced. We are eliminating the FULL TABLE SCAN.

In index each item is tuple with (value, pointer)

(pointer) => (page, offset)

Let's demonstrate this with a sales table(100000 records)

create table sales (
order_id INT primary key,
region VARCHAR not null,
country VARCHAR not null,
item VARCHAR not null,
sales_channel VARCHAR not null
created_at date not null
)

In the sales table, we will run the below query with ctid (denotes the tuple location in the page)

select ctid, * from sales limit 100

In the above image, we have a ctid column. This column defines the page number and offset of the record(tuple) on that page.

ctid(0,1) -> Page= 0 and Offset = 1

Case 1: Find a record with a Primary Key (Indexed)

explain analyze select order_id  from sales where order_id = 399401366;

Query Execution Time = 0.8 ms and It uses only Index only Scan using order_id primary index.

Case 2: Find a record with a Non-Indexed Column

explain analyze select region, order_id  from sales 
where country = 'Guinea-Bissau';

Query Execution Time = 73 ms and It uses sequential scan(scanning from page 1 to page n)

This execution time will keep on increasing as we add more records to the table.

Case 3: Add index on a country column and run the same query

create index on sales(country);

explain analyze select region, order_id  from sales 
where country = 'Guinea-Bissau';

Query Execution Time is reduced from 73 ms to ~2 ms and sequential scan is replaced by index scan (Heap scan to find additional columns).

Case 4: Add index on a country column and run the same query

explain analyze select region, order_id  from sales where country = 
'Guinea-Bissau' and item = 'Meat';

Query Execution Time = 31 ms

Index Scan on Country Column and Filtered the Records with item value = “Meat” (In analysis results we can see 496 rows are removed after applying a filter on records fetched by indexed scan)

Indexing Types:

B-tree (Also known as default index)

Works on the concept of Self Balancing Tree. It's based on the binary search tree data structure but an optimized version to efficiently handle large amounts of data.

The first page of the B-tree index is a meta page. Contains:

1. Block Number of the root page
2. Level of root
3. The block number of fast root
4. Level of fast root

select * from bt_metap('sales_country_idx')

Fetched using extension page inspect

All the pages — root, parent, and leaves have the same structure

1. Block Number
2. High Key (Max Value on that page) [This is based on Lehman and Yao Btree]
3. Pointer to the next and previous page (Pages at the same level are maintained as LinkedList) [This is based on Lehman and Yao Btree]
4. Items (Data)

Note: The rightmost key of the level doesn’t have the high key as if it will prevent that new values from being added at that level.

Pointers help in sorting for order by query.

select * from bt_page_stats('sales_country_idx', 229)

select * from bt_page_items('sales_country_idx', 229)

B Tree Index

How B-TREE Query Data?

Postgres uses scan keys to query data. Scan Keys removes the redundant part of search conditions to keep only the tightest bounds. For example:

select * from sales where order_id > 101 and order_id > 501

Scan Query will move this to the tightest bound and use the below query:

select * from sales where order_id > 501

Step 1: Once the scan query is decided, it is sent to the binary tree search algorithm with the initial pointer pointing at the root.

Step 2: Keep iterating till we find jumps to the leaf page containing data. (Follow Binary search tree algorithm)

Caveat: Once the page is in the scan(read lock is applied), new items cannot be inserted in that specific page but can be inserted on the child page.

How data is inserted in the B-tree?

Basically, during insertion, we need to find out where to insert new data.

Case 1: Auto Incrementing Sequence (Generally used with primary keys)

For this, we always need to insert value in right rightmost leaf. For this only case, Postgres uses a fast path.

• Find the rightmost leaf from the buffer. (Rightmost leaf leaf cached in buffer)
• Validate if the cached page is rightmost, the page's initial value is less than the new value, and if there is enough space on the page for new data.

Case 2: Regular Data

• Iterate to the right page and find the exact location where data can be inserted. (Same as search)

Inserting data:

• If the size of new data to be added is less than the available page size then insert the data.
• If the size of the new data to be added is more than the available page size then split the page.
• Now postgres doesn’t simply create a new page and add data on it. Instead postgres handles this scenario gracefully by creating a new page with optimizations like:

1. If it's the rightmost leaf then simply create a new page and add data. (Always true with auto-incremented data)
2. If this is not the rightmost leaf then it equalizes the free space but transfers 50% of data to a new page so that in the future, we can avoid page split.

With the above, we need to update the left and right pointers as well as the high keys of new and old pages.

If the new page is to be created at the root level then metadata needs to be updated

Deleting items from the Btree Index:

1. While deleting from the leaf, mark it deleted and it will be not used in searches. This will be present on the page as bloat and will be cleared in the Next Vaccum cycle. [ Assuming this step if there are other keys also on page].
2. Delete the page if all the items have been deleted. We need to reset the left page's right pointer points to the deleted page's right page. Vacuum will delete the page from memory.
3. In case of deleting the parent page then we need to refresh the references in the root page.

Note: A few other deletion edge cases are out of the scope of this article.

Operators:

1. Less than(<)
2. Less than equal to (≤)
3. Equal(=)
4. Greater than equal to (≥)
5. Greater than (>)
6. Between
7. In
8. Is Null
9. Is Not Null

create index on sales(region);

or

create index on sales using Btree(region);

Note: For text searches, Btree with “like” will work only with the ‘value%’ pattern and not with the (‘%value%’, ‘%value’) pattern.

Binary is compatible with all data types.

Hash Index

• Used only for equality condition(=).
• The 32-bit hashed value derived from the indexed column is saved.
• Rarely used indexes but more space efficient than B-tree Indexes. Less flexible as compared to Btree.

create index on sales using hash(region);

GIN Index

• Generalized Inverted Index.
• Handle composite values (ARRAYS, JSONB, TSVECTOR)
• Slowest as needed to index full document during creation. (Also on update reindex the full document)
• GIN indexes are binary trees.

The first page of the GIN index is a meta page like Btree. Creates index entries for every possible value.

Get Rishabh Jain’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Used for text search. It takes time to build but is performance efficient. Works well with like with all possible patterns.

create index on sales using gin(item_list);

Supported Operators:

1. <@ @>
2. &&
3. ?&
4. ?|
5. @>
6. @@
7. @@@
8. with pg_trgm (trigram) — %, <%, %>, <->, <<->, <->>, like, ~, ~*

pg_trgm — creates a trigram of worlds i.e. splits the text with a character length of 3 that will help in better full-text search.

BRIN:

Block Range Index

• Group physically adjacent pages.
• Brin contains 3 values — (page_number, min_value, max_value)
• Fast scanning for large tables.
• Size of the Brin index is quite small compared to Btree, Hash, and other indexes.

Take the case of created_at which denotes the date timestamp at which data is created.

create index on sales using brin(created_at);

It will create an index with (Page_Number, 2021–01–01, 2021–12–31), likewise many entries with different created_at dates.

For the above scenario, created_at is correlated(incremental) with adjacent entries and it becomes a candidate for the brin index.

Let's take a case with a user table with birthdates, those dates are not correlated based on storing pattern. If we create a brin index on them, the search won’t be an efficient one.

Caveats:

When data is deleted and Vaccum happens. The free spaces are used by new entries and Brin would have long ranges of data. This will make the search slow.

Operators:

1. Less than(<)
2. Less than equal to (≤)
3. Equal(=)
4. Greater than equal to (≥)
5. Greater than (>)
6. Between
7. In
8. Is Null
9. Is Not Null

Indexing Concepts

1. Multicolumn Indexes (Composite)

Index over a combination of columns is called multicolumns or composite indexes.

create index on sales(country, region);

Only B-Tree, Gin, Gist, and Brin support the Multicolumn Index.

Multicolumn B-tree/Gist index can be used for any subset of indexed columns but the most efficient query results will be when used with leading left columns.

Multicolumn Gin/Brin index can be used for any subset of indexed columns and it will be effective irrespective of which column is used and their position in index creation.

create index on sales(country);
create index on sales(sales_channel, item);
explain analyze select region from sales where country = 'Guinea-Bissau' 
and sales_channel = 'Offline' and item = 'Meat' ;

An index scan is done on the sales_channel_item index and index scan is also done on the sales_country index and BitMapAnd is done to combine the results.

create index on sales(sales_channel, item);
explain analyze select region from sales where item = 'Meat' ;

create index on sales(country, region);
 explain analyze select * from sales where region = 'Europe'
 and country = 'Malta';

2. Partial Indexes

Indexes built for the subset of table data are called Partial Indexes.

Let’s take a scenario in which we have a table with millions of user records. For each user we have a status that denotes the user is active/suspended and we only need to query only active users. So for this use case, we can make use of a partial index in which we only index active users.

With this partial indexing strategy, we can accomplish:

1. We can save the index size which ultimately helps to optimize the queries using indexes.
2. Optimizing Update Queries as no index updates are required for suspended users' records.

In the sales table, we have sales_channel with values (Offline, Online).

Case 1: Creating an Index on sales_channel

create index on sales(sales_channel);
explain analyze select region from sales where item = 'Meat';

Size of Index: 2208 kB

Case 2: Creating a partial index with sales channel value Online

create index on sales(sales_channel) where sales_channel = 'Online';

Size of Index: 1112 kB

3. Unique Indexes

For additional unique integrity on table columns. Multicolumn Unique index adds unique constraints on a combination of all columns. Only B-tree indexes can be declared as unique.

4. Indexes on Expressions

Adding indexes on computed value from expressions or Postgres functions from one or more table columns.

create index on sales(region);

explain analyze select region from sales where region = 'asia';

Index Only Scan

explain analyze select region from sales where lower(region) = 'asia';

Sequential Scan

Sequential Scan

Create Expression on Index

create index on sales(lower(region));

explain analyze select region from sales where lower(region) = 'asia';

5. Index Only Scans

When a query returns results directly from indexes without getting data from the heap, this scenario is called Index Only Scans.

explain analyze select order_id  from sales where order_id = 399401366;

6. Covering Indexes

Covering indexes provides a way to implement index-only scans to speed up the execution time. In covering indexes, we provide fields to be attached to the index so that when we query with projecting includes fields with search conditions on indexed fields.

CREATE INDEX sales ON tab(country) INCLUDE (region);

7. Combining Multiple Indexes

With Multicolumn indexes we can optimize the search query with search conditions joined with “and”. But when search conditions are joined with “or”.

explain analyze select * from sales where country = 'Germany'
 and region = 'Europe'

With “and” between the search conditions index scan works

explain analyze select * from sales where country = 'Germany'
 or region = 'Europe'

With “or” between the search conditions sequential scan happened.

To solve this problem we can make use of the multi-column index.

create index on sales(country);
create index on sales(region);
explain analyze select * from sales where country = 'Germany'
 or region = 'Europe'

we can see the BitMapAnd of the results that are fetched using data from both indexed scan subsets.

Special Case ********

create index on sales(item);
create index on sales(sales_channel);

explain analyze select region from sales where
 sales_channel = 'Offline' and item = 'Meat';

In this, we can index scan on sales_item but the filter is applied on sales_channel (no index scan here)

***Postgres internally checks whether the index can help optimize the query. If indexes don’t help then Postgres runs the sequential scan and ignores indexes.*****

Bonus:

1. Indexes can have up to 32 columns, including INCLUDE columns. (This limit can be altered when building PostgreSQL; see the file pg_config_manual.h.)
2. To find the size of the index:

select
 i.relname "Table Name",
 indexrelname "Index Name",
 pg_size_pretty(pg_relation_size(indexrelid)) "Index Size"
from
 pg_stat_all_indexes i
join pg_class c on
 i.relid = c.oid
where
 i.relname = 'sales'

3. Size of the table and all indexes:

select pg_size_pretty (pg_relation_size('sales')), pg_size_pretty (pg_indexes_size('sales'));

4. Unused Indexes: Query

select
relname,
indexrelname,
idx_scan,
idx_tup_read,
idx_tup_fetch
from
pg_stat_all_indexes
where
schemaname = 'public'
and indexrelname not like 'pg_toast_%'
and idx_scan = 0
and idx_tup_read = 0
and idx_tup_fetch = 0
and indexrelname != 'SequelizeData_pkey'

5. Sargable Search (Search Argument Able)

Sargable queries are queries that can efficiently use added indexes. Adding expressions on queries makes queries Sargable.

Reference: https://www.postgresql.org/docs/10/indexes.html

Learn more from here: https://medium.com/@rishabh171192/indexes-in-relational-databases-detailed-ba5926121c38