Message-ID: <68fde90b-bb47-1b75-f9a7-32faa7dbb8a1@enterprisedb.com>
Date: Sat, 25 Feb 2023 17:18:16 +0100
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
 Thunderbird/102.8.0
Subject: Re: BRIN index worse than sequential scan for large search set
To: Justin Pryzby <pryzby@telsasoft.com>,
 Mickael van der Beek <mickael.van.der.beek@gmail.com>
Cc: pgsql-performance@postgresql.org
References: 
 <CACM-Oyc7LomLgOPyyBQ3h2JRGA=Yr27Vghz4ovHcS8SmsunOGQ@mail.gmail.com>
 <20230224171944.GB1653@telsasoft.com>
 <CACM-Oyc-rOkzP6kV1POY+fiZcRQ+cqd5iWqR61zN6nUVRVt3sw@mail.gmail.com>
 <20230224203715.GE1653@telsasoft.com>
Content-Language: en-US
From: Tomas Vondra <tomas.vondra@enterprisedb.com>
In-Reply-To: <20230224203715.GE1653@telsasoft.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
Archived-At: 
 <https://www.postgresql.org/message-id/68fde90b-bb47-1b75-f9a7-32faa7dbb8a1%40enterprisedb.com>
Precedence: bulk

FWIW I don't think the randomness per se is the main issue. The main
problem is that this results in a loop of bitmap index scans, with 20k
loops. This is made worse by the block-range nature of BRIN indexes,
resulting in many more heap block accesses.

The table has ~80k pages, but the bitmapscan plan reads ~2559362. That
can easily happen if each loop matches 100 ranges (out of 700), each
having 128 pages. Making the ranges smaller should help to minimize the
amount of pages read unnecessarily, but the loops are an issue.

And the same range may be scanned again and again, if the range is
consistent with multiple values.

Interestingly enough, this is the kind of queries / plans I thought
about a couple weeks ago, which made me to look at SK_SEARCHARRAY
support for BRIN indexes.

Imagine you did rewrite the query to something like:

    SELECT * FROM test_brin WHERE id IN (... lilerals ...);

That would only scan the table one, reducing the number of heap pages it
has to access. The drawback is that we still have to build the bitmap,
and without the SK_SEARCHARRAY support we just scan the index for each
element again. So better.

With the SK_SEARCHARRAY patch [1] this is further optimized, and for me
the query runs a bit faster than seqscan (not by much, and it depend on
how the data is cached). At least with pages_per_range=1.

Of course, this won't help unless the query can be rewritten like this.
At least not currently, but I wonder if we could invent some sort of
"pushdown" that'd derive an array of values and push it down into a
parameterized path at once (instead of doing that for each value in a loop).

regards

[1] https://commitfest.postgresql.org/42/4187/


-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company