On 12/8/24 06:13, Tom Lane wrote:
Well, I have been working on this topic for some time. Let me share some experiences and thoughts. They may be helpful. I had a user request on this feature, a kind of 'semi-pushdown' clause. As production people said, it is quite typical in sales systems to have a table of products and additional tables describing product categories. Something like that:Andres Freund <and...@anarazel.de> writes:On 2024-12-07 17:06:52 -0500, Tom Lane wrote:One could imagine that we split up the join filter conditions into "depends on RHS" and "doesn't depend on RHS" subsets, and make the nestloop plan node evaluate the latter set only once per LHS row, and then skip the inner-side scan when that condition fails.As I wrote in my other email, I'm also somewhat dubious it's worth having explicit code for this in nodeNestloop.c.Yeah. Your idea of pushing the "doesn't depend on RHS" subset into a one-time Result filter atop the RHS is interesting though. Then we don't need any new executor machinery, but we pay for that with a more complex planner patch. Not sure how hard that would be.
CREATE TABLE products ( id int PRIMARY KEY, payload text DEFAULT 'product', price real DEFAULT random(), type text); CREATE TABLE vehicles (id int PRIMARY KEY, maxspeed int DEFAULT 250); CREATE TABLE phones (id int PRIMARY KEY, screensize real DEFAULT 6.1); INSERT INTO products (id,type) SELECT x,'v' FROM generate_series(1,5E4) AS x; INSERT INTO products (id,type) SELECT x,'p' FROM generate_series(1+5E4,1E5) AS x; INSERT INTO vehicles (id) SELECT x FROM generate_series(1,5E4) AS x; INSERT INTO phones (id) SELECT x FROM generate_series(1+5E4,1E5) AS x; VACUUM ANALYZE products, vehicles, phones;They usually need to get top-sales products from different categories querying database with something like that:
EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF) SELECT * FROM products p LEFT JOIN phones ph ON (p.id = ph.id) LEFT JOIN vehicles v ON (p.id = v.id) WHERE p.price > 0.9;Users just want to optimise such queries and get description of different products within a single query. The query they wish to execute looks like this:
EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF) SELECT * FROM products p LEFT JOIN phones ph ON (p.id = ph.id AND p.type = 'p') LEFT JOIN vehicles v ON (p.id = v.id AND p.type = 'v') WHERE p.price > 0.9;The request was: why not check the RHS-only clause inside a join node and save cycles?
To determine how difficult it could be, I wrote a prototype (very raw), which shows how it works in action and how many subsystems we have to touch. Also, I wonder why you think it could work with NestLoop only. I think avoiding touching a hash table and an index under MergeJoin can also be beneficial.
The patch and reproduction script with resulting EXPLAINs are in the attachment. Petr Petrov is doing further work. He may provide additional details, if any.
-- regards, Andrei Lepikhov
reproduction.sql
Description: application/sql
diff --git a/src/backend/executor/nodeNestloop.c b/src/backend/executor/nodeNestloop.c
index 7f4bf6c4db..fd80dc2192 100644
--- a/src/backend/executor/nodeNestloop.c
+++ b/src/backend/executor/nodeNestloop.c
@@ -66,6 +66,7 @@ ExecNestLoop(PlanState *pstate)
TupleTableSlot *outerTupleSlot;
TupleTableSlot *innerTupleSlot;
ExprState *joinqual;
+ ExprState *rhs_joinqual;
ExprState *otherqual;
ExprContext *econtext;
ListCell *lc;
@@ -79,6 +80,7 @@ ExecNestLoop(PlanState *pstate)
nl = (NestLoop *) node->js.ps.plan;
joinqual = node->js.joinqual;
+ rhs_joinqual = node->js.rhs_joinqual;
otherqual = node->js.ps.qual;
outerPlan = outerPlanState(node);
innerPlan = innerPlanState(node);
@@ -156,8 +158,15 @@ ExecNestLoop(PlanState *pstate)
*/
ENL1_printf("getting new inner tuple");
- innerTupleSlot = ExecProcNode(innerPlan);
- econtext->ecxt_innertuple = innerTupleSlot;
+ if (rhs_joinqual && !ExecQual(rhs_joinqual, econtext))
+ {
+ innerTupleSlot = NULL;
+ }
+ else
+ {
+ innerTupleSlot = ExecProcNode(innerPlan);
+ econtext->ecxt_innertuple = innerTupleSlot;
+ }
if (TupIsNull(innerTupleSlot))
{
@@ -314,6 +323,8 @@ ExecInitNestLoop(NestLoop *node, EState *estate, int eflags)
nlstate->js.jointype = node->join.jointype;
nlstate->js.joinqual =
ExecInitQual(node->join.joinqual, (PlanState *) nlstate);
+ nlstate->js.rhs_joinqual =
+ ExecInitQual(node->join.rhs_joinqual, (PlanState *) nlstate);
/*
* detect whether we need only consider the first matching inner tuple
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index f2ed0d81f6..003f949547 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -232,7 +232,7 @@ static RecursiveUnion *make_recursive_union(List *tlist,
static BitmapAnd *make_bitmap_and(List *bitmapplans);
static BitmapOr *make_bitmap_or(List *bitmapplans);
static NestLoop *make_nestloop(List *tlist,
- List *joinclauses, List *otherclauses, List *nestParams,
+ List *joinclauses, List *rhs_joinclauses, List *otherclauses, List *nestParams,
Plan *lefttree, Plan *righttree,
JoinType jointype, bool inner_unique);
static HashJoin *make_hashjoin(List *tlist,
@@ -4352,6 +4352,7 @@ create_nestloop_plan(PlannerInfo *root,
Plan *inner_plan;
List *tlist = build_path_tlist(root, &best_path->jpath.path);
List *joinrestrictclauses = best_path->jpath.joinrestrictinfo;
+ List *rhs_joinclauses = NIL;
List *joinclauses;
List *otherclauses;
Relids outerrelids;
@@ -4390,6 +4391,11 @@ create_nestloop_plan(PlannerInfo *root,
/* Sort join qual clauses into best execution order */
joinrestrictclauses = order_qual_clauses(root, joinrestrictclauses);
+ foreach_node(RestrictInfo, rinfo, best_path->jpath.rhs_joinrinfo)
+ {
+ rhs_joinclauses = lappend(rhs_joinclauses, rinfo->clause);
+ }
+
/* Get the join qual clauses (in plain expression form) */
/* Any pseudoconstant clauses are ignored here */
if (IS_OUTER_JOIN(best_path->jpath.jointype))
@@ -4423,6 +4429,7 @@ create_nestloop_plan(PlannerInfo *root,
join_plan = make_nestloop(tlist,
joinclauses,
+ rhs_joinclauses,
otherclauses,
nestParams,
outer_plan,
@@ -6021,6 +6028,7 @@ make_bitmap_or(List *bitmapplans)
static NestLoop *
make_nestloop(List *tlist,
List *joinclauses,
+ List *rhs_joinclauses,
List *otherclauses,
List *nestParams,
Plan *lefttree,
@@ -6038,6 +6046,23 @@ make_nestloop(List *tlist,
node->join.jointype = jointype;
node->join.inner_unique = inner_unique;
node->join.joinqual = joinclauses;
+
+ {
+ ListCell *lc;
+
+ foreach(lc, node->join.joinqual)
+ {
+ Node *qual = (Node *) lfirst(lc);
+
+ if (!list_member(rhs_joinclauses, qual))
+ continue;
+
+ node->join.joinqual = foreach_delete_current(node->join.joinqual, lc);
+ }
+
+ }
+
+ node->join.rhs_joinqual = rhs_joinclauses;
node->nestParams = nestParams;
return node;
diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c
index 91c7c4fe2f..0f54450ead 100644
--- a/src/backend/optimizer/plan/setrefs.c
+++ b/src/backend/optimizer/plan/setrefs.c
@@ -2294,6 +2294,14 @@ set_join_references(PlannerInfo *root, Join *join, int rtoffset)
rtoffset,
NRM_EQUAL,
NUM_EXEC_QUAL((Plan *) join));
+ join->rhs_joinqual = fix_join_expr(root,
+ join->rhs_joinqual,
+ outer_itlist,
+ inner_itlist,
+ (Index) 0,
+ rtoffset,
+ NRM_EQUAL,
+ NUM_EXEC_QUAL((Plan *) join));
/* Now do join-type-specific stuff */
if (IsA(join, NestLoop))
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index fc97bf6ee2..b7f1dbac23 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -2603,6 +2603,13 @@ create_nestloop_path(PlannerInfo *root,
pathnode->jpath.innerjoinpath = inner_path;
pathnode->jpath.joinrestrictinfo = restrict_clauses;
+ foreach_node(RestrictInfo, rinfo, restrict_clauses)
+ {
+ if (bms_is_subset(rinfo->clause_relids, outer_path->parent->relids))
+ pathnode->jpath.rhs_joinrinfo =
+ lappend(pathnode->jpath.rhs_joinrinfo, rinfo);
+ }
+
final_cost_nestloop(root, pathnode, workspace, extra);
return pathnode;
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 182a6956bb..14c7610c8c 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -2125,6 +2125,7 @@ typedef struct JoinState
bool single_match; /* True if we should skip to next outer tuple
* after finding one inner match */
ExprState *joinqual; /* JOIN quals (in addition to ps.qual) */
+ ExprState *rhs_joinqual;
} JoinState;
/* ----------------
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index add0f9e45f..c28c23c983 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -2085,7 +2085,7 @@ typedef struct JoinPath
Path *innerjoinpath; /* path for the inner side of the join */
List *joinrestrictinfo; /* RestrictInfos to apply to join */
-
+ List *rhs_joinrinfo; /* Outer-side join clauses (filters) */
/*
* See the notes for RelOptInfo and ParamPathInfo to understand why
* joinrestrictinfo is needed in JoinPath, and can't be merged into the
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index 52f29bcdb6..2c90a63e59 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -791,7 +791,8 @@ typedef struct Join
Plan plan;
JoinType jointype;
bool inner_unique;
- List *joinqual; /* JOIN quals (in addition to plan.qual) */
+ List *joinqual;
+ List *rhs_joinqual; /* JOIN quals (in addition to plan.qual) */
} Join;
/* ----------------
