Re: Improve EXPLAIN output for multicolumn B-Tree Index

On Fri, Jun 21, 2024 at 3:12 AM <Masahiro(dot)Ikeda(at)nttdata(dot)com> wrote:
> Regarding the multicolumn B-Tree Index, I'm considering
> if we can enhance the EXPLAIN output. There have been requests
> for this from our customer.

I agree that this is a real problem -- I'm not surprised to hear that
your customer asked about it.

In the past, we've heard complaints about this problem from Markus Winand, too:

https://use-the-index-luke.com/sql/explain-plan/postgresql/filter-predicates

As it happens I have been thinking about this problem a lot recently.
Specifically the user-facing aspects, what we show in EXPLAIN. It is
relevant to my ongoing work on skip scan:

https://commitfest.postgresql.org/48/5081/
https://www.postgresql.org/message-id/flat/CAH2-Wzmn1YsLzOGgjAQZdn1STSG_y8qP__vggTaPAYXJP+G4bw(at)mail(dot)gmail(dot)com

Unfortunately, my patch will make the situation more complicated for
your patch. I would like to resolve the tension between the two
patches, but I'm not sure how to do that.

If you look at the example query that I included in my introductory
email on the skip scan thread (the query against the sales_mdam_paper
table), you'll see that my patch makes it go much faster. My patch
will effectively "convert" nbtree scan keys that would traditionally
have to use non-index-bound conditions/filter predicates, into
index-bound conditions/access predicates. This all happens at runtime,
during nbtree preprocessing (not during planning).

This may mean that your patch's approach of determining which
columns/scan keys are in which category (bound vs. non-bound) cannot
rely on its current approach of placing each type of clause into one
of two categories inside btcostestimate() -- the view that we see from
btcostestimate() will be made less authoritative by skip scan. What
actually matters in what happens during nbtree preprocessing, inside
_bt_preprocess_keys().

Unfortunately, this is even more complicated than it sounds. It would
be a good idea if we moved _bt_preprocess_keys() to plan time, so that
btcostestimate() operated off of authoritative information, rather
than independently figuring out the same details for the purposes of
costing. We've talked about this before, even [1]. That way your patch
could just work off of this authoritative information. But even that
doesn't necessarily fix the problem.

Note that the skip scan patch makes _bt_preprocess_keys()
*indiscriminately* "convert" *all* scan keys to index bound conditions
-- at least where that's possible at all. There are minor
implementation restrictions that mean that we can't always do that.
But overall, the patch more or less eliminates non-bound index
conditions. That is, it'll be rare to non-existent for nbtree to fail
to mark *any* scan key as SK_BT_REQFWD/SK_BT_REQBKWD. Technically
speaking, non-bound conditions mostly won't exist anymore.

Of course, this doesn't mean that the problem that your patch is
solving will actually go away. I fully expect that the skip scan patch
will merely make some scan keys "required-by-scan/index bound
condition scan keys in name only". Technically they won't be the
problematic kind of index condition, but that won't actually be true
in any practical sense. Because users (like your customer) will still
get full index scans, and be surprised, just like today.

As I explain in my email on the skip scan thread, I believe that the
patch's aggressive approach to "converting" scan keys is an advantage.
The amount of skipping that actually takes place should be decided
dynamically, at runtime. It is a decision that should be made at the
level of individual leaf pages (or small groups of leaf pages), not at
the level of the whole scan. The distinction between index bound
conditions and non-bound conditions becomes much more "squishy", which
is mostly (though not entirely) a good thing.

I really don't know what to do about this. As I said, I agree with the
general idea of this patch -- this is definitely a real problem. And,
I don't pretend that my skip scan patch will actually define the
problem out of existence (except perhaps in those cases that it
actually makes it much faster). Maybe we could make a guess (based on
statistics) whether or not any skip attributes will leave the
lower-order clauses as useful index bound conditions at runtime. But I
don't know...that condition is actually a "continuous" condition now
-- it is not a strict dichotomy (it is not either/or, but rather a
question of degree, perhaps on a scale of 0.0 - 1.0).

It's also possible that we should just do something simple, like your
patch, even though technically it won't really be accurate in cases
where skip scan is used to good effect. Maybe showing the "default
working assumption" about how the scan keys/clauses will behave at
runtime is actually the right thing to do. Maybe I am just
overthinking it.

[1] https://www.postgresql.org/message-id/2587523.1647982549@sss.pgh.pa.us
-- the final full paragraph mentions moving _bt_preprocess_keys() into
the planner
--
Peter Geoghegan