Subject: Improve EXPLAIN output for multicolumn B-Tree Index

From: <[email-masked]>
Date: Fri, 21 Jun 2024 07:12:25 +0000

Hi,

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.

As the document says, we need to use it carefully.

> The exact rule is that equality constraints on leading columns,

> plus any inequality constraints on the first column that does

> not have an equality constraint, will be used to limit the portion

> of the index that is scanned.

https://www.postgresql.org/docs/17/indexes-multicolumn.html

However, it's not easy to confirm whether multi-column indexes are

being used efficiently because we need to compare the index

definitions and query conditions individually.

For instance, just by looking at the following EXPLAIN result, we

can't determine whether the index is being used efficiently or not

at a glance. Indeed, the current index definition is not suitable

for the query, so the cost is significantly high.

  =# EXPLAIN (VERBOSE, ANALYZE) SELECT * FROM test WHERE id1 = 1 AND id3 = 101;

                                                           QUERY PLAN

  ----------------------------------------------------------------------------------------------------------------------------

   Index Scan using test_idx on public.test  (cost=0.42..12754.76 rows=1 width=18) (actual time=0.033..54.115 rows=1 loops=1)

     Output: id1, id2, id3, value

     Index Cond: ((test.id1 = 1) AND (test.id3 = 101))    -- Is it efficient or not?

   Planning Time: 0.145 ms

   Execution Time: 54.150 ms

  (6 rows)

So, I'd like to improve the output to be more user-friendly.

# Idea

I'm considering adding new information, "Index Bound Cond", which specifies

what quals will be used for the boundary condition of the B-Tree index.

(Since this is just my current idea, I'm open to changing the output.)

Here is an example output.

-- prepare for the test

CREATE TABLE test (id1 int, id2 int, id3 int, value varchar(32));

CREATE INDEX test_idx ON test(id1, id2, id3);                -- multicolumn B-Tree index

INSERT INTO test (SELECT i % 2, i, i, 'hello' FROM generate_series(1,1000000) s(i));

 ANALYZE;

-- explain

=# EXPLAIN (VERBOSE, ANALYZE) SELECT * FROM test WHERE id1 = 1 AND id2 = 101;

                                                       QUERY PLAN

 -----------------------------------------------------------------------------------------------------------------------

  Index Scan using test_idx on public.test  (cost=0.42..8.45 rows=1 width=18) (actual time=0.046..0.047 rows=1 loops=1)

    Output: id1, id2, id3, value

    Index Cond: ((test.id1 = 1) AND (test.id2 = 101))

    Index Bound Cond: ((test.id1 = 1) AND (test.id2 = 101))  -- The B-Tree index is used efficiently.

  Planning Time: 0.124 ms

  Execution Time: 0.076 ms

(6 rows)

 =# EXPLAIN (VERBOSE, ANALYZE) SELECT * FROM test WHERE id1 = 1 AND id3 = 101;

                                                          QUERY PLAN

 ----------------------------------------------------------------------------------------------------------------------------

  Index Scan using test_idx on public.test  (cost=0.42..12754.76 rows=1 width=18) (actual time=0.033..54.115 rows=1 loops=1)

    Output: id1, id2, id3, value

    Index Cond: ((test.id1 = 1) AND (test.id3 = 101))

    Index Bound Cond: (test.id1 = 1)                        -- The B-tree index is *not* used efficiently

                                                          -- compared to the previous execution conditions,

                                                          -- because it differs from "Index Cond".

  Planning Time: 0.145 ms

  Execution Time: 54.150 ms

(6 rows)

# PoC patch

The PoC patch makes the following changes:

* Adds a new variable related to bound conditions

  to IndexPath, IndexScan, IndexOnlyScan, and BitmapIndexScan

* Adds quals for bound conditions to IndexPath when estimating cost, since

  the B-Tree index considers the boundary condition in btcostestimate()

* Adds quals for bound conditions to the output of EXPLAIN

Thank you for reading my suggestion. Please feel free to comment.

* Is this feature useful? Is there a possibility it will be accepted?

* Are there any other ideas for determining if multicolumn indexes are

being used efficiently? Although I considered calculating the efficiency using

pg_statio_all_indexes.idx_blks_read and pg_stat_all_indexes.idx_tup_read,

 I believe improving the EXPLAIN output is better because it can be output

per query and it's more user-friendly.

* Is "Index Bound Cond" the proper term?I also considered changing

"Index Cond" to only show quals for the boundary condition and adding

a new term "Index Filter".

* Would it be better to add new interfaces to Index AM? Is there any case

  to output the EXPLAIN for each index context? At least, I think it's worth

  considering whether it's good for amcostestimate() to modify the

  IndexPath directly as the PoC patch does.

Regards,

--

Masahiro Ikeda

NTT DATA CORPORATION

---

From: Peter Geoghegan <[email-masked]>
Date: Thu, 27 Jun 2024 16:01:56 -0400

> 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/[email-masked]

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/[email-masked]
-- the final full paragraph mentions moving _bt_preprocess_keys() into
the planner
-- 
Peter Geoghegan