Thread: Aggregate not using BRIN index on timestamp

Aggregate not using BRIN index on timestamp

From
Jeremy Finzel
Date:
Hello -

I have started to make much more use of BRIN indexes on timestamp fields on tables which are insert-only.  I have seen great performance with these and of course far less overhead.

However, I am noticing that a simple aggregate is not using the index.  I don't find anything obvious in the docs as to why, and I am not sure if the operator is not actually supported, or for some reason it is not choosing it because of the estimate.

I have a very large table with 4 billion rows and a BRIN index on timestamp spanning from 2013 to present.  I am running this simple query:

SELECT MIN(created_at) FROM table;

It is choosing a parallel seq scan as opposed to a BRIN bitmap scan.

Please note also that the following queries that I am using are using the index with great performance:
SELECT * FROM table WHERE created_at > '2013-04-01' AND created_at <= '2013-04-08';

I can provide more info.  But first - am I missing something obvious?

Thanks,
Jeremy

Re: Aggregate not using BRIN index on timestamp

From
Tom Lane
Date:
Jeremy Finzel <finzelj@gmail.com> writes:
> I have a very large table with 4 billion rows and a BRIN index on timestamp
> spanning from 2013 to present.  I am running this simple query:
> SELECT MIN(created_at) FROM table;
> It is choosing a parallel seq scan as opposed to a BRIN bitmap scan.

> I can provide more info.  But first - am I missing something obvious?

Yes: BRIN indexes don't provide any ordering information.  A btree
index on created_at could be used to optimize this query, but without
one of those, seqscanning the whole table is the only possibility.

            regards, tom lane



Re: Aggregate not using BRIN index on timestamp

From
Jeremy Finzel
Date:
Yes: BRIN indexes don't provide any ordering information.  A btree
index on created_at could be used to optimize this query, but without
one of those, seqscanning the whole table is the only possibility.

Thanks Tom.  So, this is a very general question, but would it be possible to develop that feature into BRIN, given what it stores?  Even if it does not have ordering information, doesn't it know which blocks would contain the lowest values, so it could choose to do a "bitmap scan ordered sort" or something, depending on the number of rows sought?  Or is the problem that it has no way of determining what value actually would be the "minimum" without the query specifying a particular date, such as less than "2013-04-01"?

Thanks!
Jeremy

Re: Aggregate not using BRIN index on timestamp

From
Tom Lane
Date:
Jeremy Finzel <finzelj@gmail.com> writes:
> Thanks Tom.  So, this is a very general question, but would it be possible
> to develop that feature into BRIN, given what it stores?

You'd need somebody who knows more about BRIN than me to opine on that.

            regards, tom lane



Re: Aggregate not using BRIN index on timestamp

From
Alvaro Herrera
Date:
On 2019-Aug-05, Jeremy Finzel wrote:

> Thanks Tom.  So, this is a very general question, but would it be possible
> to develop that feature into BRIN, given what it stores?  Even if it does
> not have ordering information, doesn't it know which blocks would contain
> the lowest values, so it could choose to do a "bitmap scan ordered sort" or
> something, depending on the number of rows sought?  Or is the problem that
> it has no way of determining what value actually would be the "minimum"
> without the query specifying a particular date, such as less than
> "2013-04-01"?

For btrees, we have planagg.c which transforms min() and max() into
subqueries (SELECT .. WHERE ... ORDER BY .. LIMIT 1).

In a BRIN index, you could execute the search by scanning the index to
determine which ranges contain the least/greatest values, and then using
a bitmap scan to scan those.  I'm not sure that this is a transformation
that can be applied cleanly, since that thing I describe doesn't look to
be a "subquery".  But maybe it can -- I think you'd need a special
executor node.

-- 
Álvaro Herrera                https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services



Re: Aggregate not using BRIN index on timestamp

From
Tom Lane
Date:
Alvaro Herrera <alvherre@2ndquadrant.com> writes:
> For btrees, we have planagg.c which transforms min() and max() into
> subqueries (SELECT .. WHERE ... ORDER BY .. LIMIT 1).

> In a BRIN index, you could execute the search by scanning the index to
> determine which ranges contain the least/greatest values, and then using
> a bitmap scan to scan those.  I'm not sure that this is a transformation
> that can be applied cleanly, since that thing I describe doesn't look to
> be a "subquery".  But maybe it can -- I think you'd need a special
> executor node.

FWIW, I suspect the hard part would be dealing with cases where the
extremal ranges (according to the index) contain no live tuples
(according to the query's snapshot).  The btree case handles the
invisible-tuples problem by continuing a scan started at the index
endpoint until it finds a visible tuple --- which, in the worst case,
can take a long time.  It's not obvious to me what you'd do with
BRIN.

            regards, tom lane



Re: Aggregate not using BRIN index on timestamp

From
Alvaro Herrera
Date:
On 2019-Aug-05, Tom Lane wrote:

> FWIW, I suspect the hard part would be dealing with cases where the
> extremal ranges (according to the index) contain no live tuples
> (according to the query's snapshot).  The btree case handles the
> invisible-tuples problem by continuing a scan started at the index
> endpoint until it finds a visible tuple --- which, in the worst case,
> can take a long time.  It's not obvious to me what you'd do with
> BRIN.

Hmm, yeah, that's a tough problem -- hadn't thought about that.

-- 
Álvaro Herrera                https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services