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 1sMFMY-001Jyj-Un for pgsql-hackers@arkaria.postgresql.org; Tue, 25 Jun 2024 23:14:11 +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 1sMFMW-000tvY-8h for pgsql-hackers@arkaria.postgresql.org; Tue, 25 Jun 2024 23:14:08 +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 1sMFMV-000tvQ-Gl for pgsql-hackers@lists.postgresql.org; Tue, 25 Jun 2024 23:14:08 +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 1sMFMR-00384j-GB for pgsql-hackers@postgresql.org; Tue, 25 Jun 2024 23:14:06 +0000 Received: from [192.168.253.77] (unknown [176.59.15.8]) (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 1F38DE210A5; Wed, 26 Jun 2024 02:13:58 +0300 (MSK) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=postgrespro.ru; s=mx2023; t=1719357239; bh=juXf/rg5wtLkDNTIwjeEO6Fncx99YqiE7/U1raKx9iA=; h=Message-ID:Date:User-Agent:Subject:To:Cc:References:From: In-Reply-To:From; b=P++IBdJGzyd2sygBMg2ZdXACdl7BbLQ7SsK8suI4ZZqiUrzP+zmFchIm1iN5ehRln Z+eJmOL2Zozg4xxv6ZusZ78ir1tGfyvt6kRPTR12x6KDd04LpP3cxJzpZ2ZgEC6032 67LJfXf3dAXnIvj9irxzr2VI3K4OZHHBEBWGJkmngxcxv/SgqcWR7EMJhRTI2bmXqX CC2Al5zyx7l8rS2kybJ80ncbI26wWCi0VlVknaMjxi7XHbPn/8dI/dD1ySF9qoMvrp 2WplzljxChaLudQYZ7vv85+YvyGDN+zukHJ503gJbz9lpczt0z5LaNi7mYtrZywPhZ +Cp6gYwfZAQdA== Content-Type: multipart/alternative; boundary="------------wsrqvayxCgEWGrDsBm2pf262" Message-ID: Date: Wed, 26 Jun 2024 02:13:53 +0300 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: POC, WIP: OR-clause support for indexes To: Robert Haas , Peter Geoghegan Cc: Alexander Korotkov , jian he , pgsql-hackers@postgresql.org, Marcos Pegoraro , teodor@sigaev.ru, Andrei Lepikhov , Tomas Vondra , Peter Eisentraut , Ranier Vilela References: <567ED6CA.2040504@sigaev.ru> <6850c306-4e9d-40b7-8096-1f3c7d29cd9e@postgrespro.ru> <0f50882c-e639-4856-aab6-6ccfec848164@postgrespro.ru> Content-Language: en-US From: Alena Rybakina In-Reply-To: X-KSMG-AntiPhishing: NotDetected, bases: 2024/06/25 20:50: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/25 21:37:00 #25712080 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. --------------wsrqvayxCgEWGrDsBm2pf262 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit On 24.06.2024 18:28, Robert Haas wrote: > On Fri, Jun 21, 2024 at 6:52 PM Alena Rybakina > wrote: >> It's hard to tell, but I think it might be one of the good places to apply transformation. Let me describe a brief conclusion on the two approaches. > This explanation is somewhat difficult for me to follow. For example: > >> In the first approach, we definitely did not process the extra "OR" expressions in the first approach, since they were packaged as an Array. It could lead to the fact that less planning time would be spent on the optimizer. > I don't know what the "first approach" refers to, or what processing > the extra "OR" expressions means, or what it would mean to package OR > expressions as an array. If you made them into an SAOP then you'd have > an array*instead of* OR expressions, not OR expressions "packaged as > an array" but even then, they'd still be processed somewhere, unless > the patch was just wrong. > > I think you should try writing this summary again and see if you can > make it a lot clearer and more precise. > > I'm suspicious based that we should actually be postponing the > transformation even further. If, for example, the transformation is > advantageous for index scans and disadvantageous for bitmap scans, or > the other way around, then this approach can't help much: it either > does the transformation and all scan types are affected, or it doesn't > do it and no scan types are affected. But if you decided for each scan > whether to transform the quals, then you could handle that. Against > that, there might be increased planning cost. But, perhaps that could > be avoided somehow. Sorry, you are right and I'll try to explain more precisely. The firstapproach isthefirstpartof the patch,wherewemade "Or" expressions into an SAOPatan earlystageof plangeneration[0],the secondonewasthe one proposedby A.Korotkov[1]. So, when we made "OR" expressions into an SAOPat the post-parsing stage of the plan generation [0], we definitely did not process the redundantexpressions"OR" expressions there (for example,duplicates), since they were transformed to SAOP expression. Furthermore, the list of OR expressions can be significantly reduced, since constants belonging to the same predicate will already be converted into an SAOP expression. I assume this may reduce planning time, as I know several places in the optimizer where these lists of "OR" expressions are scanned several times. Also the selectivity for SAOP expressions is estimated better, which could lead to the generation of a more optimal plan, but, to be honest, this is just an observation from changes in regression tests and, in general, how the process of calculating the selectivity of a complex expression works. And I think it needs further consideration. SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE (a = 1 OR a = 51) AND b = ''1'''); estimated | actual -----------+-------- - 99 | 100 + 100 | 100 (1 row) SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE (a = 1 OR a = 51) AND (b = ''1'' OR b = ''2'')'); estimated | actual -----------+-------- - 99 | 100 + 100 | 100 (1 row) SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE (a = 1 OR a = 2 OR a = 51 OR a = 52) AND (b = ''1'' OR b = ''2'')'); estimated | actual -----------+-------- - 197 | 200 + 200 | 200 Speaking of the main disadvantages, we do not give the optimizer the opportunity to generate a plan using BitmapScan, which can lead to the generation of a suboptimal plan, but in the current approach the same thing happens [2]. And you mentioned about it before: On 24.06.2024 18:28, Robert Haas wrote: > I'm suspicious based that we should actually be postponing the > transformation even further. If, for example, the transformation is > advantageous for index scans and disadvantageous for bitmap scans, or > the other way around, then this approach can't help much: it either > does the transformation and all scan types are affected, or it doesn't > do it and no scan types are affected. But if you decided for each scan > whether to transform the quals, then you could handle that. Against > that, there might be increased planning cost. But, perhaps that could > be avoided somehow. Andrei mentioned the problem, which might be caused by the transformation on the later stage of optimization is updating references to expressions in RestrictInfo [3] lists, because they can be used in different parts during the formation of the query plan. As the practice of Self-join removal [4] has shown, this can be expensive, but feasible. By applying the transformation at the analysis stage [0], because no links were created, so we did not encounter such problems, so this approach was more suitable than the others. If some things were not clear enough, let me know. [0] https://www.postgresql.org/message-id/attachment/156971/v21-0001-Transform-OR-clauses-to-ANY-expression.patch [1] https://www.postgresql.org/message-id/CAPpHfduah1PLzajBJFDmp7%2BMZuaWYpie2p%2BGsV0r03fcGghQ-g%40mail.gmail.com [2] https://www.postgresql.org/message-id/7d5aed92-d4cc-4b76-8ae0-051d182c9eec%40postgrespro.ru [3] https://www.postgresql.org/message-id/6850c306-4e9d-40b7-8096-1f3c7d29cd9e%40postgrespro.ru [4] https://commitfest.postgresql.org/48/5043/ On 24.06.2024 18:28, Robert Haas wrote: > The alternative that should be considered is not combining things if > the types don't match. If we're going to combine such things, we need > to be absolutely certain that type conversion cannot fail. Peter,Robert,thanksforthe detaileddiscussion,I realizedthathereyou needto lookcarefullyatthe patch. In general, it comes out, I need to pay attention and highlight the cases where POLA violation occurs On 24.06.2024 18:28, Robert Haas wrote: > One reason is that it is extra work to convert things to a name and > then back to an OID. It's got to be slower than using the OID you > already have. > > The other reason is that it's error-prone. If somehow the second > lookup doesn't produce the same OID as the first lookup, bad things > will happen, possibly including security vulnerabilities. I see you've > taken steps to avoid that, like nailing down the schema, and that's > good, but it's not a good enough reason to do it like this. If we > don't have a function that can construct the node we need with the OID > rather than the name as an argument, we should invent one, not do this > sort of thing. I understood. I'll try to fix it. --------------wsrqvayxCgEWGrDsBm2pf262 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit
On 24.06.2024 18:28, Robert Haas wrote:
On Fri, Jun 21, 2024 at 6:52 PM Alena Rybakina
<a.rybakina@postgrespro.ru> wrote:

It's hard to tell, but I think it might be one of the good places to apply transformation. Let me describe a brief conclusion on the two approaches.

This explanation is somewhat difficult for me to follow. For example:


In the first approach, we definitely did not process the extra "OR" expressions in the first approach, since they were packaged as an Array. It could lead to the fact that less planning time would be spent on the optimizer.

I don't know what the "first approach" refers to, or what processing
the extra "OR" expressions means, or what it would mean to package OR
expressions as an array. If you made them into an SAOP then you'd have
an array *instead of* OR expressions, not OR expressions "packaged as
an array" but even then, they'd still be processed somewhere, unless
the patch was just wrong.

I think you should try writing this summary again and see if you can
make it a lot clearer and more precise.

I'm suspicious based that we should actually be postponing the
transformation even further. If, for example, the transformation is
advantageous for index scans and disadvantageous for bitmap scans, or
the other way around, then this approach can't help much: it either
does the transformation and all scan types are affected, or it doesn't
do it and no scan types are affected. But if you decided for each scan
whether to transform the quals, then you could handle that. Against
that, there might be increased planning cost. But, perhaps that could
be avoided somehow.

Sorry, you are right and I'll try to explain more precisely. The first approach is the first part of the patch, where we made "Or" expressions into an SAOP at an early stage of plan generation [0], the second one was the one proposed by A.Korotkov [1].

So, when we made "OR" expressions into an SAOP at the post-parsing stage of the plan generation [0], we definitely did not process the redundant expressions "OR" expressions there (for example, duplicates), since they were transformed to SAOP expression. Furthermore, the list of OR expressions can be significantly reduced, since constants belonging to the same predicate will already be converted into an SAOP expression. I assume this may reduce planning time, as I know several places in the optimizer where these lists of "OR" expressions are scanned several times.
Also the selectivity for SAOP expressions is estimated better, which could lead to the generation of a more optimal plan, but, to be honest, this is just an observation from changes in regression tests and, in general, how the process of calculating the selectivity of a complex expression works. And I think it needs further consideration. SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE (a = 1 OR a = 51) AND b = ''1'''); estimated | actual -----------+-------- - 99 | 100 + 100 | 100 (1 row) SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE (a = 1 OR a = 51) AND (b = ''1'' OR b = ''2'')'); estimated | actual -----------+-------- - 99 | 100 + 100 | 100 (1 row) SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE (a = 1 OR a = 2 OR a = 51 OR a = 52) AND (b = ''1'' OR b = ''2'')'); estimated | actual -----------+-------- - 197 | 200 + 200 | 200 Speaking of the main disadvantages, we do not give the optimizer the opportunity to generate a plan using BitmapScan, which can lead to the generation of a suboptimal plan, but in the current approach the same thing happens [2]. And you mentioned about it before:

On 24.06.2024 18:28, Robert Haas wrote:
I'm suspicious based that we should actually be postponing the
transformation even further. If, for example, the transformation is
advantageous for index scans and disadvantageous for bitmap scans, or
the other way around, then this approach can't help much: it either
does the transformation and all scan types are affected, or it doesn't
do it and no scan types are affected. But if you decided for each scan
whether to transform the quals, then you could handle that. Against
that, there might be increased planning cost. But, perhaps that could
be avoided somehow.

Andrei mentioned the problem, which might be caused by the transformation on the later stage of optimization is updating references to expressions in RestrictInfo [3] lists, because they can be used in different parts during the formation of the query plan. As the practice of Self-join removal [4] has shown, this can be expensive, but feasible. By applying the transformation at the analysis stage [0], because no links were created, so we did not encounter such problems, so this approach was more suitable than the others.

If some things were not clear enough, let me know.

[0] https://www.postgresql.org/message-id/attachment/156971/v21-0001-Transform-OR-clauses-to-ANY-expression.patch [1] https://www.postgresql.org/message-id/CAPpHfduah1PLzajBJFDmp7%2BMZuaWYpie2p%2BGsV0r03fcGghQ-g%40mail.gmail.com [2] https://www.postgresql.org/message-id/7d5aed92-d4cc-4b76-8ae0-051d182c9eec%40postgrespro.ru [3] https://www.postgresql.org/message-id/6850c306-4e9d-40b7-8096-1f3c7d29cd9e%40postgrespro.ru [4] https://commitfest.postgresql.org/48/5043/

On 24.06.2024 18:28, Robert Haas wrote:
The alternative that should be considered is not combining things if
the types don't match. If we're going to combine such things, we need
to be absolutely certain that type conversion cannot fail.

Peter, Robert, thanks for the detailed discussion, I realized that here you need to look carefully at the patch. In general, it comes out, I need to pay attention and highlight the cases where POLA violation occurs

On 24.06.2024 18:28, Robert Haas wrote:
One reason is that it is extra work to convert things to a name and
then back to an OID. It's got to be slower than using the OID you
already have.

The other reason is that it's error-prone. If somehow the second
lookup doesn't produce the same OID as the first lookup, bad things
will happen, possibly including security vulnerabilities. I see you've
taken steps to avoid that, like nailing down the schema, and that's
good, but it's not a good enough reason to do it like this. If we
don't have a function that can construct the node we need with the OID
rather than the name as an argument, we should invent one, not do this
sort of thing.

I understood. I'll try to fix it.


--------------wsrqvayxCgEWGrDsBm2pf262--