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 1sVeVM-00Aweb-DB for pgsql-hackers@arkaria.postgresql.org; Sun, 21 Jul 2024 21:54:09 +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 1sVeVJ-00CSwF-1H for pgsql-hackers@arkaria.postgresql.org; Sun, 21 Jul 2024 21:54:05 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1sVeVI-00CSvz-Gq for pgsql-hackers@lists.postgresql.org; Sun, 21 Jul 2024 21:54:05 +0000 Received: from mail.postgrespro.ru ([93.174.131.139]) by magus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1sVeVB-000lhZ-RZ for pgsql-hackers@lists.postgresql.org; Sun, 21 Jul 2024 21:54:04 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=postgrespro.ru; s=mx2023; t=1721598836; bh=CBXAJFpO29H0ZXTBST6loExdsx0MZzIXf5NjdMjwO+o=; h=Message-ID:Date:User-Agent:Subject:To:Cc:References:From: In-Reply-To:From; b=Og/OSE1aOXR4ew2rPikmNBQ7sijocYEIMe4WuBJFPMdOYuc5XUUyEqc7uXgnidiDw mVo0GpFcjKoUzgOWOHTfcI5MdK48ECYy3yeFh52FDn+RKftkgVAusAS3FgnXB59/1b BKIoqxgEaYSQcKR4H08ez9fpxdPZKC3NhNPFPDOSGf2+vZnKP+N7eERUyeNl+mcO+V uMu+x3pITWcG3WREYwijoyQWIkfZr6iOMk3rLWmvyNNh5H7qcxOCv6qLAo6knW4GOx 6t3OvZm5ClqKlXPRL7/1+smBUh43/1pp6KjDWnq82oalS3WIvqGR0+ljud8FEVcjNR NdvOFPiaeeymQ== Received: from [172.28.0.22] (unknown [213.171.56.10]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (Client did not present a certificate) (Authenticated sender: a.rybakina@postgrespro.ru) by mail.postgrespro.ru (Postfix/587) with ESMTPSA id 5F79560194; Mon, 22 Jul 2024 00:53:55 +0300 (MSK) Content-Type: multipart/alternative; boundary="------------0DiEz5qssC1Zb2RBiHFcZPXa" Message-ID: <38289f6c-b8c0-4713-8fb5-703fe771872a@postgrespro.ru> Date: Mon, 22 Jul 2024 01:53:51 +0300 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: POC, WIP: OR-clause support for indexes To: Nikolay Shaplov , Alexander Korotkov Cc: pgsql-hackers@lists.postgresql.org, 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> <8969055.VV5PYv0bhD@thinkpad-pgpro> Content-Language: en-US From: Alena Rybakina In-Reply-To: <8969055.VV5PYv0bhD@thinkpad-pgpro> X-KSMG-AntiPhishing: NotDetected, bases: 2024/07/21 21:03: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/07/21 17:25:00 #26117717 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. --------------0DiEz5qssC1Zb2RBiHFcZPXa Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Hi! Thank you for your contribution to this thread! To be honest,I saw a larger problem. Look at the query bellow: master: alena@postgres=# create table t (a int not null, b int not null, c int not null); insert into t (select 1, 1, i from generate_series(1,10000) i); insert into t (select i, 2, 2 from generate_series(1,10000) i); create index t_a_b_idx on t (a, b); create statistics t_a_b_stat (mcv) on a, b from t; create statistics t_b_c_stat (mcv) on b, c from t; vacuum analyze t; CREATE TABLE INSERT 0 10000 INSERT 0 10000 CREATE INDEX CREATE STATISTICS CREATE STATISTICS VACUUM alena@postgres=# explain select * from t where a = 1 and (b = 1 or b = 2) and c = 2;                                   QUERY PLAN ------------------------------------------------------------------------------  Bitmap Heap Scan on t  (cost=156.55..465.57 rows=5001 width=12)    Recheck Cond: (a = 1)    Filter: ((c = 2) AND ((b = 1) OR (b = 2)))    ->  Bitmap Index Scan on t_a_b_idx  (cost=0.00..155.29 rows=10001 width=0)          Index Cond: (a = 1) (5 rows) The query plan if v26[0] and v27[1] versions are equal and wrong in my opinion -where is c=2 expression? v27 [1] alena@postgres=# explain select * from t where a = 1 and (b = 1 or b = 2) and c = 2;                                   QUERY PLAN ------------------------------------------------------------------------------  Bitmap Heap Scan on t  (cost=165.85..474.87 rows=5001 width=12)    Recheck Cond: ((a = 1) AND (b = ANY ('{1,2}'::integer[])))    Filter: (c = 2)    ->  Bitmap Index Scan on t_a_b_idx  (cost=0.00..164.59 rows=10001 width=0)          Index Cond: ((a = 1) AND (b = ANY ('{1,2}'::integer[]))) (5 rows) v26 [0] alena@postgres=# explain select * from t where a = 1 and (b = 1 or b = 2) and c = 2;                                   QUERY PLAN ------------------------------------------------------------------------------  Bitmap Heap Scan on t  (cost=165.85..449.86 rows=5001 width=12)    Recheck Cond: ((a = 1) AND (b = ANY ('{1,2}'::integer[])))    Filter: (c = 2)    ->  Bitmap Index Scan on t_a_b_idx  (cost=0.00..164.59 rows=10001 width=0)          Index Cond: ((a = 1) AND (b = ANY ('{1,2}'::integer[]))) (5 rows) In addition, I noticed that the ANY expression will be formed only for first group and ignore for others, like in the sample bellow: v26 version [0]: alena@postgres=# explain select * from t where (b = 1 or b = 2) and (a = 2 or a=3);                                     QUERY PLAN -----------------------------------------------------------------------------------  Index Scan using t_a_b_idx on t  (cost=0.29..24.75 rows=2 width=12)    Index Cond: ((a = ANY ('{2,3}'::integer[])) AND (b = ANY ('{1,2}'::integer[]))) (2 rows) v27 version [1]: alena@postgres=# explain select * from t where (b = 1 or b = 2 or a = 2 or a=3);                        QUERY PLAN --------------------------------------------------------  Seq Scan on t  (cost=0.00..509.00 rows=14999 width=12)    Filter: ((b = 1) OR (b = 2) OR (a = 2) OR (a = 3)) (2 rows) alena@postgres=# create index a_idx on t(a); CREATE INDEX alena@postgres=# create index b_idx on t(b); CREATE INDEX alena@postgres=# analyze; ANALYZE v26: alena@postgres=# explain select * from t where (b = 1 or b = 2 or a = 2 or a=3);                                      QUERY PLAN ------------------------------------------------------------------------------------  Bitmap Heap Scan on t  (cost=17.18..30.94 rows=4 width=12)    Recheck Cond: ((a = ANY ('{2,3}'::integer[])) OR (a = ANY ('{2,3}'::integer[])))    ->  BitmapOr  (cost=17.18..17.18 rows=4 width=0)          ->  Bitmap Index Scan on a_idx  (cost=0.00..8.59 rows=2 width=0)                Index Cond: (a = ANY ('{2,3}'::integer[]))          ->  Bitmap Index Scan on a_idx  (cost=0.00..8.59 rows=2 width=0)                Index Cond: (a = ANY ('{2,3}'::integer[])) (7 rows) v27: alena@postgres=# explain select * from t where (b = 1 or b = 2 or a = 2 or a=3);                        QUERY PLAN --------------------------------------------------------  Seq Scan on t  (cost=0.00..509.00 rows=14999 width=12)    Filter: ((b = 1) OR (b = 2) OR (a = 2) OR (a = 3)) (2 rows) The behavior in version 26 is incorrect, but in version 27, it does not select anything other than seqscan Since Thursday I have been trying to add the code forming groups of identical "OR" expressions, as in version 26. I'm currently debugging errors. On 21.07.2024 11:17, Nikolay Shaplov wrote: > В письме от среда, 17 июля 2024 г. 22:36:19 MSK пользователь Alexander > Korotkov написал: > > Hi All! > > I am continue reading the patch, now it's newer version > > First main question: > > As far a I can get, the entry point for OR->ANY convertation have been moved > to match_clause_to_indexcol funtion, that checks if some restriction can use > index for performance. > > The thing I do not understand what match_clause_to_indexcol actually received > as arguments. Should this be set of expressions with OR in between grouped by > one of the expression argument? > > If not I do not understand how this ever should work.  The point is that we do the transformation for those columns that have an index, since this transformation is most useful in these cases. we pass the parameters index relation and column number to find out information about it. > > The rest is about code readability > >> + if (bms_is_member(index->rel->relid, rinfo->right_relids)) >> + return NULL; To be honest, I'm not sure that I understand your question. Could you explain me? > This check it totally not obvious for person who is not deep into postgres > code. There should go comment explaining what are we checking for, and why it > does not suit our purposes > > >> + foreach(lc, orclause->args) >> + { I'll add it, thank you. > Being no great expert in postgres code, I am confused what are we iterating on > here? Two arguments of OR statement? (a>1) OR (b>2) those in brackets? Or > what? Comment explaining that would be a great help here. > > >> +if (sub_rinfo->is_pushed_down != rinfo->is_pushed_down || >> + sub_rinfo->is_clone != rinfo->is_clone || >> + sub_rinfo->security_level != rinfo->security_level || >> + !bms_equal(sub_rinfo->required_relids, rinfo->required_relids) || >> + !bms_equal(sub_rinfo->incompatible_relids, rinfo- > incompatible_relids) || >> + !bms_equal(sub_rinfo->outer_relids, rinfo->outer_relids)) >> + { I'll add it. > This check it totally mind-blowing... What in the name of existence is going > on here? > > I would suggest to split these checks into parts (compiler optimizer should > take care about overhead) and give each part a sane explanation. Alexander suggested moving the transformation to another place and it is correct in my opinion. All previous problems are now gone. But he also cut the code - he made a transformation for one group of "OR" expressions. I agree, some parts don't yet provide enough explanation of what's going on. I'm correcting this now. Speaking of the changes according to your suggestions, I made them in version 26 [0] and just part of that code will end up in the current version of the patch to process all groups of "OR" expressions. I'll try to do this as best I can, but it took me a while to figure out how to properly organize RestrictInfo in the index. [0] https://www.postgresql.org/message-id/3b9bb831-da52-4779-8f3e-f8b6b83ba41f%40postgrespro.ru [1] https://www.postgresql.org/message-id/CAPpHfdvhWE5pArZhgJeLViLx3-A3rxEREZvfkTj3E%3Dh7q-Bx9w%40mail.gmail.com -- Regards, Alena Rybakina Postgres Professional:http://www.postgrespro.com The Russian Postgres Company --------------0DiEz5qssC1Zb2RBiHFcZPXa Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit

Hi! Thank you for your contribution to this thread!

To be honest,I saw a larger problem. Look at the query bellow:

master:

alena@postgres=# create table t (a int not null, b int not null, c int not null);
insert into t (select 1, 1, i from generate_series(1,10000) i);
insert into t (select i, 2, 2 from generate_series(1,10000) i);
create index t_a_b_idx on t (a, b);
create statistics t_a_b_stat (mcv) on a, b from t;
create statistics t_b_c_stat (mcv) on b, c from t;
vacuum analyze t;
CREATE TABLE
INSERT 0 10000
INSERT 0 10000
CREATE INDEX
CREATE STATISTICS
CREATE STATISTICS
VACUUM
alena@postgres=# explain select * from t where a = 1 and (b = 1 or b = 2) and c = 2;
                                  QUERY PLAN                                  
------------------------------------------------------------------------------
 Bitmap Heap Scan on t  (cost=156.55..465.57 rows=5001 width=12)
   Recheck Cond: (a = 1)
   Filter: ((c = 2) AND ((b = 1) OR (b = 2)))
   ->  Bitmap Index Scan on t_a_b_idx  (cost=0.00..155.29 rows=10001 width=0)
         Index Cond: (a = 1)
(5 rows)


The query plan if v26[0] and v27[1] versions are equal and wrong in my opinion -where is c=2 expression?

v27 [1]
alena@postgres=# explain select * from t where a = 1 and (b = 1 or b = 2) and c = 2;
                                  QUERY PLAN                                  
------------------------------------------------------------------------------
 Bitmap Heap Scan on t  (cost=165.85..474.87 rows=5001 width=12)
   Recheck Cond: ((a = 1) AND (b = ANY ('{1,2}'::integer[])))
   Filter: (c = 2)
   ->  Bitmap Index Scan on t_a_b_idx  (cost=0.00..164.59 rows=10001 width=0)
         Index Cond: ((a = 1) AND (b = ANY ('{1,2}'::integer[])))
(5 rows)
v26 [0]
alena@postgres=# explain select * from t where a = 1 and (b = 1 or b = 2) and c = 2;
                                  QUERY PLAN                                  
------------------------------------------------------------------------------
 Bitmap Heap Scan on t  (cost=165.85..449.86 rows=5001 width=12)
   Recheck Cond: ((a = 1) AND (b = ANY ('{1,2}'::integer[])))
   Filter: (c = 2)
   ->  Bitmap Index Scan on t_a_b_idx  (cost=0.00..164.59 rows=10001 width=0)
         Index Cond: ((a = 1) AND (b = ANY ('{1,2}'::integer[])))
(5 rows)


In addition, I noticed that the ANY expression will be formed only for first group and ignore for others, like in the sample bellow:

v26 version [0]:

alena@postgres=# explain select * from t where (b = 1 or b = 2) and (a = 2 or a=3);
                                    QUERY PLAN                                     
-----------------------------------------------------------------------------------
 Index Scan using t_a_b_idx on t  (cost=0.29..24.75 rows=2 width=12)
   Index Cond: ((a = ANY ('{2,3}'::integer[])) AND (b = ANY ('{1,2}'::integer[])))
(2 rows)

v27 version [1]:

alena@postgres=# explain select * from t where (b = 1 or b = 2 or a = 2 or a=3);
                       QUERY PLAN                       
--------------------------------------------------------
 Seq Scan on t  (cost=0.00..509.00 rows=14999 width=12)
   Filter: ((b = 1) OR (b = 2) OR (a = 2) OR (a = 3))
(2 rows)


alena@postgres=# create index a_idx on t(a);
CREATE INDEX
alena@postgres=# create index b_idx on t(b);
CREATE INDEX
alena@postgres=# analyze;
ANALYZE

v26:

alena@postgres=# explain select * from t where (b = 1 or b = 2 or a = 2 or a=3);
                                     QUERY PLAN                                     
------------------------------------------------------------------------------------
 Bitmap Heap Scan on t  (cost=17.18..30.94 rows=4 width=12)
   Recheck Cond: ((a = ANY ('{2,3}'::integer[])) OR (a = ANY ('{2,3}'::integer[])))
   ->  BitmapOr  (cost=17.18..17.18 rows=4 width=0)
         ->  Bitmap Index Scan on a_idx  (cost=0.00..8.59 rows=2 width=0)
               Index Cond: (a = ANY ('{2,3}'::integer[]))
         ->  Bitmap Index Scan on a_idx  (cost=0.00..8.59 rows=2 width=0)
               Index Cond: (a = ANY ('{2,3}'::integer[]))
(7 rows)

v27:

alena@postgres=# explain select * from t where (b = 1 or b = 2 or a = 2 or a=3);
                       QUERY PLAN                       
--------------------------------------------------------
 Seq Scan on t  (cost=0.00..509.00 rows=14999 width=12)
   Filter: ((b = 1) OR (b = 2) OR (a = 2) OR (a = 3))
(2 rows)

The behavior in version 26 is incorrect, but in version 27, it does not select anything other than seqscan

Since Thursday I have been trying to add the code forming groups of identical "OR" expressions, as in version 26. I'm currently debugging errors.

On 21.07.2024 11:17, Nikolay Shaplov wrote:
В письме от среда, 17 июля 2024 г. 22:36:19 MSK пользователь Alexander 
Korotkov написал:

Hi All!

I am continue reading the patch, now it's newer version

First main question:

As far a I can get, the entry point for OR->ANY convertation have been moved 
to match_clause_to_indexcol funtion, that checks if some restriction can use 
index for performance.

The thing I do not understand what match_clause_to_indexcol actually received 
as arguments. Should this be set of expressions  with OR in between grouped by 
one of the expression argument?

If not I do not understand how this ever should work.
 The point is that we do the transformation for those columns that have an index, since this transformation is most useful in these cases. we pass the parameters index relation and column number to find out information about it. 

The rest is about code readability


+	if (bms_is_member(index->rel->relid, rinfo->right_relids))
+		return NULL;
To be honest, I'm not sure that I understand your question. Could you explain me?
This check it totally not obvious for person who is not deep into postgres 
code. There should go comment explaining what are we checking for, and why it 
does not suit our purposes



+	foreach(lc, orclause->args)
+	{
I'll add it, thank you.
Being no great expert in postgres code, I am confused what are we iterating on 
here? Two arguments of OR statement? (a>1) OR (b>2) those in brackets? Or 
what? Comment explaining that would be a great help here.



+if (sub_rinfo->is_pushed_down != rinfo->is_pushed_down ||
+	sub_rinfo->is_clone != rinfo->is_clone ||
+	sub_rinfo->security_level != rinfo->security_level ||
+	!bms_equal(sub_rinfo->required_relids, rinfo->required_relids) ||
+	!bms_equal(sub_rinfo->incompatible_relids, rinfo- 

incompatible_relids) ||

+	!bms_equal(sub_rinfo->outer_relids, rinfo->outer_relids))
+	{
I'll add it.
This check it totally mind-blowing... What in the name of existence is going 
on here?

I would suggest  to split these checks into parts (compiler optimizer should 
take care about overhead)  and give each part a sane explanation.

Alexander suggested moving the transformation to another place and it is correct in my opinion. All previous problems are now gone.
But he also cut the code - he made a transformation for one group of "OR" expressions. I agree, some parts don't yet
provide enough explanation of what's going on. I'm correcting this now. 

Speaking of the changes according to your suggestions, I made them in version 26 [0] and just part of that code will end up in the current version of the patch to process all groups of "OR" expressions.

I'll try to do this as best I can, but it took me a while to figure out how to properly organize RestrictInfo in the index.

[0] https://www.postgresql.org/message-id/3b9bb831-da52-4779-8f3e-f8b6b83ba41f%40postgrespro.ru

[1] https://www.postgresql.org/message-id/CAPpHfdvhWE5pArZhgJeLViLx3-A3rxEREZvfkTj3E%3Dh7q-Bx9w%40mail.gmail.com 

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