Re: BRIN indexes vs. SK_SEARCHARRAY (and preprocessing scan keys) - Mailing list pgsql-hackers

From Tomas Vondra
Subject Re: BRIN indexes vs. SK_SEARCHARRAY (and preprocessing scan keys)
Date
Msg-id 0e1f3350-c9cf-ab62-43a5-5dae314de89c@enterprisedb.com
Whole thread Raw
In response to BRIN indexes vs. SK_SEARCHARRAY (and preprocessing scan keys)  (Tomas Vondra <tomas.vondra@enterprisedb.com>)
Responses Re: BRIN indexes vs. SK_SEARCHARRAY (and preprocessing scan keys)
List pgsql-hackers
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
Attachment

pgsql-hackers by date:

Previous
From: David Rowley
Date:
Subject: Make set_ps_display faster and easier to use
Next
From: Tomas Vondra
Date:
Subject: Bug in processing conditions on multi-column BRIN indexes