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 1tev2W-00GN4Z-GA for pgsql-hackers@arkaria.postgresql.org; Mon, 03 Feb 2025 11:54:57 +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 1tev2V-00CtaZ-4g for pgsql-hackers@arkaria.postgresql.org; Mon, 03 Feb 2025 11:54:55 +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 1tev2U-00CtaK-IO for pgsql-hackers@lists.postgresql.org; Mon, 03 Feb 2025 11:54:54 +0000 Received: from mail.postgrespro.ru ([93.174.131.139]) by makus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.96) (envelope-from ) id 1tev2P-002wL6-2N for pgsql-hackers@postgresql.org; Mon, 03 Feb 2025 11:54:53 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=postgrespro.ru; s=mx2023; t=1738583687; bh=dl8EGAWprP5RaxPfkCl5t/L+34cIW+Frx7+w16XFkgE=; h=Message-ID:Date:User-Agent:Subject:To:Cc:References:From: In-Reply-To:From; b=5xLkTDZSB6v9Lg9qjSltuMEO74P9LCSoDll/V0t4MoikL2eqoonzFOUvbzQIxn0NQ CoEJXwASVH0ccPipC9IA9B+kHge0CCW4U0P/ti+xm18hIS3H5ORscJO9Z+mj1yCf26 8HeP+crOpuTDiEfxhpXlw6mxEYE61D/bBydMXM2Oe+wJpeiND2dXwLdEAMO6fQCz7P tMMUeWw/cwQbpkEKQm8fKd3zXd9FlGSrQjSN8Kcoph/q9M6y5tMwZ7Y7okrI3OXYbK /ZzR3kK9z5sRbB+c4GTm7UFUaNUhcxy4fkIioPUFnJHFamko2XhFVbKFqglKclgIIj KknFOaTQyl/lw== Received: from [10.4.12.74] (unknown [93.174.131.141]) (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 5903D60729; Mon, 3 Feb 2025 14:54:47 +0300 (MSK) Content-Type: multipart/alternative; boundary="------------PLnEt4kumNJj43REZXrYVSOH" Message-ID: <1a4f1631-86c1-4185-a520-03b24a389449@postgrespro.ru> Date: Mon, 3 Feb 2025 14:54:47 +0300 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: POC, WIP: OR-clause support for indexes To: Alexander Korotkov Cc: Ranier Vilela , Alexander Lakhin , jian he , Robert Haas , Nikolay Shaplov , pgsql-hackers@lists.postgresql.org, pgsql-hackers@postgresql.org, Peter Geoghegan , Marcos Pegoraro , teodor@sigaev.ru, Peter Eisentraut , Andrei Lepikhov References: <567ED6CA.2040504@sigaev.ru> <8174de69-9e1a-0827-0e81-ef97f56a5939@gmail.com> <3b717020-14d9-425f-8c60-ce336b5a23b3@postgrespro.ru> <43db6a40-5c5f-4909-ad62-3060b297e686@postgrespro.ru> <41ba3d47-2a48-476c-88d4-6ebd889a7af2@gmail.com> <036d64e6-4d47-485c-b047-6664d452b3e8@postgrespro.ru> Content-Language: en-US From: Alena Rybakina In-Reply-To: X-KSMG-AntiPhishing: NotDetected, bases: 2025/02/03 09:42: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: 2025/02/03 07:33:00 #27201296 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. --------------PLnEt4kumNJj43REZXrYVSOH Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit On 03.02.2025 14:32, Alexander Korotkov wrote: > On Mon, Feb 3, 2025 at 12:22 PM Alena Rybakina > wrote: >> Thank you for updated version! I agree for your version of the code. >> >> On 02.02.2025 21:00, Alexander Korotkov wrote: >> >> On Fri, Jan 31, 2025 at 4:31 PM Alena Rybakina >> wrote: >> >> I started reviewing at the patch and saw some output "ERROR" in the output of the test and is it okay here? >> >> SELECT * FROM tenk1 t1 >> WHERE t1.thousand = 42 OR t1.thousand = (SELECT t2.tenthous FROM tenk1 t2 WHERE t2.thousand = t1.tenthous); >> ERROR: more than one row returned by a subquery used as an expression >> >> The output is correct for this query. But the query is very >> unfortunate for the regression test. I've revised query in the v47 >> revision [1]. >> >> Links. >> 1.https://www.postgresql.org/message-id/CAPpHfdsBZmNt9qUoJBqsQFiVDX1%3DyCKpuVAt1YnR7JCpP%3Dk8%2BA%40mail.gmail.com >> >> While analyzing the modified query plan from the regression test, I noticed that despite using a full seqscan for table t2 in the original plan, >> its results are cached by Materialize node, and this can significantly speed up the execution of the NestedLoop algorithm. >> >> For example, after running the query several times, I got results that show that the query execution time was twice as bad. >> >> Original plan: >> >> EXPLAIN ANALYZE SELECT * FROM bitmap_split_or t1, bitmap_split_or t2 WHERE t1.a=t2.b OR t1.a=1; QUERY PLAN -------------------------------------------------------------------------------------------------------------------------------- Nested Loop (cost=0.00..70067.00 rows=2502499 width=24) (actual time=0.015..1123.247 rows=2003000 loops=1) Join Filter: ((t1.a = t2.b) OR (t1.a = 1)) Rows Removed by Join Filter: 1997000 Buffers: shared hit=22 -> Seq Scan on bitmap_split_or t1 (cost=0.00..31.00 rows=2000 width=12) (actual time=0.006..0.372 rows=2000 loops=1) Buffers: shared hit=11 -> Materialize (cost=0.00..41.00 rows=2000 width=12) (actual time=0.000..0.111 rows=2000 loops=2000) Storage: Memory Maximum Storage: 110kB Buffers: shared hit=11 -> Seq Scan on bitmap_split_or t2 (cost=0.00..31.00 rows=2000 width=12) (actual time=0.003..0.188 rows=2000 loops=1) Buffers: shared hit=11 Planning Time: 0.118 ms Execution Time: 1204.874 ms (13 rows) >> >> Query plan after the patch: >> >> EXPLAIN ANALYZE SELECT * FROM bitmap_split_or t1, bitmap_split_or t2 WHERE t1.a=t2.b OR t1.a=1; QUERY PLAN ----------------------------------------------------------------------------------------------------------------------------------------------- Nested Loop (cost=0.28..56369.00 rows=2502499 width=24) (actual time=0.121..2126.606 rows=2003000 loops=1) Buffers: shared hit=16009 read=2 -> Seq Scan on bitmap_split_or t2 (cost=0.00..31.00 rows=2000 width=12) (actual time=0.017..0.652 rows=2000 loops=1) Buffers: shared hit=11 -> Index Scan using t_a_b_idx on bitmap_split_or t1 (cost=0.28..18.15 rows=1002 width=12) (actual time=0.044..0.627 rows=1002 loops=2000) Index Cond: (a = ANY (ARRAY[t2.b, 1])) Buffers: shared hit=15998 read=2 Planning Time: 0.282 ms Execution Time: 2344.367 ms (9 rows) >> >> I'm afraid that we may lose this with this optimization. Maybe this can be taken into account somehow, what do you think? > The important aspect is that the second plan have lower cost than the > first one. So, that's the question to the cost model. The patch just > lets optimizer consider more comprehensive plurality of paths. You > can let optimizer select the first plan by tuning *_cost params. For > example, setting cpu_index_tuple_cost = 0.02 makes first plan win for > me. > > Other than that the test query is quite unfortunate as t1.a=1 is very > frequent. I've adjusted the query so that nested loop with index scan > wins both in cost and execution time. > > I've also adjusted another test query as proposed by Andrei. > > I'm going to push this patch is there is no more notes. > > Links. > 1.https://www.postgresql.org/message-id/fc1017ca-877b-4f86-b491-154cf123eedd%40gmail.com > Okay.I agree with your codeand have no more notes -- Regards, Alena Rybakina Postgres Professional --------------PLnEt4kumNJj43REZXrYVSOH Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit


On 03.02.2025 14:32, Alexander Korotkov wrote:
On Mon, Feb 3, 2025 at 12:22 PM Alena Rybakina
<a.rybakina@postgrespro.ru> wrote:

Thank you for updated version! I agree for your version of the code.

On 02.02.2025 21:00, Alexander Korotkov wrote:

On Fri, Jan 31, 2025 at 4:31 PM Alena Rybakina
<a.rybakina@postgrespro.ru> wrote:

I started reviewing at the patch and saw some output "ERROR" in the output of the test and is it okay here?

SELECT * FROM tenk1 t1
WHERE t1.thousand = 42 OR t1.thousand = (SELECT t2.tenthous FROM tenk1 t2 WHERE t2.thousand = t1.tenthous);
ERROR: more than one row returned by a subquery used as an expression

The output is correct for this query.  But the query is very
unfortunate for the regression test.  I've revised query in the v47
revision [1].

Links.
1. https://www.postgresql.org/message-id/CAPpHfdsBZmNt9qUoJBqsQFiVDX1%3DyCKpuVAt1YnR7JCpP%3Dk8%2BA%40mail.gmail.com

While analyzing the modified query plan from the regression test, I noticed that despite using a full seqscan for table t2 in the original plan,
its results are cached by Materialize node, and this can significantly speed up the execution of the NestedLoop algorithm.

For example, after running the query several times, I got results that show that the query execution time was twice as bad.

Original plan:

EXPLAIN ANALYZE SELECT * FROM bitmap_split_or t1, bitmap_split_or t2 WHERE t1.a=t2.b OR t1.a=1; QUERY PLAN -------------------------------------------------------------------------------------------------------------------------------- Nested Loop (cost=0.00..70067.00 rows=2502499 width=24) (actual time=0.015..1123.247 rows=2003000 loops=1) Join Filter: ((t1.a = t2.b) OR (t1.a = 1)) Rows Removed by Join Filter: 1997000 Buffers: shared hit=22 -> Seq Scan on bitmap_split_or t1 (cost=0.00..31.00 rows=2000 width=12) (actual time=0.006..0.372 rows=2000 loops=1) Buffers: shared hit=11 -> Materialize (cost=0.00..41.00 rows=2000 width=12) (actual time=0.000..0.111 rows=2000 loops=2000) Storage: Memory Maximum Storage: 110kB Buffers: shared hit=11 -> Seq Scan on bitmap_split_or t2 (cost=0.00..31.00 rows=2000 width=12) (actual time=0.003..0.188 rows=2000 loops=1) Buffers: shared hit=11 Planning Time: 0.118 ms Execution Time: 1204.874 ms (13 rows)

Query plan after the patch:

EXPLAIN ANALYZE SELECT * FROM bitmap_split_or t1, bitmap_split_or t2 WHERE t1.a=t2.b OR t1.a=1; QUERY PLAN ----------------------------------------------------------------------------------------------------------------------------------------------- Nested Loop (cost=0.28..56369.00 rows=2502499 width=24) (actual time=0.121..2126.606 rows=2003000 loops=1) Buffers: shared hit=16009 read=2 -> Seq Scan on bitmap_split_or t2 (cost=0.00..31.00 rows=2000 width=12) (actual time=0.017..0.652 rows=2000 loops=1) Buffers: shared hit=11 -> Index Scan using t_a_b_idx on bitmap_split_or t1 (cost=0.28..18.15 rows=1002 width=12) (actual time=0.044..0.627 rows=1002 loops=2000) Index Cond: (a = ANY (ARRAY[t2.b, 1])) Buffers: shared hit=15998 read=2 Planning Time: 0.282 ms Execution Time: 2344.367 ms (9 rows)

I'm afraid that we may lose this with this optimization. Maybe this can be taken into account somehow, what do you think?

The important aspect is that the second plan have lower cost than the
first one.  So, that's the question to the cost model.  The patch just
lets optimizer consider more comprehensive plurality of paths.  You
can let optimizer select the first plan by tuning *_cost params.  For
example, setting cpu_index_tuple_cost = 0.02 makes first plan win for
me.

Other than that the test query is quite unfortunate as t1.a=1 is very
frequent. I've adjusted the query so that nested loop with index scan
wins both in cost and execution time.

I've also adjusted another test query as proposed by Andrei.

I'm going to push this patch is there is no more notes.

Links.
1. https://www.postgresql.org/message-id/fc1017ca-877b-4f86-b491-154cf123eedd%40gmail.com

Okay.I agree with your code and have no more notes 

-- 
Regards,
Alena Rybakina
Postgres Professional
--------------PLnEt4kumNJj43REZXrYVSOH--