Handling outliers in BRIN indexes with the new multi minmax operator class

By Lukas Fittl

August 03, 2023

In E79 of “5mins of Postgres” we're going to talk about when good correlation is not enough, the cases where BRIN indexes can be worse than having no index at all.

Share this episode: Click here to share this episode on twitter, or sign up for our newsletter and subscribe to our YouTube channel.

When using an index can be slower than not using one
How do BRIN indexes work?
What does Postgres do with a BRIN index?
When to use BRIN indexes
Outliers and BRIN indexes
- Find outliers in BRIN indexes with minmax_multi_ops
What we have discussed in this episode of 5mins of Postgres
Learn more about Indexing in Postgres

Transcript

Let's jump in!

When using an index can be slower than not using one

This is a blog post by Haki Benita where he describes a particular situation where a BRIN index performed really badly. That was surprising because they actually seemingly had a good correlation between the physical order and the logical order of the values in the table.

At the end of the post, Haki gives some background on how this happened in production. In their situation, they had a table of payment processes and that table had a high correlation on their creation date column of 0.97 between logical and physical order. Generally speaking, that's a good fit for a BRIN index, and so they added that BRIN index. Initially, it was actually quite fast. But then, over time, queries became slower and slower, and queries ultimately started timing out.

They were quite surprised because this should have been a good fit for a BRIN index. So, why wasn't it actually performing as expected?

As Haki describes in his post, the problem here ultimately has to do with outliers. Let's take a look at a few of the aspects of BRIN indexes to start with.

How do BRIN indexes work?

Generally speaking, BRIN indexes will split your table into multiple blocks of pages. The idea behind a BRIN index is: let's say, for example, you have 3 ranges

a range for the page 1 to 3
a range for the page 4 to 6 and
a range for the page 7 to 9.

Each of those ranges tracks the minimum and maximum value. In this example for value "E", you know that only the middle block in this case, which contains the "D" to "F" min/max, would be matching the value "E". You know for sure that the first and the last are not going to include those values because the min/max values there do not include "E". It helps zoom in on a particular part of the table.

What does Postgres do with a BRIN index?

What Postgres actually does then is to run what's called index recheck. It looks at the index first, and then in the second step goes in and actually looks at the table, but it knows where in the table to look and to confirm which rows are actually matching.

A BRIN index is not definitive. A BRIN index is a lossy index. You have to remember that a BRIN index will always do a table lookup, but the benefit of a BRIN index working as expected is that it will be a much smaller portion of a table than if it was doing a sequential scan.

When to use BRIN indexes

BRIN indexes are a good fit when you have a statistical correlation between physical row ordering and logical ordering of column values. And this is something that Postgres itself tracks in the pg_stats correlation column. It tracks that so that the Postgres planner can make a decision whether a BRIN index, for example, is a good fit or not.

In his article, Haki runs a quick benchmark to show how a BRIN index functions. He creates a table with a million records. Here it's perfect correlation on the timestamp column because it's just incrementing the timestamps as you create the table. There, he gets a sequential scan of 1.3 seconds.

If we create a BRIN index, we're down to 8.5 milliseconds for the query. This of course is a big improvement. You can also see a bitmap index scan on the BRIN index, and then it will do that index recheck and it will actually remove 59 rows that are not matching in the actual pages. When you're thinking about the performance of a BRIN index, this is a very important metric.

Outliers and BRIN indexes

Then, very interestingly so, Haki shows a case where BRIN indexes were not working well. What he did for every 70 rows was to insert an outlier and he pushed the timestamp value that was on that row 1 year into the future.

And what that meant, of course, was that the index was looking very differently. What's surprising is that the correlation measurement that Postgres makes still has very high correlation. This still looks like a good index to Postgres, even though it has these outliers.

And so when you now run an EXPLAIN ANALYZE on this query, you actually see that this is worse than a sequential scan. If you remember, the sequential scan was 1.3 seconds, now we have 3.2 seconds to run the query with the BRIN index. The reason that's so much worse is, remember it is a million row table, Postgres actually ends up looking at all of the table and all of the index.

This clearly is bad. This could happen in reality, if you had outliers like this, this could happen to you.

Find outliers in BRIN indexes with minmax_multi_ops

Kindly, Haki then shows how the new minmax_multi_ops operator class that was added in Postgres 14 actually helps you avoid this. The way that works is when you create the BRIN index, you have to specify that particular operator class, which then structures the BRIN index slightly differently, enabling it to find outliers like that much better.

Keep in mind, when you create the index with this option the index does get twice as large. Instead of 520 kilobytes, it's now 1.3 megabytes. But, what you can see here is that the query now actually performs almost as good as before we added the outliers.

Underneath the hood, as Haki shows in his blog post, the way this works is that Postgres will actually remember particular values as well as a set of ranges. It's essentially remembering multiple sets of pages that are matching. Haki goes into a lot more details, and I would encourage you to read the article if you want to understand everything.

I think what his article shows very clearly is that if you have a table that has outliers and you're on Postgres 14, it makes a lot of sense to switch to that new operator class to avoid this problematic behavior around outliers, causing your BRIN index to be really slow.

Thanks for tuning into E79 of 5mins of Postgres. Subscribe to our YouTube channel, sign up for our newsletter and follow us on LinkedIn and Twitter to get updates about new episodes!