Thread: num_sa_scans in genericcostestimate
When costing a btree index scan, num_sa_scans gets computed twice, once in btcostestmeate and once in genericcostestimate. But the computations are different. It looks like the generic one includes all =ANY in any column in the index, while the bt one includes only =ANY which or on columns for which all the preceding index columns are tested for equality.
It looks like the generic one was there first then the bt-specific one was added later to improve planning of btree indexes. But then shouldn't the value be passed down to generic, rather than recomputed (differently)? I've attached a patch to do that. Generic still computes the value itself for other-than-btree indexes.
Or, is there a reason we want a different value to be used in genericcostestimate?
The context for this is that I was looking at cases where btree indexes were not using all the columns they could, but rather shoving some of the conditions down into a Filter unnecessarily/unhelpfully. This change doesn't fix that, but it does seem to be moving in the right direction.
This does cause a regression test failure due to an (apparently?) uninteresting plan change.
Cheers,
Jeff
Attachment
On Sun, Aug 21, 2022 at 2:45 PM Jeff Janes <jeff.janes@gmail.com> wrote:
...
The context for this is that I was looking at cases where btree indexes were not using all the columns they could, but rather shoving some of the conditions down into a Filter unnecessarily/unhelpfully. This change doesn't fix that, but it does seem to be moving in the right direction.
Added to commitfest.
This does cause a regression test failure due to an (apparently?) uninteresting plan change.
Looking more at the regression test plan change, it points up an interesting question which is only tangentially related to this patch.
With patch applied:
[local] 417536 regression=# explain analyze SELECT thousand, tenthous FROM tenk1
WHERE thousand < 2 AND tenthous IN (1001,3000)
ORDER BY thousand;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------
Sort (cost=4.55..4.56 rows=1 width=8) (actual time=0.100..0.101 rows=2 loops=1)
Sort Key: thousand
Sort Method: quicksort Memory: 25kB
-> Index Only Scan using tenk1_thous_tenthous on tenk1 (cost=0.29..4.50 rows=1 width=8) (actual time=0.044..0.048 rows=2 loops=1)
Index Cond: ((thousand < 2) AND (tenthous = ANY ('{1001,3000}'::integer[])))
Heap Fetches: 0
Planning Time: 1.040 ms
Execution Time: 0.149 ms
(8 rows)
[local] 417536 regression=# set enable_sort TO off ;
WHERE thousand < 2 AND tenthous IN (1001,3000)
ORDER BY thousand;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------
Sort (cost=4.55..4.56 rows=1 width=8) (actual time=0.100..0.101 rows=2 loops=1)
Sort Key: thousand
Sort Method: quicksort Memory: 25kB
-> Index Only Scan using tenk1_thous_tenthous on tenk1 (cost=0.29..4.50 rows=1 width=8) (actual time=0.044..0.048 rows=2 loops=1)
Index Cond: ((thousand < 2) AND (tenthous = ANY ('{1001,3000}'::integer[])))
Heap Fetches: 0
Planning Time: 1.040 ms
Execution Time: 0.149 ms
(8 rows)
[local] 417536 regression=# set enable_sort TO off ;
[local] 417536 regression=# explain analyze SELECT thousand, tenthous FROM tenk1
WHERE thousand < 2 AND tenthous IN (1001,3000)
ORDER BY thousand;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------
Index Only Scan using tenk1_thous_tenthous on tenk1 (cost=0.29..4.71 rows=1 width=8) (actual time=0.021..0.024 rows=2 loops=1)
Index Cond: (thousand < 2)
Filter: (tenthous = ANY ('{1001,3000}'::integer[]))
Rows Removed by Filter: 18
Heap Fetches: 0
Planning Time: 0.156 ms
Execution Time: 0.039 ms
(7 rows)
WHERE thousand < 2 AND tenthous IN (1001,3000)
ORDER BY thousand;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------
Index Only Scan using tenk1_thous_tenthous on tenk1 (cost=0.29..4.71 rows=1 width=8) (actual time=0.021..0.024 rows=2 loops=1)
Index Cond: (thousand < 2)
Filter: (tenthous = ANY ('{1001,3000}'::integer[]))
Rows Removed by Filter: 18
Heap Fetches: 0
Planning Time: 0.156 ms
Execution Time: 0.039 ms
(7 rows)
Why does having the =ANY in the "Index Cond:" rather than the "Filter:" inhibit it from understanding that the rows will still be delivered in order by "thousand"?
Cheers,
Jeff
Jeff Janes <jeff.janes@gmail.com> writes:
> When costing a btree index scan, num_sa_scans gets computed twice, once in
> btcostestmeate and once in genericcostestimate. But the computations are
> different. It looks like the generic one includes all =ANY in any column
> in the index, while the bt one includes only =ANY which or on columns for
> which all the preceding index columns are tested for equality.
I think this is correct. As per the comments in btcostestimate:
* For a btree scan, only leading '=' quals plus inequality quals for the
* immediately next attribute contribute to index selectivity (these are
* the "boundary quals" that determine the starting and stopping points of
* the index scan). Additional quals can suppress visits to the heap, so
* it's OK to count them in indexSelectivity, but they should not count
* for estimating numIndexTuples. So we must examine the given indexquals
* to find out which ones count as boundary quals. ...
and further down
/* count number of SA scans induced by indexBoundQuals only */
if (alength > 1)
num_sa_scans *= alength;
This num_sa_scans value computed by btcostestimate is (or should be)
only used in calculations related to numIndexTuples, whereas the one
in genericcostestimate should be used for calculations related to the
overall number of heap tuples returned by the indexscan. Maybe there
is someplace that is using the wrong one, but it's not a bug that they
are different.
> The context for this is that I was looking at cases where btree indexes
> were not using all the columns they could, but rather shoving some of the
> conditions down into a Filter unnecessarily/unhelpfully. This change
> doesn't fix that, but it does seem to be moving in the right direction.
If it helps, it's only accidental, because this patch is surely wrong.
We *should* be distinguishing these numbers.
regards, tom lane
Jeff Janes <jeff.janes@gmail.com> writes:
> Why does having the =ANY in the "Index Cond:" rather than the "Filter:"
> inhibit it from understanding that the rows will still be delivered in
> order by "thousand"?
They won't be. The =ANY in index conditions results in multiple
index scans, that is we effectively do a scan with
Index Cond: (thousand < 2) AND (tenthous = 1001)
and then another with
Index Cond: (thousand < 2) AND (tenthous = 3000)
and only by very good luck would the overall result be sorted by
"thousand". On the other hand, if the ScalarArrayOp is a plain
filter condition, then it doesn't affect the number of index
scans --- it's just a (rather expensive) filter condition.
indxpath.c's get_index_paths() is explicitly aware of these
considerations, maybe reading the comments there would help.
I don't say there couldn't be a bug here, but you haven't
demonstrated one. I believe that get_index_paths() will
generate paths both ways, with the ScalarArrayOp as a filter
condition and an indexqual, and it's evidently deciding the
first way is cheaper.
regards, tom lane