From: Justin Pryzby <pryzby@telsasoft.com>
To: Mickael van der Beek <mickael.van.der.beek@gmail.com>
Cc: pgsql-performance@postgresql.org
Subject: Re: BRIN index worse than sequential scan for large search set
Date: Fri, 24 Feb 2023 14:37:15 -0600
Message-ID: <20230224203715.GE1653@telsasoft.com> (raw)
In-Reply-To: <CACM-Oyc-rOkzP6kV1POY+fiZcRQ+cqd5iWqR61zN6nUVRVt3sw@mail.gmail.com>
References: <CACM-Oyc7LomLgOPyyBQ3h2JRGA=Yr27Vghz4ovHcS8SmsunOGQ@mail.gmail.com>
<20230224171944.GB1653@telsasoft.com>
<CACM-Oyc-rOkzP6kV1POY+fiZcRQ+cqd5iWqR61zN6nUVRVt3sw@mail.gmail.com>
On Fri, Feb 24, 2023 at 06:51:00PM +0100, Mickael van der Beek wrote:
> Hello Justin,
>
> Thanks for the quick response!
>
> > The table may be dense, but the tuples aren't. You're asking to return
> > 1/1000th of the tuples, across the entire table. Suppose there are ~100
> > tuples per page, and you need to read about every 10th page. It makes
> > sense that it's slow to read a large amount of data nonsequentially.
>
> Ah, of course, you're right!
> I forgot that the BRIN indexes store ranges that are not fully covered by
> the row values and that PostgreSQL has to double-check (bitmap heap scan)
> ...
> Would you thus advise to only use BRIN indexes for columns who's values are
> (1) monotonically increasing but also (2) close to each other?
It's not important whether they're "rigidly" monotonic (nor "strictly").
What's important is that a query doesn't need to access a large number
of pages.
For example, some of the BRIN indexes that I'm familiar with are created
on a column called "start time", but the table's data tends to be
naturally sorted by "end time" - and that's good enough. If someone
queries for data between 12pm and 1pm, there's surely no data for the
first 12 hours of the day's table (because it hadn't happened yet) and
there's probably no data for the last 9+ hours of the day, either, so
it's only got to read data for a 1-2h interval in the middle. This
assumes that the column's data is typically correlated. If the tuples
aren't clustered/"close to each other" then it probably doesn't work
well. I haven't played with brin "multi minmax", though.
> > > 2. Since we only select the "idx" column, why does the BRIN index not
> > > simply return the searched value if included in one of it's ranges?
> > > Hitting the actual row data stored in the table seems to be unnessary no?
> >
> > Because it's necessary to check if the tuple is visible to the current
> > transaction. It might be from an uncommited/aborted transaction.
Actually, a better explanation is that all the brin scan returns is the page,
and not the tuples.
"BRIN indexes can satisfy queries via regular bitmap index scans, and
will return all tuples in all pages within each range if the summary
info stored by the index is CONSISTENT with the query conditions. The
query executor is in charge of rechecking these tuples and discarding
those that do not match the query conditions — in other words, these
indexes are LOSSY".
The index is returning pages where matching tuples *might* be found,
after excluding those pages where it's certain that no tuples are found.
--
Justin
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-performance@postgresql.org
Cc: pryzby@telsasoft.com, mickael.van.der.beek@gmail.com
Subject: Re: BRIN index worse than sequential scan for large search set
In-Reply-To: <20230224203715.GE1653@telsasoft.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox