Thread: bt Scankey in another contradictory case
Hi,
when i read source code of the part of nbtree, i detected another kind of contradictory case postgresql has not eliminated
(eg. x >4 and x <3) in the function _bt_preprocess_keys in nbtutils.c. this cause next unnecessary index scan and qual evaluation.
it seems no one will write SQL like that, but maybe it generated from the ec or degenerate qual.
the function just invoked in function _bt_first during initializing index scan, so it’s cheap to eliminate this case in the function.
we just pay attention on the opposite operator, so there are four detailed cases (ie. x >4 and x <3 , x >4 and x <=3, x >=4 and x <3, x >=4 and x <=3).
when test the case is contradictory or not, it's need to use the more restrictive operator when less and more restrictive operator both appeared,
case like x >4 and x <=4, if we choose <=, 4 <= 4 is satisfied, actually x >4 and x <=4 is contradictory.
when >= with <= or > with <, it's ok to pick any one of them.
i have added this feature in my local environment and tested. but i am not sure it's worth to spend more effort on it.
bigbro_wq@hotmail.com
On Fri, Aug 30, 2024 at 7:36 AM b ro <bigbro_wq@hotmail.com> wrote: > this is the patch attachment. We discussed this recently: https://www.postgresql.org/message-id/80384.1715458896%40sss.pgh.pa.us I think that we should do this. It doesn't make a huge difference in practice, because we'll still end the scan once the leaf level is reached. But it matters more when array keys are involved, where there might be more than one descent to the leaf level. Plus we might as well just be thorough about this stuff. -- Peter Geoghegan
Hi,
I have reanalysed the code of function _bt_first. I notice that using a multi-attribute index
if we can't identify the starting boundaries and the following attributes markded not required ,
that means we need start at first or last page in the index to examine every tuple to satisfy the
qual or not, in the meantime the scan will be stopped while the first attribute evaluated failed.
For instance:
create table c_s( x int, y int);
insert into c_s select generate_series(1, 20000), generate_series(1, 20000);
create index my_c_s_idx on c_s using btree(x,y);
explain (analyze, buffers) select * from c_s where x >4000 and y >10 and y <10 order by x desc;
--------------------------------------------------------------------------------------------------------------------------------
Index Only Scan Backward using my_c_s_idx on c_s (cost=0.29..384.31 rows=1 width=8) (actual time=1.302..1.304 rows=0 loops=1)
Index Cond: ((x > 4000) AND (y > 10) AND (y < 10))
Heap Fetches: 0
Buffers: shared read=46
Planning:
Buffers: shared hit=51 read=15
Planning Time: 1.311 ms
Execution Time: 1.435 ms
(8 rows)
The instance is a little different for description above due to the implies NOT NULL Scankey,
but it has no effect on the whole situation.
What's more, if i change the number 4000 to 1000.
-----------------------------------------------------------------------------------------------------
Sort (cost=441.01..441.01 rows=1 width=8) (actual time=2.974..2.975 rows=0 loops=1)
Sort Key: x DESC
Sort Method: quicksort Memory: 25kB
Buffers: shared hit=89
-> Seq Scan on c_s (cost=0.00..441.00 rows=1 width=8) (actual time=2.971..2.971 rows=0 loops=1)
Filter: ((x > 1000) AND (y > 10) AND (y < 10))
Rows Removed by Filter: 20000
Buffers: shared hit=89
Planning:
Buffers: shared hit=2
Planning Time: 0.113 ms
Execution Time: 2.990 ms
(12 rows)
The planner choosed the Seq Scan, and the executor have done the unnecessary jobs 20000 times.
Let's don't confine to the plain attributes or row comparison and Seq Scan or Index Scan .
We can pretend row-comparison as multi-attributes comparison. The qual is implicit-AND format,
that means once one attribute is self-contradictory, we can abandon the qual immediately.
Maybe we can do more efficient jobs during planning time. Like at the phase of function deconstruct_recurse
invoked, we can identify qual that is self-contradictory then flag it. With this information we know who is
a dummy relation named arbitrarily.
For instance:
explain (analyze, buffers) select * from c_s a , c_s b where a.y >10 and a.y<10 and a.x=b.x;
QUERY PLAN
-------------------------------------------------------------------------------------------------------
Nested Loop (cost=0.29..393.31 rows=1 width=16) (actual time=1.858..1.858 rows=0 loops=1)
Buffers: shared hit=89
-> Seq Scan on c_s a (cost=0.00..389.00 rows=1 width=8) (actual time=1.857..1.857 rows=0 loops=1)
Filter: ((y > 10) AND (y < 10))
Rows Removed by Filter: 20000
Buffers: shared hit=89
-> Index Only Scan using my_c_s_idx on c_s b (cost=0.29..4.30 rows=1 width=8) (never executed)
Index Cond: (x = a.x)
Heap Fetches: 0
Planning:
Buffers: shared hit=12
Planning Time: 0.236 ms
Execution Time: 1.880 ms
(13 rows)
After deconstruct_recurse invoked, qual(a.y >10 and a.y<10) was distributed to relation "a" and relation "a" is
a dummy relation. When "a" and "b" make inner join, "a" will supply nothing. That means the inner-join rel is
a dummy relation too. If there is a outer join above the inner join and some one who can commute with it,
we can do more efficient jobs and so on.
It also has benefit on path-competing phase with this feature due to it doesn't cost anything.
It's need to discuss the idea whether is feasible or not and it will takes a lot of effort to complete this feature.
Anyway we can fix these issues what we had encountered first.
bigbro_wq@hotmail.com
From: Peter GeogheganDate: 2024-08-30 22:32To: b roCC: pgsql-hackersSubject: Re: bt Scankey in another contradictory caseOn Fri, Aug 30, 2024 at 7:36 AM b ro <bigbro_wq@hotmail.com> wrote:> this is the patch attachment.We discussed this recently:https://www.postgresql.org/message-id/80384.1715458896%40sss.pgh.pa.usI think that we should do this.It doesn't make a huge difference in practice, because we'll still endthe scan once the leaf level is reached. But it matters more whenarray keys are involved, where there might be more than one descent tothe leaf level. Plus we might as well just be thorough about thisstuff.--Peter Geoghegan
On Sun, Sep 1, 2024 at 11:44 AM bigbro_wq@hotmail.com <bigbro_wq@hotmail.com> wrote: > I have reanalysed the code of function _bt_first. I notice that using a multi-attribute index > if we can't identify the starting boundaries and the following attributes markded not required , > that means we need start at first or last page in the index to examine every tuple to satisfy the > qual or not, in the meantime the scan will be stopped while the first attribute evaluated failed. I'm not sure of what it is that you're trying to draw attention to. The behavior of _bt_first doesn't seem relevant to this patch to me. For one thing, _bt_first doesn't actually care about whether or not a scan key is marked required -- _bt_first independently applies its own similar rules to determine which scan keys can be used in the insertion scan key used to find an initial position on the leaf level. More importantly, whether a scan key is marked required doesn't seem relevant to this patch (that is relevant to _bt_preprocess_keys, but doesn't seem relevant to the changes that you propose to make to _bt_preprocess_keys). > For instance: > create table c_s( x int, y int); > insert into c_s select generate_series(1, 20000), generate_series(1, 20000); > create index my_c_s_idx on c_s using btree(x,y); > explain (analyze, buffers) select * from c_s where x >4000 and y >10 and y <10 order by x desc; Your patch (which I haven't tested for myself) is based on the observation that "y > 10 and y < 10" is a contradictory condition. This is true regardless of any other factor, such as whether we're able to mark the "y" scan key required. All that _bt_first has to do is return when it notices "so->qual_ok" was set to false within _bt_preprocess_keys. It doesn't matter if there is an "x > 4000", and it doesn't matter if you use a composite index like this that completely omits a condition on "x". > What's more, if i change the number 4000 to 1000. > ----------------------------------------------------------------------------------------------------- > Sort (cost=441.01..441.01 rows=1 width=8) (actual time=2.974..2.975 rows=0 loops=1) > Sort Key: x DESC > Sort Method: quicksort Memory: 25kB > Buffers: shared hit=89 > -> Seq Scan on c_s (cost=0.00..441.00 rows=1 width=8) (actual time=2.971..2.971 rows=0 loops=1) > Filter: ((x > 1000) AND (y > 10) AND (y < 10)) > Rows Removed by Filter: 20000 > Buffers: shared hit=89 > Planning: > Buffers: shared hit=2 > Planning Time: 0.113 ms > Execution Time: 2.990 ms > (12 rows) > > The planner choosed the Seq Scan, and the executor have done the unnecessary jobs 20000 times. It's true that a sequential scan won't ever apply the logic from _bt_preprocess_keys, nor any similar logic. A sequential scan with contradictory quals will therefore not be detected in cases where it would have been detected had we used an index scan with the same quals. This inconsistency doesn't make much sense; it's just an implementation deficiency. It's historical. We've talked about moving the current _bt_preprocess_keys logic to plan time before. See Tom's remarks at the end of this email: https://www.postgresql.org/message-id/2587523.1647982549@sss.pgh.pa.us I think that it would be possible to move _bt_preprocess_keys to plan time, and to generalize it to work with sequential scans, but that is a much larger project. It seems out of scope. I think that you should just focus on the immediate problem of not detecting contradictory quals that happen to involve (> or >=) and (< or <=) operators. It's a completely independent problem, and one that is well scoped. -- Peter Geoghegan
On Fri, Aug 30, 2024 at 10:32 AM Peter Geoghegan <pg@bowt.ie> wrote: > It doesn't make a huge difference in practice, because we'll still end > the scan once the leaf level is reached. But it matters more when > array keys are involved, where there might be more than one descent to > the leaf level. Plus we might as well just be thorough about this > stuff. Was your "explain (analyze, buffers) select * from c_s where x >4000 and y >10 and y <10 order by x desc" example intended to illustrate that these earlier remarks of mine about the problem not being so bad aren't always correct? With your patch, we can detect contradictory quals regardless of their required-ness. There will be some cases where (with your patch) we'll now avoid a very inefficient full index scan -- contrary to what I said about it back on August 30. If that is what you meant, then I accept your argument. I didn't quite get your point before, but this is a logical, useful argument. (You didn't really need to convince me, but this argument still helps your patch.) -- Peter Geoghegan