Hello hackers, Attached is a patch that lets the planner rewrite an OR clause that spans several relations into a UNION ALL with one branch per arm, and use that plan when it is estimated to be cheaper.
Background OR clauses that mention more than one relation are awkward for the planner today. If the OR is the join condition itself (a.x = b.y OR a.x = b.z), it cannot be a hash or merge join clause, so the only choice left is a nested loop, usually with a BitmapOr of index scans on the inner side that is run again for every outer row. If it is a filter on two different tables (a.f = 1 OR b.g = 2), BitmapOr cannot help either, since it only combinesindexes of one relation, and the OR ends up as a join filter. The textbook case is a star schema with an OR over conditions on two dimension tables.
I ran into this while working on undirected edge patterns in SQL/PGQ [1]. An undirected edge becomes an OR over the two directions of the edge in the join condition, and on LSQB the nested loop
with the per-row BitmapOr ran the inner scan about 61 million times at SF 0.1. Writing the same query by hand as a UNION ALL took it from 91.7 s to 1.6 s, and at greater scale factors it was faster by 4610x . I first did the rewrite in the GRAPH_TABLE rewriter, but Ashutosh pointed out thatit belongs in the planner: if at any time its added, the rewrite for SQL/PGQ would be redundant.
Previous workThere was a previous discussion on this, Tom Lane posted a patch for this in 2017 [2], in the thread . The idea is: plan the arms before query_planner() runs and add
the result as an Append path afterwards. The differences are the wayduplicates are avoided and what is accepted. At that time it wasn't clear how to prove correctness on deduplication (which was done with a Unique on CTIDs of base relations), last message of the thread actually puts the proof of doing the expansion with negating previous arms' clauses. The latter way of doing it is far better than deduplication with CTIDs because: we are not limited to plain tables, we don't need a unique step.
What the patch does For an OR with arms C1..Cn, branch k is planned as the original query with the OR replaced by Ck AND (C1) IS NOT TRUE AND ... AND (C(k-1)) IS NOT TRUE so a row that satisfies several arms is returned only by the first of them. IS NOT TRUE (rather than NOT) keeps rows where an earlier arm evaluates to NULL, so the result has the same rows and multiplicity as the original query and no duplicate elimination step is needed. Each branch isplanned with query_planner() on a copy of the query, the cheapest path of each branch is taken, and they are combined into an Append that is added to the top scan/join relation with add_path(). Here i followed exactly what Tom's patch did.
Outer joins are reduced again inside each branch, since the branch's quals can make it null-rejecting.
Where it applies: An OR in the WHERE clause with between 2 and or_expansion_limit arms that refers to at least two relations: either the OR is the join condition, or it is a filter spanning two tables. SELECT ... FROM a, b WHERE a.x = b.y OR a.x = b.z; SELECT ... FROM a JOIN b ON a.id = b.a_id WHERE a.f = 1 OR b.g = 2; Where it is not considered:- ORs that only reference one relation, the argument is that in this case, surely a BitmapOr or anything else do the job.
- volatile functions in the jointree, security quals or function/subquery RTEs, since the arms are evaluated more than once - FULL joins, TABLESAMPLE, FOR UPDATE/SHARE, CTEs, set operations, recursive queries, well anything other than SELECT ? - partitioned tables, also inside subqueries. Child RTEs are created inside query_planner(), so after arms prune differently their range tableindexes no longer match the original one, i didn't try to make it work yet the solution here is maybe to refix pointers back to match root PlannerInfo for each arm, but this felt too much, i wonder if its worth it for the benefit it can get for partitioned tables.
- ORs in JOIN ... ON clauses. Only the top level WHERE quals are looked at for now. or_expansion_limit (default 8, 0 disables) bounds the number of arms. Every arm costs one extra planner run, and arm n carries n-1 negated copies of the earlier arms, so planning cost can grow quickly with the number ofarms. It is also an off switch to makes before/after comparisons easy for the moment. The default of 8 is a nice guess because i found that starting from 7 arms, planning time sometimes doubles (in complicated queries).
Some simlpe benchmark results 12 vCPUs, 15GB RAM, NVMe, shared_buffers = 2GB, work_mem = 128MB, max_parallel_workers_per_gather = 2. Star schema, 20M row fact table, OR between a condition on a customer dimension and one on a product dimension: 1893 ms -> 148 ms (planning 0.26 ms -> 0.52 ms) Two 2M row tables, selective OR with one arm on each table: 415 ms -> 26 ms (planning 0.94 ms -> 1.07 ms) Three tables, three selective arms: 891 ms -> 125 ms (planning 1.6 ms -> 3.0 ms) Join of two 2M row tables on (a = a OR b = b), join columns indexed, outer side limited to id < 100k: 1520 ms -> 435 ms (buffer hits 57,204,110 -> 179,797) Same with no indexes, id < 50k: 1508 ms -> 484 ms With id < 10k, indexed / not indexed: 841 ms -> 417 ms / 1538 ms -> 451 ms Where the arms are not selective (about 20% of the rows each) the original plans are kept. Patch and simple benchmark files attached.[1] https://www.postgresql.org/message-id/4ab664c3585d3c2da2d4c1d1bbed430e%40data-bene.io [2] https://www.postgresql.org/message-id/flat/7f70bd5a-5d16-e05c-f0b4-2fdfc8873489%40BlueTreble.com
Regards, Ayoub Kazar
From 7975143947d22eff59ce6751826951d7d97ef14c Mon Sep 17 00:00:00 2001 From: AyoubKAZ <[email protected]> Date: Tue, 6 Oct 2026 12:46:32 +0200 Subject: [PATCH] Expand OR clauses in joins to UNION ALL (Append) paths --- src/backend/optimizer/path/costsize.c | 1 + src/backend/optimizer/plan/Makefile | 1 + src/backend/optimizer/plan/meson.build | 1 + src/backend/optimizer/plan/planner.c | 13 + src/backend/optimizer/plan/planorexpand.c | 563 +++++++++++++++++++++ src/backend/utils/misc/guc_parameters.dat | 10 + src/include/optimizer/cost.h | 1 + src/include/optimizer/planmain.h | 7 + src/test/regress/expected/join.out | 26 +- src/test/regress/expected/or_expansion.out | 249 +++++++++ src/test/regress/sql/or_expansion.sql | 122 +++++ 11 files changed, 987 insertions(+), 7 deletions(-) create mode 100644 src/backend/optimizer/plan/planorexpand.c create mode 100644 src/test/regress/expected/or_expansion.out create mode 100644 src/test/regress/sql/or_expansion.sql diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index 7bbddb8bee4..ca653439b01 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -162,6 +162,7 @@ bool enable_partitionwise_join = false; bool enable_partitionwise_aggregate = false; bool enable_parallel_append = true; bool enable_parallel_hash = true; +int or_expansion_limit = 8; bool enable_partition_pruning = true; bool enable_presorted_aggregate = true; bool enable_async_append = true; diff --git a/src/backend/optimizer/plan/Makefile b/src/backend/optimizer/plan/Makefile index 80ef162e484..3abff3baf65 100644 --- a/src/backend/optimizer/plan/Makefile +++ b/src/backend/optimizer/plan/Makefile @@ -18,6 +18,7 @@ OBJS = \ initsplan.o \ planagg.o \ planmain.o \ + planorexpand.o \ planner.o \ setrefs.o \ subselect.o diff --git a/src/backend/optimizer/plan/meson.build b/src/backend/optimizer/plan/meson.build index c565b2adbcc..7e900b3107b 100644 --- a/src/backend/optimizer/plan/meson.build +++ b/src/backend/optimizer/plan/meson.build @@ -6,6 +6,7 @@ backend_sources += files( 'initsplan.c', 'planagg.c', 'planmain.c', + 'planorexpand.c', 'planner.c', 'setrefs.c', 'subselect.c', diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index edaa42d713a..f0f0e526fe0 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -1850,6 +1850,7 @@ grouping_planner(PlannerInfo *root, double tuple_fraction, List *activeWindows = NIL; grouping_sets_data *gset_data = NULL; standard_qp_extra qp_extra; + List *or_cands; /* A recursive query should always have setOperations */ Assert(!root->hasRecursion); @@ -1925,6 +1926,11 @@ grouping_planner(PlannerInfo *root, double tuple_fraction, if (parse->hasAggs) preprocess_minmax_aggregates(root); + /* + * Consider expanding eligible OR clauses to UNION ALL (Append) paths. + */ + or_cands = plan_or_expansion_arms(root); + /* * Figure out whether there's a hard limit on the number of rows that * query_planner's result subplan needs to return. Even if we know a @@ -1961,6 +1967,13 @@ grouping_planner(PlannerInfo *root, double tuple_fraction, */ current_rel = query_planner(root, standard_qp_callback, &qp_extra); + /* + * If we generated any OR-expansion candidates, add the resulting + * Append path(s) to the topmost scan/join relation. + */ + if (or_cands != NIL) + add_or_expansion_paths(root, current_rel, or_cands); + /* * Convert the query's result tlist into PathTarget format. * diff --git a/src/backend/optimizer/plan/planorexpand.c b/src/backend/optimizer/plan/planorexpand.c new file mode 100644 index 00000000000..783787c0789 --- /dev/null +++ b/src/backend/optimizer/plan/planorexpand.c @@ -0,0 +1,563 @@ +/*------------------------------------------------------------------------- + * + * planorexpand.c + * Consider whether OR clauses in join queries can be expanded to + * UNION ALL (Append) paths. + * + * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * IDENTIFICATION + * src/backend/optimizer/plan/planorexpand.c + * + *------------------------------------------------------------------------- + */ +#include "postgres.h" + +#include "catalog/pg_class.h" +#include "catalog/pg_type.h" +#include "nodes/makefuncs.h" +#include "nodes/nodeFuncs.h" +#include "optimizer/clauses.h" +#include "optimizer/cost.h" +#include "optimizer/optimizer.h" +#include "optimizer/pathnode.h" +#include "optimizer/planmain.h" +#include "optimizer/prep.h" +#include "optimizer/tlist.h" + + +static bool is_query_safe_for_or_expansion(PlannerInfo *root); +static bool has_partitioned_table_walker(Node *node, void *ctx); +static void or_expansion_qp_callback(PlannerInfo *root, void *extra); +static List *create_or_expansion_subpaths(PlannerInfo *root, BoolExpr *orclause, + int qual_idx); +static bool has_outer_joins(Node *jtnode); +static bool match_target_expr(Node *want, Node *have); +static Path *or_expansion_align_path(PlannerInfo *root, RelOptInfo *joinrel, Path *arm); + +/* + * has_partitioned_table_walker + * Return true if the query (or any subquery within it) references a + * partitioned table. Used by is_query_safe_for_or_expansion to catch + * partitioned tables that are hidden inside derived-table subqueries. + */ +static bool +has_partitioned_table_walker(Node *node, void *ctx) +{ + if (node == NULL) + return false; + if (IsA(node, RangeTblEntry)) + { + RangeTblEntry *rte = (RangeTblEntry *) node; + + if (rte->rtekind == RTE_RELATION && + rte->relkind == RELKIND_PARTITIONED_TABLE) + return true; + /* subquery contents are visited by query_tree_walker automatically */ + return false; + } + if (IsA(node, Query)) + return query_tree_walker((Query *) node, + has_partitioned_table_walker, ctx, + QTW_EXAMINE_RTES_BEFORE); + return expression_tree_walker(node, has_partitioned_table_walker, ctx); +} + +/* + * is_query_safe_for_or_expansion + * Verify query-level safety gates for OR expansion. + */ +static bool +is_query_safe_for_or_expansion(PlannerInfo *root) +{ + Query *parse = root->parse; + ListCell *lc; + + /* Volatile functions in jointree (WHERE or FROM) are unsafe to duplicate */ + if (contain_volatile_functions((Node *) parse->jointree)) + return false; + + /* + * Should we disallow queries with lateral references? + */ + + /* + * if (root->hasLateralRTEs) return false; + */ + + /* Check RTEs */ + foreach(lc, parse->rtable) + { + RangeTblEntry *rte = (RangeTblEntry *) lfirst(lc); + + /* + * Do not attempt transformation if the query contains FULL joins. + */ + if (rte->rtekind == RTE_JOIN && rte->jointype == JOIN_FULL) + return false; + + /* + * Disallow partitioned tables (directly or inside any subquery) until + * arm partition pruning and rangetable index synchronization are + * supported. A partitioned table hidden inside a derived-table + * subquery triggers the same index-mismatch as a top-level one. + */ + if (rte->rtekind == RTE_RELATION && + rte->relkind == RELKIND_PARTITIONED_TABLE) + return false; + if (rte->rtekind == RTE_SUBQUERY && + has_partitioned_table_walker((Node *) rte->subquery, NULL)) + return false; + + /* Disallow tablesample (arms could sample different rows ?) */ + if (rte->tablesample != NULL) + return false; + + /* Security barrier quals must not contain volatile functions */ + if (contain_volatile_functions((Node *) rte->securityQuals)) + return false; + + /* Disallow volatile function RTEs */ + if (rte->rtekind == RTE_FUNCTION && + contain_volatile_functions((Node *) rte->functions)) + return false; + + /* Disallow volatile expressions in subquery/values/tablefunc */ + if (rte->rtekind == RTE_SUBQUERY && + contain_volatile_functions((Node *) rte->subquery)) + return false; + + if (rte->rtekind == RTE_VALUES && + contain_volatile_functions((Node *) rte->values_lists)) + return false; + + if (rte->rtekind == RTE_TABLEFUNC && + contain_volatile_functions((Node *) rte->tablefunc)) + return false; + } + + return true; +} + +static bool +has_outer_joins(Node *jtnode) +{ + if (jtnode == NULL) + return false; + if (IsA(jtnode, FromExpr)) + { + FromExpr *f = (FromExpr *) jtnode; + ListCell *lc; + + foreach(lc, f->fromlist) + { + if (has_outer_joins(lfirst(lc))) + return true; + } + return false; + } + if (IsA(jtnode, JoinExpr)) + { + JoinExpr *j = (JoinExpr *) jtnode; + + if (IS_OUTER_JOIN(j->jointype)) + return true; + return has_outer_joins(j->larg) || has_outer_joins(j->rarg); + } + + return false; +} + +/* + * or_expansion_qp_callback + * Query planner callback for subroot arm planning. + */ +static void +or_expansion_qp_callback(PlannerInfo *root, void *extra) +{ + /* + * Ordering is destroyed through UNION ALL / Append, so clear pathkeys + * that might otherwise restrict lower paths. + */ + root->group_pathkeys = NIL; + root->window_pathkeys = NIL; + root->distinct_pathkeys = NIL; + root->sort_pathkeys = NIL; + root->query_pathkeys = NIL; +} + +/* + * create_or_expansion_subpaths + * Create best paths for each arm of the candidate OR clause. + */ +static List * +create_or_expansion_subpaths(PlannerInfo *root, BoolExpr *orclause, int qual_idx) +{ + List *subpaths = NIL; + int num_arms = list_length(orclause->args); + int k; + + for (k = 0; k < num_arms; k++) + { + PlannerInfo *subroot; + Query *parse; + List *arm_quals = NIL; + ListCell *lc; + int q_idx; + Node *arm_k; + int j; + RelOptInfo *final_rel; + Path *subpath; + + /* Clone PlannerInfo state modeled on planagg.c */ + subroot = (PlannerInfo *) palloc(sizeof(PlannerInfo)); + memcpy(subroot, root, sizeof(PlannerInfo)); + subroot->parse = parse = (Query *) copyObject(root->parse); + + /* + * subroot will set up its own rel/rte arrays inside query_planner. + */ + subroot->simple_rel_array = NULL; + subroot->simple_rte_array = NULL; + subroot->simple_rel_array_size = 0; + + subroot->processed_tlist = (List *) copyObject(root->processed_tlist); + subroot->append_rel_list = (List *) copyObject(root->append_rel_list); + subroot->tuple_fraction = 1.0; + subroot->limit_tuples = -1.0; + + /* + * give subroot its own JoinDomain and reset planner working lists so + * query_planner(subroot) does not corrupt root's state. + */ + subroot->join_domains = list_make1(makeNode(JoinDomain)); + subroot->plan_params = NIL; + subroot->outer_params = NULL; + subroot->rowMarks = NIL; + subroot->init_plans = NIL; + subroot->agginfos = NIL; + subroot->aggtransinfos = NIL; + subroot->join_info_list = NIL; + subroot->eq_classes = NIL; + subroot->placeholder_list = NIL; + subroot->placeholder_array = NULL; + subroot->placeholder_array_size = 0; + subroot->left_join_clauses = NIL; + subroot->right_join_clauses = NIL; + subroot->full_join_clauses = NIL; + subroot->fkey_list = NIL; + subroot->initial_rels = NIL; + subroot->last_rinfo_serial = 0; + + /* + * Build arm quals: R AND C_k AND (C_0 IS NOT TRUE) AND ... AND + * (C_{k-1} IS NOT TRUE) + */ + q_idx = 0; + foreach(lc, (List *) root->parse->jointree->quals) + { + if (q_idx != qual_idx) + arm_quals = lappend(arm_quals, copyObject(lfirst(lc))); + q_idx++; + } + + /* Add arm k's disjunct, flattened if it is an AND expression */ + arm_k = (Node *) copyObject(list_nth(orclause->args, k)); + arm_quals = list_concat(arm_quals, make_ands_implicit((Expr *) arm_k)); + + /* Add null-safe exclusion conditions for all previous arms */ + for (j = 0; j < k; j++) + { + Node *prev_arm = (Node *) copyObject(list_nth(orclause->args, j)); + BooleanTest *btest; + + btest = makeNode(BooleanTest); + btest->arg = (Expr *) prev_arm; + btest->booltesttype = IS_NOT_TRUE; + btest->location = -1; + + arm_quals = lappend(arm_quals, btest); + } + + parse->jointree->quals = (Node *) arm_quals; + + /* Re-run reduce_outer_joins if rtable contains outer joins */ + if (has_outer_joins((Node *) parse->jointree)) + reduce_outer_joins(subroot); + + /* Plan this arm */ + final_rel = query_planner(subroot, or_expansion_qp_callback, NULL); + + if (!final_rel || !final_rel->cheapest_total_path || + final_rel->cheapest_total_path->param_info != NULL) + return NIL; + + subpath = final_rel->cheapest_total_path; + subpaths = lappend(subpaths, subpath); + } + + return subpaths; +} + +/* + * plan_or_expansion_arms + * Check eligibility and generate subpaths for OR clauses in top-level WHERE. + * Called by grouping_planner() before query_planner(). + */ +List * +plan_or_expansion_arms(PlannerInfo *root) +{ + List *results = NIL; + Query *parse = root->parse; + bool checked_query = false; + ListCell *lc; + int qual_idx; + + /* Cheap gates first */ + if (or_expansion_limit < 2) + return NIL; + + if (parse->commandType != CMD_SELECT || + parse->rowMarks != NIL || + parse->setOperations != NULL || + parse->cteList != NIL || + root->hasRecursion) + return NIL; + + if (list_length(parse->rtable) < 2) + return NIL; + + if (parse->jointree == NULL || parse->jointree->quals == NULL) + return NIL; + + /* Scan top-level WHERE quals for eligible OR clauses */ + qual_idx = 0; + foreach(lc, (List *) parse->jointree->quals) + { + Node *qual = (Node *) lfirst(lc); + + if (is_orclause(qual)) + { + BoolExpr *orclause = (BoolExpr *) qual; + int num_arms = list_length(orclause->args); + Relids all_arm_varnos = NULL; + ListCell *lc_arm; + + if (num_arms < 2 || num_arms > or_expansion_limit) + { + qual_idx++; + continue; + } + + /* Structural case gate: check referenced relations */ + foreach(lc_arm, orclause->args) + { + Node *arm = (Node *) lfirst(lc_arm); + Relids arm_varnos = pull_varnos(root, arm); + + all_arm_varnos = bms_join(all_arm_varnos, arm_varnos); + } + + /* + * Require the OR clause to reference at least 2 distinct + * relations. + */ + if (bms_num_members(all_arm_varnos) < 2) + { + bms_free(all_arm_varnos); + qual_idx++; + continue; + } + bms_free(all_arm_varnos); + + /* Query-level safety check */ + if (!checked_query) + { + if (!is_query_safe_for_or_expansion(root)) + return NIL; + checked_query = true; + } + + /* Transform OR clause and generate subpaths for each arm */ + { + List *subpaths = create_or_expansion_subpaths(root, orclause, qual_idx); + + if (subpaths != NIL) + results = lappend(results, subpaths); + } + } + qual_idx++; + } + + return results; +} + +/* + * match_target_expr + * Check if two targetlist expressions match, ignoring varnullingrels + * differences that may arise from outer join reduction in subroot. + */ +static bool +match_target_expr(Node *want, Node *have) +{ + if (want == have) + return true; + if (want == NULL || have == NULL) + return false; + if (nodeTag(want) != nodeTag(have)) + return false; + + if (IsA(want, Var)) + { + Var *v1 = (Var *) want; + Var *v2 = (Var *) have; + + return (v1->varno == v2->varno && + v1->varattno == v2->varattno && + v1->varlevelsup == v2->varlevelsup); + } + + if (IsA(want, PlaceHolderVar)) + { + PlaceHolderVar *p1 = (PlaceHolderVar *) want; + PlaceHolderVar *p2 = (PlaceHolderVar *) have; + + return (p1->phid == p2->phid && + p1->phlevelsup == p2->phlevelsup); + } + + return equal(want, have); +} + +/* + * or_expansion_align_path + * Ensure the arm path emits columns in the exact order needed by joinrel. + * If column order differs, wrap with a projection using the arm's own + * expressions. + */ +static Path * +or_expansion_align_path(PlannerInfo *root, RelOptInfo *joinrel, Path *arm) +{ + List *want = joinrel->reltarget->exprs; + List *have = arm->pathtarget->exprs; + List *new_exprs = NIL; + bool identical = true; + ListCell *lc_want; + ListCell *lc_have; + PathTarget *newtarget; + + if (list_length(want) != list_length(have)) + identical = false; + + lc_have = list_head(have); + foreach(lc_want, want) + { + Node *want_node = (Node *) lfirst(lc_want); + Node *matched = NULL; + ListCell *lc; + + if (identical && lc_have != NULL) + { + if (match_target_expr(want_node, (Node *) lfirst(lc_have))) + { + matched = (Node *) lfirst(lc_have); + lc_have = lnext(have, lc_have); + } + else + identical = false; + } + + if (matched == NULL) + { + foreach(lc, have) + { + Node *have_node = (Node *) lfirst(lc); + + if (match_target_expr(want_node, have_node)) + { + matched = have_node; + break; + } + } + } + + if (matched == NULL) + return NULL; + + new_exprs = lappend(new_exprs, matched); + } + + if (identical) + return arm; + + newtarget = create_empty_pathtarget(); + newtarget->exprs = new_exprs; + set_pathtarget_cost_width(root, newtarget); + + /* Apply projection in-place if supported, or wrap with a ProjectionPath */ + return apply_projection_to_path(root, joinrel, arm, newtarget); +} + +/* + * add_or_expansion_paths + * Combine arm subpaths into an AppendPath and add to the top join rel. + * Called by grouping_planner() right after query_planner(). + */ +void +add_or_expansion_paths(PlannerInfo *root, RelOptInfo *joinrel, List *or_cands) +{ + ListCell *lc; + bool added_any = false; + + if (joinrel == NULL || joinrel->reltarget == NULL) + return; + + foreach(lc, or_cands) + { + List *subpaths = (List *) lfirst(lc); + List *aligned_subpaths = NIL; + ListCell *lc_subpath; + bool valid = true; + AppendPathInput ainput; + AppendPath *appendpath; + + foreach(lc_subpath, subpaths) + { + Path *subpath = (Path *) lfirst(lc_subpath); + Path *aligned; + + aligned = or_expansion_align_path(root, joinrel, subpath); + if (aligned == NULL) + { + valid = false; + break; + } + aligned_subpaths = lappend(aligned_subpaths, aligned); + } + + if (!valid) + continue; + + ainput.subpaths = aligned_subpaths; + ainput.partial_subpaths = NIL; + ainput.child_append_relid_sets = NIL; + + /* Build Append path combining arm subpaths */ + appendpath = create_append_path(root, + joinrel, + ainput, + NIL, + NULL, + 0, + false, + -1); + + add_path(joinrel, (Path *) appendpath); + added_any = true; + } + + /* We need to refigure which is the cheapest path for the joinrel */ + if (added_any) + set_cheapest(joinrel); +} diff --git a/src/backend/utils/misc/guc_parameters.dat b/src/backend/utils/misc/guc_parameters.dat index c57441f7d98..8682f2531a3 100644 --- a/src/backend/utils/misc/guc_parameters.dat +++ b/src/backend/utils/misc/guc_parameters.dat @@ -2326,6 +2326,16 @@ ifdef => 'DEBUG_BOUNDED_SORT', }, +{ name => 'or_expansion_limit', type => 'int', context => 'PGC_USERSET', group => 'QUERY_TUNING_OTHER', + short_desc => 'Sets the maximum number of OR arms considered for OR-expansion.', + long_desc => 'The planner will consider expanding OR clauses if they have no more than this many arms. 0 disables OR-expansion.', + flags => 'GUC_EXPLAIN', + variable => 'or_expansion_limit', + boot_val => '8', + min => '0', + max => 'INT_MAX', +}, + { name => 'output_plugin_libraries', type => 'string', context => 'PGC_SUSET', group => 'REPLICATION_SENDING', short_desc => 'Lists libraries that may be named as logical decoding output plugins.', long_desc => 'Users with REPLICATION privileges may only use plugins in this list when creating logical replication slots.', diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h index 14255c900fc..f5e22c39c6c 100644 --- a/src/include/optimizer/cost.h +++ b/src/include/optimizer/cost.h @@ -68,6 +68,7 @@ extern PGDLLIMPORT bool enable_partitionwise_join; extern PGDLLIMPORT bool enable_partitionwise_aggregate; extern PGDLLIMPORT bool enable_parallel_append; extern PGDLLIMPORT bool enable_parallel_hash; +extern PGDLLIMPORT int or_expansion_limit; extern PGDLLIMPORT bool enable_partition_pruning; extern PGDLLIMPORT bool enable_presorted_aggregate; extern PGDLLIMPORT bool enable_async_append; diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h index c23ab568b98..e7c780d774c 100644 --- a/src/include/optimizer/planmain.h +++ b/src/include/optimizer/planmain.h @@ -36,6 +36,13 @@ extern RelOptInfo *query_planner(PlannerInfo *root, */ extern void preprocess_minmax_aggregates(PlannerInfo *root); +/* + * prototypes for plan/planorexpand.c + */ +extern List *plan_or_expansion_arms(PlannerInfo *root); +extern void add_or_expansion_paths(PlannerInfo *root, RelOptInfo *joinrel, + List *or_cands); + /* * prototypes for plan/createplan.c */ diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out index 25a9a39cdc1..e9187d82378 100644 --- a/src/test/regress/expected/join.out +++ b/src/test/regress/expected/join.out @@ -11817,14 +11817,26 @@ WHERE ss.unique1 = ss.phv AND t1.unique1 < 100; EXPLAIN (COSTS OFF) SELECT COUNT(*) FROM tenk1 t1, tenk1 t2 WHERE t2.thousand = t1.tenthous OR t2.thousand = t1.unique1 OR t2.thousand = t1.unique2; - QUERY PLAN ------------------------------------------------------------------------------------------ + QUERY PLAN +--------------------------------------------------------------------------------------------------------------------- Aggregate - -> Nested Loop - -> Seq Scan on tenk1 t1 - -> Index Only Scan using tenk1_thous_tenthous on tenk1 t2 - Index Cond: (thousand = ANY (ARRAY[t1.tenthous, t1.unique1, t1.unique2])) -(5 rows) + -> Append + -> Hash Join + Hash Cond: (t2.thousand = t1.tenthous) + -> Index Only Scan using tenk1_thous_tenthous on tenk1 t2 + -> Hash + -> Index Only Scan using tenk1_thous_tenthous on tenk1 t1 + -> Merge Join + Merge Cond: (t1.unique1 = t2.thousand) + Join Filter: ((t2.thousand = t1.tenthous) IS NOT TRUE) + -> Index Scan using tenk1_unique1 on tenk1 t1 + -> Index Only Scan using tenk1_thous_tenthous on tenk1 t2 + -> Merge Join + Merge Cond: (t1.unique2 = t2.thousand) + Join Filter: (((t2.thousand = t1.tenthous) IS NOT TRUE) AND ((t2.thousand = t1.unique1) IS NOT TRUE)) + -> Index Scan using tenk1_unique2 on tenk1 t1 + -> Index Only Scan using tenk1_thous_tenthous on tenk1 t2 +(17 rows) SELECT COUNT(*) FROM tenk1 t1, tenk1 t2 WHERE t2.thousand = t1.tenthous OR t2.thousand = t1.unique1 OR t2.thousand = t1.unique2; diff --git a/src/test/regress/expected/or_expansion.out b/src/test/regress/expected/or_expansion.out new file mode 100644 index 00000000000..aae75315f27 --- /dev/null +++ b/src/test/regress/expected/or_expansion.out @@ -0,0 +1,249 @@ +-- +-- Tests for OR-expansion to UNION ALL (Append) +-- +CREATE TABLE orexp_a (id int, val int); +CREATE TABLE orexp_b (x int, y int, val int); +INSERT INTO orexp_a VALUES + (1, 10), + (2, 20), + (3, 30), + (4, NULL), + (5, 50); +INSERT INTO orexp_b VALUES + (1, 99, 100), + (99, 2, 200), + (3, 3, 300), + (4, 99, 400), + (99, 99, 500), + (NULL, NULL, 600); +-- Verify GUC exists and can be toggled +SHOW or_expansion_limit; + or_expansion_limit +-------------------- + 8 +(1 row) + +-- Case C3: Join condition OR (disjunction of join keys) +-- With default or_expansion_limit = 8, planner should expand to Append of joins +EXPLAIN (COSTS OFF) +SELECT a.id, b.x, b.y FROM orexp_a a, orexp_b b +WHERE a.id = b.x OR a.id = b.y +ORDER BY a.id, b.x, b.y; + QUERY PLAN +------------------------------------------------------- + Sort + Sort Key: a.id, b.x, b.y + -> Append + -> Merge Join + Merge Cond: (b.x = a.id) + -> Sort + Sort Key: b.x + -> Seq Scan on orexp_b b + -> Sort + Sort Key: a.id + -> Seq Scan on orexp_a a + -> Merge Join + Merge Cond: (b.y = a.id) + Join Filter: ((a.id = b.x) IS NOT TRUE) + -> Sort + Sort Key: b.y + -> Seq Scan on orexp_b b + -> Sort + Sort Key: a.id + -> Seq Scan on orexp_a a +(20 rows) + +SELECT a.id, b.x, b.y FROM orexp_a a, orexp_b b +WHERE a.id = b.x OR a.id = b.y +ORDER BY a.id, b.x, b.y; + id | x | y +----+----+---- + 1 | 1 | 99 + 2 | 99 | 2 + 3 | 3 | 3 + 4 | 4 | 99 +(4 rows) + +-- Result must match or_expansion_limit = 0 (disabled) +SET or_expansion_limit = 0; +EXPLAIN (COSTS OFF) +SELECT a.id, b.x, b.y FROM orexp_a a, orexp_b b +WHERE a.id = b.x OR a.id = b.y +ORDER BY a.id, b.x, b.y; + QUERY PLAN +----------------------------------------------------- + Sort + Sort Key: a.id, b.x, b.y + -> Nested Loop + Join Filter: ((a.id = b.x) OR (a.id = b.y)) + -> Seq Scan on orexp_a a + -> Materialize + -> Seq Scan on orexp_b b +(7 rows) + +SELECT a.id, b.x, b.y FROM orexp_a a, orexp_b b +WHERE a.id = b.x OR a.id = b.y +ORDER BY a.id, b.x, b.y; + id | x | y +----+----+---- + 1 | 1 | 99 + 2 | 99 | 2 + 3 | 3 | 3 + 4 | 4 | 99 +(4 rows) + +-- Case C4: Cross-table filter with separate join key +-- Tests null-safety, 3-valued logic, and duplicate exclusion +SET or_expansion_limit = 8; +EXPLAIN (COSTS OFF) +SELECT a.id, a.val, b.val FROM orexp_a a JOIN orexp_b b ON a.id = b.x +WHERE a.val = 10 OR b.val = 300 +ORDER BY a.id, a.val, b.val; + QUERY PLAN +------------------------------------------------------ + Sort + Sort Key: a.id, a.val, b.val + -> Append + -> Hash Join + Hash Cond: (b.x = a.id) + -> Seq Scan on orexp_b b + -> Hash + -> Seq Scan on orexp_a a + Filter: (val = 10) + -> Hash Join + Hash Cond: (a.id = b.x) + -> Seq Scan on orexp_a a + Filter: ((val = 10) IS NOT TRUE) + -> Hash + -> Seq Scan on orexp_b b + Filter: (val = 300) +(16 rows) + +SELECT a.id, a.val, b.val FROM orexp_a a JOIN orexp_b b ON a.id = b.x +WHERE a.val = 10 OR b.val = 300 +ORDER BY a.id, a.val, b.val; + id | val | val +----+-----+----- + 1 | 10 | 100 + 3 | 30 | 300 +(2 rows) + +SET or_expansion_limit = 0; +SELECT a.id, a.val, b.val FROM orexp_a a JOIN orexp_b b ON a.id = b.x +WHERE a.val = 10 OR b.val = 300 +ORDER BY a.id, a.val, b.val; + id | val | val +----+-----+----- + 1 | 10 | 100 + 3 | 30 | 300 +(2 rows) + +-- Case C5: Non-flattened subquery over ordinary table with cross-table OR +-- Verifies expression_tree_walker is not called on RangeTblEntry nodes +CREATE TABLE orexp_c (id int, tier text); +CREATE TABLE orexp_d (cid int, val int); +INSERT INTO orexp_c VALUES (1, 'vip'), (2, 'std'); +INSERT INTO orexp_d VALUES (1, 10), (1, 20), (2, 5); +SET or_expansion_limit = 8; +EXPLAIN (COSTS OFF) +SELECT c.id, s.n FROM orexp_c c + JOIN (SELECT cid, count(*) n FROM orexp_d GROUP BY cid) s ON s.cid = c.id +WHERE c.tier = 'vip' OR s.n > 20 +ORDER BY c.id; + QUERY PLAN +------------------------------------------------------------- + Sort + Sort Key: c.id + -> Hash Join + Hash Cond: (c.id = s.cid) + Join Filter: ((c.tier = 'vip'::text) OR (s.n > 20)) + -> Seq Scan on orexp_c c + -> Hash + -> Subquery Scan on s + -> HashAggregate + Group Key: orexp_d.cid + -> Seq Scan on orexp_d +(11 rows) + +SELECT c.id, s.n FROM orexp_c c + JOIN (SELECT cid, count(*) n FROM orexp_d GROUP BY cid) s ON s.cid = c.id +WHERE c.tier = 'vip' OR s.n > 20 +ORDER BY c.id; + id | n +----+--- + 1 | 2 +(1 row) + +SET or_expansion_limit = 0; +SELECT c.id, s.n FROM orexp_c c + JOIN (SELECT cid, count(*) n FROM orexp_d GROUP BY cid) s ON s.cid = c.id +WHERE c.tier = 'vip' OR s.n > 20 +ORDER BY c.id; + id | n +----+--- + 1 | 2 +(1 row) + +DROP TABLE orexp_c; +DROP TABLE orexp_d; +-- Case C6: Subquery over partitioned table (gate must reject OR expansion) +CREATE TABLE orexp_part (id int, d int) PARTITION BY RANGE (d); +CREATE TABLE orexp_part1 PARTITION OF orexp_part FOR VALUES FROM (0) TO (10); +CREATE TABLE orexp_part2 PARTITION OF orexp_part FOR VALUES FROM (10) TO (20); +INSERT INTO orexp_part VALUES (1, 5), (2, 15); +SET or_expansion_limit = 8; +EXPLAIN (COSTS OFF) +SELECT a.id, s.d FROM orexp_a a, + (SELECT id, d FROM orexp_part GROUP BY id, d) s +WHERE a.id = s.id OR s.d = 15 +ORDER BY a.id, s.d; + QUERY PLAN +-------------------------------------------------------------------------- + Sort + Sort Key: a.id, s.d + -> Nested Loop + Join Filter: ((a.id = s.id) OR (s.d = 15)) + -> Seq Scan on orexp_a a + -> Materialize + -> Subquery Scan on s + -> HashAggregate + Group Key: orexp_part.id, orexp_part.d + -> Append + -> Seq Scan on orexp_part1 orexp_part_1 + -> Seq Scan on orexp_part2 orexp_part_2 +(12 rows) + +SELECT a.id, s.d FROM orexp_a a, + (SELECT id, d FROM orexp_part GROUP BY id, d) s +WHERE a.id = s.id OR s.d = 15 +ORDER BY a.id, s.d; + id | d +----+---- + 1 | 5 + 1 | 15 + 2 | 15 + 3 | 15 + 4 | 15 + 5 | 15 +(6 rows) + +SET or_expansion_limit = 0; +SELECT a.id, s.d FROM orexp_a a, + (SELECT id, d FROM orexp_part GROUP BY id, d) s +WHERE a.id = s.id OR s.d = 15 +ORDER BY a.id, s.d; + id | d +----+---- + 1 | 5 + 1 | 15 + 2 | 15 + 3 | 15 + 4 | 15 + 5 | 15 +(6 rows) + +DROP TABLE orexp_part; +-- Clean up +RESET or_expansion_limit; +DROP TABLE orexp_a; +DROP TABLE orexp_b; diff --git a/src/test/regress/sql/or_expansion.sql b/src/test/regress/sql/or_expansion.sql new file mode 100644 index 00000000000..a3a035d6f05 --- /dev/null +++ b/src/test/regress/sql/or_expansion.sql @@ -0,0 +1,122 @@ +-- +-- Tests for OR-expansion to UNION ALL (Append) +-- + +CREATE TABLE orexp_a (id int, val int); +CREATE TABLE orexp_b (x int, y int, val int); + +INSERT INTO orexp_a VALUES + (1, 10), + (2, 20), + (3, 30), + (4, NULL), + (5, 50); + +INSERT INTO orexp_b VALUES + (1, 99, 100), + (99, 2, 200), + (3, 3, 300), + (4, 99, 400), + (99, 99, 500), + (NULL, NULL, 600); + +-- Verify GUC exists and can be toggled +SHOW or_expansion_limit; + +-- Case C3: Join condition OR (disjunction of join keys) +-- With default or_expansion_limit = 8, planner should expand to Append of joins +EXPLAIN (COSTS OFF) +SELECT a.id, b.x, b.y FROM orexp_a a, orexp_b b +WHERE a.id = b.x OR a.id = b.y +ORDER BY a.id, b.x, b.y; + +SELECT a.id, b.x, b.y FROM orexp_a a, orexp_b b +WHERE a.id = b.x OR a.id = b.y +ORDER BY a.id, b.x, b.y; + +-- Result must match or_expansion_limit = 0 (disabled) +SET or_expansion_limit = 0; +EXPLAIN (COSTS OFF) +SELECT a.id, b.x, b.y FROM orexp_a a, orexp_b b +WHERE a.id = b.x OR a.id = b.y +ORDER BY a.id, b.x, b.y; + +SELECT a.id, b.x, b.y FROM orexp_a a, orexp_b b +WHERE a.id = b.x OR a.id = b.y +ORDER BY a.id, b.x, b.y; + +-- Case C4: Cross-table filter with separate join key +-- Tests null-safety, 3-valued logic, and duplicate exclusion +SET or_expansion_limit = 8; +EXPLAIN (COSTS OFF) +SELECT a.id, a.val, b.val FROM orexp_a a JOIN orexp_b b ON a.id = b.x +WHERE a.val = 10 OR b.val = 300 +ORDER BY a.id, a.val, b.val; + +SELECT a.id, a.val, b.val FROM orexp_a a JOIN orexp_b b ON a.id = b.x +WHERE a.val = 10 OR b.val = 300 +ORDER BY a.id, a.val, b.val; + +SET or_expansion_limit = 0; +SELECT a.id, a.val, b.val FROM orexp_a a JOIN orexp_b b ON a.id = b.x +WHERE a.val = 10 OR b.val = 300 +ORDER BY a.id, a.val, b.val; + +-- Case C5: Non-flattened subquery over ordinary table with cross-table OR +-- Verifies expression_tree_walker is not called on RangeTblEntry nodes +CREATE TABLE orexp_c (id int, tier text); +CREATE TABLE orexp_d (cid int, val int); +INSERT INTO orexp_c VALUES (1, 'vip'), (2, 'std'); +INSERT INTO orexp_d VALUES (1, 10), (1, 20), (2, 5); + +SET or_expansion_limit = 8; +EXPLAIN (COSTS OFF) +SELECT c.id, s.n FROM orexp_c c + JOIN (SELECT cid, count(*) n FROM orexp_d GROUP BY cid) s ON s.cid = c.id +WHERE c.tier = 'vip' OR s.n > 20 +ORDER BY c.id; + +SELECT c.id, s.n FROM orexp_c c + JOIN (SELECT cid, count(*) n FROM orexp_d GROUP BY cid) s ON s.cid = c.id +WHERE c.tier = 'vip' OR s.n > 20 +ORDER BY c.id; + +SET or_expansion_limit = 0; +SELECT c.id, s.n FROM orexp_c c + JOIN (SELECT cid, count(*) n FROM orexp_d GROUP BY cid) s ON s.cid = c.id +WHERE c.tier = 'vip' OR s.n > 20 +ORDER BY c.id; + +DROP TABLE orexp_c; +DROP TABLE orexp_d; + +-- Case C6: Subquery over partitioned table (gate must reject OR expansion) +CREATE TABLE orexp_part (id int, d int) PARTITION BY RANGE (d); +CREATE TABLE orexp_part1 PARTITION OF orexp_part FOR VALUES FROM (0) TO (10); +CREATE TABLE orexp_part2 PARTITION OF orexp_part FOR VALUES FROM (10) TO (20); +INSERT INTO orexp_part VALUES (1, 5), (2, 15); + +SET or_expansion_limit = 8; +EXPLAIN (COSTS OFF) +SELECT a.id, s.d FROM orexp_a a, + (SELECT id, d FROM orexp_part GROUP BY id, d) s +WHERE a.id = s.id OR s.d = 15 +ORDER BY a.id, s.d; + +SELECT a.id, s.d FROM orexp_a a, + (SELECT id, d FROM orexp_part GROUP BY id, d) s +WHERE a.id = s.id OR s.d = 15 +ORDER BY a.id, s.d; + +SET or_expansion_limit = 0; +SELECT a.id, s.d FROM orexp_a a, + (SELECT id, d FROM orexp_part GROUP BY id, d) s +WHERE a.id = s.id OR s.d = 15 +ORDER BY a.id, s.d; + +DROP TABLE orexp_part; + +-- Clean up +RESET or_expansion_limit; +DROP TABLE orexp_a; +DROP TABLE orexp_b; -- 2.34.1
star_schema.sql
Description: application/sql
or_expansion_benchmark.sql
Description: application/sql
