btree vs. BRIN: 2 options for indexing in PostgreSQL data warehouses

Indexing is the key to good performance. However, people often ask: Is there an alternative to btree indexing? Can we make indexes in PostgreSQL smaller? Can we create indexes in PostgreSQL faster? And how can we index in a data warehouse?

This blog will answer all those questions and show which options you have to index tables in a data warehouse. We're going to focus on the epic battle between btree (AKA B-tree) and BRIN indexes.

Types of indexes in PostgreSQL

Unlike many other relational databases, PostgreSQL supports more than just one index type. The reason for that is that not all indexes are suitable for the same type of operation. An index that works fine to index names does not necessarily work for GIS data, and vice versa. That's why people have the choice of which index to use in PostgreSQL.

How can we figure out which types of indexes actually exist in PostgreSQL? Here's how it works:

The pg_am system table reveals which types of indexes are supported by your system. Note that an index can actually be loaded as an extension, which means that the list you see is not necessarily constant - you might see more entries.

Loading sample data

Before we dive into the details of btree and BRIN indexes, it makes sense to load some sample data. The easiest way to do that is to make use of generate_series. This is the Swiss army knife type of function which is basically used by most PostgreSQL consultants to generate huge tables for testing purposes:

In this case, we created 5 billion rows which lead to a 206 GB table. Here we have two columns: The first column is ascending. It contains numbers ranging from 1 to 5 billion.

The second column contains a hash value. Take a look:

The point here is that the hash value is pretty much random and should be evenly distributed. It gives us the chance to see how various index types such as btree and BRIN behave in these two quite common use cases.

CREATE INDEX: Performance issues with btree

Let's create a simple btree. In a first step we use the PostgreSQL default configuration (the only change I made was to set max_wal_size to 100 GB - all other settings are default)

Creating a standard btree index will cost us 35 minutes:

However, we can do better. If we drop the index again and pump maintenance_work_mem to 1 GB, and if we increase the number of worker processes PostgreSQL is allowed to use, we can speed things up:

Now let's create the same btree index again and see what happens:

When looking at vmstat we see that PostgreSQL starts to read hundreds of MB per second, and starts to spill hundreds of MB/second to disk at a time. Since we cannot sort everything in memory, this is exactly what we expected to happen.

During the first phase we see exactly what happens as revealed by the progress monitoring infrastructure:

PostgreSQL will first scan the table and prepare the data for sorting.

In the process table we can see that all desired cores are working at full speed to make this happen:

Once this step is done, PostgreSQL can start to sort those partial data sets.

Remember, the table is too big to make this happen in memory, so we had to spill to disk:

After this stage PostgreSQL will add data to the tree and write the index to disk:

We managed to almost double the performance of our indexing process - which is a really great achievement:

If you want to know more about indexes I can also recommend one of my other blog posts dealing with faster index creation in PostgreSQL.

What is noteworthy here is the size of the index we've just created:

105 GB's is pretty massive. However, it basically confirms the following rule of thumb: Usually an index needs around 25 bytes per index entry - assuming we do not have any duplicate entries.

Create a second index:

In this case, we have indexed the randomized column. As our input stream is not sorted anymore it takes a bit longer to create this index.

Running queries using btrees

Run a query and see what the btree index has done so far:

What we see here is stunning performance.

We managed to extract 10 million rows in just 358 milliseconds. Let's look deep into the execution plans and see what happens:

The above is a parallel-index-only scan.

Actually this is good news because it means that it's enough to scan the index. There's no need to fetch data from the underlying table. All we need to ensure is the existence of the row (which is in this case done through PostgreSQL hint bits).

Now we'll run the same query, but this time we'll use the random column.

Note that I reduced the range a bit to ensure that we also get 10 million rows. The size of the result set is therefore roughly identical:

The parallel query using more than one core is gone. But, it's even worse … see what happens during the query:

Wow, we see 120 MB / sec sustained I/O which translates to horrible runtime.
Note that the amount of data is the same - all that has changes is the distribution of data on disk:

5 minutes. As you can see here the runtime has exploded. We can figure out why:

Data is spread all over the place. Therefore we need millions of 8k pages to handle the query. In those blocks we only need a subset of data. That causes substantial runtime.

BRIN indexes come to the rescue?

BRIN indexes are often seen as a savior for warehousing applications. However, you should not be so sure about that.

First, we'll create an index:

The index is made really quickly. What is also extremely convincing is the size of the BRIN index:

it's only 7 MB which saves us a stunning 10 GB on disk.

What we can also see during index creation is that the process looks slightly different:

BRIN is not as extensive a sorting exercise as normal btree index creation. This is important because it translates to less temporary I/O and faster index creation.

Compare queries:

The btree managed to run the query with just 27,000 blocks - now we need around 55,000 - which translates to more runtime.

While a BRIN index is usually a good idea for such use cases, it's not always the magic bullet. It does need significantly less space and it can be built faster. But is does not magically fix all cases under all circumstances.

Please keep in mind that I AM NOT SAYING that BRIN is bad - it's usually a speedup compared to btree indexes. What I am saying is that you should compare various setups and decide what is best. Also: Keep in mind that correlation does matter.

Finally …

To find out about reduced B-tree index bloat, check out Laurenz' post.

If you want to learn more about PostgreSQL and if you want to read something about GIS data right now I can highly recommend Florian Nadler’s post dealing with historical data and MobilityDB.