Re: Inefficient nbtree behavior with row-comparison quals

On Sat, May 11, 2024 at 3:19 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> This produces something like
>
>  Index Only Scan using my_idx on t  (cost=0.43..8.46 rows=1 width=8) (actual time=475.713..475.713 rows=0 loops=1)
>    Index Cond: ((ROW(a, b) > ROW(123450, 123444)) AND (a = 0))
>    Heap Fetches: 0
>    Buffers: shared hit=1 read=33731
>  Planning:
>    Buffers: shared read=4
>  Planning Time: 0.247 ms
>  Execution Time: 475.744 ms
>
> showing that we are reading practically the whole index, which
> is pretty sad considering the index conditions are visibly
> mutually contradictory.  What's going on?

There's another problem along these lines, that seems at least as bad:
queries involving contradictory >= and <= quals aren't recognized as
contradictory during preprocessing. There's no reason why
_bt_preprocessing_keys couldn't detect that case; it just doesn't
right now.

> So this seems pretty horrid.  It would be nice if _bt_preprocess_keys
> were smart enough to notice the contradictory nature of these quals,
> but I grant that (a) that routine is dauntingly complex already and
> (b) this doesn't seem like a common enough kind of query to be worth
> moving heaven and earth to optimize.

I don't think that it would be all that hard.

> However, I do think we should do something about the unstated
> assumption that _bt_preprocess_keys can emit the quals (for a given
> column) in any random order it feels like.  This is evidently not so,
> and it's probably capable of pessimizing other examples besides this
> one.  Unless we want to slow down _bt_check_compare by making it
> continue to examine quals after the first failure, we need to insist
> that required quals appear before non-required quals, thus ensuring
> that a comparison failure will clear continuescan if possible.

Obviously that general principle is important, but I don't think that
we fail to do the right thing anywhere else -- this seems likely to be
the only one.

Row comparisons are kind of a special case, both during preprocessing
and during the scan itself. I find it natural to blame this problem on
the fact that preprocessing makes exactly zero effort to detect
contradictory conditions that happen to involve a RowCompare. Making
non-zero effort in that direction would already be a big improvement.

> Even that looks a little nontrivial, because it seems like nbtree
> may be making some assumptions about the order in which array keys
> appear.  I see the bit about

> However, despite the rather over-the-top verbosity of commenting in
> _bt_advance_array_keys, it's far from clear why or how it depends on
> that.  So I feel a little stuck about what needs to be done here.

The dependency is fairly simple. In the presence of multiple arrays on
the same column, which must be contradictory/redundant, but cannot be
simplified solely due to lack of suitable cross-type support, we have
multiple arrays on the same index column. _bt_advance_array_keys wants
to deal with this by assuming that the scan key order matches the
array key order. After all, there is no indirection to disambiguate
which array belongs to which scan key. We make sure that
_bt_advance_array_keys expectations are never violated by having
preprocessing make sure that the arrays match input scan key order.
Preprocessing must also make sure that the output scan keys are in the
same order as the input scan keys.

I doubt that this detail makes the task of improving row compare
preprocessing any harder. It only comes up in scenarios involving
incomplete opfamilies, which is quite niche (obviously it's not a
factor in your test case, for example). But even if you assume that
incomplete opfamilies are common, it still doesn't seem like this
detail matters.

--
Peter Geoghegan