public inbox for [email protected]
help / color / mirror / Atom feedFrom: David Rowley <[email protected]>
To: Andrei Lepikhov <[email protected]>
Cc: PostgreSQL-development <[email protected]>
Subject: Re: Memoize ANTI and SEMI JOIN inner
Date: Thu, 20 Mar 2025 19:02:16 +1300
Message-ID: <CAApHDvr2NRbjLXEUXvvKNCDcHfhC6UBL6ZmJzXZ29MBPi3+y8g@mail.gmail.com> (raw)
In-Reply-To: <[email protected]>
References: <[email protected]>
<[email protected]>
On Thu, 20 Mar 2025 at 06:16, Andrei Lepikhov <[email protected]> wrote:
> How can we be sure that semi or anti-join needs only one tuple? I think
> it would be enough to control the absence of join clauses and filters in
> the join. Unfortunately, we only have such a guarantee in the plan
> creation stage (maybe even setrefs.c). So, it seems we need to invent an
> approach like AlternativeSubplan.
I suggest looking at what 9e215378d did. You might be able to also
allow semi and anti-joins providing the cache keys cover the entire
join condition. I think this might be safe as Nested Loop will only
ask its inner subnode for the first match before skipping to the next
outer row and with anti-join, there's no reason to look for additional
rows after the first. Semi-join and unique joins do the same thing in
nodeNestloop.c. To save doing additional checks at run-time, the code
does:
nlstate->js.single_match = (node->join.inner_unique ||
node->join.jointype == JOIN_SEMI);
For making this work, I think the attached should be about the guts of
the code changes. I didn't look at the comments. Right now I can't
think of any reason why this can't be done, but some experimentation
might reveal some reason that it can't.
David
Attachments:
[application/octet-stream] memoize_semi_and_anti_joins_experiment.patch (1.7K, ../CAApHDvr2NRbjLXEUXvvKNCDcHfhC6UBL6ZmJzXZ29MBPi3+y8g@mail.gmail.com/2-memoize_semi_and_anti_joins_experiment.patch)
download | inline diff:
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 18891ce9156..03b4506e873 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -714,19 +714,6 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
ph_lateral_vars == NIL)
return NULL;
- /*
- * Currently we don't do this for SEMI and ANTI joins unless they're
- * marked as inner_unique. This is because nested loop SEMI/ANTI joins
- * don't scan the inner node to completion, which will mean memoize cannot
- * mark the cache entry as complete.
- *
- * XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique
- * = true. Should we? See add_paths_to_joinrel()
- */
- if (!extra->inner_unique && (jointype == JOIN_SEMI ||
- jointype == JOIN_ANTI))
- return NULL;
-
/*
* Memoize normally marks cache entries as complete when it runs out of
* tuples to read from its subplan. However, with unique joins, Nested
@@ -753,7 +740,7 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
* the inner scan's filter instead of the join filter. Maybe it's worth
* considering doing that?
*/
- if (extra->inner_unique &&
+ if ((extra->inner_unique || jointype == JOIN_SEMI || jointype == JOIN_ANTI) &&
(inner_path->param_info == NULL ||
bms_num_members(inner_path->param_info->ppi_serials) <
list_length(extra->restrictlist)))
@@ -808,7 +795,7 @@ get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel,
inner_path,
param_exprs,
hash_operators,
- extra->inner_unique,
+ extra->inner_unique || jointype == JOIN_SEMI || jointype == JOIN_ANTI,
binary_mode,
outer_path->rows);
}
view thread (26+ messages) latest in thread
reply
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: [email protected]
Cc: [email protected], [email protected]
Subject: Re: Memoize ANTI and SEMI JOIN inner
In-Reply-To: <CAApHDvr2NRbjLXEUXvvKNCDcHfhC6UBL6ZmJzXZ29MBPi3+y8g@mail.gmail.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox