Thread

Commits

Improve nbtree unsatisfiable RowCompare detection.
- ec986020decf 18.0 landed

More reliable nbtree detection of unsatisfiable RowCompare quals involving a leading NULL key/element

Peter Geoghegan <pg@bowt.ie> — 2024-12-23T18:02:59Z

Currently, nbtree has inconsistent detection of unsatisfiable
RowCompare quals that involve a leading NULL key. I'll show a test
case that illustrates where nbtree doesn't behave as expected right
now, resulting in an unnecessary full index scan.

Test case setup
===============

pg@regression:5432=# create table rowcompare_test as select i as
first, i as second, i as third from generate_series(1,10000) i;
SELECT 10000
pg@regression:5432=# create index on rowcompare_test (first, second, third);
CREATE INDEX

Query where nbtree detects an unsatisfiable qual, as expected
=============================================================

The following query is recognized as having an unsatisfiable qual, as
evidenced by the fact that we see nothing about any buffer hits in
explain analyze output (though you might have to repeat the query to
account for syscache effects):

pg@regression:5432=# explain (analyze, timing off, costs off) select *
from rowcompare_test where first = 1 and (second, third) > (NULL,0);
┌─────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                               QUERY PLAN
                                   │
├─────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│ Index Only Scan using rowcompare_test_first_second_third_idx on
rowcompare_test (actual rows=0 loops=1) │
│   Index Cond: ((first = 1) AND (ROW(second, third) >
ROW(NULL::integer, 0)))                            │
│   Heap Fetches: 0
                                   │
│ Planning Time: 0.034 ms
                                   │
│ Execution Time: 0.013 ms
                                   │
└─────────────────────────────────────────────────────────────────────────────────────────────────────────┘
(5 rows)

Query where nbtree fails to detect an unsatisfiable qual
========================================================

However, this very similar query *won't* have its unsatisfiable qual
detected by nbtree, so we get a useless full index scan instead (we
see "Buffers: shared hit=40" now):

pg@regression:5432=# explain (analyze, timing off, costs off) select *
from rowcompare_test where (second, third) > (NULL,0);
┌─────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                               QUERY PLAN
                                   │
├─────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│ Index Only Scan using rowcompare_test_first_second_third_idx on
rowcompare_test (actual rows=0 loops=1) │
│   Index Cond: (ROW(second, third) > ROW(NULL::integer, 0))
                                   │
│   Heap Fetches: 0
                                   │
│   Buffers: shared hit=40
                                   │
│ Planning Time: 0.048 ms
                                   │
│ Execution Time: 0.321 ms
                                   │
└─────────────────────────────────────────────────────────────────────────────────────────────────────────┘
(6 rows)

Patch
=====

The underlying issue is that nbtree currently detects this case in
_bt_first, which is an ugly special case -- every other unsatisfiable
qual gets detected earlier, in _bt_preprocess_keys (this is an
important responsibility of nbtree preprocessing). Handling the issue
in _bt_first has an undesirable downside, that my test case
highlights: _bt_first can only detect an unsatisfiable NULL RowCompare
qual at the point where it builds an insertion scan key using
RowCompare member input scan keys. That works out in the first test
query, but doesn't work out in the second test query.

There is no good reason for this inconsistency -- it is intrinsically
impossible for a row comparison with a row whose first element is NULL
to ever return anything other than NULL, regardless of any other
factor (though note that this isn't true of later elements that happen
to be NULL, only the first element, since only the first element is
guaranteed to be compared [1]).

Attached patch fixes the problem by moving detection of RowCompare
unsatisfiable-due-to-NULL cases into _bt_fix_scankey_strategy.
_bt_fix_scankey_strategy is called by _bt_preprocess_keys for every
scan key. And so with the patch applied, both cases will have their
unsatisfiable quals detected, allowing nbtree to consistently avoid
these useless full index scans. (My main motivation is removing the
annoying, distracting special case from _bt_first, though.)

[1] https://www.postgresql.org/docs/devel/functions-comparisons.html#ROW-WISE-COMPARISON

-- 
Peter Geoghegan

Re: More reliable nbtree detection of unsatisfiable RowCompare quals involving a leading NULL key/element

Peter Geoghegan <pg@bowt.ie> — 2024-12-27T22:03:12Z

On Mon, Dec 23, 2024 at 1:02 PM Peter Geoghegan <pg@bowt.ie> wrote:
> Attached patch fixes the problem by moving detection of RowCompare
> unsatisfiable-due-to-NULL cases into _bt_fix_scankey_strategy.

Attached is v2, which adds several new regression tests, giving
certain relevant nbtree code paths test coverage.

v2 also makes some small tweaks to _bt_check_rowcompare(), the actual
comparator used by scans with a RowCompare qual. We no longer need to
account for the possibility that the first row member from a
RowCompare scan key contains a null once the scan is underway (we know
that _bt_preprocess_keys would have recognized the qual as
unsatisfiable had the RowCompare looked like that).

-- 
Peter Geoghegan

Re: More reliable nbtree detection of unsatisfiable RowCompare quals involving a leading NULL key/element

Matthias van de Meent <boekewurm+postgres@gmail.com> — 2025-01-07T12:57:59Z

On Fri, 27 Dec 2024 at 23:03, Peter Geoghegan <pg@bowt.ie> wrote:
>
> On Mon, Dec 23, 2024 at 1:02 PM Peter Geoghegan <pg@bowt.ie> wrote:
> > Attached patch fixes the problem by moving detection of RowCompare
> > unsatisfiable-due-to-NULL cases into _bt_fix_scankey_strategy.
>
> Attached is v2, which adds several new regression tests, giving
> certain relevant nbtree code paths test coverage.
>
> v2 also makes some small tweaks to _bt_check_rowcompare(), the actual
> comparator used by scans with a RowCompare qual. We no longer need to
> account for the possibility that the first row member from a
> RowCompare scan key contains a null once the scan is underway (we know
> that _bt_preprocess_keys would have recognized the qual as
> unsatisfiable had the RowCompare looked like that).

backend/access/nbtree/nbtsearch.c:_bt_first
> +             * Cannot be a NULL in the first row member (that would make the
> +             * qual unsatisfiable, preventing it from ever getting this far)

This doesn't really clarify _why_ we'd never get this far, so I'd word that as

+             * Cannot be a NULL in the first row member: _bt_preprocess_keys
+             * would've marked the qual as unsatisfyable, preventing us from
+             * ever getting this far.

Apart from that minor issue, LGTM.

Kind regards,

Matthias van de Meent

Re: More reliable nbtree detection of unsatisfiable RowCompare quals involving a leading NULL key/element

Peter Geoghegan <pg@bowt.ie> — 2025-01-07T15:39:44Z

On Tue, Jan 7, 2025 at 7:58 AM Matthias van de Meent
<boekewurm+postgres@gmail.com> wrote:
> This doesn't really clarify _why_ we'd never get this far, so I'd word that as
>
> +             * Cannot be a NULL in the first row member: _bt_preprocess_keys
> +             * would've marked the qual as unsatisfyable, preventing us from
> +             * ever getting this far.
>
> Apart from that minor issue, LGTM.

Pushed this just now. I used your suggested wording in the committed patch.

Thanks for the review!

--
Peter Geoghegan