Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1sJ9gX-002hdx-TX for pgsql-hackers@arkaria.postgresql.org; Mon, 17 Jun 2024 10:34:02 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.94.2) (envelope-from ) id 1sJ9gV-00FSQQ-8Q for pgsql-hackers@arkaria.postgresql.org; Mon, 17 Jun 2024 10:34:00 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1sJ9gU-00FSQI-Dy for pgsql-hackers@lists.postgresql.org; Mon, 17 Jun 2024 10:33:59 +0000 Received: from mail.postgrespro.ru ([93.174.131.139]) by makus.postgresql.org with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1sJ9gM-001jXN-Nw for pgsql-hackers@postgresql.org; Mon, 17 Jun 2024 10:33:57 +0000 Received: from [10.4.12.74] (unknown [93.174.131.141]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client did not present a certificate) (Authenticated sender: a.rybakina@postgrespro.ru) by mail.postgrespro.ru (Postfix/587) with ESMTPSA id 94DF1E20FEC; Mon, 17 Jun 2024 13:33:46 +0300 (MSK) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=postgrespro.ru; s=mx2023; t=1718620426; bh=ToBa1QmR+U9ns58FE8DLk4HDraIrvXU76zlQ3VQ5zFA=; h=Message-ID:Date:User-Agent:Subject:To:Cc:References:From: In-Reply-To:From; b=5bYmq+5nJyUMSpzmUYu0Lpz1qkGEwNJ0JKSUoM7ss0N9Z8i4me0D+t1Wk5XJb8MAV VoBoifVkjB/SadNfDMOa8kv7xYvjG9AVVe9JTqub4MklC2ApUxqKzVeB1qC2RBO1wX QUR2hNFw9wpMeruiC8qcymYeJ7MfIcD2ldzrYxg0pe/qZ9MTK06mBfgE888ltDO/bR HP5UwFLhvwmbwRMCIhZTv4aZKT0rF8Sq1+gRl7uGbbo72NNWzsSkImnlgcDh+N9lW6 eItf+hs4sfKt3d4orw9yrjcXTbxjjWwEYt3XorQW0qBf6MjKVa6X7NpqvmMKuKq3tf N7dBAiKl9ISIw== Content-Type: multipart/alternative; boundary="------------0Dj0eWJKz00FNlJvWJoBDsqP" Message-ID: <7d5aed92-d4cc-4b76-8ae0-051d182c9eec@postgrespro.ru> Date: Mon, 17 Jun 2024 13:33:49 +0300 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: POC, WIP: OR-clause support for indexes To: Alexander Korotkov Cc: Andrei Lepikhov , jian he , Robert Haas , pgsql-hackers@postgresql.org, Peter Geoghegan , "Finnerty, Jim" , Marcos Pegoraro , teodor@sigaev.ru, Tomas Vondra , Peter Eisentraut , Ranier Vilela References: <567ED6CA.2040504@sigaev.ru> <7389d0dd-05d5-41b7-a12d-2e73f939f851@postgrespro.ru> <74e3c8bc-dccd-45e5-ad2d-6a6e96fc5864@postgrespro.ru> <6d27d752-db0b-4cac-9843-6ba3dd7a1e94@postgrespro.ru> Content-Language: en-US From: Alena Rybakina In-Reply-To: X-KSMG-AntiPhishing: NotDetected, bases: 2024/06/17 09:19:00 X-KSMG-AntiSpam-Interceptor-Info: not scanned X-KSMG-AntiSpam-Status: not scanned, disabled by settings X-KSMG-AntiVirus: Kaspersky Secure Mail Gateway, version 2.1.0.7854, bases: 2024/06/17 05:46:00 #25635423 X-KSMG-AntiVirus-Status: NotDetected, skipped X-KSMG-LinksScanning: not scanned, disabled by settings X-KSMG-Message-Action: skipped X-KSMG-Rule-ID: 1 List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk This is a multi-part message in MIME format. --------------0Dj0eWJKz00FNlJvWJoBDsqP Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Hi, thank you for your work with this subject! On 14.06.2024 15:00, Alexander Korotkov wrote: > On Mon, Apr 8, 2024 at 1:34 AM Alexander Korotkov wrote: >> I've revised the patch. Did some beautification, improvements for >> documentation, commit messages etc. >> >> I've pushed the 0001 patch without 0002. I think 0001 is good by >> itself given that there is the or_to_any_transform_limit GUC option. >> The more similar OR clauses are here the more likely grouping them >> into SOAP will be a win. But I've changed the default value to 5. >> This will make it less invasive and affect only queries with obvious >> repeating patterns. That also reduced the changes in the regression >> tests expected outputs. >> >> Regarding 0002, it seems questionable since it could cause a planning >> slowdown for SAOP's with large arrays. Also, it might reduce the win >> of transformation made by 0001. So, I think we should skip it for >> now. > The patch has been reverted from pg17. Let me propose a new version > for pg18 based on the valuable feedback from Tom Lane [1][2]. > > * The transformation is moved to the stage of adding restrictinfos to > the base relation (in particular add_base_clause_to_rel()). This > leads to interesting consequences. While this allows IndexScans to > use transformed clauses, BitmapScans and SeqScans seem unaffected. > Therefore, I wasn't able to find a planning regression. > * As soon as there is no planning regression anymore, I've removed > or_to_any_transform_limit GUC, which was a source of critics. > * Now, not only Consts allowed in the SAOP's list, but also Params. > * The criticized hash based on expression jumbling has been removed. > Now, the plain list is used instead. > * OrClauseGroup now gets a legal node tag. That allows to mix it in > the list with other nodes without hacks. > > I think this patch shouldn't be as good as before for optimizing > performance of large OR lists, given that BitmapScans and SeqScans > still deal with ORs. However, it allows IndexScans to handle more, > doesn't seem to cause planning regression and therefore introduce no > extra GUC. Overall, this seems like a good compromise. > > This patch could use some polishing, but I'd like to first hear some > feedback on general design. > > Links > 1.https://www.postgresql.org/message-id/3604469.1712628736%40sss.pgh.pa.us > 2.https://www.postgresql.org/message-id/3649287.1712642139%40sss.pgh.pa.us Inoticedthat7librarieshave beenaddedtosrc/backend/optimizer/plan/initsplan.c,andas faras Iremember,TomLanehas alreadyexpresseddoubtsaboutthe approachthatrequiresaddinga largenumberof libraries[0], but I'm afraid I'm out of ideas about alternative approach. In addition,Icheckedthe fixinthe previouscasesthatyouwroteearlier[1]andnoticedthatSeqScancontinuesto generate,unfortunately,withoutconvertingexpressions: with patch: create table test as (select (random()*10)::int x, (random()*1000) y from generate_series(1,1000000) i); create index test_x_1_y on test (y) where x = 1; create index test_x_2_y on test (y) where x = 2; vacuum analyze test; SELECT 1000000 CREATE INDEX CREATE INDEX VACUUM alena@postgres=# explain select * from test where (x = 1 or x = 2) and y = 100; QUERY PLAN -------------------------------------------------------------------------- Gather (cost=1000.00..12690.10 rows=1 width=12) Workers Planned: 2 -> Parallel Seq Scan on test (cost=0.00..11690.00 rows=1 width=12) Filter: (((x = 1) OR (x = 2)) AND (y = '100'::double precision)) (4 rows) alena@postgres=# set enable_seqscan =off; SET alena@postgres=# explain select * from test where (x = 1 or x = 2) and y = 100; QUERY PLAN ------------------------------------------------------------------------- Seq Scan on test (cost=10000000000.00..10000020440.00 rows=1 width=12) Filter: (((x = 1) OR (x = 2)) AND (y = '100'::double precision)) (2 rows) without patch: -------------------------------------------------------------------------------------------------------------- Bitmap Heap Scan on test (cost=8.60..12.62 rows=1 width=12) Recheck Cond: (((y = '100'::double precision) AND (x = 1)) OR ((y = '100'::double precision) AND (x = 2))) -> BitmapOr (cost=8.60..8.60 rows=1 width=0) -> Bitmap Index Scan on test_x_1_y (cost=0.00..4.30 rows=1 width=0) Index Cond: (y = '100'::double precision) -> Bitmap Index Scan on test_x_2_y (cost=0.00..4.30 rows=1 width=0) Index Cond: (y = '100'::double precision) (7 rows) [0] https://www.postgresql.org/message-id/3604469.1712628736%40sss.pgh.pa.us [1] https://www.postgresql.org/message-id/CAPpHfduJtO0s9E%3DSHUTzrCD88BH0eik0UNog1_q3XBF2wLmH6g%40mail.gmail.com -- Regards, Alena Rybakina Postgres Professional:http://www.postgrespro.com The Russian Postgres Company --------------0Dj0eWJKz00FNlJvWJoBDsqP Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit

Hi, thank you for your work with this subject!

On 14.06.2024 15:00, Alexander Korotkov wrote:
On Mon, Apr 8, 2024 at 1:34 AM Alexander Korotkov <aekorotkov@gmail.com> wrote:

I've revised the patch.  Did some beautification, improvements for
documentation, commit messages etc.

I've pushed the 0001 patch without 0002.  I think 0001 is good by
itself given that there is the or_to_any_transform_limit GUC option.
The more similar OR clauses are here the more likely grouping them
into SOAP will be a win.  But I've changed the default value to 5.
This will make it less invasive and affect only queries with obvious
repeating patterns.  That also reduced the changes in the regression
tests expected outputs.

Regarding 0002, it seems questionable since it could cause a planning
slowdown for SAOP's with large arrays.  Also, it might reduce the win
of transformation made by 0001.  So, I think we should skip it for
now.

The patch has been reverted from pg17.  Let me propose a new version
for pg18 based on the valuable feedback from Tom Lane [1][2].

 * The transformation is moved to the stage of adding restrictinfos to
the base relation (in particular add_base_clause_to_rel()).  This
leads to interesting consequences.  While this allows IndexScans to
use transformed clauses, BitmapScans and SeqScans seem unaffected.
Therefore, I wasn't able to find a planning regression.
 * As soon as there is no planning regression anymore, I've removed
or_to_any_transform_limit GUC, which was a source of critics.
 * Now, not only Consts allowed in the SAOP's list, but also Params.
 * The criticized hash based on expression jumbling has been removed.
Now, the plain list is used instead.
 * OrClauseGroup now gets a legal node tag.  That allows to mix it in
the list with other nodes without hacks.

I think this patch shouldn't be as good as before for optimizing
performance of large OR lists, given that BitmapScans and SeqScans
still deal with ORs.  However, it allows IndexScans to handle more,
doesn't seem to cause planning regression and therefore introduce no
extra GUC.  Overall, this seems like a good compromise.

This patch could use some polishing, but I'd like to first hear some
feedback on general design.

Links
1. https://www.postgresql.org/message-id/3604469.1712628736%40sss.pgh.pa.us
2. https://www.postgresql.org/message-id/3649287.1712642139%40sss.pgh.pa.us

I noticed that 7 libraries have been added to src/backend/optimizer/plan/initsplan.c, and as far as I remember, Tom Lane has already expressed doubts about the approach that requires adding a large number of libraries [0], but I'm afraid I'm out of ideas about alternative approach.

In addition, I checked the fix in the previous cases that you wrote earlier [1] and noticed that SeqScan continues to generate, unfortunately, without converting expressions:

with patch:

create table test as (select (random()*10)::int x, (random()*1000) y from generate_series(1,1000000) i); create index test_x_1_y on test (y) where x = 1; create index test_x_2_y on test (y) where x = 2; vacuum analyze test; SELECT 1000000 CREATE INDEX CREATE INDEX VACUUM alena@postgres=# explain select * from test where (x = 1 or x = 2) and y = 100; QUERY PLAN -------------------------------------------------------------------------- Gather (cost=1000.00..12690.10 rows=1 width=12) Workers Planned: 2 -> Parallel Seq Scan on test (cost=0.00..11690.00 rows=1 width=12) Filter: (((x = 1) OR (x = 2)) AND (y = '100'::double precision)) (4 rows) alena@postgres=# set enable_seqscan =off; SET alena@postgres=# explain select * from test where (x = 1 or x = 2) and y = 100; QUERY PLAN ------------------------------------------------------------------------- Seq Scan on test (cost=10000000000.00..10000020440.00 rows=1 width=12) Filter: (((x = 1) OR (x = 2)) AND (y = '100'::double precision)) (2 rows)

without patch:

-------------------------------------------------------------------------------------------------------------- Bitmap Heap Scan on test (cost=8.60..12.62 rows=1 width=12) Recheck Cond: (((y = '100'::double precision) AND (x = 1)) OR ((y = '100'::double precision) AND (x = 2))) -> BitmapOr (cost=8.60..8.60 rows=1 width=0) -> Bitmap Index Scan on test_x_1_y (cost=0.00..4.30 rows=1 width=0) Index Cond: (y = '100'::double precision) -> Bitmap Index Scan on test_x_2_y (cost=0.00..4.30 rows=1 width=0) Index Cond: (y = '100'::double precision) (7 rows)

[0] https://www.postgresql.org/message-id/3604469.1712628736%40sss.pgh.pa.us

[1] https://www.postgresql.org/message-id/CAPpHfduJtO0s9E%3DSHUTzrCD88BH0eik0UNog1_q3XBF2wLmH6g%40mail.gmail.com 

-- 
Regards,
Alena Rybakina
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
--------------0Dj0eWJKz00FNlJvWJoBDsqP--