Re: Inefficient nbtree behavior with row-comparison quals

On Sat, May 11, 2024 at 5:05 PM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Hmm, I'm generally in favor of a lot of small patches rather than one
> enormously complex one. Isn't this point something that could be
> broken out?

That's not really possible here.

Skip scan generally works by consing up a special "skip" array +
equality scan key for attributes that lack input scan keys that use
the equality strategy (up to and including the least significant input
scan key's index attribute). In the case of quals like "WHERE sdate
BETWEEN '2024-01-01' and '2024-01-31'" (assume that there is no index
column before "sdate" here), we generate a skip scan key + skip array
for "sdate" early during preprocessing. This "array" works in mostly
the same way as arrays work in Postgres 17; the big difference is that
it procedurally generates its values, on-demand. The values are
generated from within given range of values -- often every possible
value for the underlying type. Often, but not always -- there's also
range predicates to consider.

Later preprocessing inside _bt_compare_array_scankey_args() will limit
the range of values that our magical skip array generates, when we try
to compare it against inequalities. So for the BETWEEN example, both
the >= scan key and the <= scan key are "eliminated", though in a way
that leaves us with a skip array + scan key that generates the
required range of values. It's very easy to make
_bt_compare_array_scankey_args() detect the case where a skip array's
upper and lower bounds are contradictory, which is how this is
handled.

That said, there'll likely be cases where this kind of transformation
isn't possible. I hope to be able to always set the scan keys up this
way, even in cases where skipping isn't expected to be useful (that
should be a problem for the index scan to deal with at runtime). But I
think I'll probably end up falling short of that ideal in some way or other.
Maybe that creates a need to independently detect contradictory >= and
<= scan keys (keys that don't go through this skip array preprocessing
path).

Obviously this is rather up in the air right now. As I said, I think
that we could directly fix this case quite easily, if we had to. And
I'm sympathetic; this is pretty horrible if you happen to run into it.

--
Peter Geoghegan