From: Andrei Lepikhov <a.lepikhov@postgrespro.ru>
To: Alexander Korotkov <aekorotkov@gmail.com>
Cc: Gregory Stark (as CFM) <stark.cfm@gmail.com>
Cc: Michał Kłeczek <michal@kleczek.org>
Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Subject: Re: Removing unneeded self joins
Date: Mon, 16 Oct 2023 15:28:13 +0700
Message-ID: <8800ccf2-ae82-461c-92a1-d4c0a22f8cf2@postgrespro.ru> (raw)
In-Reply-To: <CAPpHfdsQkY0Gu7bQ9Ekdyzo_5Xxz74TYKbwmk1on1WAASpxXcQ@mail.gmail.com>
References: <64486b0b-0404-e39e-322d-0801154901f3@postgrespro.ru>
<CALNJ-vTyL-LpvSOPZxpC63Et3LJLUAFZSfRqGEhT5Rj7_EEj7w@mail.gmail.com>
<0fd15c10-eaa5-51bd-b5c7-e635fe03a94d@postgrespro.ru>
<d9493d5a-b950-465e-f09b-62c92a23fba1@postgrespro.ru>
<20221206184643.zya44h5auv6f45zp@awork3.anarazel.de>
<36579124-f9d9-a51e-38b3-af3511921c7e@postgrespro.ru>
<88079CBD-B5BB-4C61-A68B-A8C67599E1C7@kleczek.org>
<CAM-w4HMZXW+hKc8C+WLQ+gdpEkoh9378a2UGKyZRz7mZVerG+Q@mail.gmail.com>
<c97574c4-13e6-9107-26ab-af2bd626fc85@postgrespro.ru>
<bcf2f3c5-fbdc-f85b-af3e-ebec616160f6@postgrespro.ru>
<05469e80-454b-41d7-d04f-421f42bbd4a9@postgrespro.ru>
<CAPpHfdt9G3EU+vXuqexhweEQoMF-acPUUFuB6hV2Kg0gCy7AjA@mail.gmail.com>
<ebe66358-428c-439f-85dd-da72c9b2b0c2@postgrespro.ru>
<CAPpHfdt-0kVV7O==aJEbjY2iGYBu+XBzTHEbPv_6sVNeC7fffQ@mail.gmail.com>
<48c11b23-9c23-440e-9a3c-020e05196449@postgrespro.ru>
<CAPpHfdsQkY0Gu7bQ9Ekdyzo_5Xxz74TYKbwmk1on1WAASpxXcQ@mail.gmail.com>
On 12/10/2023 18:32, Alexander Korotkov wrote:
> On Thu, Oct 5, 2023 at 12:17 PM Andrei Lepikhov
> <a.lepikhov@postgrespro.ru> wrote:
>> On 4/10/2023 14:34, Alexander Korotkov wrote:
>>> > Relid replacement machinery is the most contradictory code here. We used
>>> > a utilitarian approach and implemented a simplistic variant.
>>>
>>> > > 2) It would be nice to skip the insertion of IS NOT NULL checks when
>>> > > they are not necessary. [1] points that infrastructure from [2] might
>>> > > be useful. The patchset from [2] seems committed mow. However, I
>>> > > can't see it is directly helpful in this matter. Could we just skip
>>> > > adding IS NOT NULL clause for the columns, that have
>>> > > pg_attribute.attnotnull set?
>>> > Thanks for the links, I will look into that case.
>> To be more precise, in the attachment, you can find a diff to the main
>> patch, which shows the volume of changes to achieve the desired behaviour.
>> Some explains in regression tests shifted. So, I've made additional tests:
>>
>> DROP TABLE test CASCADE;
>> CREATE TABLE test (a int, b int not null);
>> CREATE UNIQUE INDEX abc ON test(b);
>> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a)
>> WHERE t1.b=t2.b;
>> CREATE UNIQUE INDEX abc1 ON test(a,b);
>> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a)
>> WHERE t1.b=t2.b;
>> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a)
>> WHERE t1.b=t2.b AND (t1.a=t2.a OR t2.a=t1.a);
>> DROP INDEX abc1;
>> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a)
>> WHERE t1.b=t2.b AND (t1.b=t2.b OR t2.b=t1.b);
>>
>> We have almost the results we wanted to have. But in the last explain
>> you can see that nothing happened with the OR clause. We should use the
>> expression mutator instead of walker to handle such clauses. But It
>> doesn't process the RestrictInfo node ... I'm inclined to put a solution
>> of this issue off for a while.
>
> OK. I think it doesn't worth to eliminate IS NULL quals with this
> complexity (at least at this stage of work).
>
> I made improvements over the code. Mostly new comments, grammar
> corrections of existing comments and small refactoring.
>
> Also, I found that the suggestion from David Rowley [1] to qsort
> array of relations to faster find duplicates is still unaddressed.
> I've implemented it. That helps to evade quadratic complexity with
> large number of relations.
>
> Also I've incorporated improvements from Alena Rybakina except one for
> skipping SJ removal when no SJ quals is found. It's not yet clear for
> me if this check fix some cases. But at least optimization got skipped
> in some useful cases (as you can see in regression tests).
I would like to propose one more minor improvement (see in attachment).
The idea here is that after removing a self-join and changing clauses we
should re-probe the set of relids with the same Oid, because we can find
more removable self-joins (see the demo test in join.sql).
--
regards,
Andrey Lepikhov
Postgres Professional
Attachments:iterative_elimination.diff (text/plain, 4.4K) downloaddiff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.cindex 7b8dc7a2b7..f7ccda5231 100644--- a/src/backend/optimizer/plan/analyzejoins.c+++ b/src/backend/optimizer/plan/analyzejoins.c@@ -2298,6 +2298,7 @@ remove_self_joins_recurse(PlannerInfo *root, List *joinlist, Relids toRemove)
{
/* Create group of relation indexes with the same oid */
Relids group = NULL;
+ Relids removed;
while (i < j)
{
@@ -2306,8 +2307,21 @@ remove_self_joins_recurse(PlannerInfo *root, List *joinlist, Relids toRemove)
}
relids = bms_del_members(relids, group);
- toRemove = bms_add_members(toRemove,- remove_self_joins_one_group(root, group));++ /*+ * Try to remove self-joins from a group of identical entries.+ * Make next attempt iteratively - if something is deleted from+ * a group, changes in clauses and equivalence classes can give+ * us a chance to find more candidates.+ */+ do {+ Assert(!bms_overlap(group, toRemove));+ removed = remove_self_joins_one_group(root, group);+ toRemove = bms_add_members(toRemove, removed);+ group = bms_del_members(group, removed);+ } while (!bms_is_empty(removed) &&+ bms_membership(group) == BMS_MULTIPLE);+ bms_free(removed);
bms_free(group);
}
else
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.outindex 12a90bd42e..cb2429645c 100644--- a/src/test/regress/expected/join.out+++ b/src/test/regress/expected/join.out@@ -6786,6 +6786,36 @@ SELECT * FROM emp1 e1, emp1 e2 WHERE e1.id = e2.id AND e2.code <> e1.code;
Filter: ((e2.id IS NOT NULL) AND (e2.code <> e2.code))
(3 rows)
+-- Shuffle self-joined relations. Only in the case of iterative deletion+-- attempts explains of these queries will be identical.+CREATE UNIQUE INDEX ON emp1((id*id));+explain SELECT count(*) FROM emp1 c1, emp1 c2, emp1 c3+WHERE c1.id=c2.id AND c1.id*c2.id=c3.id*c3.id;+ QUERY PLAN +-----------------------------------------------------------------+ Aggregate (cost=43.84..43.85 rows=1 width=8)+ -> Seq Scan on emp1 c3 (cost=0.00..38.25 rows=2237 width=0)+ Filter: ((id IS NOT NULL) AND ((id * id) IS NOT NULL))+(3 rows)++explain SELECT count(*) FROM emp1 c1, emp1 c2, emp1 c3+WHERE c1.id=c3.id AND c1.id*c3.id=c2.id*c2.id;+ QUERY PLAN +-----------------------------------------------------------------+ Aggregate (cost=43.84..43.85 rows=1 width=8)+ -> Seq Scan on emp1 c3 (cost=0.00..38.25 rows=2237 width=0)+ Filter: ((id IS NOT NULL) AND ((id * id) IS NOT NULL))+(3 rows)++explain SELECT count(*) FROM emp1 c1, emp1 c2, emp1 c3+WHERE c3.id=c2.id AND c3.id*c2.id=c1.id*c1.id;+ QUERY PLAN +-----------------------------------------------------------------+ Aggregate (cost=43.84..43.85 rows=1 width=8)+ -> Seq Scan on emp1 c3 (cost=0.00..38.25 rows=2237 width=0)+ Filter: ((id IS NOT NULL) AND ((id * id) IS NOT NULL))+(3 rows)+
-- We can remove the join even if we find the join can't duplicate rows and
-- the base quals of each side are different. In the following case we end up
-- moving quals over to s1 to make it so it can't match any rows.
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sqlindex 4d49c0767a..55147263ca 100644--- a/src/test/regress/sql/join.sql+++ b/src/test/regress/sql/join.sql@@ -2576,6 +2576,16 @@ CREATE TABLE emp1 ( id SERIAL PRIMARY KEY NOT NULL, code int);
explain (verbose, costs off)
SELECT * FROM emp1 e1, emp1 e2 WHERE e1.id = e2.id AND e2.code <> e1.code;
+-- Shuffle self-joined relations. Only in the case of iterative deletion+-- attempts explains of these queries will be identical.+CREATE UNIQUE INDEX ON emp1((id*id));+explain SELECT count(*) FROM emp1 c1, emp1 c2, emp1 c3+WHERE c1.id=c2.id AND c1.id*c2.id=c3.id*c3.id;+explain SELECT count(*) FROM emp1 c1, emp1 c2, emp1 c3+WHERE c1.id=c3.id AND c1.id*c3.id=c2.id*c2.id;+explain SELECT count(*) FROM emp1 c1, emp1 c2, emp1 c3+WHERE c3.id=c2.id AND c3.id*c2.id=c1.id*c1.id;+
-- We can remove the join even if we find the join can't duplicate rows and
-- the base quals of each side are different. In the following case we end up
-- moving quals over to s1 to make it so it can't match any rows.
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: a.lepikhov@postgrespro.ru, aekorotkov@gmail.com, stark.cfm@gmail.com, michal@kleczek.org, pgsql-hackers@lists.postgresql.org
Subject: Re: Removing unneeded self joins
In-Reply-To: <8800ccf2-ae82-461c-92a1-d4c0a22f8cf2@postgrespro.ru>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox