Generalised Inverted Index (GIN Index) in Postgre SQL

We can apply the Generalised Inverted Index (GIN Index) to the following column types

Arrays ( text[], integer[], etc.)

JSONB ( jsonb )

Full-Text Search Documents ( tsvector )

Normal Text/Varchar (sirf tab jab pg_trgm extension ke sath use karein)

The main difference between GIN Index and a traditional B-Tree Index (regular index which is applied on Int, Strings, Data, Timestamps, Booleans column values is that a B-tree index is applied on columns of a table, but a GIN index is applied on each element of each column value.Read here everything about B-Tree Index

Need for GIN Indexing

For multivalued data like JSONB, a GIN indexing technique is used.

JSONB is a data type that stores JSON but in binary format.

We can utilize this type to store JSON, like given below

INSERT INTO products (name, attributes) VALUES

(‘iPhone 15 Pro’, ‘{“brand”: “Apple”, “color”: “Titanium”, “storage”: “256GB”, “specs”: {“ram”: “8GB”}, “tags”: [“electronics”, “phone”, “premium”]}’),

(‘Samsung S24 Ultra’, ‘{“brand”: “Samsung”, “color”: “Yellow”, “storage”: “512GB”, “specs”: {“ram”: “12GB”}, “tags”: [“electronics”, “phone”, “premium”]}’),

(‘Sony WH-1000XM5’, ‘{“brand”: “Sony”, “color”: “Black”, “type”: “Over-Ear”, “specs”: {“battery”: “30h”}, “tags”: [“electronics”, “audio”, “wireless”]}’),

(‘MacBook Air M3’, ‘{“brand”: “Apple”, “color”: “Space Gray”, “storage”: “512GB”, “specs”: {“ram”: “16GB”}, “tags”: [“electronics”, “laptop”]}’),

Now, without a GIN, we will see what will happen internally

SELECT * FROM products WHERE attributes @> ‘{“color”: “Black”}’;

Whenever a query is fired, the query planner is executed to see if any indexing is used; if no indexing is there, a full scan is the only option for Postgres

If a particular column has big JSON, a sequential scan for each row of the specified table

Without any index, Postgres will start pulling all required data in shared RAM, and this is a huge load on I/O

Decoding Problem

While comparing JSONB values, Postgres has to decode values because it stores JSON as binary; a full scan and decoding, then comparing for thousands of rows will exhaust CPU.

Full-Text Search ( tsvector )

When we want to save large text that can be searchable, tsvector type is used, and for this type, GIN is also used; without GIN, the same will happen as we discussed in the JSONB full scan scenario

Histoy of GIN

Postgres was failing with regular indexing while working with arrays and big text fields

If a field has values like ‘apple’, ‘Banana’, ‘Orange’, a regular index could not find ‘Banana’ because a regular index works on the entire value, not individual values in one field

Russian developers Oleg Bartunov and Oleg Bartunov invented the GIN technique for Postgres

How GIN works internally

We will take an example of how GIN works with JSONB

If we apply GIN on a JSONB field by following query

For JSONB type, GINs are of two types: default GIN and Path GIN

We will see how both types behave; first, we will see default GIN

CREATE INDEX idx_products_attributes ON products USING gin (attributes);

When you create a GIN for any column on a table, Postgres creates a separate new file so that it can store indexing information in this file.

Before we see the structure of the GIN file, we need to know that GIN files are of two types

1. Small data: GIN file structure is simple

2. Large data: GIN file structure is complicated because table will have massive numbers of rows

1. GIN for small data

Consider the query we fired for creating GIN; that table contains thousands or 1k records, then the GIN file structure will be as given below

For a simple GIN information file, Postgres does not use any complex data structures.

It uses a block of Pages to store indexing information

Each block or page has a size of 8 kb

Each GIN file will have a ‘Meta Block’ or ‘Block 0’

This block contains security information to validate that the file is a GIN file, and it has a pointer that points to the starting block

————-+ | BLOCK 0: META BLOCK | | | | [ Root Pointer: Block 1 ] ————–+—–+ +——————————————+ | | ▼ +——————–+ | BLOCK 1: STARTING ENTRY BLOCK | | (All Unique Keys A-Z sorted will be here) | +————–+

Because this example is for the default GIN on JSONB, the default GIN treats keys and values as separate elements; each element will be written in a block with its row ids on each block in sorted order.

Below is an example how the GIN file in text format look like (all this information is stored in binary format)

[PAGE HEADER: Block 2 | Type: Posting List Page (8 KB)]

| Element / Token | Type Flag | Row IDs List (TIDs) |

| ‘128 GB’ | Value | [Row #102, Row #103] | | ‘256 GB’ | Value | [Row #101] | | ‘Apple’ | Value | [Row #101, Row #103] | | ‘Samsung’ | Value | [Row #102] | | ‘brand’ | Key | [Row #101, Row #102, Row #103] | | ‘storage’ | Key | [Row #101, Row #102, Row #103] |

| <———————– Free Space ————————–> |

As you can see, values which is repeated; for those values, the rows in which vales is repeated are given in the same line

Now we will see what will happen after the SELECT query

SELECT * FROM products

WHERE attributes @> ‘{“brand”: “Apple”, “storage”: “128 GB”}’;

Because the field already has GIN applied

Postgres will start looking at the GIN file.

File will be loaded in RAM in shared buffer, but not the whole file; it will open one block at a time

Control will enter in Block 0

Block 0 will point to Block 1, because it is the entry point

Block 1 will be open in memory, and Postgres will do Binary search on that block to find the key and row id.

This process is followed until the query is satisfied

Postgres does not need to scan all the file because every key has all the row IDs specified before that key

Row ids are actually TID, Tuple Id.

How TID is matched with the physical address of that specific record

Because each file is stored as 8 kb.

So formula for calculating exact physical location will be fixed

Physical Byte Offset = Block Number * Block Size

This formula is applied on each row which is given against specified key

In this way Postgres reaches the exact record without scanning the entire table

GIN with path for JSONB

CREATE INDEX idx_prod_path ON products USING gin (attributes jsonb_path_ops);

Another way of creating GIN for JSONB is using path

Now the GIN file structure will be hash

Suppose your element is {"user":

{"profile": {"age": 25}}}. Postgres computes a distinct 32-bit integer hash for the key and value at every nesting level. It then combines these hashes using bitwise XOR ($\oplus$) and rotation operations to compress the entire path into a single final 4-byte (32-bit) integer token.

It uses bitwise operators to calculate the exact disk location of the record

GIN for big table with large volume of data

GIN file storing is the same for big table: storing keys along with their row ids, but while retrieving value from these files, Postgres strategy of handling this file in RAM is totally different

When select query fired, Postgres loads Block 0 in RAM

After reading Block 0, Postgres immediately understands that it is a B-tree page, because for big table GIN stores information in a B-Tree structure

Since it uses B-Tree structure, the details of how B-Tree is organised, is given in this article

GIN file has root page which contains ranges of pages where lement can be found, all data is already sorted.

EX: all data starting wth K is in between pages 8 to 12

According to ranges, pages required will be loaded in to memory

That page will contain line pointers, like TIDs related to ‘apple’

Because the target page is loaded in the shared buffer, which acts as an array, Postgres does binary search on the shared buffer to extract the TIDs of the elements

and then it retrieves the actual rows from the table

Subscribe to get updates and Programming Articles

The form can be filled in the actual website url.

About the Author

Nadeem Ahmed has 12 years of experience in System Pro…