Re: BRIN indexes vs. SK_SEARCHARRAY (and preprocessing scan keys)

Hi,

Attached is a patch series adopting the idea of scan key preprocessing
in brinrescan(), and producing scan keys. It turns out to work pretty
nicely, and it allows different opclasses doing different things:

- minmax / minmax-multi: sort the array values (leave scalars alone)
- inclusion: no preprocessing
- bloom: precalculate hash values

The _consistent functions are modified to leverage the preprocessed
keys. I wonder if it should check the existence of the (optional)
procedure, and fallback to the non-optimized search if not defined.

That would allow opclasses (e.g. from extensions) to keep using the
built-in consistent function without tweaking the definition to also
have the preprocess function. But that seems like a rather minor issue,
especially because the number of external opclasses is tiny and updating
the definition to also reference the preprocess function is trivial. I
don't think it's worth the extra code complexity.

0001 and 0002 are minor code cleanup in the opclasses introduced in PG
13. There's a couple places assigning boolean values to Datum variables,
and misleading comments.

0003 is a minor refactoring making the Bloom filter size calculation
easier to reuse.

0004 introduces the optional "preprocess" opclass procedure, and calls
it for keys from brinrescan().

0005-0008 add the preprocess procedure to the various BRIN types, and
adjust the consistent procedures accordingly.

Attached is a python script I used to measure this. It builds a table
with 10M rows, with sequential but slightly randomized (value may move
within the 1% of table), and minmax/bloom indexes. The table has ~500MB,
the indexes are using pages_per_range=1 (tiny, but simulates large table
with regular page ranges).

And then the script queries the table with different number of random
values in the "IN (...)" clause, and measures query duration (in ms).

The results look like this:

int text
index values master patched master patched int text
------------------------------------------------------------------
minmax 1 7 7 27 25 100% 92%
10 66 15 277 70 23% 25%
20 132 16 558 85 12% 15%
50 331 21 1398 102 7% 7%
100 663 29 2787 118 4% 4%
500 3312 81 13964 198 2% 1%
------------------------------------------------------------------
bloom 1 30 27 23 18 92% 77%
10 302 208 231 35 69% 15%
20 585 381 463 54 65% 12%
50 1299 761 1159 111 59% 10%
100 2194 1099 2312 204 50% 9%
500 6850 1228 11559 918 18% 8%
------------------------------------------------------------------

With minmax, consider for example queries with 20 values, which used to
take ~130ms, but with the patch this drops to 16ms (~23%). And the
improvement is even more significant for larger number of values. For
text data the results are pretty comparable.

With bloom indexes, the improvements are proportional to how expensive
the hash function is (for the data type). For int the hash is fairly
cheap, so the improvement is rather moderate (but visible). For text,
the improvements are way more significant - for 10 values the duration
is reduced by a whopping 85%.

regards

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