Thread: [HACKERS] Improve OR conditions on joined columns.
I've a client interested enough in $SUBJECT that they're willing to
offer a bounty on it. An example of the pain is (working example attached):
create temp view denorm as
select f.*, d1.t t1, d2.t t2
from fact f
left join dim d1 on f1=d1.id
left join dim d2 on f2=d2.id
;
-- Fast
explain analyze select count(*) from denorm where 1 in (f1,f2);
explain analyze select count(*) from denorm where '1' in (t1);
-- Slow
explain analyze select count(*) from denorm where '1' in (t1,t2);
They currently work around this by doing a union:
select ... from denorm where t1 = '1'
union
select ... from denorm where t2 = '1'
... or depending on needs using IN instead of =.
AFAICT this can be transformed into a UNION (not all) if dim.id is
unique. Does the upper planner pathification make this any easier?
There's another transform using arrays that's possible as well (see
attached example); I believe that would work regardless of uniqueness.
Just to be clear; the OR by itself is not a problem (as shown by the
first fast query); it's the OR with the JOIN that's a problem.
--
Jim Nasby, Data Architect, Blue Treble Consulting, Austin TX
Experts in Analytics, Data Architecture and PostgreSQL
Data in Trouble? Get it in Treble! http://BlueTreble.com
855-TREBLE2 (855-873-2532)
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Attachment
Jim Nasby <Jim.Nasby@BlueTreble.com> writes:
> AFAICT this can be transformed into a UNION (not all) if dim.id is
> unique. Does the upper planner pathification make this any easier?
What I did in 9.6 is a first step. The next step, I think, is to
replace prepunion.c with something that can consider more than one
implementation path for a union.
Although ... actually, that may not be the bottleneck for what you're
after. The issue here is not so much discovering a clever plan for
a union as realizing that the query could be cast as a union in the
first place.
Maybe it'd be better to imagine this as something closer to planagg.c,
that is it knows how to apply a specific high-level optimization that
might or might not be a win, so it builds a path describing that and sees
if it looks cheaper than a path done the normal way. The fact that
we could even build a path describing a union is something that wasn't
there before 9.6, but maybe there's enough infrastructure for that now.
> There's another transform using arrays that's possible as well (see
> attached example); I believe that would work regardless of uniqueness.
That doesn't look terribly promising for automated application.
And I think it's really dependent on the exact shape of the OR
clause, which is an unpleasant limitation. Considering the amount
of work this will take to do at all, you'd want it to be pretty
general I think. I'm imagining something that would look for an
OR in which each clause referenced only one rel, then if it can
identify a way to re-unique-ify the result, split into a UNION
with an arm for each rel used in the OR. The nature of the
conditions in each OR arm don't seem to matter ... though probably
you'd have to insist on there not being volatile conditions anywhere
in the query, because they'd get evaluated too many times.
regards, tom lane
Re: [HACKERS] Improve OR conditions on joined columns (common starschema problem)
From
Jim Nasby
Date:
On 2/8/17 5:54 PM, Tom Lane wrote:
> Although ... actually, that may not be the bottleneck for what you're
> after. The issue here is not so much discovering a clever plan for
> a union as realizing that the query could be cast as a union in the
> first place.
Right; their current workaround is to manually write a UNION. That's
*significantly* faster than the OR.
> Maybe it'd be better to imagine this as something closer to planagg.c,
> that is it knows how to apply a specific high-level optimization that
> might or might not be a win, so it builds a path describing that and sees
> if it looks cheaper than a path done the normal way. The fact that
> we could even build a path describing a union is something that wasn't
> there before 9.6, but maybe there's enough infrastructure for that now.
It's encouraging that there's at least a template to follow there... If
there is missing infrastructure, is it likely to be major? My uninformed
guess would be that the pathification was the major hurdle.
>> There's another transform using arrays that's possible as well (see
>> attached example); I believe that would work regardless of uniqueness.
>
> That doesn't look terribly promising for automated application.
> And I think it's really dependent on the exact shape of the OR
> clause, which is an unpleasant limitation. Considering the amount
Not sure what you mean by shape; do you mean whether the OR conditions
are rels vs Consts or Vars?
> of work this will take to do at all, you'd want it to be pretty
> general I think. I'm imagining something that would look for an
> OR in which each clause referenced only one rel, then if it can
> identify a way to re-unique-ify the result, split into a UNION
> with an arm for each rel used in the OR. The nature of the
> conditions in each OR arm don't seem to matter ... though probably
> you'd have to insist on there not being volatile conditions anywhere
> in the query, because they'd get evaluated too many times.
In my experience, the common use case here is a large fact table that
joins to a number of dimension tables. If you can filter the large fact
table down to a fairly small size, those joins don't matter much. But if
a big chunk of your filter comes from the joins, you're in trouble.
UNION isn't really a great way to solve this problem because you still
end up doing a full join just to run the filter, but really all that you
need are the values from the dimension table(s) that you need for the
filter. IOW, change
WHERE t1 IN ('a','b') OR t2 IN ('c','d')
into
WHERE f1 IN (1,2) OR f2 IN (3,4)
(assuming a,b,c,d maps to 1,2,3,4)
BTW, there's an important caveat here: users generally do NOT want
duplicate rows from the fact table if the dimension table results aren't
unique. I thought my array solution was equivalent to what the JOINs
would do in that case but that's actually wrong. The array solution does
provide the behavior users generally want here though. JOIN is the
easiest tool to pick up for this, so it's what people gravitate to, but
I suspect most users would be happier with a construct that worked like
the array trick does, but was easier to accomplish.
I wonder if any other databases have come up with non-standard syntax to
do this.
--
Jim Nasby, Data Architect, Blue Treble Consulting, Austin TX
Experts in Analytics, Data Architecture and PostgreSQL
Data in Trouble? Get it in Treble! http://BlueTreble.com
855-TREBLE2 (855-873-2532)
Re: [HACKERS] Improve OR conditions on joined columns (common starschema problem)
From
Claudio Freire
Date:
On Thu, Feb 9, 2017 at 9:50 PM, Jim Nasby <Jim.Nasby@bluetreble.com> wrote:
> WHERE t1 IN ('a','b') OR t2 IN ('c','d')
>
> into
>
> WHERE f1 IN (1,2) OR f2 IN (3,4)
>
> (assuming a,b,c,d maps to 1,2,3,4)
>
> BTW, there's an important caveat here: users generally do NOT want duplicate
> rows from the fact table if the dimension table results aren't unique. I
> thought my array solution was equivalent to what the JOINs would do in that
> case but that's actually wrong. The array solution does provide the behavior
> users generally want here though. JOIN is the easiest tool to pick up for
> this, so it's what people gravitate to, but I suspect most users would be
> happier with a construct that worked like the array trick does, but was
> easier to accomplish.
>
> I wonder if any other databases have come up with non-standard syntax to do
> this.
What I've been doing is do those transforms (tn -> fn) in application
code. While it's a chore, the improvement in plans is usually well
worth the trouble.
IF there's a FK between fact and dimension tables, you can be certain
the transform will yield equivalent results, becuase you'll be certain
the joins don't duplicate rows.
So the transform should be rather general and useful.
If you have a join of the form:
a join b on a.f1 = b.id
Where a.f1 has an FK referencing b.id, and a filter on b X of any
form, you can turn the plan into:
with b_ids as (select id from b where X)
...
a join b on a.f1 = b.id and a.f1 in (select id from b_ids)
In order to be useful, the expected row count from b_ids should be rather small.
Re: [HACKERS] Improve OR conditions on joined columns (common star schema problem)
From
Tom Lane
Date:
Jim Nasby <Jim.Nasby@BlueTreble.com> writes:
> On 2/8/17 5:54 PM, Tom Lane wrote:
>> Maybe it'd be better to imagine this as something closer to planagg.c,
>> that is it knows how to apply a specific high-level optimization that
>> might or might not be a win, so it builds a path describing that and sees
>> if it looks cheaper than a path done the normal way. The fact that
>> we could even build a path describing a union is something that wasn't
>> there before 9.6, but maybe there's enough infrastructure for that now.
> It's encouraging that there's at least a template to follow there... If
> there is missing infrastructure, is it likely to be major? My uninformed
> guess would be that the pathification was the major hurdle.
I wrote a POC patch for this on a long airplane ride. It's not complete,
and I'm sure there are bugs as well, but it makes your example case
better. What I did about the de-duplication issue is to de-dup using
the CTIDs of all baserels in the query. This means the optimization
is only applicable to cases where all the rels have CTIDs ... but other
methods such as inspecting unique keys ain't gonna work for non-table
rels either, so I think this is about the best we can hope for.
However, I did not understand your point about:
> BTW, there's an important caveat here: users generally do NOT want
> duplicate rows from the fact table if the dimension table results aren't
> unique.
so maybe we should be thinking about some other way entirely?
Anyway, what's attached below produces this on your example query:
Aggregate (cost=38.12..38.13 rows=1 width=8) (actual time=0.158..0.158 rows=1 loops=1)
-> Result (cost=38.03..38.11 rows=4 width=0) (actual time=0.151..0.155 rows=3 loops=1)
-> Unique (cost=38.03..38.07 rows=4 width=18) (actual time=0.150..0.154 rows=3 loops=1)
-> Sort (cost=38.03..38.04 rows=4 width=18) (actual time=0.150..0.151 rows=4 loops=1)
Sort Key: f.ctid, d1.ctid, d2.ctid
Sort Method: quicksort Memory: 25kB
-> Append (cost=4.85..37.99 rows=4 width=18) (actual time=0.070..0.106 rows=4 loops=1)
-> Nested Loop Left Join (cost=4.85..19.00 rows=2 width=18) (actual time=0.069..0.075
rows=2loops=1)
-> Nested Loop (cost=4.57..18.37 rows=2 width=16) (actual time=0.035..0.038 rows=2
loops=1)
-> Index Scan using dim_t_key on dim d1 (cost=0.28..8.29 rows=1 width=10)
(actualtime=0.009..0.009 rows=1 loops=1)
Index Cond: ('1'::text = t)
-> Bitmap Heap Scan on fact f (cost=4.30..10.05 rows=2 width=14) (actual
time=0.023..0.025rows=2 loops=1)
Recheck Cond: (f1 = d1.s)
Heap Blocks: exact=2
-> Bitmap Index Scan on f_f1 (cost=0.00..4.29 rows=2 width=0) (actual
time=0.016..0.016rows=2 loops=1)
Index Cond: (f1 = d1.s)
-> Index Scan using dim_pkey on dim d2 (cost=0.28..0.31 rows=1 width=10) (actual
time=0.016..0.017rows=0 loops=2)
Index Cond: (f.f2 = s)
-> Nested Loop Left Join (cost=4.85..19.00 rows=2 width=18) (actual time=0.025..0.029
rows=2loops=1)
-> Nested Loop (cost=4.57..18.37 rows=2 width=16) (actual time=0.022..0.025 rows=2
loops=1)
-> Index Scan using dim_t_key on dim d2 (cost=0.28..8.29 rows=1 width=10)
(actualtime=0.003..0.003 rows=1 loops=1)
Index Cond: ('1'::text = t)
-> Bitmap Heap Scan on fact f (cost=4.30..10.05 rows=2 width=14) (actual
time=0.017..0.019rows=2 loops=1)
Recheck Cond: (f2 = d2.s)
Heap Blocks: exact=2
-> Bitmap Index Scan on f_f2 (cost=0.00..4.29 rows=2 width=0) (actual
time=0.014..0.014rows=2 loops=1)
Index Cond: (f2 = d2.s)
-> Index Scan using dim_pkey on dim d1 (cost=0.28..0.31 rows=1 width=10) (actual
time=0.001..0.001rows=0 loops=2)
Index Cond: (f.f1 = s)
The main remaining piece of work here is that, as you can see from the
above, it fails to eliminate joins to tables that we don't actually need
in a particular UNION arm. This is because the references to those
tables' ctid columns prevent analyzejoins.c from removing the joins.
I've thought about ways to deal with that but haven't come up with
anything that wasn't pretty ugly and/or invasive.
regards, tom lane
diff --git a/src/backend/optimizer/plan/Makefile b/src/backend/optimizer/plan/Makefile
index 88a9f7ff8c0177b920b60900276335022ae0e813..1db6bd55278cd4e3072e9c1ea7b2e648a01e9eed 100644
*** a/src/backend/optimizer/plan/Makefile
--- b/src/backend/optimizer/plan/Makefile
*************** top_builddir = ../../../..
*** 13,18 ****
include $(top_builddir)/src/Makefile.global
OBJS = analyzejoins.o createplan.o initsplan.o planagg.o planmain.o planner.o \
! setrefs.o subselect.o
include $(top_srcdir)/src/backend/common.mk
--- 13,18 ----
include $(top_builddir)/src/Makefile.global
OBJS = analyzejoins.o createplan.o initsplan.o planagg.o planmain.o planner.o \
! planunionor.o setrefs.o subselect.o
include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 881742f46b66d7cfcdf5161f93277a57ff39307c..2a4dff6c87de50c7f43745df182399cb39f0da56 100644
*** a/src/backend/optimizer/plan/planner.c
--- b/src/backend/optimizer/plan/planner.c
*************** grouping_planner(PlannerInfo *root, bool
*** 1496,1501 ****
--- 1496,1502 ----
List *activeWindows = NIL;
List *rollup_lists = NIL;
List *rollup_groupclauses = NIL;
+ List *union_or_subpaths;
standard_qp_extra qp_extra;
/* A recursive query should always have setOperations */
*************** grouping_planner(PlannerInfo *root, bool
*** 1656,1661 ****
--- 1657,1670 ----
preprocess_minmax_aggregates(root, tlist);
/*
+ * Preprocess join OR clauses that might be better handled as UNIONs.
+ * This likewise needs to be close to the query_planner() call. But
+ * it doesn't matter which of preprocess_minmax_aggregates() and this
+ * function we call first, because they treat disjoint sets of cases.
+ */
+ union_or_subpaths = split_join_or_clauses(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
* hard limit overall, it doesn't apply if the query has any
*************** grouping_planner(PlannerInfo *root, bool
*** 1689,1694 ****
--- 1698,1711 ----
standard_qp_callback, &qp_extra);
/*
+ * If we found any way to convert a join OR clause to a union, finish
+ * up generating the path(s) for that, and add them into the topmost
+ * scan/join relation.
+ */
+ if (union_or_subpaths)
+ finish_union_or_paths(root, current_rel, union_or_subpaths);
+
+ /*
* Convert the query's result tlist into PathTarget format.
*
* Note: it's desirable to not do this till after query_planner(),
diff --git a/src/backend/optimizer/plan/planunionor.c b/src/backend/optimizer/plan/planunionor.c
index ...ce744d6b47c5ca3eb119f42017e1513c3941b585 .
*** a/src/backend/optimizer/plan/planunionor.c
--- b/src/backend/optimizer/plan/planunionor.c
***************
*** 0 ****
--- 1,596 ----
+ /*-------------------------------------------------------------------------
+ *
+ * planunionor.c
+ * Consider whether join OR clauses can be converted to UNION queries.
+ *
+ * This module looks for OR clauses whose arms each reference a single
+ * query relation (but not all the same rel), and tries to generate a path
+ * representing conversion of such an OR clause into a UNION operation.
+ * For example,
+ * SELECT ... FROM a, b WHERE (cond-on-A OR cond-on-B) AND other-conds
+ * can be implemented as
+ * SELECT ... FROM a, b WHERE cond-on-A AND other-conds
+ * UNION
+ * SELECT ... FROM a, b WHERE cond-on-B AND other-conds
+ * given a suitable definition of "UNION" (one that won't merge rows that
+ * would have been separate in the original query output). Since this change
+ * converts join clauses into restriction clauses, the modified query can be
+ * much faster to run than the original, despite the duplication of effort
+ * involved and the extra UNION processing. It's particularly useful for
+ * star-schema queries where the OR arms reference different dimension tables;
+ * each separated query may be able to remove joins to all but one dimension
+ * table.
+ *
+ * We must insist that the WHERE and JOIN/ON clauses contain no volatile
+ * functions, because of the likelihood that qual clauses will be evaluated
+ * more times than a naive programmer would expect. We need not restrict
+ * the SELECT's tlist, because that will be evaluated after the UNION.
+ *
+ * The current implementation of the UNION step is to de-duplicate using
+ * row CTIDs. A big limitation is that this only works on plain relations,
+ * and not for instance on foreign tables. Another problem is that we can
+ * only de-duplicate by sort/unique, not hashing; but that could be fixed
+ * if we write a hash opclass for TID.
+ *
+ *
+ * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ * src/backend/optimizer/plan/planunionor.c
+ *
+ *-------------------------------------------------------------------------
+ */
+ #include "postgres.h"
+
+ #include "access/sysattr.h"
+ #include "catalog/pg_class.h"
+ #include "catalog/pg_operator.h"
+ #include "catalog/pg_type.h"
+ #include "miscadmin.h"
+ #include "nodes/makefuncs.h"
+ #include "optimizer/clauses.h"
+ #include "optimizer/cost.h"
+ #include "optimizer/pathnode.h"
+ #include "optimizer/planmain.h"
+ #include "optimizer/prep.h"
+ #include "optimizer/subselect.h"
+ #include "optimizer/tlist.h"
+ #include "optimizer/var.h"
+
+
+ static bool is_suitable_join_or_clause(BoolExpr *orclause, List **relids);
+ static bool is_query_safe_for_union_or_transform(PlannerInfo *root,
+ Relids allbaserels);
+ static List *create_union_or_subpaths(PlannerInfo *root, BoolExpr *orclause,
+ int n, List *armrelids, Relids allbaserels);
+ static void union_or_qp_callback(PlannerInfo *root, void *extra);
+
+
+ /*
+ * split_join_or_clauses - create paths based on splitting join OR clauses
+ *
+ * This should be called by grouping_planner() just before it's ready to call
+ * query_planner(), because we generate simplified join paths by cloning the
+ * planner's state and invoking query_planner() on a modified version of
+ * the query parsetree. Thus, all preprocessing needed before query_planner()
+ * must already be done. Note however that we repeat reduce_outer_joins()
+ * because of the possibility that the simplified WHERE clause allows reduction
+ * of an outer join to inner-join form. That's okay for now, but maybe we
+ * should move the reduce_outer_joins() call into query_planner()?
+ *
+ * The result is a list (one entry per potential join OR path) of sublists of
+ * best paths for the inputs to the UNION step. Adding the UNION processing
+ * is pretty mechanical, but we can't do it until we have a RelOptInfo for the
+ * top-level join rel.
+ */
+ List *
+ split_join_or_clauses(PlannerInfo *root)
+ {
+ List *results = NIL;
+ Query *parse = root->parse;
+ Relids allbaserels = NULL;
+ bool checked_query = false;
+ ListCell *lc;
+ int n;
+
+ /*
+ * At least for now, we restrict this optimization to plain SELECTs.
+ */
+ if (parse->commandType != CMD_SELECT ||
+ parse->rowMarks ||
+ parse->setOperations)
+ return NIL;
+
+ /*
+ * Reject if query contains any CTEs; copying them would break
+ * single-evaluation semantics. (In principle we could arrange for all
+ * UNION arms to read from a single instance of a CTE, but that's an
+ * improvement for another day, especially since we have no way to de-dup
+ * CTE outputs anyway.)
+ */
+ if (parse->cteList)
+ return NIL;
+
+ /*
+ * The query must reference multiple tables, else we certainly aren't
+ * going to find any suitable OR clauses. Do a quick check that there's
+ * more than one RTE.
+ */
+ if (list_length(parse->rtable) < 2)
+ return NIL;
+
+ /*
+ * Scan the top-level WHERE clause looking for suitable OR clauses, and
+ * for each one, generate paths for the UNION input sub-queries. There
+ * might be more than one suitable OR clause, in which case we can try the
+ * transformation for each one of them separately and add that list of
+ * paths to the results.
+ *
+ * XXX we should also search the JOIN/ON clauses of any top-level inner
+ * JOIN nodes, since those are semantically equivalent to WHERE. But it's
+ * hard to see how to do that without either copying the whole JOIN tree
+ * in advance or repeating the search after copying, and neither of those
+ * options seems attractive.
+ */
+ n = 0;
+ foreach(lc, (List *) parse->jointree->quals)
+ {
+ Node *qual = (Node *) lfirst(lc);
+ List *armrelids;
+
+ if (or_clause(qual) &&
+ is_suitable_join_or_clause((BoolExpr *) qual, &armrelids))
+ {
+ List *subpaths;
+
+ /*
+ * Check that the query as a whole is safe for this optimization.
+ * We only need to do this once, but it's somewhat expensive, so
+ * don't do it till we find a candidate OR clause. This is also a
+ * good time to compute the set of baserels in the query, which
+ * we'll need at each step.
+ */
+ if (!checked_query)
+ {
+ allbaserels = get_relids_in_jointree((Node *) parse->jointree,
+ false);
+ if (!is_query_safe_for_union_or_transform(root, allbaserels))
+ return NIL;
+ checked_query = true;
+ }
+ /* OK, transform the query and create a list of sub-paths */
+ subpaths = create_union_or_subpaths(root, (BoolExpr *) qual,
+ n, armrelids, allbaserels);
+ results = lappend(results, subpaths);
+ }
+ n++;
+ }
+
+ return results;
+ }
+
+ /*
+ * Finish constructing Paths representing the UNION implementation of join
+ * OR clause(s), and attach them to "joinrel", which is the final scan/join
+ * relation returned by query_planner() for the conventional implementation of
+ * the query. "union_or_subpaths" is the output of split_join_or_clauses().
+ */
+ void
+ finish_union_or_paths(PlannerInfo *root, RelOptInfo *joinrel,
+ List *union_or_subpaths)
+ {
+ Relids allbaserels;
+ ListCell *lc;
+
+ /*
+ * XXX better to pass this forward from split_join_or_clauses? Seems like
+ * we could get a different answer if join removal happened in main query,
+ * and that would probably be bad.
+ */
+ allbaserels = get_relids_in_jointree((Node *) root->parse->jointree, false);
+
+ /* This loop iterates once per splittable OR clause */
+ foreach(lc, union_or_subpaths)
+ {
+ List *subpaths = (List *) lfirst(lc);
+ Path *appendpath;
+ List *uniq_operators;
+ List *uniq_exprs;
+ int brelid;
+ UniquePath *pathnode;
+ Path sort_path; /* dummy for result of cost_sort */
+ int numCols;
+
+ /* Generate Append path combining the sub-paths for one UNION */
+ appendpath = (Path *) create_append_path(joinrel, subpaths, NULL, 0);
+
+ /*
+ * The Append path's pathtarget has to match what is actually coming
+ * out of the subpaths, since Append can't project. Assume that they
+ * all generate equivalent pathtargets.
+ *
+ * XXX this is going to be wrong when join removal removes some vars?
+ */
+ appendpath->pathtarget =
+ copy_pathtarget(((Path *) linitial(subpaths))->pathtarget);
+
+ /*
+ * Make the operator and expression lists needed for the Unique path.
+ */
+ uniq_operators = uniq_exprs = NIL;
+ brelid = -1;
+ while ((brelid = bms_next_member(allbaserels, brelid)) >= 0)
+ {
+ Var *var;
+
+ var = makeVar(brelid,
+ SelfItemPointerAttributeNumber,
+ TIDOID,
+ -1,
+ InvalidOid,
+ 0);
+ uniq_operators = lappend_oid(uniq_operators, TIDEqualOperator);
+ uniq_exprs = lappend(uniq_exprs, var);
+ }
+
+ /*
+ * Generate a Unique path representing the de-duplication step. For
+ * now, we can only consider sort+unique implementation.
+ *
+ * XXX maybe refactor to share some code with create_unique_path()?
+ */
+ pathnode = makeNode(UniquePath);
+
+ pathnode->path.pathtype = T_Unique;
+ pathnode->path.parent = joinrel;
+ pathnode->path.pathtarget = appendpath->pathtarget;
+ pathnode->path.param_info = appendpath->param_info;
+ pathnode->path.parallel_aware = false;
+ pathnode->path.parallel_safe = joinrel->consider_parallel &&
+ appendpath->parallel_safe;
+ pathnode->path.parallel_workers = appendpath->parallel_workers;
+
+ /*
+ * Treat the output as unsorted, since it almost certainly doesn't
+ * match any useful pathkeys.
+ */
+ pathnode->path.pathkeys = NIL;
+
+ pathnode->subpath = appendpath;
+ pathnode->in_operators = uniq_operators;
+ pathnode->uniq_exprs = uniq_exprs;
+
+ /* Estimate number of output rows */
+ pathnode->path.rows = appendpath->rows;
+ numCols = list_length(uniq_exprs);
+
+ /*
+ * Estimate cost for sort+unique implementation
+ */
+ cost_sort(&sort_path, root, NIL,
+ appendpath->total_cost,
+ appendpath->rows,
+ appendpath->pathtarget->width,
+ 0.0,
+ work_mem,
+ -1.0);
+
+ /*
+ * Charge one cpu_operator_cost per comparison per input tuple. We
+ * assume all columns get compared at most of the tuples. (XXX
+ * probably this is an overestimate.) This should agree with
+ * create_unique_path.
+ */
+ sort_path.total_cost += cpu_operator_cost * appendpath->rows * numCols;
+
+ pathnode->umethod = UNIQUE_PATH_SORT;
+
+ pathnode->path.startup_cost = sort_path.startup_cost;
+ pathnode->path.total_cost = sort_path.total_cost;
+
+ /* Attach it to the joinrel */
+ add_path(joinrel, (Path *) pathnode);
+ }
+
+ /* We need to refigure which is the cheapest path */
+ set_cheapest(joinrel);
+ }
+
+ /*
+ * Is this OR clause a suitable clause for splitting?
+ *
+ * Each of its arms must reference just one rel, and they must not all be
+ * the same rel.
+ * On success, pass back a list of the relids referenced by each OR arm,
+ * so we don't have to repeat the pull_varnos() work later.
+ */
+ static bool
+ is_suitable_join_or_clause(BoolExpr *orclause, List **relids)
+ {
+ bool ok = false;
+ List *relidlist = NIL;
+ int firstrelid = 0;
+ ListCell *lc;
+
+ *relids = NIL; /* prevent uninitialized-variable warnings */
+ foreach(lc, orclause->args)
+ {
+ Node *qual = (Node *) lfirst(lc);
+ Relids varnos = pull_varnos(qual);
+ int relid;
+
+ if (!bms_get_singleton_member(varnos, &relid))
+ return false; /* this arm fails the sine qua non */
+ if (relidlist == NIL)
+ firstrelid = relid;
+ else if (firstrelid != relid)
+ ok = true; /* arms reference more than one relid */
+ relidlist = lappend_int(relidlist, relid);
+ }
+ *relids = relidlist;
+ return ok;
+ }
+
+ /*
+ * Is query as a whole safe to apply union OR transformation to?
+ * This checks relatively-expensive conditions that we don't want to
+ * worry about until we've found a candidate OR clause.
+ */
+ static bool
+ is_query_safe_for_union_or_transform(PlannerInfo *root, Relids allbaserels)
+ {
+ Query *parse = root->parse;
+ ListCell *lc;
+ int relid;
+
+ /*
+ * Must not have any volatile functions in FROM or WHERE (see notes at
+ * head of file).
+ */
+ if (contain_volatile_functions((Node *) parse->jointree))
+ return false;
+
+ /*
+ * We insist that all baserels used in the query be plain relations, so
+ * that we can use their ctids as unique row identifiers in the UNION
+ * step. One could imagine ways to relax this later, for instance by
+ * forcibly adding WITH ORDINALITY to function RTEs. We'd have to examine
+ * each RTE anyway, though, to check for volatile functions.
+ */
+ relid = 0;
+ foreach(lc, parse->rtable)
+ {
+ RangeTblEntry *rte = (RangeTblEntry *) lfirst(lc);
+
+ relid++;
+
+ /* ignore RTEs that aren't referenced baserels */
+ if (!bms_is_member(relid, allbaserels))
+ continue;
+
+ /* fail if not plain rel */
+ if (rte->rtekind != RTE_RELATION)
+ return false;
+ /* fail if it doesn't have CTIDs */
+ if (rte->relkind != RELKIND_RELATION &&
+ rte->relkind != RELKIND_MATVIEW)
+ return false;
+
+ /* disallow TABLESAMPLE (might be okay if repeatable?) */
+ if (rte->tablesample)
+ return false;
+
+ /* check for volatiles in security barrier quals */
+ if (contain_volatile_functions((Node *) rte->securityQuals))
+ return false;
+ }
+
+ /* OK to proceed */
+ return true;
+ }
+
+ /*
+ * Split the query and the given OR clause into one UNION arm per relation
+ * mentioned in the OR clause, and make a list of best paths for the UNION
+ * arms. (Since the UNION step will lose any ordering or fast-start
+ * properties of the paths, there's no need to consider any but the
+ * cheapest-total path for each arm; hence it's okay to return just one path
+ * per arm.)
+ * "n" is the OR clause's index in the query's WHERE list.
+ * "armrelids" is the OR-arm-to-referenced-rel mapping.
+ * "allbaserels" is the relids of all baserels used in the query. We use
+ * this to build the list of CTID variables we'll need to de-duplicate.
+ */
+ static List *
+ create_union_or_subpaths(PlannerInfo *root, BoolExpr *orclause,
+ int n, List *armrelids, Relids allbaserels)
+ {
+ List *subpaths = NIL;
+ Relids orrels;
+ int relid;
+ ListCell *lc;
+ ListCell *lc2;
+
+ /*
+ * There might be multiple OR arms referring to the same rel, which we
+ * should combine into a restriction OR clause. So first identify the set
+ * of rels used in the OR.
+ */
+ orrels = NULL;
+ foreach(lc, armrelids)
+ orrels = bms_add_member(orrels, lfirst_int(lc));
+
+ /* Now, for each such rel, generate a path for a UNION arm */
+ while ((relid = bms_first_member(orrels)) >= 0)
+ {
+ List *orarms;
+ PlannerInfo *subroot;
+ Query *parse;
+ List *subquery_quals;
+ List *tlist;
+ int brelid;
+ bool hasOuterJoins;
+ RelOptInfo *final_rel;
+ Path *subpath;
+ int k;
+ ListCell *prev;
+
+ /* Extract the OR arms for this rel, making copies for safety */
+ orarms = NIL;
+ forboth(lc, orclause->args, lc2, armrelids)
+ {
+ Node *qual = (Node *) lfirst(lc);
+ int qualrelid = lfirst_int(lc2);
+
+ if (qualrelid == relid)
+ orarms = lappend(orarms, copyObject(qual));
+ }
+ Assert(orarms != NIL);
+ if (list_length(orarms) == 1)
+ {
+ /*
+ * When there's just a single arm for this rel (the typical case),
+ * it goes directly into the subquery's WHERE list. But it might
+ * be a sub-AND, in which case we must flatten it into a qual list
+ * to preserve AND/OR flatness.
+ */
+ orarms = make_ands_implicit((Expr *) linitial(orarms));
+ }
+ else
+ {
+ /*
+ * When there's more than one arm, convert back to an OR clause.
+ * No flatness worries here, the arms were already valid OR-list
+ * elements.
+ */
+ orarms = list_make1(make_orclause(orarms));
+ }
+
+ /* Clone the planner's state */
+ subroot = (PlannerInfo *) palloc(sizeof(PlannerInfo));
+ memcpy(subroot, root, sizeof(PlannerInfo));
+ subroot->parse = parse = (Query *) copyObject(root->parse);
+ /* XXX likely there's more to do here */
+
+ /* Probably should drop any ordering, limit clauses? */
+ subroot->tuple_fraction = 1.0;
+ subroot->limit_tuples = -1.0;
+
+ /*
+ * Remove the subquery's copy of the original OR clause, which we
+ * identify by its index in the WHERE clause list.
+ */
+ subquery_quals = (List *) parse->jointree->quals;
+ k = 0;
+ prev = NULL;
+ foreach(lc, subquery_quals)
+ {
+ if (k == n)
+ {
+ subquery_quals = list_delete_cell(subquery_quals, lc, prev);
+ break;
+ }
+ k++;
+ prev = lc;
+ }
+
+ /* And instead add the qual or quals we extracted from the OR clause */
+ subquery_quals = list_concat(subquery_quals, orarms);
+ parse->jointree->quals = (Node *) subquery_quals;
+
+ /*
+ * We must add all the baserels' CTID columns to the subquery's tlist
+ * so that they'll be available for de-duplication purposes.
+ *
+ * XXX need a way to prevent these from preventing join removal.
+ */
+ tlist = (List *) copyObject(root->processed_tlist);
+ brelid = -1;
+ while ((brelid = bms_next_member(allbaserels, brelid)) >= 0)
+ {
+ Var *var;
+ char resname[32];
+ TargetEntry *tle;
+
+ var = makeVar(brelid,
+ SelfItemPointerAttributeNumber,
+ TIDOID,
+ -1,
+ InvalidOid,
+ 0);
+ snprintf(resname, sizeof(resname), "union_ctid%u", brelid);
+ tle = makeTargetEntry((Expr *) var,
+ list_length(tlist) + 1,
+ pstrdup(resname),
+ true);
+ tlist = lappend(tlist, tle);
+
+ }
+ subroot->processed_tlist = tlist;
+
+ /* Re-apply reduce_outer_joins() in case we can now reduce some */
+ /* (XXX would be better if this just got moved into query_planner) */
+ hasOuterJoins = false;
+ foreach(lc, parse->rtable)
+ {
+ RangeTblEntry *rte = (RangeTblEntry *) lfirst(lc);
+
+ if (rte->rtekind == RTE_JOIN)
+ {
+ if (IS_OUTER_JOIN(rte->jointype))
+ {
+ hasOuterJoins = true;
+ break;
+ }
+ }
+ }
+ if (hasOuterJoins)
+ reduce_outer_joins(subroot);
+
+ /* Plan the modified query */
+ final_rel = query_planner(subroot, subroot->processed_tlist,
+ union_or_qp_callback, NULL);
+
+ /*
+ * Since we didn't go through subquery_planner() to handle the
+ * subquery, we have to do some of the same cleanup it would do, in
+ * particular cope with params and initplans used within this
+ * subquery. (This won't matter if we end up not using the subplan.)
+ */
+ SS_identify_outer_params(subroot);
+ SS_charge_for_initplans(subroot, final_rel);
+
+ /*
+ * Get the cheapest-total path for the subquery; there's little value
+ * in considering any others.
+ */
+ subpath = final_rel->cheapest_total_path;
+ Assert(subpath);
+
+ /* Add cheapest-total path to subpaths list */
+ subpaths = lappend(subpaths, subpath);
+ }
+
+ return subpaths;
+ }
+
+ /*
+ * Compute query_pathkeys and other pathkeys during plan generation
+ */
+ static void
+ union_or_qp_callback(PlannerInfo *root, void *extra)
+ {
+ /*
+ * Since the output of the subquery is going to go through a UNION step
+ * that destroys ordering, there's little need to worry about what its
+ * output order is. Hence, don't bother telling it about pathkeys that
+ * might apply to these later execution steps.
+ */
+ root->group_pathkeys = NIL;
+ root->window_pathkeys = NIL;
+ root->distinct_pathkeys = NIL;
+ root->sort_pathkeys = NIL;
+ root->query_pathkeys = NIL;
+ }
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index 94ef84bca9cba62d80187aa174947c74ace525f1..4743a0ca2c58946390d77f6c5e6b6870b0ce6720 100644
*** a/src/include/optimizer/planmain.h
--- b/src/include/optimizer/planmain.h
*************** extern RelOptInfo *query_planner(Planner
*** 45,50 ****
--- 45,57 ----
extern void preprocess_minmax_aggregates(PlannerInfo *root, List *tlist);
/*
+ * prototypes for plan/planunionor.c
+ */
+ extern List *split_join_or_clauses(PlannerInfo *root);
+ extern void finish_union_or_paths(PlannerInfo *root, RelOptInfo *joinrel,
+ List *union_or_subpaths);
+
+ /*
* prototypes for plan/createplan.c
*/
extern Plan *create_plan(PlannerInfo *root, Path *best_path);
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Improve OR conditions on joined columns (common starschema problem)
From
David Rowley
Date:
On 12 February 2017 at 13:30, Tom Lane <tgl@sss.pgh.pa.us> wrote: > I wrote a POC patch for this on a long airplane ride. It's not complete, > and I'm sure there are bugs as well, but it makes your example case > better. What I did about the de-duplication issue is to de-dup using > the CTIDs of all baserels in the query. This means the optimization > is only applicable to cases where all the rels have CTIDs ... but other > methods such as inspecting unique keys ain't gonna work for non-table > rels either, so I think this is about the best we can hope for. > However, I did not understand your point about: This is very interesting. Couldn't this be even more generic and instead of looking at just the jointree quals, also look at the join conditions too, as I think you can use this to also transforms queries such as: select * from t1 inner join t2 on t1.a = t2.a or t1.b = t2.b; I imagine you'd also want an enable_unionor GUC which can be used to disable this for when the planner makes a poor choice. -- David Rowley http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training & Services
Re: [HACKERS] Improve OR conditions on joined columns (common star schema problem)
From
Tom Lane
Date:
David Rowley <david.rowley@2ndquadrant.com> writes:
> This is very interesting. Couldn't this be even more generic and
> instead of looking at just the jointree quals, also look at the join
> conditions too, as I think you can use this to also transforms queries
> such as:
The hard part of that is to remember exactly where you need to do surgery
on the querytree to replace the OR clause, keeping in mind that a tree
copy step is going to happen in between first searching for the OR and
doing the replacement. I'm sure it's soluble but it would've involved
more complexity than I felt justified for a POC.
> I imagine you'd also want an enable_unionor GUC which can be used to
> disable this for when the planner makes a poor choice.
It's not so much poor choices as the cost of the optimization attempt ---
if there's a K-relation OR clause, this will increase the cost of planning
by a factor approaching K+1, whether or not you get a better plan out of
it. I ran the regression tests with some instrumentation and determined
that this logic fires a dozen or two times, and fails to produce a plan
that looks cheaper than the standard plan in any of those cases. So if we
go down this road, not only do we need a GUC but I suspect it had better
default to off; only people using star schemas are really likely to get a
win out of it.
Maybe we could improve that situation by applying some heuristics that
prevent the optimization from being attempted unless it's more likely to
produce a win. But I'm not sure what that would look like. We have to
make the decision pretty early and without a lot of information. As an
example, Jim's case fails completely if we don't do the transformation
before reduce_outer_joins, because one of the things that *has* to happen
to get a desirable plan is to recognize that the extracted restriction
clause allows the left join to the dimension table to be simplified to an
inner join.
Having written the POC, I find myself not terribly satisfied with it.
It seems brute-force and not at all integrated with the rest of the
planner. Still, asking for integration with the existing UNION planning
is probably silly, since that really needs to be thrown away and rewritten.
Maybe this is a reasonable way forward until we get a clearer view of
what that area needs to look like.
regards, tom lane
Re: [HACKERS] Improve OR conditions on joined columns (common starschema problem)
From
David Rowley
Date:
On 13 February 2017 at 06:32, Tom Lane <tgl@sss.pgh.pa.us> wrote: > It's not so much poor choices as the cost of the optimization attempt --- > if there's a K-relation OR clause, this will increase the cost of planning > by a factor approaching K+1, whether or not you get a better plan out of > it. I ran the regression tests with some instrumentation and determined > that this logic fires a dozen or two times, and fails to produce a plan > that looks cheaper than the standard plan in any of those cases. So if we > go down this road, not only do we need a GUC but I suspect it had better > default to off; only people using star schemas are really likely to get a > win out of it. I always try to shy away from assuming that the regression test suite is a good reflection of a real world set of queries. It's full of tests for edge cases that are rarely seen in reality. FWIW I did a similar experiment with unique joins and was disappointed to see that it didn't apply in more cases. Yet I've worked with OLTP applications since 2005, and I struggle to recall any many:many joins at all. Perhaps this optimisation is a candidate for only being applied when some sort of planner_strength GUC (as mentioned in FOSDEM developer meeting in 2016) reaches some threshold. There's certainly already some planner smarts that can be skipped when such a GUC is set to a lower level (e.g join removal). We could likely save many cycles if we had the ability to re-plan queries where total_cost > X with more smarts enabled. -- David Rowley http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training & Services
Re: [HACKERS] Improve OR conditions on joined columns (common starschema problem)
From
Jim Nasby
Date:
On 2/12/17 5:06 PM, David Rowley wrote: > Yet I've worked with OLTP applications > since 2005, and I struggle to recall any many:many joins at all. Interesting... I've run across it numerous times. In any case, for OLTP there's other things you can do fairly easily. > Perhaps this optimisation is a candidate for only being applied when > some sort of planner_strength GUC (as mentioned in FOSDEM developer > meeting in 2016) reaches some threshold. There's certainly already > some planner smarts that can be skipped when such a GUC is set to a > lower level (e.g join removal). We could likely save many cycles if we > had the ability to re-plan queries where total_cost > X with more > smarts enabled. Yeah, I strongly suspect some kind of "multi-stage" planner would be a big win. As for the POC, that's the same kind of plan I'm seeing IRL: a nested loop gets used essentially to do the lookup of dimension text to dimension ID. I'm wondering if there's any tricks that could be applied on the sort since it's dealing with CTIDs. I do think it'd be even better if we had the ability to do that lookup as part of planning, so you could discover the exact stats for the relevant ID values, but that's even more involved. -- Jim Nasby, Data Architect, Blue Treble Consulting, Austin TX Experts in Analytics, Data Architecture and PostgreSQL Data in Trouble? Get it in Treble! http://BlueTreble.com 855-TREBLE2 (855-873-2532)
Re: [HACKERS] Improve OR conditions on joined columns (common star schema problem)
From
Tom Lane
Date:
I wrote:
> The main remaining piece of work here is that, as you can see from the
> above, it fails to eliminate joins to tables that we don't actually need
> in a particular UNION arm. This is because the references to those
> tables' ctid columns prevent analyzejoins.c from removing the joins.
> I've thought about ways to deal with that but haven't come up with
> anything that wasn't pretty ugly and/or invasive.
I thought of a way that wasn't too awful, which was to inject the requests
for CTID columns only after we've done join removal. The attached v2
patch produces this for your test case:
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=36.84..36.85 rows=1 width=8) (actual time=0.075..0.075 rows=1 loops=1)
-> Result (cost=36.77..36.83 rows=4 width=0) (actual time=0.069..0.073 rows=3 loops=1)
-> Unique (cost=36.77..36.79 rows=4 width=6) (actual time=0.069..0.072 rows=3 loops=1)
-> Sort (cost=36.77..36.78 rows=4 width=6) (actual time=0.068..0.069 rows=4 loops=1)
Sort Key: f.ctid
Sort Method: quicksort Memory: 25kB
-> Append (cost=4.57..36.73 rows=4 width=6) (actual time=0.018..0.033 rows=4 loops=1)
-> Nested Loop (cost=4.57..18.37 rows=2 width=6) (actual time=0.018..0.020 rows=2 loops=1)
-> Index Scan using dim_t_key on dim d1 (cost=0.28..8.29 rows=1 width=10) (actual
time=0.005..0.005rows=1 loops=1)
Index Cond: ('1'::text = t)
-> Bitmap Heap Scan on fact f (cost=4.30..10.05 rows=2 width=14) (actual
time=0.010..0.012rows=2 loops=1)
Recheck Cond: (f1 = d1.s)
Heap Blocks: exact=2
-> Bitmap Index Scan on f_f1 (cost=0.00..4.29 rows=2 width=0) (actual
time=0.006..0.006rows=2 loops=1)
Index Cond: (f1 = d1.s)
-> Nested Loop (cost=4.57..18.37 rows=2 width=6) (actual time=0.009..0.011 rows=2 loops=1)
-> Index Scan using dim_t_key on dim d2 (cost=0.28..8.29 rows=1 width=10) (actual
time=0.003..0.003rows=1 loops=1)
Index Cond: ('1'::text = t)
-> Bitmap Heap Scan on fact f (cost=4.30..10.05 rows=2 width=14) (actual
time=0.005..0.006rows=2 loops=1)
Recheck Cond: (f2 = d2.s)
Heap Blocks: exact=2
-> Bitmap Index Scan on f_f2 (cost=0.00..4.29 rows=2 width=0) (actual
time=0.003..0.003rows=2 loops=1)
Index Cond: (f2 = d2.s)
Planning time: 0.732 ms
Execution time: 0.156 ms
(25 rows)
I think this might be code-complete, modulo the question of whether we
want an enabling GUC for it. I'm still concerned about the question
of whether it adds more planning time than it's worth for most users.
(Obviously it needs some regression test cases too, and a lot more
real-world testing than I've given it.)
One point that could use further review is whether the de-duplication
algorithm is actually correct. I'm only about 95% convinced by the
argument I wrote in planunionor.c's header comment.
Potential future work includes finding join ORs in upper-level INNER JOIN
ON clauses, and improving matters so we can do the unique-ification with
hashing as well as sorting. I don't think either of those things has to
be in the first commit, though.
regards, tom lane
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 1560ac3..fa34efb 100644
*** a/src/backend/nodes/outfuncs.c
--- b/src/backend/nodes/outfuncs.c
*************** _outPlannerInfo(StringInfo str, const Pl
*** 2078,2083 ****
--- 2078,2084 ----
WRITE_FLOAT_FIELD(tuple_fraction, "%.4f");
WRITE_FLOAT_FIELD(limit_tuples, "%.0f");
WRITE_UINT_FIELD(qual_security_level);
+ WRITE_BOOL_FIELD(needBaseTids);
WRITE_BOOL_FIELD(hasInheritedTarget);
WRITE_BOOL_FIELD(hasJoinRTEs);
WRITE_BOOL_FIELD(hasLateralRTEs);
diff --git a/src/backend/optimizer/plan/Makefile b/src/backend/optimizer/plan/Makefile
index 88a9f7f..1db6bd5 100644
*** a/src/backend/optimizer/plan/Makefile
--- b/src/backend/optimizer/plan/Makefile
*************** top_builddir = ../../../..
*** 13,18 ****
include $(top_builddir)/src/Makefile.global
OBJS = analyzejoins.o createplan.o initsplan.o planagg.o planmain.o planner.o \
! setrefs.o subselect.o
include $(top_srcdir)/src/backend/common.mk
--- 13,18 ----
include $(top_builddir)/src/Makefile.global
OBJS = analyzejoins.o createplan.o initsplan.o planagg.o planmain.o planner.o \
! planunionor.o setrefs.o subselect.o
include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 438baf1..237e7da 100644
*** a/src/backend/optimizer/plan/analyzejoins.c
--- b/src/backend/optimizer/plan/analyzejoins.c
*************** clause_sides_match_join(RestrictInfo *ri
*** 149,154 ****
--- 149,157 ----
* cases, but we don't have the infrastructure to prove them.) We also
* have to check that the inner side doesn't generate any variables needed
* above the join.
+ *
+ * Note: making this significantly smarter might break planunionor.c.
+ * Study that file before doing so.
*/
static bool
join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index 3c58d05..64de570 100644
*** a/src/backend/optimizer/plan/planmain.c
--- b/src/backend/optimizer/plan/planmain.c
*************** query_planner(PlannerInfo *root, List *t
*** 200,205 ****
--- 200,213 ----
add_placeholders_to_base_rels(root);
/*
+ * Also, if we have a request to emit baserel CTIDs, add those to the
+ * baserel targetlists now. This likewise has to be done after join
+ * removal, because we only want CTIDs for rels that survive join removal.
+ */
+ if (root->needBaseTids)
+ add_base_rel_ctids(root);
+
+ /*
* Construct the lateral reference sets now that we have finalized
* PlaceHolderVar eval levels.
*/
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index abb4f12..160b694 100644
*** a/src/backend/optimizer/plan/planner.c
--- b/src/backend/optimizer/plan/planner.c
*************** subquery_planner(PlannerGlobal *glob, Qu
*** 479,484 ****
--- 479,485 ----
root->grouping_map = NULL;
root->minmax_aggs = NIL;
root->qual_security_level = 0;
+ root->needBaseTids = false;
root->hasInheritedTarget = false;
root->hasRecursion = hasRecursion;
if (hasRecursion)
*************** grouping_planner(PlannerInfo *root, bool
*** 1496,1501 ****
--- 1497,1503 ----
List *activeWindows = NIL;
List *rollup_lists = NIL;
List *rollup_groupclauses = NIL;
+ List *union_or_subpaths;
standard_qp_extra qp_extra;
/* A recursive query should always have setOperations */
*************** grouping_planner(PlannerInfo *root, bool
*** 1656,1661 ****
--- 1658,1671 ----
preprocess_minmax_aggregates(root, tlist);
/*
+ * Preprocess join OR clauses that might be better handled as UNIONs.
+ * This likewise needs to be close to the query_planner() call. But
+ * it doesn't matter which of preprocess_minmax_aggregates() and this
+ * function we call first, because they treat disjoint sets of cases.
+ */
+ union_or_subpaths = split_join_or_clauses(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
* hard limit overall, it doesn't apply if the query has any
*************** grouping_planner(PlannerInfo *root, bool
*** 1689,1694 ****
--- 1699,1712 ----
standard_qp_callback, &qp_extra);
/*
+ * If we found any way to convert a join OR clause to a union, finish
+ * up generating the path(s) for that, and add them into the topmost
+ * scan/join relation.
+ */
+ if (union_or_subpaths)
+ finish_union_or_paths(root, current_rel, union_or_subpaths);
+
+ /*
* Convert the query's result tlist into PathTarget format.
*
* Note: it's desirable to not do this till after query_planner(),
diff --git a/src/backend/optimizer/plan/planunionor.c b/src/backend/optimizer/plan/planunionor.c
index ...a5518d9 .
*** a/src/backend/optimizer/plan/planunionor.c
--- b/src/backend/optimizer/plan/planunionor.c
***************
*** 0 ****
--- 1,666 ----
+ /*-------------------------------------------------------------------------
+ *
+ * planunionor.c
+ * Consider whether join OR clauses can be converted to UNION queries.
+ *
+ * This module looks for OR clauses whose arms each reference a single
+ * query relation (but not all the same rel), and tries to generate a path
+ * representing conversion of such an OR clause into a UNION operation.
+ * For example,
+ * SELECT ... FROM a, b WHERE (cond-on-A OR cond-on-B) AND other-conds
+ * can be implemented as
+ * SELECT ... FROM a, b WHERE cond-on-A AND other-conds
+ * UNION
+ * SELECT ... FROM a, b WHERE cond-on-B AND other-conds
+ * given a suitable definition of "UNION" (one that won't merge rows that
+ * would have been separate in the original query output). Since this change
+ * converts join clauses into restriction clauses, the modified query can be
+ * much faster to run than the original, despite the duplication of effort
+ * involved and the extra UNION processing. It's particularly useful for
+ * star-schema queries where the OR arms reference different dimension tables;
+ * each separated query may be able to remove joins to all but one dimension
+ * table, and arrange that join to use an inner indexscan on the fact table.
+ *
+ * We must insist that the WHERE and JOIN/ON clauses contain no volatile
+ * functions, because of the likelihood that qual clauses will be evaluated
+ * more times than a naive programmer would expect. We need not restrict
+ * the SELECT's tlist, because that will be evaluated after the UNION.
+ *
+ * The current implementation of the UNION step is to de-duplicate using
+ * row CTIDs. A big limitation is that this only works on plain relations,
+ * and not for instance on foreign tables. Another problem is that we can
+ * only de-duplicate by sort/unique, not hashing; but that could be fixed
+ * if we write a hash opclass for TID.
+ *
+ * To allow join removal to happen, we can't reference the CTID column
+ * of an otherwise-removable relation. Therefore, this code proceeds by
+ * de-duplicating output rows using only the CTIDs of relations that are not
+ * removable in any UNION arm. It is not immediately obvious that that works
+ * at all, but it does, given one restriction. If a rel is removed in some
+ * arm, then it is not referenced above the joins in that arm (in particular,
+ * it's not used in that arm's version of the OR clause), and we were able
+ * to prove that removing it doesn't change the output rowcount in that arm.
+ * Therefore there's no need to consider it for de-duplication so far as that
+ * arm's output is concerned. The identical proof can be expected to apply
+ * in other arms, except in an arm that references that rel in its version
+ * of the OR clause. But in such an arm, we have effectively added a
+ * restriction clause to what is known in other arms, which means that the
+ * set of rows output by that rel can't increase compared to other arms.
+ * Therefore the situation in such an arm must be that including the rel
+ * could result in either zero or one output row, rather than exactly one
+ * output row as in other arms. So we still don't need to consider it for
+ * de-duplication. But there's a hole in this argument, which is that we
+ * must consider the effects of reduce_outer_joins() as well as
+ * remove_useless_joins(). Addition of a restriction clause could result in
+ * simplifying a FULL join into a LEFT join, which might allow join removal
+ * to happen against the right side of that join; but the same proof would
+ * fail in arms that didn't restrict the left side. We deal with this issue
+ * by not attempting union OR transformation if the query has any FULL joins.
+ *
+ *
+ * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ * src/backend/optimizer/plan/planunionor.c
+ *
+ *-------------------------------------------------------------------------
+ */
+ #include "postgres.h"
+
+ #include "access/sysattr.h"
+ #include "catalog/pg_class.h"
+ #include "catalog/pg_operator.h"
+ #include "catalog/pg_type.h"
+ #include "miscadmin.h"
+ #include "nodes/makefuncs.h"
+ #include "optimizer/clauses.h"
+ #include "optimizer/cost.h"
+ #include "optimizer/pathnode.h"
+ #include "optimizer/planmain.h"
+ #include "optimizer/prep.h"
+ #include "optimizer/subselect.h"
+ #include "optimizer/tlist.h"
+ #include "optimizer/var.h"
+
+
+ static bool is_suitable_join_or_clause(BoolExpr *orclause, List **relids);
+ static bool is_query_safe_for_union_or_transform(PlannerInfo *root);
+ static List *create_union_or_subpaths(PlannerInfo *root, BoolExpr *orclause,
+ int n, List *armrelids);
+ static void union_or_qp_callback(PlannerInfo *root, void *extra);
+
+
+ /*
+ * split_join_or_clauses - create paths based on splitting join OR clauses
+ *
+ * This should be called by grouping_planner() just before it's ready to call
+ * query_planner(), because we generate simplified join paths by cloning the
+ * planner's state and invoking query_planner() on a modified version of
+ * the query parsetree. Thus, all preprocessing needed before query_planner()
+ * must already be done. Note however that we repeat reduce_outer_joins()
+ * because of the possibility that the simplified WHERE clause allows reduction
+ * of an outer join to inner-join form. That's okay for now, but maybe we
+ * should move the reduce_outer_joins() call into query_planner()?
+ *
+ * The result is a list (one entry per potential union OR path) of sublists of
+ * best paths for the inputs to the UNION step. Adding the UNION processing
+ * is retty mechanical, but we can't do it until we have a RelOptInfo for the
+ * top-level join rel.
+ */
+ List *
+ split_join_or_clauses(PlannerInfo *root)
+ {
+ List *results = NIL;
+ Query *parse = root->parse;
+ bool checked_query = false;
+ ListCell *lc;
+ int n;
+
+ /*
+ * At least for now, we restrict this optimization to plain SELECTs.
+ */
+ if (parse->commandType != CMD_SELECT ||
+ parse->rowMarks ||
+ parse->setOperations)
+ return NIL;
+
+ /*
+ * Reject if query contains any CTEs; copying them would break
+ * single-evaluation semantics. (In principle we could arrange for all
+ * UNION arms to read from a single instance of a CTE, but that's an
+ * improvement for another day, especially since we have no way to de-dup
+ * CTE outputs anyway.)
+ */
+ if (parse->cteList)
+ return NIL;
+
+ /*
+ * The query must reference multiple tables, else we certainly aren't
+ * going to find any suitable OR clauses. Do a quick check that there's
+ * more than one RTE.
+ */
+ if (list_length(parse->rtable) < 2)
+ return NIL;
+
+ /*
+ * Scan the top-level WHERE clause looking for suitable OR clauses, and
+ * for each one, generate paths for the UNION input sub-queries. There
+ * might be more than one suitable OR clause, in which case we can try the
+ * transformation for each one of them separately and add that list of
+ * paths to the results.
+ *
+ * XXX we should also search the JOIN/ON clauses of any top-level inner
+ * JOIN nodes, since those are semantically equivalent to WHERE. But it's
+ * hard to see how to do that without either copying the whole JOIN tree
+ * in advance or repeating the search after copying, and neither of those
+ * options seems attractive.
+ */
+ n = 0;
+ foreach(lc, (List *) parse->jointree->quals)
+ {
+ Node *qual = (Node *) lfirst(lc);
+ List *armrelids;
+
+ if (or_clause(qual) &&
+ is_suitable_join_or_clause((BoolExpr *) qual, &armrelids))
+ {
+ List *subpaths;
+
+ /*
+ * Check that the query as a whole is safe for this optimization.
+ * We only need to do this once, but it's somewhat expensive, so
+ * don't do it till we find a candidate OR clause.
+ */
+ if (!checked_query)
+ {
+ if (!is_query_safe_for_union_or_transform(root))
+ return NIL;
+ checked_query = true;
+ }
+ /* OK, transform the query and create a list of sub-paths */
+ subpaths = create_union_or_subpaths(root, (BoolExpr *) qual,
+ n, armrelids);
+ results = lappend(results, subpaths);
+ }
+ n++;
+ }
+
+ return results;
+ }
+
+ /*
+ * Make sure that a UNION subpath will emit the CTID columns for all its
+ * (surviving) baserels. This is called after we've done join removal in
+ * the UNION arm.
+ */
+ void
+ add_base_rel_ctids(PlannerInfo *root)
+ {
+ Relids allbaserels;
+ List *vars;
+ int brelid;
+
+ /* Find out the set of baserels that survived join removal */
+ allbaserels = get_relids_in_jointree((Node *) root->parse->jointree, false);
+ /* For each such rel, make a Var for its CTID column */
+ vars = NIL;
+ brelid = -1;
+ while ((brelid = bms_next_member(allbaserels, brelid)) >= 0)
+ {
+ Var *var;
+
+ var = makeVar(brelid,
+ SelfItemPointerAttributeNumber,
+ TIDOID,
+ -1,
+ InvalidOid,
+ 0);
+ vars = lappend(vars, var);
+ }
+ /* Add to rel tlists if not present, and mark as needed at top level */
+ add_vars_to_targetlist(root, vars, bms_make_singleton(0), false);
+ }
+
+ /*
+ * Finish constructing Paths representing the UNION implementation of join
+ * OR clause(s), and attach them to "joinrel", which is the final scan/join
+ * relation returned by query_planner() for the conventional implementation of
+ * the query. "union_or_subpaths" is the output of split_join_or_clauses().
+ */
+ void
+ finish_union_or_paths(PlannerInfo *root, RelOptInfo *joinrel,
+ List *union_or_subpaths)
+ {
+ ListCell *lc;
+
+ /* This loop iterates once per splittable OR clause */
+ foreach(lc, union_or_subpaths)
+ {
+ List *subpaths = (List *) lfirst(lc);
+ List *common_exprs;
+ PathTarget *common_target;
+ Path *appendpath;
+ List *uniq_operators;
+ List *uniq_exprs;
+ UniquePath *pathnode;
+ Path sort_path; /* dummy for result of cost_sort */
+ int numCols;
+ ListCell *lc2;
+
+ /*
+ * Join removal in the sub-queries might have resulted in different
+ * sub-paths returning different sets of Vars, in particular we might
+ * not see the full set of artificially-added CTID Vars coming out of
+ * each sub-path. Fortunately, we only need the ones that are
+ * available from every sub-path. Since Append can't project, we need
+ * to build a pathtarget containing only the commonly available Vars,
+ * and force each sub-path to return that target.
+ *
+ * This coding assumes that the commonly available Vars will appear in
+ * the same order in each subpath target, which should be true but
+ * it's surely an implementation artifact. If it stops being true, we
+ * could fall back on list_intersection(), but that'd be O(N^3).
+ */
+ common_exprs = (List *)
+ copyObject(((Path *) linitial(subpaths))->pathtarget->exprs);
+ for_each_cell(lc2, lnext(list_head(subpaths)))
+ {
+ Path *subpath = (Path *) lfirst(lc2);
+ ListCell *lcs;
+ ListCell *lcc;
+ ListCell *prevc;
+
+ lcs = list_head(subpath->pathtarget->exprs);
+ prevc = NULL;
+ lcc = list_head(common_exprs);
+ while (lcc)
+ {
+ ListCell *nextc = lnext(lcc);
+
+ if (lcs && equal(lfirst(lcs), lfirst(lcc)))
+ {
+ lcs = lnext(lcs);
+ prevc = lcc;
+ }
+ else
+ common_exprs = list_delete_cell(common_exprs, lcc, prevc);
+ lcc = nextc;
+ }
+ }
+ common_target = create_empty_pathtarget();
+ common_target->exprs = common_exprs;
+ set_pathtarget_cost_width(root, common_target);
+ /* Now forcibly apply this target to each subpath */
+ foreach(lc2, subpaths)
+ {
+ Path *subpath = (Path *) lfirst(lc2);
+
+ lfirst(lc2) = create_projection_path(root,
+ joinrel,
+ subpath,
+ common_target);
+ }
+
+ /*
+ * Generate Append path combining the sub-paths for this UNION. The
+ * Append path's pathtarget has to match what is actually coming out
+ * of the subpaths, since Append can't project.
+ */
+ appendpath = (Path *) create_append_path(joinrel, subpaths, NULL, 0);
+ appendpath->pathtarget = common_target;
+
+ /*
+ * Make the operator and expression lists needed for the Unique path.
+ * We need to unique-ify on every CTID that is commonly available from
+ * all the sub-paths. (See discussion at head of file.)
+ */
+ uniq_operators = uniq_exprs = NIL;
+ foreach(lc2, common_exprs)
+ {
+ Var *var = (Var *) lfirst(lc2);
+
+ if (IsA(var, Var) &&
+ var->varattno == SelfItemPointerAttributeNumber &&
+ var->varlevelsup == 0)
+ {
+ Assert(var->vartype == TIDOID);
+ uniq_operators = lappend_oid(uniq_operators, TIDEqualOperator);
+ uniq_exprs = lappend(uniq_exprs, var);
+ }
+ }
+ Assert(uniq_exprs != NIL);
+
+ /*
+ * Generate a Unique path representing the de-duplication step. For
+ * now, we can only consider sort+unique implementation, since we lack
+ * hashing support for type "tid".
+ *
+ * XXX maybe refactor to share some code with create_unique_path()?
+ */
+ pathnode = makeNode(UniquePath);
+
+ pathnode->path.pathtype = T_Unique;
+ pathnode->path.parent = joinrel;
+ pathnode->path.pathtarget = appendpath->pathtarget;
+ pathnode->path.param_info = appendpath->param_info;
+ pathnode->path.parallel_aware = false;
+ pathnode->path.parallel_safe = joinrel->consider_parallel &&
+ appendpath->parallel_safe;
+ pathnode->path.parallel_workers = appendpath->parallel_workers;
+
+ /*
+ * Treat the output as unsorted, since it almost certainly doesn't
+ * match any useful pathkeys.
+ */
+ pathnode->path.pathkeys = NIL;
+
+ pathnode->subpath = appendpath;
+ pathnode->in_operators = uniq_operators;
+ pathnode->uniq_exprs = uniq_exprs;
+
+ /* Estimate number of output rows */
+ pathnode->path.rows = appendpath->rows;
+ numCols = list_length(uniq_exprs);
+
+ /*
+ * Estimate cost for sort+unique implementation
+ */
+ cost_sort(&sort_path, root, NIL,
+ appendpath->total_cost,
+ appendpath->rows,
+ appendpath->pathtarget->width,
+ 0.0,
+ work_mem,
+ -1.0);
+
+ /*
+ * Charge one cpu_operator_cost per comparison per input tuple. We
+ * assume all columns get compared at most of the tuples. (XXX
+ * probably this is an overestimate.) This should agree with
+ * create_unique_path.
+ */
+ sort_path.total_cost += cpu_operator_cost * appendpath->rows * numCols;
+
+ pathnode->umethod = UNIQUE_PATH_SORT;
+
+ pathnode->path.startup_cost = sort_path.startup_cost;
+ pathnode->path.total_cost = sort_path.total_cost;
+
+ /* Attach it to the joinrel */
+ add_path(joinrel, (Path *) pathnode);
+ }
+
+ /* We need to refigure which is the cheapest path for the joinrel */
+ set_cheapest(joinrel);
+ }
+
+ /*
+ * Is this OR clause a suitable clause for splitting?
+ *
+ * Each of its arms must reference just one rel, and they must not all be
+ * the same rel.
+ * On success, pass back a list of the relids referenced by each OR arm,
+ * so we don't have to repeat the pull_varnos() work later.
+ */
+ static bool
+ is_suitable_join_or_clause(BoolExpr *orclause, List **relids)
+ {
+ bool ok = false;
+ List *relidlist = NIL;
+ int firstrelid = 0;
+ ListCell *lc;
+
+ *relids = NIL; /* prevent uninitialized-variable warnings */
+ foreach(lc, orclause->args)
+ {
+ Node *qual = (Node *) lfirst(lc);
+ Relids varnos = pull_varnos(qual);
+ int relid;
+
+ if (!bms_get_singleton_member(varnos, &relid))
+ return false; /* this arm fails the sine qua non */
+ if (relidlist == NIL)
+ firstrelid = relid;
+ else if (firstrelid != relid)
+ ok = true; /* arms reference more than one relid */
+ relidlist = lappend_int(relidlist, relid);
+ }
+ *relids = relidlist;
+ return ok;
+ }
+
+ /*
+ * Is query as a whole safe to apply union OR transformation to?
+ * This checks relatively-expensive conditions that we don't want to
+ * worry about until we've found a candidate OR clause.
+ */
+ static bool
+ is_query_safe_for_union_or_transform(PlannerInfo *root)
+ {
+ Query *parse = root->parse;
+ Relids allbaserels;
+ ListCell *lc;
+ int relid;
+
+ /*
+ * Must not have any volatile functions in FROM or WHERE (see notes at
+ * head of file).
+ */
+ if (contain_volatile_functions((Node *) parse->jointree))
+ return false;
+
+ /*
+ * We insist that all baserels used in the query be plain relations, so
+ * that we can use their ctids as unique row identifiers in the UNION
+ * step. One could imagine ways to relax this later, for instance by
+ * forcibly adding WITH ORDINALITY to function RTEs. We'd have to examine
+ * each RTE anyway, though, to check for volatile functions.
+ */
+ allbaserels = get_relids_in_jointree((Node *) parse->jointree, false);
+ relid = 0;
+ foreach(lc, parse->rtable)
+ {
+ RangeTblEntry *rte = (RangeTblEntry *) lfirst(lc);
+
+ relid++;
+
+ /* fail if query contains any FULL joins (see head of this file) */
+ if (rte->rtekind == RTE_JOIN && rte->jointype == JOIN_FULL)
+ return false;
+
+ /* otherwise, ignore RTEs that aren't referenced baserels */
+ if (!bms_is_member(relid, allbaserels))
+ continue;
+
+ /* fail if not plain rel */
+ if (rte->rtekind != RTE_RELATION)
+ return false;
+ /* fail if it doesn't have CTIDs */
+ if (rte->relkind != RELKIND_RELATION &&
+ rte->relkind != RELKIND_MATVIEW)
+ return false;
+
+ /* disallow TABLESAMPLE (might be okay if repeatable?) */
+ if (rte->tablesample)
+ return false;
+
+ /* check for volatiles in security barrier quals */
+ if (contain_volatile_functions((Node *) rte->securityQuals))
+ return false;
+ }
+
+ /* OK to proceed */
+ return true;
+ }
+
+ /*
+ * Split the query and the given OR clause into one UNION arm per relation
+ * mentioned in the OR clause, and make a list of best paths for the UNION
+ * arms. (Since the UNION step will lose any ordering or fast-start
+ * properties of the paths, there's no need to consider any but the
+ * cheapest-total path for each arm; hence it's okay to return just one path
+ * per arm.)
+ *
+ * "n" is the OR clause's index in the query's WHERE list.
+ * "armrelids" is the OR-arm-to-referenced-rel mapping.
+ */
+ static List *
+ create_union_or_subpaths(PlannerInfo *root, BoolExpr *orclause,
+ int n, List *armrelids)
+ {
+ List *subpaths = NIL;
+ Relids orrels;
+ int relid;
+ ListCell *lc;
+ ListCell *lc2;
+
+ /*
+ * There might be multiple OR arms referring to the same rel, which we
+ * should combine into a restriction OR clause. So first identify the set
+ * of rels used in the OR.
+ */
+ orrels = NULL;
+ foreach(lc, armrelids)
+ orrels = bms_add_member(orrels, lfirst_int(lc));
+
+ /* Now, for each such rel, generate a path for a UNION arm */
+ while ((relid = bms_first_member(orrels)) >= 0)
+ {
+ List *orarms;
+ PlannerInfo *subroot;
+ Query *parse;
+ List *subquery_quals;
+ bool hasOuterJoins;
+ RelOptInfo *final_rel;
+ Path *subpath;
+ int k;
+ ListCell *prev;
+
+ /* Extract the OR arms for this rel, making copies for safety */
+ orarms = NIL;
+ forboth(lc, orclause->args, lc2, armrelids)
+ {
+ Node *qual = (Node *) lfirst(lc);
+ int qualrelid = lfirst_int(lc2);
+
+ if (qualrelid == relid)
+ orarms = lappend(orarms, copyObject(qual));
+ }
+ Assert(orarms != NIL);
+ if (list_length(orarms) == 1)
+ {
+ /*
+ * When there's just a single arm for this rel (the typical case),
+ * it goes directly into the subquery's WHERE list. But it might
+ * be a sub-AND, in which case we must flatten it into a qual list
+ * to preserve AND/OR flatness.
+ */
+ orarms = make_ands_implicit((Expr *) linitial(orarms));
+ }
+ else
+ {
+ /*
+ * When there's more than one arm, convert back to an OR clause.
+ * No flatness worries here; the arms were already valid OR-list
+ * elements.
+ */
+ orarms = list_make1(make_orclause(orarms));
+ }
+
+ /* Clone the planner's state */
+ subroot = (PlannerInfo *) palloc(sizeof(PlannerInfo));
+ memcpy(subroot, root, sizeof(PlannerInfo));
+ subroot->parse = parse = (Query *) copyObject(root->parse);
+ /* Making copies of these might be overkill, but be safe */
+ subroot->processed_tlist = (List *) copyObject(root->processed_tlist);
+ subroot->append_rel_list = (List *) copyObject(root->append_rel_list);
+ /* Tell query_planner to expect full retrieval of UNION input */
+ subroot->tuple_fraction = 1.0;
+ subroot->limit_tuples = -1.0;
+
+ /*
+ * Remove the subquery's copy of the original OR clause, which we
+ * identify by its index in the WHERE clause list.
+ */
+ subquery_quals = (List *) parse->jointree->quals;
+ k = 0;
+ prev = NULL;
+ foreach(lc, subquery_quals)
+ {
+ if (k == n)
+ {
+ subquery_quals = list_delete_cell(subquery_quals, lc, prev);
+ break;
+ }
+ k++;
+ prev = lc;
+ }
+
+ /* And instead add the qual or quals we extracted from the OR clause */
+ subquery_quals = list_concat(subquery_quals, orarms);
+ parse->jointree->quals = (Node *) subquery_quals;
+
+ /*
+ * Ask for baserel CTIDs to be added to the output of the subquery. We
+ * only want CTIDs of rels that will survive join removal, so we can't
+ * add them now, as that would in itself prevent join removal.
+ */
+ subroot->needBaseTids = true;
+
+ /* Re-apply reduce_outer_joins() in case we can now reduce some */
+ /* (XXX would be better if this just got moved into query_planner) */
+ hasOuterJoins = false;
+ foreach(lc, parse->rtable)
+ {
+ RangeTblEntry *rte = (RangeTblEntry *) lfirst(lc);
+
+ if (rte->rtekind == RTE_JOIN)
+ {
+ if (IS_OUTER_JOIN(rte->jointype))
+ {
+ hasOuterJoins = true;
+ break;
+ }
+ }
+ }
+ if (hasOuterJoins)
+ reduce_outer_joins(subroot);
+
+ /* Plan the modified query */
+ final_rel = query_planner(subroot, subroot->processed_tlist,
+ union_or_qp_callback, NULL);
+
+ /*
+ * Get the cheapest-total path for the subquery; there's little value
+ * in considering any others.
+ */
+ subpath = final_rel->cheapest_total_path;
+ Assert(subpath);
+
+ /* Add cheapest-total path to subpaths list */
+ subpaths = lappend(subpaths, subpath);
+ }
+
+ return subpaths;
+ }
+
+ /*
+ * Compute query_pathkeys and other pathkeys during plan generation
+ */
+ static void
+ union_or_qp_callback(PlannerInfo *root, void *extra)
+ {
+ /*
+ * Since the output of the subquery is going to go through a UNION step
+ * that destroys ordering, there's little need to worry about what its
+ * output order is. Hence, don't bother telling it about pathkeys that
+ * might apply to these later execution steps.
+ */
+ root->group_pathkeys = NIL;
+ root->window_pathkeys = NIL;
+ root->distinct_pathkeys = NIL;
+ root->sort_pathkeys = NIL;
+ root->query_pathkeys = NIL;
+ }
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 6911177..bd7f8b0 100644
*** a/src/backend/optimizer/prep/prepjointree.c
--- b/src/backend/optimizer/prep/prepjointree.c
*************** pull_up_simple_subquery(PlannerInfo *roo
*** 914,919 ****
--- 914,920 ----
subroot->grouping_map = NULL;
subroot->minmax_aggs = NIL;
subroot->qual_security_level = 0;
+ subroot->needBaseTids = false;
subroot->hasInheritedTarget = false;
subroot->hasRecursion = false;
subroot->wt_param_id = -1;
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 643be54..b8fe1dc 100644
*** a/src/include/nodes/relation.h
--- b/src/include/nodes/relation.h
*************** typedef struct PlannerInfo
*** 289,294 ****
--- 289,295 ----
Index qual_security_level; /* minimum security_level for quals */
/* Note: qual_security_level is zero if there are no securityQuals */
+ bool needBaseTids; /* true to force outputting baserel CTIDs */
bool hasInheritedTarget; /* true if parse->resultRelation is an
* inheritance child rel */
bool hasJoinRTEs; /* true if any RTEs are RTE_JOIN kind */
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index 94ef84b..ae52546 100644
*** a/src/include/optimizer/planmain.h
--- b/src/include/optimizer/planmain.h
*************** extern RelOptInfo *query_planner(Planner
*** 45,50 ****
--- 45,58 ----
extern void preprocess_minmax_aggregates(PlannerInfo *root, List *tlist);
/*
+ * prototypes for plan/planunionor.c
+ */
+ extern List *split_join_or_clauses(PlannerInfo *root);
+ extern void add_base_rel_ctids(PlannerInfo *root);
+ extern void finish_union_or_paths(PlannerInfo *root, RelOptInfo *joinrel,
+ List *union_or_subpaths);
+
+ /*
* prototypes for plan/createplan.c
*/
extern Plan *create_plan(PlannerInfo *root, Path *best_path);
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Improve OR conditions on joined columns (common starschema problem)
From
Jim Nasby
Date:
On 2/14/17 1:18 PM, Tom Lane wrote: > I think this might be code-complete, modulo the question of whether we > want an enabling GUC for it. I'm still concerned about the question > of whether it adds more planning time than it's worth for most users. > (Obviously it needs some regression test cases too, and a lot more > real-world testing than I've given it.) Don't we normally provide a GUC for this level of query manipulation? We can always remove it later if evidence shows there's not sufficient downside (perhaps after gaining the ability for the planner to do extra work on queries that appear to be large enough to warrant it). > One point that could use further review is whether the de-duplication > algorithm is actually correct. I'm only about 95% convinced by the > argument I wrote in planunionor.c's header comment. Another reason for a GUC... I'll put some thought into it and see if I can find any holes. Are you only worried about the removal of "useless" rels or is there more? -- Jim Nasby, Data Architect, Blue Treble Consulting, Austin TX Experts in Analytics, Data Architecture and PostgreSQL Data in Trouble? Get it in Treble! http://BlueTreble.com 855-TREBLE2 (855-873-2532)
Re: [HACKERS] Improve OR conditions on joined columns (common star schema problem)
From
Tom Lane
Date:
Jim Nasby <Jim.Nasby@BlueTreble.com> writes:
> On 2/14/17 1:18 PM, Tom Lane wrote:
>> One point that could use further review is whether the de-duplication
>> algorithm is actually correct. I'm only about 95% convinced by the
>> argument I wrote in planunionor.c's header comment.
> I'll put some thought into it and see if I can find any holes. Are you
> only worried about the removal of "useless" rels or is there more?
Well, the key point is whether it's really OK to de-dup on the basis
of only the CTIDs that are not eliminated in any UNION arm. I was
feeling fairly good about that until I thought of the full-join-to-
left-join-to-no-join conversion issue mentioned in the comment.
Now I'm wondering if there are other holes; or maybe I'm wrong about
that one and it's not necessary to be afraid of full joins.
regards, tom lane
[HACKERS] Re: Improve OR conditions on joined columns (common star schemaproblem)
From
David Steele
Date:
On 2/14/17 4:03 PM, Tom Lane wrote: > Jim Nasby <Jim.Nasby@BlueTreble.com> writes: >> On 2/14/17 1:18 PM, Tom Lane wrote: >>> One point that could use further review is whether the de-duplication >>> algorithm is actually correct. I'm only about 95% convinced by the >>> argument I wrote in planunionor.c's header comment. > >> I'll put some thought into it and see if I can find any holes. Are you >> only worried about the removal of "useless" rels or is there more? > > Well, the key point is whether it's really OK to de-dup on the basis > of only the CTIDs that are not eliminated in any UNION arm. I was > feeling fairly good about that until I thought of the full-join-to- > left-join-to-no-join conversion issue mentioned in the comment. > Now I'm wondering if there are other holes; or maybe I'm wrong about > that one and it's not necessary to be afraid of full joins. This patch applies cleanly (with offsets) and compiles at cccbdde. Jim, have you had time to think about this? Any insights? -- -David david@pgmasters.net
[HACKERS] Re: Improve OR conditions on joined columns (common star schemaproblem)
From
Jim Nasby
Date:
On 3/16/17 11:54 AM, David Steele wrote: > On 2/14/17 4:03 PM, Tom Lane wrote: >> Jim Nasby <Jim.Nasby@BlueTreble.com> writes: >>> On 2/14/17 1:18 PM, Tom Lane wrote: >>>> One point that could use further review is whether the de-duplication >>>> algorithm is actually correct. I'm only about 95% convinced by the >>>> argument I wrote in planunionor.c's header comment. >> >>> I'll put some thought into it and see if I can find any holes. Are you >>> only worried about the removal of "useless" rels or is there more? >> >> Well, the key point is whether it's really OK to de-dup on the basis >> of only the CTIDs that are not eliminated in any UNION arm. I was >> feeling fairly good about that until I thought of the full-join-to- >> left-join-to-no-join conversion issue mentioned in the comment. >> Now I'm wondering if there are other holes; or maybe I'm wrong about >> that one and it's not necessary to be afraid of full joins. > > This patch applies cleanly (with offsets) and compiles at cccbdde. > > Jim, have you had time to think about this? Any insights? Having thought about it, I share Tom's concerns. And now I'm worried about what happens if there are multiple separate OR clauses. I guess those would be handled by separate UNIONs? I'm also finding it a bit hard to follow the comment Tom mentioned. I'm pretty sure I understand what's going on until this part: > The identical proof can be expected to apply > + * in other arms, except in an arm that references that rel in its version > + * of the OR clause. But in such an arm, we have effectively added a > + * restriction clause to what is known in other arms, which means that the > + * set of rows output by that rel can't increase compared to other arms. AIUI, this is describing a case something like this: SELECT child.blah FROM child LEFT JOIN parent USING(parent_id) WHERE child.foo AND (child.baz=1 or child.baz=2) given that parent.parent_id is unique. Except for these concerns, there would need to be a complex OR somewhere in here that sometimes referenced parent and sometimes didn't, such as WHERE child.foo AND (child.baz=1 OR parent.foo=3) But I'm not following the logic here (very possibly because I'm wrong about what I said above): > + * Therefore the situation in such an arm must be that including the rel > + * could result in either zero or one output row, rather than exactly one > + * output row as in other arms. So we still don't need to consider it for > + * de-duplication. I'm definitely not certain about the rest of it. Tom, could you expand the description some, especially with some examples? -- Jim Nasby, Chief Data Architect, Austin TX OpenSCG http://OpenSCG.com
Re: [HACKERS] Re: Improve OR conditions on joined columns (common star schema problem)
From
Tom Lane
Date:
Jim Nasby <jim.nasby@openscg.com> writes:
> On 3/16/17 11:54 AM, David Steele wrote:
>> On 2/14/17 4:03 PM, Tom Lane wrote:
>>> Well, the key point is whether it's really OK to de-dup on the basis
>>> of only the CTIDs that are not eliminated in any UNION arm. I was
>>> feeling fairly good about that until I thought of the full-join-to-
>>> left-join-to-no-join conversion issue mentioned in the comment.
>> Jim, have you had time to think about this? Any insights?
> Having thought about it, I share Tom's concerns. And now I'm worried
> about what happens if there are multiple separate OR clauses. I guess
> those would be handled by separate UNIONs?
As proposed, the patch would try to optimize by splitting each OR clause
independently, and would choose whichever way gave the best cost estimate.
I'm not sure it's possible to do better than that, and even if it is,
I think improving it could be left for later.
> Tom, could you expand the description some, especially with some examples?
Here's a counterexample --- admittedly rather artificial, but still a
counterexample --- to applying the optimization when there are FULL joins.
Consider
SELECT count(*)FROM a FULL JOIN b ON (a.id = b.id)WHERE (a.x = 42 OR b.y = 43);
and suppose that a and b have mutual FK constraints guaranteeing that
every non-null a.id value has exactly one match in b and vice versa. (For
the purposes of this example, I think it doesn't matter whether or not we
allow there to be null id values.) Also suppose that there are some join
rows satisfying both a.x = 42 and b.y = 43, while other join rows satisfy
only one of the OR arms. The patch would try to implement this query as,
approximately,
SELECT count(*)FROM( SELECT FROM a FULL JOIN b ON (a.id = b.id) WHERE a.x = 42 UNION-using-ctids SELECT FROM a FULL
JOINb ON (a.id = b.id) WHERE b.y = 43 )
Now in the first UNION arm, we'd observe that the strict a.x = 42
condition allows reduction of the join strength to LEFT JOIN, and then
we'd deduce from the FK on b that the join to b can be dropped altogether.
In the second arm, we'd similarly conclude that a can be dropped
altogether, leaving
SELECT count(*)FROM( SELECT FROM a WHERE a.x = 42 UNION-using-ctids SELECT FROM b WHERE b.y = 43 )
But at this point there are no rels that are not eliminated in any UNION
arm, so that no de-duping would occur in the UNION, meaning that we'd
double-count any join rows in which both a.x = 42 and b.y = 43.
I'd also considered an approach of de-duping on the basis of all relation
ctids, while allowing a rel's ctid to be returned as NULL from a UNION arm
in which the rel was eliminated entirely. But that doesn't fix it,
because in this example the first arm would return (a.ctid, NULL) while
the second arm would return (NULL, b.ctid), so that the UNION step would
still fail to detect any duplication. To make it work, we'd have to not
eliminate the joins, which would pretty much defeat the usefulness of
the optimization for your original example case.
So full joins definitely break this whole optimization. I think it's okay
with left joins though, because when starting from "a left join b" it will
never be possible to remove "a" so we'll always include a.ctid in the
UNION de-duping step. If b is removed in some arm, then it must be true
that we get exactly one left-join output row per a row, regardless of the
contents of b, in that arm. The argument for the patch being okay is
essentially that we must get exactly one left-join output row per a row,
regardless of the contents of b, in *every* arm, because the various
modified versions of the OR clause can't affect that conclusion. In some
of the arms we might not remove b, and we might even be able to reduce the
left join to an inner join, but there should still be no more than one
join output row per a row. That being the case, it should be sufficient
to de-dup using a.ctid while ignoring b.ctid.
Any clearer yet?
regards, tom lane
Re: [HACKERS] Re: Improve OR conditions on joined columns (common star schema problem)
From
Tom Lane
Date:
I wrote:
> Consider
> SELECT count(*)
> FROM a FULL JOIN b ON (a.id = b.id)
> WHERE (a.x = 42 OR b.y = 43);
> and suppose that a and b have mutual FK constraints guaranteeing that
> every non-null a.id value has exactly one match in b and vice versa.
Oh, that was sloppy of me. Join removal depends on unique constraints
not FK constraints. So actually, this example just requires assuming
that both a.id and b.id are known unique, which is much less far-fetched
than assuming circular FK constraints.
regards, tom lane
Re: [HACKERS] Re: Improve OR conditions on joined columns (commonstar schema problem)
From
Jim Nasby
Date:
On 3/19/17 2:32 PM, Tom Lane wrote: > Jim Nasby <jim.nasby@openscg.com> writes: >> Having thought about it, I share Tom's concerns. And now I'm worried >> about what happens if there are multiple separate OR clauses. I guess >> those would be handled by separate UNIONs? > > As proposed, the patch would try to optimize by splitting each OR clause > independently, and would choose whichever way gave the best cost estimate. > I'm not sure it's possible to do better than that, and even if it is, > I think improving it could be left for later. Agreed. > I'd also considered an approach of de-duping on the basis of all relation > ctids, while allowing a rel's ctid to be returned as NULL from a UNION arm > in which the rel was eliminated entirely. But that doesn't fix it, > because in this example the first arm would return (a.ctid, NULL) while > the second arm would return (NULL, b.ctid), so that the UNION step would > still fail to detect any duplication. To make it work, we'd have to not > eliminate the joins, which would pretty much defeat the usefulness of > the optimization for your original example case. It might still be worth-while in some circumstances. In your example, if there were these indexes: a__id ON a(id), a__x ON a(x) b__id ON b(id), b__y ON b(y) then it might be faster to nested loop a__x=42 to b__id=a.id and union that with b__y=43 nested to a__id=b.id. That said, now isn't the time to be adding more complexity. > So full joins definitely break this whole optimization. I think it's okay > with left joins though, because when starting from "a left join b" it will > never be possible to remove "a" so we'll always include a.ctid in the > UNION de-duping step. If b is removed in some arm, then it must be true > that we get exactly one left-join output row per a row, regardless of the > contents of b, in that arm. The argument for the patch being okay is > essentially that we must get exactly one left-join output row per a row, > regardless of the contents of b, in *every* arm, because the various > modified versions of the OR clause can't affect that conclusion. In some > of the arms we might not remove b, and we might even be able to reduce the > left join to an inner join, but there should still be no more than one > join output row per a row. That being the case, it should be sufficient > to de-dup using a.ctid while ignoring b.ctid. The only case I can think of is: would it be possible (perhaps not today; maybe in the future) for other parts of the query to affect join elimination? I can't conceive of how that might happen, but if it did then it's possible that the elimination would work differently with the UNION than it would with an OR. The comment on join_is_removable() does mention that there's other potentially interesting cases that we can't handle now; it's maybe worth mentioning Other than that, I can't see any issues with your logic. > Any clearer yet? Absolutely. I think it would be very valuable to include that with the initial comment in planunionor.c. Join reduction and removal is already tricky enough to wrap your head around. Other comments: > + * is retty mechanical, but we can't do it until we have a RelOptInfo for the s/retty/pretty/ I suspect that in many systems single-table queries are far more common than CTEs, so maybe it's worth reversing those two tests in split_join_or_clauses(). For the Unique path, it would be nice if the code did what would be necessary to consider a TID hash join, since that means a user could create the appropriate operator and it would just be picked up. Certainly not worth much effort at this point though. > + /* > + * Must not have any volatile functions in FROM or WHERE (see notes at > + * head of file). > + */ > + if (contain_volatile_functions((Node *) parse->jointree)) Is there by chance anywhere else that needs to check that? Maybe worth adding the info to the Query struct if so. > + * We insist that all baserels used in the query be plain relations, so Dumb question... views have already be decomposed at this point, right? Perhaps less dumb question... what happens if the original query already had setOps? AIUI setOps work has already been done by the time split_join_or_clauses() happens; I just want to check that that's OK. I'm not sure a GUC is worth it... I suspect that any query with multiple rels and an OR condition is going to be expensive enough that whatever additional plan time there is won't be noticeable. I've verified that the patch still applies and make check-world is clean. -- Jim Nasby, Chief Data Architect, Austin TX OpenSCG http://OpenSCG.com
Hi, On 2017-02-14 14:18:54 -0500, Tom Lane wrote: > I think this might be code-complete, modulo the question of whether we > want an enabling GUC for it. I'm still concerned about the question > of whether it adds more planning time than it's worth for most users. > (Obviously it needs some regression test cases too, and a lot more > real-world testing than I've given it.) > One point that could use further review is whether the de-duplication > algorithm is actually correct. I'm only about 95% convinced by the > argument I wrote in planunionor.c's header comment. > > Potential future work includes finding join ORs in upper-level INNER JOIN > ON clauses, and improving matters so we can do the unique-ification with > hashing as well as sorting. I don't think either of those things has to > be in the first commit, though. Are you planning to push this into v10? Given the looming freeze I'm inclined to bump this to the next CF. - Andres
Andres Freund <andres@anarazel.de> writes:
> On 2017-02-14 14:18:54 -0500, Tom Lane wrote:
>> One point that could use further review is whether the de-duplication
>> algorithm is actually correct. I'm only about 95% convinced by the
>> argument I wrote in planunionor.c's header comment.
> Are you planning to push this into v10? Given the looming freeze I'm
> inclined to bump this to the next CF.
I'm still not fully convinced the patch is correct, so I have no problem
with bumping it out.
regards, tom lane
Re: [HACKERS] Re: Improve OR conditions on joined columns (common star schema problem)
From
Tom Lane
Date:
Jim Nasby <jim.nasby@openscg.com> writes:
> I've verified that the patch still applies and make check-world is clean.
Not any more :-(. Here's a v3 rebased over HEAD. No substantive
change from v2.
regards, tom lane
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index b83d919..0311a50 100644
*** a/src/backend/nodes/outfuncs.c
--- b/src/backend/nodes/outfuncs.c
*************** _outPlannerInfo(StringInfo str, const Pl
*** 2228,2233 ****
--- 2228,2234 ----
WRITE_FLOAT_FIELD(tuple_fraction, "%.4f");
WRITE_FLOAT_FIELD(limit_tuples, "%.0f");
WRITE_UINT_FIELD(qual_security_level);
+ WRITE_BOOL_FIELD(needBaseTids);
WRITE_BOOL_FIELD(hasInheritedTarget);
WRITE_BOOL_FIELD(hasJoinRTEs);
WRITE_BOOL_FIELD(hasLateralRTEs);
diff --git a/src/backend/optimizer/plan/Makefile b/src/backend/optimizer/plan/Makefile
index 88a9f7f..1db6bd5 100644
*** a/src/backend/optimizer/plan/Makefile
--- b/src/backend/optimizer/plan/Makefile
*************** top_builddir = ../../../..
*** 13,18 ****
include $(top_builddir)/src/Makefile.global
OBJS = analyzejoins.o createplan.o initsplan.o planagg.o planmain.o planner.o \
! setrefs.o subselect.o
include $(top_srcdir)/src/backend/common.mk
--- 13,18 ----
include $(top_builddir)/src/Makefile.global
OBJS = analyzejoins.o createplan.o initsplan.o planagg.o planmain.o planner.o \
! planunionor.o setrefs.o subselect.o
include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 34317fe..8424e04 100644
*** a/src/backend/optimizer/plan/analyzejoins.c
--- b/src/backend/optimizer/plan/analyzejoins.c
*************** clause_sides_match_join(RestrictInfo *ri
*** 154,159 ****
--- 154,162 ----
* cases, but we don't have the infrastructure to prove them.) We also
* have to check that the inner side doesn't generate any variables needed
* above the join.
+ *
+ * Note: making this significantly smarter might break planunionor.c.
+ * Study that file before doing so.
*/
static bool
join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index f4e0a6e..1350417 100644
*** a/src/backend/optimizer/plan/planmain.c
--- b/src/backend/optimizer/plan/planmain.c
*************** query_planner(PlannerInfo *root, List *t
*** 206,211 ****
--- 206,219 ----
add_placeholders_to_base_rels(root);
/*
+ * Also, if we have a request to emit baserel CTIDs, add those to the
+ * baserel targetlists now. This likewise has to be done after join
+ * removal, because we only want CTIDs for rels that survive join removal.
+ */
+ if (root->needBaseTids)
+ add_base_rel_ctids(root);
+
+ /*
* Construct the lateral reference sets now that we have finalized
* PlaceHolderVar eval levels.
*/
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 6b79b3a..5eb025f 100644
*** a/src/backend/optimizer/plan/planner.c
--- b/src/backend/optimizer/plan/planner.c
*************** subquery_planner(PlannerGlobal *glob, Qu
*** 528,533 ****
--- 528,534 ----
root->grouping_map = NULL;
root->minmax_aggs = NIL;
root->qual_security_level = 0;
+ root->needBaseTids = false;
root->hasInheritedTarget = false;
root->hasRecursion = hasRecursion;
if (hasRecursion)
*************** grouping_planner(PlannerInfo *root, bool
*** 1584,1589 ****
--- 1585,1591 ----
WindowFuncLists *wflists = NULL;
List *activeWindows = NIL;
grouping_sets_data *gset_data = NULL;
+ List *union_or_subpaths;
standard_qp_extra qp_extra;
/* A recursive query should always have setOperations */
*************** grouping_planner(PlannerInfo *root, bool
*** 1667,1672 ****
--- 1669,1682 ----
preprocess_minmax_aggregates(root, tlist);
/*
+ * Preprocess join OR clauses that might be better handled as UNIONs.
+ * This likewise needs to be close to the query_planner() call. But
+ * it doesn't matter which of preprocess_minmax_aggregates() and this
+ * function we call first, because they treat disjoint sets of cases.
+ */
+ union_or_subpaths = split_join_or_clauses(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
* hard limit overall, it doesn't apply if the query has any
*************** grouping_planner(PlannerInfo *root, bool
*** 1701,1706 ****
--- 1711,1724 ----
standard_qp_callback, &qp_extra);
/*
+ * If we found any way to convert a join OR clause to a union, finish
+ * up generating the path(s) for that, and add them into the topmost
+ * scan/join relation.
+ */
+ if (union_or_subpaths)
+ finish_union_or_paths(root, current_rel, union_or_subpaths);
+
+ /*
* Convert the query's result tlist into PathTarget format.
*
* Note: it's desirable to not do this till after query_planner(),
diff --git a/src/backend/optimizer/plan/planunionor.c b/src/backend/optimizer/plan/planunionor.c
index ...12ffed5 .
*** a/src/backend/optimizer/plan/planunionor.c
--- b/src/backend/optimizer/plan/planunionor.c
***************
*** 0 ****
--- 1,667 ----
+ /*-------------------------------------------------------------------------
+ *
+ * planunionor.c
+ * Consider whether join OR clauses can be converted to UNION queries.
+ *
+ * This module looks for OR clauses whose arms each reference a single
+ * query relation (but not all the same rel), and tries to generate a path
+ * representing conversion of such an OR clause into a UNION operation.
+ * For example,
+ * SELECT ... FROM a, b WHERE (cond-on-A OR cond-on-B) AND other-conds
+ * can be implemented as
+ * SELECT ... FROM a, b WHERE cond-on-A AND other-conds
+ * UNION
+ * SELECT ... FROM a, b WHERE cond-on-B AND other-conds
+ * given a suitable definition of "UNION" (one that won't merge rows that
+ * would have been separate in the original query output). Since this change
+ * converts join clauses into restriction clauses, the modified query can be
+ * much faster to run than the original, despite the duplication of effort
+ * involved and the extra UNION processing. It's particularly useful for
+ * star-schema queries where the OR arms reference different dimension tables;
+ * each separated query may be able to remove joins to all but one dimension
+ * table, and arrange that join to use an inner indexscan on the fact table.
+ *
+ * We must insist that the WHERE and JOIN/ON clauses contain no volatile
+ * functions, because of the likelihood that qual clauses will be evaluated
+ * more times than a naive programmer would expect. We need not restrict
+ * the SELECT's tlist, because that will be evaluated after the UNION.
+ *
+ * The current implementation of the UNION step is to de-duplicate using
+ * row CTIDs. A big limitation is that this only works on plain relations,
+ * and not for instance on foreign tables. Another problem is that we can
+ * only de-duplicate by sort/unique, not hashing; but that could be fixed
+ * if we write a hash opclass for TID.
+ *
+ * To allow join removal to happen, we can't reference the CTID column
+ * of an otherwise-removable relation. Therefore, this code proceeds by
+ * de-duplicating output rows using only the CTIDs of relations that are not
+ * removable in any UNION arm. It is not immediately obvious that that works
+ * at all, but it does, given one restriction. If a rel is removed in some
+ * arm, then it is not referenced above the joins in that arm (in particular,
+ * it's not used in that arm's version of the OR clause), and we were able
+ * to prove that removing it doesn't change the output rowcount in that arm.
+ * Therefore there's no need to consider it for de-duplication so far as that
+ * arm's output is concerned. The identical proof can be expected to apply
+ * in other arms, except in an arm that references that rel in its version
+ * of the OR clause. But in such an arm, we have effectively added a
+ * restriction clause to what is known in other arms, which means that the
+ * set of rows output by that rel can't increase compared to other arms.
+ * Therefore the situation in such an arm must be that including the rel
+ * could result in either zero or one output row, rather than exactly one
+ * output row as in other arms. So we still don't need to consider it for
+ * de-duplication. But there's a hole in this argument, which is that we
+ * must consider the effects of reduce_outer_joins() as well as
+ * remove_useless_joins(). Addition of a restriction clause could result in
+ * simplifying a FULL join into a LEFT join, which might allow join removal
+ * to happen against the right side of that join; but the same proof would
+ * fail in arms that didn't restrict the left side. We deal with this issue
+ * by not attempting union OR transformation if the query has any FULL joins.
+ *
+ *
+ * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ * src/backend/optimizer/plan/planunionor.c
+ *
+ *-------------------------------------------------------------------------
+ */
+ #include "postgres.h"
+
+ #include "access/sysattr.h"
+ #include "catalog/pg_class.h"
+ #include "catalog/pg_operator.h"
+ #include "catalog/pg_type.h"
+ #include "miscadmin.h"
+ #include "nodes/makefuncs.h"
+ #include "optimizer/clauses.h"
+ #include "optimizer/cost.h"
+ #include "optimizer/pathnode.h"
+ #include "optimizer/planmain.h"
+ #include "optimizer/prep.h"
+ #include "optimizer/subselect.h"
+ #include "optimizer/tlist.h"
+ #include "optimizer/var.h"
+
+
+ static bool is_suitable_join_or_clause(BoolExpr *orclause, List **relids);
+ static bool is_query_safe_for_union_or_transform(PlannerInfo *root);
+ static List *create_union_or_subpaths(PlannerInfo *root, BoolExpr *orclause,
+ int n, List *armrelids);
+ static void union_or_qp_callback(PlannerInfo *root, void *extra);
+
+
+ /*
+ * split_join_or_clauses - create paths based on splitting join OR clauses
+ *
+ * This should be called by grouping_planner() just before it's ready to call
+ * query_planner(), because we generate simplified join paths by cloning the
+ * planner's state and invoking query_planner() on a modified version of
+ * the query parsetree. Thus, all preprocessing needed before query_planner()
+ * must already be done. Note however that we repeat reduce_outer_joins()
+ * because of the possibility that the simplified WHERE clause allows reduction
+ * of an outer join to inner-join form. That's okay for now, but maybe we
+ * should move the reduce_outer_joins() call into query_planner()?
+ *
+ * The result is a list (one entry per potential union OR path) of sublists of
+ * best paths for the inputs to the UNION step. Adding the UNION processing
+ * is retty mechanical, but we can't do it until we have a RelOptInfo for the
+ * top-level join rel.
+ */
+ List *
+ split_join_or_clauses(PlannerInfo *root)
+ {
+ List *results = NIL;
+ Query *parse = root->parse;
+ bool checked_query = false;
+ ListCell *lc;
+ int n;
+
+ /*
+ * At least for now, we restrict this optimization to plain SELECTs.
+ */
+ if (parse->commandType != CMD_SELECT ||
+ parse->rowMarks ||
+ parse->setOperations)
+ return NIL;
+
+ /*
+ * Reject if query contains any CTEs; copying them would break
+ * single-evaluation semantics. (In principle we could arrange for all
+ * UNION arms to read from a single instance of a CTE, but that's an
+ * improvement for another day, especially since we have no way to de-dup
+ * CTE outputs anyway.)
+ */
+ if (parse->cteList)
+ return NIL;
+
+ /*
+ * The query must reference multiple tables, else we certainly aren't
+ * going to find any suitable OR clauses. Do a quick check that there's
+ * more than one RTE.
+ */
+ if (list_length(parse->rtable) < 2)
+ return NIL;
+
+ /*
+ * Scan the top-level WHERE clause looking for suitable OR clauses, and
+ * for each one, generate paths for the UNION input sub-queries. There
+ * might be more than one suitable OR clause, in which case we can try the
+ * transformation for each one of them separately and add that list of
+ * paths to the results.
+ *
+ * XXX we should also search the JOIN/ON clauses of any top-level inner
+ * JOIN nodes, since those are semantically equivalent to WHERE. But it's
+ * hard to see how to do that without either copying the whole JOIN tree
+ * in advance or repeating the search after copying, and neither of those
+ * options seems attractive.
+ */
+ n = 0;
+ foreach(lc, (List *) parse->jointree->quals)
+ {
+ Node *qual = (Node *) lfirst(lc);
+ List *armrelids;
+
+ if (or_clause(qual) &&
+ is_suitable_join_or_clause((BoolExpr *) qual, &armrelids))
+ {
+ List *subpaths;
+
+ /*
+ * Check that the query as a whole is safe for this optimization.
+ * We only need to do this once, but it's somewhat expensive, so
+ * don't do it till we find a candidate OR clause.
+ */
+ if (!checked_query)
+ {
+ if (!is_query_safe_for_union_or_transform(root))
+ return NIL;
+ checked_query = true;
+ }
+ /* OK, transform the query and create a list of sub-paths */
+ subpaths = create_union_or_subpaths(root, (BoolExpr *) qual,
+ n, armrelids);
+ results = lappend(results, subpaths);
+ }
+ n++;
+ }
+
+ return results;
+ }
+
+ /*
+ * Make sure that a UNION subpath will emit the CTID columns for all its
+ * (surviving) baserels. This is called after we've done join removal in
+ * the UNION arm.
+ */
+ void
+ add_base_rel_ctids(PlannerInfo *root)
+ {
+ Relids allbaserels;
+ List *vars;
+ int brelid;
+
+ /* Find out the set of baserels that survived join removal */
+ allbaserels = get_relids_in_jointree((Node *) root->parse->jointree, false);
+ /* For each such rel, make a Var for its CTID column */
+ vars = NIL;
+ brelid = -1;
+ while ((brelid = bms_next_member(allbaserels, brelid)) >= 0)
+ {
+ Var *var;
+
+ var = makeVar(brelid,
+ SelfItemPointerAttributeNumber,
+ TIDOID,
+ -1,
+ InvalidOid,
+ 0);
+ vars = lappend(vars, var);
+ }
+ /* Add to rel tlists if not present, and mark as needed at top level */
+ add_vars_to_targetlist(root, vars, bms_make_singleton(0), false);
+ }
+
+ /*
+ * Finish constructing Paths representing the UNION implementation of join
+ * OR clause(s), and attach them to "joinrel", which is the final scan/join
+ * relation returned by query_planner() for the conventional implementation of
+ * the query. "union_or_subpaths" is the output of split_join_or_clauses().
+ */
+ void
+ finish_union_or_paths(PlannerInfo *root, RelOptInfo *joinrel,
+ List *union_or_subpaths)
+ {
+ ListCell *lc;
+
+ /* This loop iterates once per splittable OR clause */
+ foreach(lc, union_or_subpaths)
+ {
+ List *subpaths = (List *) lfirst(lc);
+ List *common_exprs;
+ PathTarget *common_target;
+ Path *appendpath;
+ List *uniq_operators;
+ List *uniq_exprs;
+ UniquePath *pathnode;
+ Path sort_path; /* dummy for result of cost_sort */
+ int numCols;
+ ListCell *lc2;
+
+ /*
+ * Join removal in the sub-queries might have resulted in different
+ * sub-paths returning different sets of Vars, in particular we might
+ * not see the full set of artificially-added CTID Vars coming out of
+ * each sub-path. Fortunately, we only need the ones that are
+ * available from every sub-path. Since Append can't project, we need
+ * to build a pathtarget containing only the commonly available Vars,
+ * and force each sub-path to return that target.
+ *
+ * This coding assumes that the commonly available Vars will appear in
+ * the same order in each subpath target, which should be true but
+ * it's surely an implementation artifact. If it stops being true, we
+ * could fall back on list_intersection(), but that'd be O(N^3).
+ */
+ common_exprs = (List *)
+ copyObject(((Path *) linitial(subpaths))->pathtarget->exprs);
+ for_each_cell(lc2, lnext(list_head(subpaths)))
+ {
+ Path *subpath = (Path *) lfirst(lc2);
+ ListCell *lcs;
+ ListCell *lcc;
+ ListCell *prevc;
+
+ lcs = list_head(subpath->pathtarget->exprs);
+ prevc = NULL;
+ lcc = list_head(common_exprs);
+ while (lcc)
+ {
+ ListCell *nextc = lnext(lcc);
+
+ if (lcs && equal(lfirst(lcs), lfirst(lcc)))
+ {
+ lcs = lnext(lcs);
+ prevc = lcc;
+ }
+ else
+ common_exprs = list_delete_cell(common_exprs, lcc, prevc);
+ lcc = nextc;
+ }
+ }
+ common_target = create_empty_pathtarget();
+ common_target->exprs = common_exprs;
+ set_pathtarget_cost_width(root, common_target);
+ /* Now forcibly apply this target to each subpath */
+ foreach(lc2, subpaths)
+ {
+ Path *subpath = (Path *) lfirst(lc2);
+
+ lfirst(lc2) = create_projection_path(root,
+ joinrel,
+ subpath,
+ common_target);
+ }
+
+ /*
+ * Generate Append path combining the sub-paths for this UNION. The
+ * Append path's pathtarget has to match what is actually coming out
+ * of the subpaths, since Append can't project.
+ */
+ appendpath = (Path *) create_append_path(joinrel, subpaths,
+ NULL, 0, NIL);
+ appendpath->pathtarget = common_target;
+
+ /*
+ * Make the operator and expression lists needed for the Unique path.
+ * We need to unique-ify on every CTID that is commonly available from
+ * all the sub-paths. (See discussion at head of file.)
+ */
+ uniq_operators = uniq_exprs = NIL;
+ foreach(lc2, common_exprs)
+ {
+ Var *var = (Var *) lfirst(lc2);
+
+ if (IsA(var, Var) &&
+ var->varattno == SelfItemPointerAttributeNumber &&
+ var->varlevelsup == 0)
+ {
+ Assert(var->vartype == TIDOID);
+ uniq_operators = lappend_oid(uniq_operators, TIDEqualOperator);
+ uniq_exprs = lappend(uniq_exprs, var);
+ }
+ }
+ Assert(uniq_exprs != NIL);
+
+ /*
+ * Generate a Unique path representing the de-duplication step. For
+ * now, we can only consider sort+unique implementation, since we lack
+ * hashing support for type "tid".
+ *
+ * XXX maybe refactor to share some code with create_unique_path()?
+ */
+ pathnode = makeNode(UniquePath);
+
+ pathnode->path.pathtype = T_Unique;
+ pathnode->path.parent = joinrel;
+ pathnode->path.pathtarget = appendpath->pathtarget;
+ pathnode->path.param_info = appendpath->param_info;
+ pathnode->path.parallel_aware = false;
+ pathnode->path.parallel_safe = joinrel->consider_parallel &&
+ appendpath->parallel_safe;
+ pathnode->path.parallel_workers = appendpath->parallel_workers;
+
+ /*
+ * Treat the output as unsorted, since it almost certainly doesn't
+ * match any useful pathkeys.
+ */
+ pathnode->path.pathkeys = NIL;
+
+ pathnode->subpath = appendpath;
+ pathnode->in_operators = uniq_operators;
+ pathnode->uniq_exprs = uniq_exprs;
+
+ /* Estimate number of output rows */
+ pathnode->path.rows = appendpath->rows;
+ numCols = list_length(uniq_exprs);
+
+ /*
+ * Estimate cost for sort+unique implementation
+ */
+ cost_sort(&sort_path, root, NIL,
+ appendpath->total_cost,
+ appendpath->rows,
+ appendpath->pathtarget->width,
+ 0.0,
+ work_mem,
+ -1.0);
+
+ /*
+ * Charge one cpu_operator_cost per comparison per input tuple. We
+ * assume all columns get compared at most of the tuples. (XXX
+ * probably this is an overestimate.) This should agree with
+ * create_unique_path.
+ */
+ sort_path.total_cost += cpu_operator_cost * appendpath->rows * numCols;
+
+ pathnode->umethod = UNIQUE_PATH_SORT;
+
+ pathnode->path.startup_cost = sort_path.startup_cost;
+ pathnode->path.total_cost = sort_path.total_cost;
+
+ /* Attach it to the joinrel */
+ add_path(joinrel, (Path *) pathnode);
+ }
+
+ /* We need to refigure which is the cheapest path for the joinrel */
+ set_cheapest(joinrel);
+ }
+
+ /*
+ * Is this OR clause a suitable clause for splitting?
+ *
+ * Each of its arms must reference just one rel, and they must not all be
+ * the same rel.
+ * On success, pass back a list of the relids referenced by each OR arm,
+ * so we don't have to repeat the pull_varnos() work later.
+ */
+ static bool
+ is_suitable_join_or_clause(BoolExpr *orclause, List **relids)
+ {
+ bool ok = false;
+ List *relidlist = NIL;
+ int firstrelid = 0;
+ ListCell *lc;
+
+ *relids = NIL; /* prevent uninitialized-variable warnings */
+ foreach(lc, orclause->args)
+ {
+ Node *qual = (Node *) lfirst(lc);
+ Relids varnos = pull_varnos(qual);
+ int relid;
+
+ if (!bms_get_singleton_member(varnos, &relid))
+ return false; /* this arm fails the sine qua non */
+ if (relidlist == NIL)
+ firstrelid = relid;
+ else if (firstrelid != relid)
+ ok = true; /* arms reference more than one relid */
+ relidlist = lappend_int(relidlist, relid);
+ }
+ *relids = relidlist;
+ return ok;
+ }
+
+ /*
+ * Is query as a whole safe to apply union OR transformation to?
+ * This checks relatively-expensive conditions that we don't want to
+ * worry about until we've found a candidate OR clause.
+ */
+ static bool
+ is_query_safe_for_union_or_transform(PlannerInfo *root)
+ {
+ Query *parse = root->parse;
+ Relids allbaserels;
+ ListCell *lc;
+ int relid;
+
+ /*
+ * Must not have any volatile functions in FROM or WHERE (see notes at
+ * head of file).
+ */
+ if (contain_volatile_functions((Node *) parse->jointree))
+ return false;
+
+ /*
+ * We insist that all baserels used in the query be plain relations, so
+ * that we can use their ctids as unique row identifiers in the UNION
+ * step. One could imagine ways to relax this later, for instance by
+ * forcibly adding WITH ORDINALITY to function RTEs. We'd have to examine
+ * each RTE anyway, though, to check for volatile functions.
+ */
+ allbaserels = get_relids_in_jointree((Node *) parse->jointree, false);
+ relid = 0;
+ foreach(lc, parse->rtable)
+ {
+ RangeTblEntry *rte = (RangeTblEntry *) lfirst(lc);
+
+ relid++;
+
+ /* fail if query contains any FULL joins (see head of this file) */
+ if (rte->rtekind == RTE_JOIN && rte->jointype == JOIN_FULL)
+ return false;
+
+ /* otherwise, ignore RTEs that aren't referenced baserels */
+ if (!bms_is_member(relid, allbaserels))
+ continue;
+
+ /* fail if not plain rel */
+ if (rte->rtekind != RTE_RELATION)
+ return false;
+ /* fail if it doesn't have CTIDs */
+ if (rte->relkind != RELKIND_RELATION &&
+ rte->relkind != RELKIND_MATVIEW)
+ return false;
+
+ /* disallow TABLESAMPLE (might be okay if repeatable?) */
+ if (rte->tablesample)
+ return false;
+
+ /* check for volatiles in security barrier quals */
+ if (contain_volatile_functions((Node *) rte->securityQuals))
+ return false;
+ }
+
+ /* OK to proceed */
+ return true;
+ }
+
+ /*
+ * Split the query and the given OR clause into one UNION arm per relation
+ * mentioned in the OR clause, and make a list of best paths for the UNION
+ * arms. (Since the UNION step will lose any ordering or fast-start
+ * properties of the paths, there's no need to consider any but the
+ * cheapest-total path for each arm; hence it's okay to return just one path
+ * per arm.)
+ *
+ * "n" is the OR clause's index in the query's WHERE list.
+ * "armrelids" is the OR-arm-to-referenced-rel mapping.
+ */
+ static List *
+ create_union_or_subpaths(PlannerInfo *root, BoolExpr *orclause,
+ int n, List *armrelids)
+ {
+ List *subpaths = NIL;
+ Relids orrels;
+ int relid;
+ ListCell *lc;
+ ListCell *lc2;
+
+ /*
+ * There might be multiple OR arms referring to the same rel, which we
+ * should combine into a restriction OR clause. So first identify the set
+ * of rels used in the OR.
+ */
+ orrels = NULL;
+ foreach(lc, armrelids)
+ orrels = bms_add_member(orrels, lfirst_int(lc));
+
+ /* Now, for each such rel, generate a path for a UNION arm */
+ while ((relid = bms_first_member(orrels)) >= 0)
+ {
+ List *orarms;
+ PlannerInfo *subroot;
+ Query *parse;
+ List *subquery_quals;
+ bool hasOuterJoins;
+ RelOptInfo *final_rel;
+ Path *subpath;
+ int k;
+ ListCell *prev;
+
+ /* Extract the OR arms for this rel, making copies for safety */
+ orarms = NIL;
+ forboth(lc, orclause->args, lc2, armrelids)
+ {
+ Node *qual = (Node *) lfirst(lc);
+ int qualrelid = lfirst_int(lc2);
+
+ if (qualrelid == relid)
+ orarms = lappend(orarms, copyObject(qual));
+ }
+ Assert(orarms != NIL);
+ if (list_length(orarms) == 1)
+ {
+ /*
+ * When there's just a single arm for this rel (the typical case),
+ * it goes directly into the subquery's WHERE list. But it might
+ * be a sub-AND, in which case we must flatten it into a qual list
+ * to preserve AND/OR flatness.
+ */
+ orarms = make_ands_implicit((Expr *) linitial(orarms));
+ }
+ else
+ {
+ /*
+ * When there's more than one arm, convert back to an OR clause.
+ * No flatness worries here; the arms were already valid OR-list
+ * elements.
+ */
+ orarms = list_make1(make_orclause(orarms));
+ }
+
+ /* Clone the planner's state */
+ subroot = (PlannerInfo *) palloc(sizeof(PlannerInfo));
+ memcpy(subroot, root, sizeof(PlannerInfo));
+ subroot->parse = parse = (Query *) copyObject(root->parse);
+ /* Making copies of these might be overkill, but be safe */
+ subroot->processed_tlist = (List *) copyObject(root->processed_tlist);
+ subroot->append_rel_list = (List *) copyObject(root->append_rel_list);
+ /* Tell query_planner to expect full retrieval of UNION input */
+ subroot->tuple_fraction = 1.0;
+ subroot->limit_tuples = -1.0;
+
+ /*
+ * Remove the subquery's copy of the original OR clause, which we
+ * identify by its index in the WHERE clause list.
+ */
+ subquery_quals = (List *) parse->jointree->quals;
+ k = 0;
+ prev = NULL;
+ foreach(lc, subquery_quals)
+ {
+ if (k == n)
+ {
+ subquery_quals = list_delete_cell(subquery_quals, lc, prev);
+ break;
+ }
+ k++;
+ prev = lc;
+ }
+
+ /* And instead add the qual or quals we extracted from the OR clause */
+ subquery_quals = list_concat(subquery_quals, orarms);
+ parse->jointree->quals = (Node *) subquery_quals;
+
+ /*
+ * Ask for baserel CTIDs to be added to the output of the subquery. We
+ * only want CTIDs of rels that will survive join removal, so we can't
+ * add them now, as that would in itself prevent join removal.
+ */
+ subroot->needBaseTids = true;
+
+ /* Re-apply reduce_outer_joins() in case we can now reduce some */
+ /* (XXX would be better if this just got moved into query_planner) */
+ hasOuterJoins = false;
+ foreach(lc, parse->rtable)
+ {
+ RangeTblEntry *rte = (RangeTblEntry *) lfirst(lc);
+
+ if (rte->rtekind == RTE_JOIN)
+ {
+ if (IS_OUTER_JOIN(rte->jointype))
+ {
+ hasOuterJoins = true;
+ break;
+ }
+ }
+ }
+ if (hasOuterJoins)
+ reduce_outer_joins(subroot);
+
+ /* Plan the modified query */
+ final_rel = query_planner(subroot, subroot->processed_tlist,
+ union_or_qp_callback, NULL);
+
+ /*
+ * Get the cheapest-total path for the subquery; there's little value
+ * in considering any others.
+ */
+ subpath = final_rel->cheapest_total_path;
+ Assert(subpath);
+
+ /* Add cheapest-total path to subpaths list */
+ subpaths = lappend(subpaths, subpath);
+ }
+
+ return subpaths;
+ }
+
+ /*
+ * Compute query_pathkeys and other pathkeys during plan generation
+ */
+ static void
+ union_or_qp_callback(PlannerInfo *root, void *extra)
+ {
+ /*
+ * Since the output of the subquery is going to go through a UNION step
+ * that destroys ordering, there's little need to worry about what its
+ * output order is. Hence, don't bother telling it about pathkeys that
+ * might apply to these later execution steps.
+ */
+ root->group_pathkeys = NIL;
+ root->window_pathkeys = NIL;
+ root->distinct_pathkeys = NIL;
+ root->sort_pathkeys = NIL;
+ root->query_pathkeys = NIL;
+ }
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index f3bb73a..71e7428 100644
*** a/src/backend/optimizer/prep/prepjointree.c
--- b/src/backend/optimizer/prep/prepjointree.c
*************** pull_up_simple_subquery(PlannerInfo *roo
*** 914,919 ****
--- 914,920 ----
subroot->grouping_map = NULL;
subroot->minmax_aggs = NIL;
subroot->qual_security_level = 0;
+ subroot->needBaseTids = false;
subroot->hasInheritedTarget = false;
subroot->hasRecursion = false;
subroot->wt_param_id = -1;
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index a39e59d..b21c6d4 100644
*** a/src/include/nodes/relation.h
--- b/src/include/nodes/relation.h
*************** typedef struct PlannerInfo
*** 294,299 ****
--- 294,300 ----
Index qual_security_level; /* minimum security_level for quals */
/* Note: qual_security_level is zero if there are no securityQuals */
+ bool needBaseTids; /* true to force outputting baserel CTIDs */
bool hasInheritedTarget; /* true if parse->resultRelation is an
* inheritance child rel */
bool hasJoinRTEs; /* true if any RTEs are RTE_JOIN kind */
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index f1d16cf..a2bfe15 100644
*** a/src/include/optimizer/planmain.h
--- b/src/include/optimizer/planmain.h
*************** extern RelOptInfo *query_planner(Planner
*** 45,50 ****
--- 45,58 ----
extern void preprocess_minmax_aggregates(PlannerInfo *root, List *tlist);
/*
+ * prototypes for plan/planunionor.c
+ */
+ extern List *split_join_or_clauses(PlannerInfo *root);
+ extern void add_base_rel_ctids(PlannerInfo *root);
+ extern void finish_union_or_paths(PlannerInfo *root, RelOptInfo *joinrel,
+ List *union_or_subpaths);
+
+ /*
* prototypes for plan/createplan.c
*/
extern Plan *create_plan(PlannerInfo *root, Path *best_path);
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Re: Improve OR conditions on joined columns (commonstar schema problem)
From
Michael Paquier
Date:
On Tue, Sep 12, 2017 at 9:48 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote: > Jim Nasby <jim.nasby@openscg.com> writes: >> I've verified that the patch still applies and make check-world is clean. > > Not any more :-(. Here's a v3 rebased over HEAD. No substantive > change from v2. Patch applies and compiles, and it got no reviews. Moved to CF 2018-01. -- Michael
Re: [HACKERS] Re: Improve OR conditions on joined columns (common star schema problem)
From
Tom Lane
Date:
I wrote:
> Jim Nasby <jim.nasby@openscg.com> writes:
>> I've verified that the patch still applies and make check-world is clean.
> Not any more :-(. Here's a v3 rebased over HEAD. No substantive
> change from v2.
Again rebased up to HEAD; still no substantive changes.
regards, tom lane
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 5e72df1..1644f8b 100644
*** a/src/backend/nodes/outfuncs.c
--- b/src/backend/nodes/outfuncs.c
*************** _outPlannerInfo(StringInfo str, const Pl
*** 2237,2242 ****
--- 2237,2243 ----
WRITE_FLOAT_FIELD(tuple_fraction, "%.4f");
WRITE_FLOAT_FIELD(limit_tuples, "%.0f");
WRITE_UINT_FIELD(qual_security_level);
+ WRITE_BOOL_FIELD(needBaseTids);
WRITE_BOOL_FIELD(hasInheritedTarget);
WRITE_BOOL_FIELD(hasJoinRTEs);
WRITE_BOOL_FIELD(hasLateralRTEs);
diff --git a/src/backend/optimizer/plan/Makefile b/src/backend/optimizer/plan/Makefile
index 88a9f7f..1db6bd5 100644
*** a/src/backend/optimizer/plan/Makefile
--- b/src/backend/optimizer/plan/Makefile
*************** top_builddir = ../../../..
*** 13,18 ****
include $(top_builddir)/src/Makefile.global
OBJS = analyzejoins.o createplan.o initsplan.o planagg.o planmain.o planner.o \
! setrefs.o subselect.o
include $(top_srcdir)/src/backend/common.mk
--- 13,18 ----
include $(top_builddir)/src/Makefile.global
OBJS = analyzejoins.o createplan.o initsplan.o planagg.o planmain.o planner.o \
! planunionor.o setrefs.o subselect.o
include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index ef25fef..c99b028 100644
*** a/src/backend/optimizer/plan/analyzejoins.c
--- b/src/backend/optimizer/plan/analyzejoins.c
*************** clause_sides_match_join(RestrictInfo *ri
*** 154,159 ****
--- 154,162 ----
* cases, but we don't have the infrastructure to prove them.) We also
* have to check that the inner side doesn't generate any variables needed
* above the join.
+ *
+ * Note: making this significantly smarter might break planunionor.c.
+ * Study that file before doing so.
*/
static bool
join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index 7a34abc..cd09aaa 100644
*** a/src/backend/optimizer/plan/planmain.c
--- b/src/backend/optimizer/plan/planmain.c
*************** query_planner(PlannerInfo *root, List *t
*** 206,211 ****
--- 206,219 ----
add_placeholders_to_base_rels(root);
/*
+ * Also, if we have a request to emit baserel CTIDs, add those to the
+ * baserel targetlists now. This likewise has to be done after join
+ * removal, because we only want CTIDs for rels that survive join removal.
+ */
+ if (root->needBaseTids)
+ add_base_rel_ctids(root);
+
+ /*
* Construct the lateral reference sets now that we have finalized
* PlaceHolderVar eval levels.
*/
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 7b52dad..3a29d8d 100644
*** a/src/backend/optimizer/plan/planner.c
--- b/src/backend/optimizer/plan/planner.c
*************** subquery_planner(PlannerGlobal *glob, Qu
*** 547,552 ****
--- 547,553 ----
root->grouping_map = NULL;
root->minmax_aggs = NIL;
root->qual_security_level = 0;
+ root->needBaseTids = false;
root->hasInheritedTarget = false;
root->hasRecursion = hasRecursion;
if (hasRecursion)
*************** grouping_planner(PlannerInfo *root, bool
*** 1667,1672 ****
--- 1668,1674 ----
WindowFuncLists *wflists = NULL;
List *activeWindows = NIL;
grouping_sets_data *gset_data = NULL;
+ List *union_or_subpaths;
standard_qp_extra qp_extra;
/* A recursive query should always have setOperations */
*************** grouping_planner(PlannerInfo *root, bool
*** 1744,1749 ****
--- 1746,1759 ----
preprocess_minmax_aggregates(root, tlist);
/*
+ * Preprocess join OR clauses that might be better handled as UNIONs.
+ * This likewise needs to be close to the query_planner() call. But
+ * it doesn't matter which of preprocess_minmax_aggregates() and this
+ * function we call first, because they treat disjoint sets of cases.
+ */
+ union_or_subpaths = split_join_or_clauses(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
* hard limit overall, it doesn't apply if the query has any
*************** grouping_planner(PlannerInfo *root, bool
*** 1778,1783 ****
--- 1788,1801 ----
standard_qp_callback, &qp_extra);
/*
+ * If we found any way to convert a join OR clause to a union, finish
+ * up generating the path(s) for that, and add them into the topmost
+ * scan/join relation.
+ */
+ if (union_or_subpaths)
+ finish_union_or_paths(root, current_rel, union_or_subpaths);
+
+ /*
* Convert the query's result tlist into PathTarget format.
*
* Note: it's desirable to not do this till after query_planner(),
diff --git a/src/backend/optimizer/plan/planunionor.c b/src/backend/optimizer/plan/planunionor.c
index ...dd11e72 .
*** a/src/backend/optimizer/plan/planunionor.c
--- b/src/backend/optimizer/plan/planunionor.c
***************
*** 0 ****
--- 1,667 ----
+ /*-------------------------------------------------------------------------
+ *
+ * planunionor.c
+ * Consider whether join OR clauses can be converted to UNION queries.
+ *
+ * This module looks for OR clauses whose arms each reference a single
+ * query relation (but not all the same rel), and tries to generate a path
+ * representing conversion of such an OR clause into a UNION operation.
+ * For example,
+ * SELECT ... FROM a, b WHERE (cond-on-A OR cond-on-B) AND other-conds
+ * can be implemented as
+ * SELECT ... FROM a, b WHERE cond-on-A AND other-conds
+ * UNION
+ * SELECT ... FROM a, b WHERE cond-on-B AND other-conds
+ * given a suitable definition of "UNION" (one that won't merge rows that
+ * would have been separate in the original query output). Since this change
+ * converts join clauses into restriction clauses, the modified query can be
+ * much faster to run than the original, despite the duplication of effort
+ * involved and the extra UNION processing. It's particularly useful for
+ * star-schema queries where the OR arms reference different dimension tables;
+ * each separated query may be able to remove joins to all but one dimension
+ * table, and arrange that join to use an inner indexscan on the fact table.
+ *
+ * We must insist that the WHERE and JOIN/ON clauses contain no volatile
+ * functions, because of the likelihood that qual clauses will be evaluated
+ * more times than a naive programmer would expect. We need not restrict
+ * the SELECT's tlist, because that will be evaluated after the UNION.
+ *
+ * The current implementation of the UNION step is to de-duplicate using
+ * row CTIDs. A big limitation is that this only works on plain relations,
+ * and not for instance on foreign tables. Another problem is that we can
+ * only de-duplicate by sort/unique, not hashing; but that could be fixed
+ * if we write a hash opclass for TID.
+ *
+ * To allow join removal to happen, we can't reference the CTID column
+ * of an otherwise-removable relation. Therefore, this code proceeds by
+ * de-duplicating output rows using only the CTIDs of relations that are not
+ * removable in any UNION arm. It is not immediately obvious that that works
+ * at all, but it does, given one restriction. If a rel is removed in some
+ * arm, then it is not referenced above the joins in that arm (in particular,
+ * it's not used in that arm's version of the OR clause), and we were able
+ * to prove that removing it doesn't change the output rowcount in that arm.
+ * Therefore there's no need to consider it for de-duplication so far as that
+ * arm's output is concerned. The identical proof can be expected to apply
+ * in other arms, except in an arm that references that rel in its version
+ * of the OR clause. But in such an arm, we have effectively added a
+ * restriction clause to what is known in other arms, which means that the
+ * set of rows output by that rel can't increase compared to other arms.
+ * Therefore the situation in such an arm must be that including the rel
+ * could result in either zero or one output row, rather than exactly one
+ * output row as in other arms. So we still don't need to consider it for
+ * de-duplication. But there's a hole in this argument, which is that we
+ * must consider the effects of reduce_outer_joins() as well as
+ * remove_useless_joins(). Addition of a restriction clause could result in
+ * simplifying a FULL join into a LEFT join, which might allow join removal
+ * to happen against the right side of that join; but the same proof would
+ * fail in arms that didn't restrict the left side. We deal with this issue
+ * by not attempting union OR transformation if the query has any FULL joins.
+ *
+ *
+ * Portions Copyright (c) 1996-2018, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ * src/backend/optimizer/plan/planunionor.c
+ *
+ *-------------------------------------------------------------------------
+ */
+ #include "postgres.h"
+
+ #include "access/sysattr.h"
+ #include "catalog/pg_class.h"
+ #include "catalog/pg_operator.h"
+ #include "catalog/pg_type.h"
+ #include "miscadmin.h"
+ #include "nodes/makefuncs.h"
+ #include "optimizer/clauses.h"
+ #include "optimizer/cost.h"
+ #include "optimizer/pathnode.h"
+ #include "optimizer/planmain.h"
+ #include "optimizer/prep.h"
+ #include "optimizer/subselect.h"
+ #include "optimizer/tlist.h"
+ #include "optimizer/var.h"
+
+
+ static bool is_suitable_join_or_clause(BoolExpr *orclause, List **relids);
+ static bool is_query_safe_for_union_or_transform(PlannerInfo *root);
+ static List *create_union_or_subpaths(PlannerInfo *root, BoolExpr *orclause,
+ int n, List *armrelids);
+ static void union_or_qp_callback(PlannerInfo *root, void *extra);
+
+
+ /*
+ * split_join_or_clauses - create paths based on splitting join OR clauses
+ *
+ * This should be called by grouping_planner() just before it's ready to call
+ * query_planner(), because we generate simplified join paths by cloning the
+ * planner's state and invoking query_planner() on a modified version of
+ * the query parsetree. Thus, all preprocessing needed before query_planner()
+ * must already be done. Note however that we repeat reduce_outer_joins()
+ * because of the possibility that the simplified WHERE clause allows reduction
+ * of an outer join to inner-join form. That's okay for now, but maybe we
+ * should move the reduce_outer_joins() call into query_planner()?
+ *
+ * The result is a list (one entry per potential union OR path) of sublists of
+ * best paths for the inputs to the UNION step. Adding the UNION processing
+ * is retty mechanical, but we can't do it until we have a RelOptInfo for the
+ * top-level join rel.
+ */
+ List *
+ split_join_or_clauses(PlannerInfo *root)
+ {
+ List *results = NIL;
+ Query *parse = root->parse;
+ bool checked_query = false;
+ ListCell *lc;
+ int n;
+
+ /*
+ * At least for now, we restrict this optimization to plain SELECTs.
+ */
+ if (parse->commandType != CMD_SELECT ||
+ parse->rowMarks ||
+ parse->setOperations)
+ return NIL;
+
+ /*
+ * Reject if query contains any CTEs; copying them would break
+ * single-evaluation semantics. (In principle we could arrange for all
+ * UNION arms to read from a single instance of a CTE, but that's an
+ * improvement for another day, especially since we have no way to de-dup
+ * CTE outputs anyway.)
+ */
+ if (parse->cteList)
+ return NIL;
+
+ /*
+ * The query must reference multiple tables, else we certainly aren't
+ * going to find any suitable OR clauses. Do a quick check that there's
+ * more than one RTE.
+ */
+ if (list_length(parse->rtable) < 2)
+ return NIL;
+
+ /*
+ * Scan the top-level WHERE clause looking for suitable OR clauses, and
+ * for each one, generate paths for the UNION input sub-queries. There
+ * might be more than one suitable OR clause, in which case we can try the
+ * transformation for each one of them separately and add that list of
+ * paths to the results.
+ *
+ * XXX we should also search the JOIN/ON clauses of any top-level inner
+ * JOIN nodes, since those are semantically equivalent to WHERE. But it's
+ * hard to see how to do that without either copying the whole JOIN tree
+ * in advance or repeating the search after copying, and neither of those
+ * options seems attractive.
+ */
+ n = 0;
+ foreach(lc, (List *) parse->jointree->quals)
+ {
+ Node *qual = (Node *) lfirst(lc);
+ List *armrelids;
+
+ if (or_clause(qual) &&
+ is_suitable_join_or_clause((BoolExpr *) qual, &armrelids))
+ {
+ List *subpaths;
+
+ /*
+ * Check that the query as a whole is safe for this optimization.
+ * We only need to do this once, but it's somewhat expensive, so
+ * don't do it till we find a candidate OR clause.
+ */
+ if (!checked_query)
+ {
+ if (!is_query_safe_for_union_or_transform(root))
+ return NIL;
+ checked_query = true;
+ }
+ /* OK, transform the query and create a list of sub-paths */
+ subpaths = create_union_or_subpaths(root, (BoolExpr *) qual,
+ n, armrelids);
+ results = lappend(results, subpaths);
+ }
+ n++;
+ }
+
+ return results;
+ }
+
+ /*
+ * Make sure that a UNION subpath will emit the CTID columns for all its
+ * (surviving) baserels. This is called after we've done join removal in
+ * the UNION arm.
+ */
+ void
+ add_base_rel_ctids(PlannerInfo *root)
+ {
+ Relids allbaserels;
+ List *vars;
+ int brelid;
+
+ /* Find out the set of baserels that survived join removal */
+ allbaserels = get_relids_in_jointree((Node *) root->parse->jointree, false);
+ /* For each such rel, make a Var for its CTID column */
+ vars = NIL;
+ brelid = -1;
+ while ((brelid = bms_next_member(allbaserels, brelid)) >= 0)
+ {
+ Var *var;
+
+ var = makeVar(brelid,
+ SelfItemPointerAttributeNumber,
+ TIDOID,
+ -1,
+ InvalidOid,
+ 0);
+ vars = lappend(vars, var);
+ }
+ /* Add to rel tlists if not present, and mark as needed at top level */
+ add_vars_to_targetlist(root, vars, bms_make_singleton(0), false);
+ }
+
+ /*
+ * Finish constructing Paths representing the UNION implementation of join
+ * OR clause(s), and attach them to "joinrel", which is the final scan/join
+ * relation returned by query_planner() for the conventional implementation of
+ * the query. "union_or_subpaths" is the output of split_join_or_clauses().
+ */
+ void
+ finish_union_or_paths(PlannerInfo *root, RelOptInfo *joinrel,
+ List *union_or_subpaths)
+ {
+ ListCell *lc;
+
+ /* This loop iterates once per splittable OR clause */
+ foreach(lc, union_or_subpaths)
+ {
+ List *subpaths = (List *) lfirst(lc);
+ List *common_exprs;
+ PathTarget *common_target;
+ Path *appendpath;
+ List *uniq_operators;
+ List *uniq_exprs;
+ UniquePath *pathnode;
+ Path sort_path; /* dummy for result of cost_sort */
+ int numCols;
+ ListCell *lc2;
+
+ /*
+ * Join removal in the sub-queries might have resulted in different
+ * sub-paths returning different sets of Vars, in particular we might
+ * not see the full set of artificially-added CTID Vars coming out of
+ * each sub-path. Fortunately, we only need the ones that are
+ * available from every sub-path. Since Append can't project, we need
+ * to build a pathtarget containing only the commonly available Vars,
+ * and force each sub-path to return that target.
+ *
+ * This coding assumes that the commonly available Vars will appear in
+ * the same order in each subpath target, which should be true but
+ * it's surely an implementation artifact. If it stops being true, we
+ * could fall back on list_intersection(), but that'd be O(N^3).
+ */
+ common_exprs = (List *)
+ copyObject(((Path *) linitial(subpaths))->pathtarget->exprs);
+ for_each_cell(lc2, lnext(list_head(subpaths)))
+ {
+ Path *subpath = (Path *) lfirst(lc2);
+ ListCell *lcs;
+ ListCell *lcc;
+ ListCell *prevc;
+
+ lcs = list_head(subpath->pathtarget->exprs);
+ prevc = NULL;
+ lcc = list_head(common_exprs);
+ while (lcc)
+ {
+ ListCell *nextc = lnext(lcc);
+
+ if (lcs && equal(lfirst(lcs), lfirst(lcc)))
+ {
+ lcs = lnext(lcs);
+ prevc = lcc;
+ }
+ else
+ common_exprs = list_delete_cell(common_exprs, lcc, prevc);
+ lcc = nextc;
+ }
+ }
+ common_target = create_empty_pathtarget();
+ common_target->exprs = common_exprs;
+ set_pathtarget_cost_width(root, common_target);
+ /* Now forcibly apply this target to each subpath */
+ foreach(lc2, subpaths)
+ {
+ Path *subpath = (Path *) lfirst(lc2);
+
+ lfirst(lc2) = create_projection_path(root,
+ joinrel,
+ subpath,
+ common_target);
+ }
+
+ /*
+ * Generate Append path combining the sub-paths for this UNION. The
+ * Append path's pathtarget has to match what is actually coming out
+ * of the subpaths, since Append can't project.
+ */
+ appendpath = (Path *) create_append_path(joinrel, subpaths, NIL,
+ NULL, 0, false, NIL, -1);
+ appendpath->pathtarget = common_target;
+
+ /*
+ * Make the operator and expression lists needed for the Unique path.
+ * We need to unique-ify on every CTID that is commonly available from
+ * all the sub-paths. (See discussion at head of file.)
+ */
+ uniq_operators = uniq_exprs = NIL;
+ foreach(lc2, common_exprs)
+ {
+ Var *var = (Var *) lfirst(lc2);
+
+ if (IsA(var, Var) &&
+ var->varattno == SelfItemPointerAttributeNumber &&
+ var->varlevelsup == 0)
+ {
+ Assert(var->vartype == TIDOID);
+ uniq_operators = lappend_oid(uniq_operators, TIDEqualOperator);
+ uniq_exprs = lappend(uniq_exprs, var);
+ }
+ }
+ Assert(uniq_exprs != NIL);
+
+ /*
+ * Generate a Unique path representing the de-duplication step. For
+ * now, we can only consider sort+unique implementation, since we lack
+ * hashing support for type "tid".
+ *
+ * XXX maybe refactor to share some code with create_unique_path()?
+ */
+ pathnode = makeNode(UniquePath);
+
+ pathnode->path.pathtype = T_Unique;
+ pathnode->path.parent = joinrel;
+ pathnode->path.pathtarget = appendpath->pathtarget;
+ pathnode->path.param_info = appendpath->param_info;
+ pathnode->path.parallel_aware = false;
+ pathnode->path.parallel_safe = joinrel->consider_parallel &&
+ appendpath->parallel_safe;
+ pathnode->path.parallel_workers = appendpath->parallel_workers;
+
+ /*
+ * Treat the output as unsorted, since it almost certainly doesn't
+ * match any useful pathkeys.
+ */
+ pathnode->path.pathkeys = NIL;
+
+ pathnode->subpath = appendpath;
+ pathnode->in_operators = uniq_operators;
+ pathnode->uniq_exprs = uniq_exprs;
+
+ /* Estimate number of output rows */
+ pathnode->path.rows = appendpath->rows;
+ numCols = list_length(uniq_exprs);
+
+ /*
+ * Estimate cost for sort+unique implementation
+ */
+ cost_sort(&sort_path, root, NIL,
+ appendpath->total_cost,
+ appendpath->rows,
+ appendpath->pathtarget->width,
+ 0.0,
+ work_mem,
+ -1.0);
+
+ /*
+ * Charge one cpu_operator_cost per comparison per input tuple. We
+ * assume all columns get compared at most of the tuples. (XXX
+ * probably this is an overestimate.) This should agree with
+ * create_unique_path.
+ */
+ sort_path.total_cost += cpu_operator_cost * appendpath->rows * numCols;
+
+ pathnode->umethod = UNIQUE_PATH_SORT;
+
+ pathnode->path.startup_cost = sort_path.startup_cost;
+ pathnode->path.total_cost = sort_path.total_cost;
+
+ /* Attach it to the joinrel */
+ add_path(joinrel, (Path *) pathnode);
+ }
+
+ /* We need to refigure which is the cheapest path for the joinrel */
+ set_cheapest(joinrel);
+ }
+
+ /*
+ * Is this OR clause a suitable clause for splitting?
+ *
+ * Each of its arms must reference just one rel, and they must not all be
+ * the same rel.
+ * On success, pass back a list of the relids referenced by each OR arm,
+ * so we don't have to repeat the pull_varnos() work later.
+ */
+ static bool
+ is_suitable_join_or_clause(BoolExpr *orclause, List **relids)
+ {
+ bool ok = false;
+ List *relidlist = NIL;
+ int firstrelid = 0;
+ ListCell *lc;
+
+ *relids = NIL; /* prevent uninitialized-variable warnings */
+ foreach(lc, orclause->args)
+ {
+ Node *qual = (Node *) lfirst(lc);
+ Relids varnos = pull_varnos(qual);
+ int relid;
+
+ if (!bms_get_singleton_member(varnos, &relid))
+ return false; /* this arm fails the sine qua non */
+ if (relidlist == NIL)
+ firstrelid = relid;
+ else if (firstrelid != relid)
+ ok = true; /* arms reference more than one relid */
+ relidlist = lappend_int(relidlist, relid);
+ }
+ *relids = relidlist;
+ return ok;
+ }
+
+ /*
+ * Is query as a whole safe to apply union OR transformation to?
+ * This checks relatively-expensive conditions that we don't want to
+ * worry about until we've found a candidate OR clause.
+ */
+ static bool
+ is_query_safe_for_union_or_transform(PlannerInfo *root)
+ {
+ Query *parse = root->parse;
+ Relids allbaserels;
+ ListCell *lc;
+ int relid;
+
+ /*
+ * Must not have any volatile functions in FROM or WHERE (see notes at
+ * head of file).
+ */
+ if (contain_volatile_functions((Node *) parse->jointree))
+ return false;
+
+ /*
+ * We insist that all baserels used in the query be plain relations, so
+ * that we can use their ctids as unique row identifiers in the UNION
+ * step. One could imagine ways to relax this later, for instance by
+ * forcibly adding WITH ORDINALITY to function RTEs. We'd have to examine
+ * each RTE anyway, though, to check for volatile functions.
+ */
+ allbaserels = get_relids_in_jointree((Node *) parse->jointree, false);
+ relid = 0;
+ foreach(lc, parse->rtable)
+ {
+ RangeTblEntry *rte = (RangeTblEntry *) lfirst(lc);
+
+ relid++;
+
+ /* fail if query contains any FULL joins (see head of this file) */
+ if (rte->rtekind == RTE_JOIN && rte->jointype == JOIN_FULL)
+ return false;
+
+ /* otherwise, ignore RTEs that aren't referenced baserels */
+ if (!bms_is_member(relid, allbaserels))
+ continue;
+
+ /* fail if not plain rel */
+ if (rte->rtekind != RTE_RELATION)
+ return false;
+ /* fail if it doesn't have CTIDs */
+ if (rte->relkind != RELKIND_RELATION &&
+ rte->relkind != RELKIND_MATVIEW)
+ return false;
+
+ /* disallow TABLESAMPLE (might be okay if repeatable?) */
+ if (rte->tablesample)
+ return false;
+
+ /* check for volatiles in security barrier quals */
+ if (contain_volatile_functions((Node *) rte->securityQuals))
+ return false;
+ }
+
+ /* OK to proceed */
+ return true;
+ }
+
+ /*
+ * Split the query and the given OR clause into one UNION arm per relation
+ * mentioned in the OR clause, and make a list of best paths for the UNION
+ * arms. (Since the UNION step will lose any ordering or fast-start
+ * properties of the paths, there's no need to consider any but the
+ * cheapest-total path for each arm; hence it's okay to return just one path
+ * per arm.)
+ *
+ * "n" is the OR clause's index in the query's WHERE list.
+ * "armrelids" is the OR-arm-to-referenced-rel mapping.
+ */
+ static List *
+ create_union_or_subpaths(PlannerInfo *root, BoolExpr *orclause,
+ int n, List *armrelids)
+ {
+ List *subpaths = NIL;
+ Relids orrels;
+ int relid;
+ ListCell *lc;
+ ListCell *lc2;
+
+ /*
+ * There might be multiple OR arms referring to the same rel, which we
+ * should combine into a restriction OR clause. So first identify the set
+ * of rels used in the OR.
+ */
+ orrels = NULL;
+ foreach(lc, armrelids)
+ orrels = bms_add_member(orrels, lfirst_int(lc));
+
+ /* Now, for each such rel, generate a path for a UNION arm */
+ while ((relid = bms_first_member(orrels)) >= 0)
+ {
+ List *orarms;
+ PlannerInfo *subroot;
+ Query *parse;
+ List *subquery_quals;
+ bool hasOuterJoins;
+ RelOptInfo *final_rel;
+ Path *subpath;
+ int k;
+ ListCell *prev;
+
+ /* Extract the OR arms for this rel, making copies for safety */
+ orarms = NIL;
+ forboth(lc, orclause->args, lc2, armrelids)
+ {
+ Node *qual = (Node *) lfirst(lc);
+ int qualrelid = lfirst_int(lc2);
+
+ if (qualrelid == relid)
+ orarms = lappend(orarms, copyObject(qual));
+ }
+ Assert(orarms != NIL);
+ if (list_length(orarms) == 1)
+ {
+ /*
+ * When there's just a single arm for this rel (the typical case),
+ * it goes directly into the subquery's WHERE list. But it might
+ * be a sub-AND, in which case we must flatten it into a qual list
+ * to preserve AND/OR flatness.
+ */
+ orarms = make_ands_implicit((Expr *) linitial(orarms));
+ }
+ else
+ {
+ /*
+ * When there's more than one arm, convert back to an OR clause.
+ * No flatness worries here; the arms were already valid OR-list
+ * elements.
+ */
+ orarms = list_make1(make_orclause(orarms));
+ }
+
+ /* Clone the planner's state */
+ subroot = (PlannerInfo *) palloc(sizeof(PlannerInfo));
+ memcpy(subroot, root, sizeof(PlannerInfo));
+ subroot->parse = parse = (Query *) copyObject(root->parse);
+ /* Making copies of these might be overkill, but be safe */
+ subroot->processed_tlist = (List *) copyObject(root->processed_tlist);
+ subroot->append_rel_list = (List *) copyObject(root->append_rel_list);
+ /* Tell query_planner to expect full retrieval of UNION input */
+ subroot->tuple_fraction = 1.0;
+ subroot->limit_tuples = -1.0;
+
+ /*
+ * Remove the subquery's copy of the original OR clause, which we
+ * identify by its index in the WHERE clause list.
+ */
+ subquery_quals = (List *) parse->jointree->quals;
+ k = 0;
+ prev = NULL;
+ foreach(lc, subquery_quals)
+ {
+ if (k == n)
+ {
+ subquery_quals = list_delete_cell(subquery_quals, lc, prev);
+ break;
+ }
+ k++;
+ prev = lc;
+ }
+
+ /* And instead add the qual or quals we extracted from the OR clause */
+ subquery_quals = list_concat(subquery_quals, orarms);
+ parse->jointree->quals = (Node *) subquery_quals;
+
+ /*
+ * Ask for baserel CTIDs to be added to the output of the subquery. We
+ * only want CTIDs of rels that will survive join removal, so we can't
+ * add them now, as that would in itself prevent join removal.
+ */
+ subroot->needBaseTids = true;
+
+ /* Re-apply reduce_outer_joins() in case we can now reduce some */
+ /* (XXX would be better if this just got moved into query_planner) */
+ hasOuterJoins = false;
+ foreach(lc, parse->rtable)
+ {
+ RangeTblEntry *rte = (RangeTblEntry *) lfirst(lc);
+
+ if (rte->rtekind == RTE_JOIN)
+ {
+ if (IS_OUTER_JOIN(rte->jointype))
+ {
+ hasOuterJoins = true;
+ break;
+ }
+ }
+ }
+ if (hasOuterJoins)
+ reduce_outer_joins(subroot);
+
+ /* Plan the modified query */
+ final_rel = query_planner(subroot, subroot->processed_tlist,
+ union_or_qp_callback, NULL);
+
+ /*
+ * Get the cheapest-total path for the subquery; there's little value
+ * in considering any others.
+ */
+ subpath = final_rel->cheapest_total_path;
+ Assert(subpath);
+
+ /* Add cheapest-total path to subpaths list */
+ subpaths = lappend(subpaths, subpath);
+ }
+
+ return subpaths;
+ }
+
+ /*
+ * Compute query_pathkeys and other pathkeys during plan generation
+ */
+ static void
+ union_or_qp_callback(PlannerInfo *root, void *extra)
+ {
+ /*
+ * Since the output of the subquery is going to go through a UNION step
+ * that destroys ordering, there's little need to worry about what its
+ * output order is. Hence, don't bother telling it about pathkeys that
+ * might apply to these later execution steps.
+ */
+ root->group_pathkeys = NIL;
+ root->window_pathkeys = NIL;
+ root->distinct_pathkeys = NIL;
+ root->sort_pathkeys = NIL;
+ root->query_pathkeys = NIL;
+ }
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 0e2a220..8d47f4a 100644
*** a/src/backend/optimizer/prep/prepjointree.c
--- b/src/backend/optimizer/prep/prepjointree.c
*************** pull_up_simple_subquery(PlannerInfo *roo
*** 914,919 ****
--- 914,920 ----
subroot->grouping_map = NULL;
subroot->minmax_aggs = NIL;
subroot->qual_security_level = 0;
+ subroot->needBaseTids = false;
subroot->hasInheritedTarget = false;
subroot->hasRecursion = false;
subroot->wt_param_id = -1;
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 71689b8..5a399da 100644
*** a/src/include/nodes/relation.h
--- b/src/include/nodes/relation.h
*************** typedef struct PlannerInfo
*** 297,302 ****
--- 297,303 ----
Index qual_security_level; /* minimum security_level for quals */
/* Note: qual_security_level is zero if there are no securityQuals */
+ bool needBaseTids; /* true to force outputting baserel CTIDs */
bool hasInheritedTarget; /* true if parse->resultRelation is an
* inheritance child rel */
bool hasJoinRTEs; /* true if any RTEs are RTE_JOIN kind */
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index 7132c88..cef62cf 100644
*** a/src/include/optimizer/planmain.h
--- b/src/include/optimizer/planmain.h
*************** extern RelOptInfo *query_planner(Planner
*** 46,51 ****
--- 46,59 ----
extern void preprocess_minmax_aggregates(PlannerInfo *root, List *tlist);
/*
+ * prototypes for plan/planunionor.c
+ */
+ extern List *split_join_or_clauses(PlannerInfo *root);
+ extern void add_base_rel_ctids(PlannerInfo *root);
+ extern void finish_union_or_paths(PlannerInfo *root, RelOptInfo *joinrel,
+ List *union_or_subpaths);
+
+ /*
* prototypes for plan/createplan.c
*/
extern Plan *create_plan(PlannerInfo *root, Path *best_path);
Re: [HACKERS] Re: Improve OR conditions on joined columns (commonstar schema problem)
From
Tomas Vondra
Date:
On 01/04/2018 11:50 PM, Tom Lane wrote: > I wrote: >> Jim Nasby <jim.nasby@openscg.com> writes: >>> I've verified that the patch still applies and make check-world is clean. > >> Not any more :-(. Here's a v3 rebased over HEAD. No substantive >> change from v2. > > Again rebased up to HEAD; still no substantive changes. > ISTM this patch got somewhat stuck as we're not quite sure the transformation is correct in all cases. Is my impression correct? If yes, how to we convince ourselves? Would some sort of automated testing (generating data and queries) help? I'm willing to spend some cycles on that, if considered helpful. regards -- Tomas Vondra http://www.2ndQuadrant.com PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
Re: [HACKERS] Re: Improve OR conditions on joined columns (common star schema problem)
From
Tom Lane
Date:
Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:
> ISTM this patch got somewhat stuck as we're not quite sure the
> transformation is correct in all cases. Is my impression correct?
Yeah, that's the core issue.
> If yes, how to we convince ourselves? Would some sort of automated testing
> (generating data and queries) help? I'm willing to spend some cycles on
> that, if considered helpful.
I'm not sure if that would be enough to convince doubters. On the other
hand, if it found problems, that would definitely be useful.
regards, tom lane
Re: [HACKERS] Re: Improve OR conditions on joined columns (commonstar schema problem)
From
Tomas Vondra
Date:
On 02/02/2018 03:26 PM, Tom Lane wrote: > Tomas Vondra <tomas.vondra@2ndquadrant.com> writes: >> ISTM this patch got somewhat stuck as we're not quite sure the >> transformation is correct in all cases. Is my impression correct? > > Yeah, that's the core issue. > >> If yes, how to we convince ourselves? Would some sort of automated testing >> (generating data and queries) help? I'm willing to spend some cycles on >> that, if considered helpful. > > I'm not sure if that would be enough to convince doubters. On the other > hand, if it found problems, that would definitely be useful. > OK, I'll take a stab at this, then. I wasn't really suggesting it might prove definitely prove the transformation is correct - clearly, it can only find counter-examples. But I think it's worth it anyway. BTW wouldn't it be possible to derive "traditional" proof in relational algebra, similarly to other transforms? regards -- Tomas Vondra http://www.2ndQuadrant.com PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
Re: [HACKERS] Re: Improve OR conditions on joined columns (common star schema problem)
From
Tom Lane
Date:
Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:
> BTW wouldn't it be possible to derive "traditional" proof in relational
> algebra, similarly to other transforms?
Perhaps. The patch depends on CTID, but you could probably model that
as a primary key in a proof.
regards, tom lane
Re: [HACKERS] Re: Improve OR conditions on joined columns (commonstar schema problem)
From
Peter Geoghegan
Date:
On Fri, Feb 2, 2018 at 4:53 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote: > Tomas Vondra <tomas.vondra@2ndquadrant.com> writes: >> BTW wouldn't it be possible to derive "traditional" proof in relational >> algebra, similarly to other transforms? > > Perhaps. The patch depends on CTID, but you could probably model that > as a primary key in a proof. I'll remind you that commit b648b703 made the TID sort performed by CREATE INDEX CONCURRENTLY over 3 times faster in cases where the sort completes in memory. The simplest way to get a significant portion of that benefit for your approach with sort+unique on CTID would be to add sortsupport with abbreviated keys to the TID btree opclass. -- Peter Geoghegan
Re: [HACKERS] Re: Improve OR conditions on joined columns (commonstar schema problem)
From
Andres Freund
Date:
Hi,
I've only skimmed the thread, looking at the patch on its own.
On 2018-01-04 17:50:48 -0500, Tom Lane wrote:
> diff --git a/src/backend/optimizer/plan/plaindex ...dd11e72 .
> --- a/src/backend/optimizer/plan/planunionor.c
> +++ b/src/backend/optimizer/plan/planunionor.c
> @@ -0,0 +1,667 @@
> +/*-------------------------------------------------------------------------
> + *
> + * planunionor.c
> + * Consider whether join OR clauses can be converted to UNION queries.
> + *
> + * The current implementation of the UNION step is to de-duplicate using
> + * row CTIDs.
Could we skip using the ctid if there's a DISTINCT (or something to that
effect) above? We do not need to avoid removing rows that are identical
if that's done anyway.
> A big limitation is that this only works on plain relations,
> + * and not for instance on foreign tables. Another problem is that we can
> + * only de-duplicate by sort/unique, not hashing; but that could be fixed
> + * if we write a hash opclass for TID.
I wonder if an alternative could be some sort of rowid that we invent.
It'd not be that hard to introduce an executor node (or do it in
projection) that simply counts row and returns that as a
column. Together with e.g. range table id that'd be unique. But for that
we would need to guarantee that foreign tables / subqueries /
... returned the same result in two scans. We could do so by pushing
the data gathering into a CTE, but that'd make this exercise moot.
Why can't we ask at least FDWs to return something ctid like?
> + * To allow join removal to happen, we can't reference the CTID column
> + * of an otherwise-removable relation.
A brief hint why wouldn't hurt.
> +/*
> + * Is query as a whole safe to apply union OR transformation to?
> + * This checks relatively-expensive conditions that we don't want to
> + * worry about until we've found a candidate OR clause.
> + */
> +static bool
> +is_query_safe_for_union_or_transform(PlannerInfo *root)
> +{
> + Query *parse = root->parse;
> + Relids allbaserels;
> + ListCell *lc;
> + int relid;
> +
> + /*
> + * Must not have any volatile functions in FROM or WHERE (see notes at
> + * head of file).
> + */
> + if (contain_volatile_functions((Node *) parse->jointree))
> + return false;
Hm, are there any SRFs that could be in relevant places? I think we
reject them everywhere were they'd be problematic (as targetlist is
processed above)?
Do you have any plans for this patch at this moment?
Greetings,
Andres Freund
Re: [HACKERS] Re: Improve OR conditions on joined columns (commonstar schema problem)
From
David Rowley
Date:
On 3 February 2018 at 03:26, Tom Lane <tgl@sss.pgh.pa.us> wrote: > Tomas Vondra <tomas.vondra@2ndquadrant.com> writes: >> ISTM this patch got somewhat stuck as we're not quite sure the >> transformation is correct in all cases. Is my impression correct? > > Yeah, that's the core issue. > >> If yes, how to we convince ourselves? Would some sort of automated testing >> (generating data and queries) help? I'm willing to spend some cycles on >> that, if considered helpful. > > I'm not sure if that would be enough to convince doubters. On the other > hand, if it found problems, that would definitely be useful. I've read over this thread and as far as I can see there is concern that the UNION on the ctids might not re-uniquify the rows again. Tom mentioned a problem with FULL JOINs, but the concern appears to have been invalidated due to wrong thinking about how join removals work. As of now, I'm not quite sure who exactly is concerned. Tom thought there was an issue but quickly corrected himself. As far as I see it, there are a few cases we'd need to disable the optimization: 1. Query contains target SRFs (the same row might get duplicated, we don't want to UNION these duplicates out again, they're meant to be there) 2. Query has setops (ditto) 3. Any base rels are not RELKIND_RELATION (we need the ctid to uniquely identify rows) 4. Query has volatile functions (don't want to evaluate volatile functions more times than requested) As far as the DISTINCT clause doing the right thing for joins, I see no issues, even with FULL JOINs. In both branches of the UNION the join condition will be the same so each side of the join always has the same candidate row to join to. I don't think the optimization is possible if there are OR clauses in the join condition, but that's not being proposed. FULL JOINS appear to be fine as the row is never duplicated on a non-match, so there will only be one version of t1.ctid, NULL::tid or NULL::tid, t1.ctid and all ctids in the distinctClauses cannot all be NULL at once. I used the following SQL to help my brain think through this. There are two versions of each query, one with DISTINCT and one without. If the DISTINCT returns fewer rows than the one without then we need to disable this optimization for that case. I've written queries for 3 of the above 4 cases. I saw from reading the thread that case #4 is already disabled: drop table if exists t1,t2; create table t1 (a int); create table t2 (a int); insert into t1 values(1),(1),(2),(4); insert into t2 values(1),(1),(3),(3),(4),(4); select t1.ctid,t2.ctid from t1 full join t2 on t1.a = t2.a; select distinct t1.ctid,t2.ctid from t1 full join t2 on t1.a = t2.a; -- case 1: must disable in face of tSRFs select ctid from (select ctid,generate_Series(1,2) from t1) t; select distinct ctid from (select ctid,generate_Series(1,2) from t1) t; -- case 2: must disable optimization with setops. select ctid from (select ctid from t1 union all select ctid from t1) t; select distinct ctid from (select ctid from t1 union all select ctid from t1) t; -- case 3: must disable if we join to anything other than a RELKIND_RELATION (no ctid) select ctid from (select t1.ctid from t1 inner join (values(1),(1)) x(x) on t1.a = x.x) t; select distinct ctid from (select t1.ctid from t1 inner join (values(1),(1)) x(x) on t1.a = x.x) t; I've not read the patch yet, but I understand what it's trying to achieve. My feelings about the patch are that it would be useful to have. I think if someone needs this then they'll be very happythat we've added it. I also think there should be a GUC to disable it, and it should be enabled through the entire alpha/beta period, and we should consider what the final value for it should be just before RC1. It's a bit sad to exclude foreign tables, and I'm not too sure what hurdles this leaves out for pluggable storage. No doubt we'll need to disable the optimization for those too unless they can provide us with some row identifier. -- David Rowley http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training & Services
Re: [HACKERS] Re: Improve OR conditions on joined columns (commonstar schema problem)
From
David Rowley
Date:
On 30 March 2018 at 15:05, Andres Freund <andres@anarazel.de> wrote: >> + * To allow join removal to happen, we can't reference the CTID column >> + * of an otherwise-removable relation. > > A brief hint why wouldn't hurt. Maybe something like: /* * Join removal is only ever possible when no columns of the to-be-removed relation * are referenced. If we added the CTID here then we could inadvertently disable join * removal. We'll need to delay adding the CTID until after join removal takes place. */ (I've not read the code, just the thread) -- David Rowley http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training & Services
Re: [HACKERS] Re: Improve OR conditions on joined columns (common star schema problem)
From
Tom Lane
Date:
I wrote:
> [ join-or-to-union-4.patch ]
Rebased up to HEAD, per cfbot nagging. Still no substantive change from
v2.
regards, tom lane
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 6269f47..8935503 100644
*** a/src/backend/nodes/outfuncs.c
--- b/src/backend/nodes/outfuncs.c
*************** _outPlannerInfo(StringInfo str, const Pl
*** 2310,2315 ****
--- 2310,2316 ----
WRITE_FLOAT_FIELD(limit_tuples, "%.0f");
WRITE_UINT_FIELD(qual_security_level);
WRITE_ENUM_FIELD(inhTargetKind, InheritanceKind);
+ WRITE_BOOL_FIELD(needBaseTids);
WRITE_BOOL_FIELD(hasJoinRTEs);
WRITE_BOOL_FIELD(hasLateralRTEs);
WRITE_BOOL_FIELD(hasDeletedRTEs);
diff --git a/src/backend/optimizer/plan/Makefile b/src/backend/optimizer/plan/Makefile
index 88a9f7f..1db6bd5 100644
*** a/src/backend/optimizer/plan/Makefile
--- b/src/backend/optimizer/plan/Makefile
*************** top_builddir = ../../../..
*** 13,18 ****
include $(top_builddir)/src/Makefile.global
OBJS = analyzejoins.o createplan.o initsplan.o planagg.o planmain.o planner.o \
! setrefs.o subselect.o
include $(top_srcdir)/src/backend/common.mk
--- 13,18 ----
include $(top_builddir)/src/Makefile.global
OBJS = analyzejoins.o createplan.o initsplan.o planagg.o planmain.o planner.o \
! planunionor.o setrefs.o subselect.o
include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 0e73f9c..fdffb6b 100644
*** a/src/backend/optimizer/plan/analyzejoins.c
--- b/src/backend/optimizer/plan/analyzejoins.c
*************** clause_sides_match_join(RestrictInfo *ri
*** 155,160 ****
--- 155,163 ----
* cases, but we don't have the infrastructure to prove them.) We also
* have to check that the inner side doesn't generate any variables needed
* above the join.
+ *
+ * Note: making this significantly smarter might break planunionor.c.
+ * Study that file before doing so.
*/
static bool
join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index b05adc7..4486885 100644
*** a/src/backend/optimizer/plan/planmain.c
--- b/src/backend/optimizer/plan/planmain.c
*************** query_planner(PlannerInfo *root, List *t
*** 212,217 ****
--- 212,225 ----
add_placeholders_to_base_rels(root);
/*
+ * Also, if we have a request to emit baserel CTIDs, add those to the
+ * baserel targetlists now. This likewise has to be done after join
+ * removal, because we only want CTIDs for rels that survive join removal.
+ */
+ if (root->needBaseTids)
+ add_base_rel_ctids(root);
+
+ /*
* Construct the lateral reference sets now that we have finalized
* PlaceHolderVar eval levels.
*/
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 96bf060..36907a4 100644
*** a/src/backend/optimizer/plan/planner.c
--- b/src/backend/optimizer/plan/planner.c
*************** subquery_planner(PlannerGlobal *glob, Qu
*** 623,628 ****
--- 623,629 ----
root->minmax_aggs = NIL;
root->qual_security_level = 0;
root->inhTargetKind = INHKIND_NONE;
+ root->needBaseTids = false;
root->hasRecursion = hasRecursion;
if (hasRecursion)
root->wt_param_id = SS_assign_special_param(root);
*************** grouping_planner(PlannerInfo *root, bool
*** 1797,1802 ****
--- 1798,1804 ----
WindowFuncLists *wflists = NULL;
List *activeWindows = NIL;
grouping_sets_data *gset_data = NULL;
+ List *union_or_subpaths;
standard_qp_extra qp_extra;
/* A recursive query should always have setOperations */
*************** grouping_planner(PlannerInfo *root, bool
*** 1874,1879 ****
--- 1876,1889 ----
preprocess_minmax_aggregates(root, tlist);
/*
+ * Preprocess join OR clauses that might be better handled as UNIONs.
+ * This likewise needs to be close to the query_planner() call. But
+ * it doesn't matter which of preprocess_minmax_aggregates() and this
+ * function we call first, because they treat disjoint sets of cases.
+ */
+ union_or_subpaths = split_join_or_clauses(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
* hard limit overall, it doesn't apply if the query has any
*************** grouping_planner(PlannerInfo *root, bool
*** 1908,1913 ****
--- 1918,1931 ----
standard_qp_callback, &qp_extra);
/*
+ * If we found any way to convert a join OR clause to a union, finish
+ * up generating the path(s) for that, and add them into the topmost
+ * scan/join relation.
+ */
+ if (union_or_subpaths)
+ finish_union_or_paths(root, current_rel, union_or_subpaths);
+
+ /*
* Convert the query's result tlist into PathTarget format.
*
* Note: it's desirable to not do this till after query_planner(),
diff --git a/src/backend/optimizer/plan/planunionor.c b/src/backend/optimizer/plan/planunionor.c
index ...08b545f .
*** a/src/backend/optimizer/plan/planunionor.c
--- b/src/backend/optimizer/plan/planunionor.c
***************
*** 0 ****
--- 1,667 ----
+ /*-------------------------------------------------------------------------
+ *
+ * planunionor.c
+ * Consider whether join OR clauses can be converted to UNION queries.
+ *
+ * This module looks for OR clauses whose arms each reference a single
+ * query relation (but not all the same rel), and tries to generate a path
+ * representing conversion of such an OR clause into a UNION operation.
+ * For example,
+ * SELECT ... FROM a, b WHERE (cond-on-A OR cond-on-B) AND other-conds
+ * can be implemented as
+ * SELECT ... FROM a, b WHERE cond-on-A AND other-conds
+ * UNION
+ * SELECT ... FROM a, b WHERE cond-on-B AND other-conds
+ * given a suitable definition of "UNION" (one that won't merge rows that
+ * would have been separate in the original query output). Since this change
+ * converts join clauses into restriction clauses, the modified query can be
+ * much faster to run than the original, despite the duplication of effort
+ * involved and the extra UNION processing. It's particularly useful for
+ * star-schema queries where the OR arms reference different dimension tables;
+ * each separated query may be able to remove joins to all but one dimension
+ * table, and arrange that join to use an inner indexscan on the fact table.
+ *
+ * We must insist that the WHERE and JOIN/ON clauses contain no volatile
+ * functions, because of the likelihood that qual clauses will be evaluated
+ * more times than a naive programmer would expect. We need not restrict
+ * the SELECT's tlist, because that will be evaluated after the UNION.
+ *
+ * The current implementation of the UNION step is to de-duplicate using
+ * row CTIDs. A big limitation is that this only works on plain relations,
+ * and not for instance on foreign tables. Another problem is that we can
+ * only de-duplicate by sort/unique, not hashing; but that could be fixed
+ * if we write a hash opclass for TID.
+ *
+ * To allow join removal to happen, we can't reference the CTID column
+ * of an otherwise-removable relation. Therefore, this code proceeds by
+ * de-duplicating output rows using only the CTIDs of relations that are not
+ * removable in any UNION arm. It is not immediately obvious that that works
+ * at all, but it does, given one restriction. If a rel is removed in some
+ * arm, then it is not referenced above the joins in that arm (in particular,
+ * it's not used in that arm's version of the OR clause), and we were able
+ * to prove that removing it doesn't change the output rowcount in that arm.
+ * Therefore there's no need to consider it for de-duplication so far as that
+ * arm's output is concerned. The identical proof can be expected to apply
+ * in other arms, except in an arm that references that rel in its version
+ * of the OR clause. But in such an arm, we have effectively added a
+ * restriction clause to what is known in other arms, which means that the
+ * set of rows output by that rel can't increase compared to other arms.
+ * Therefore the situation in such an arm must be that including the rel
+ * could result in either zero or one output row, rather than exactly one
+ * output row as in other arms. So we still don't need to consider it for
+ * de-duplication. But there's a hole in this argument, which is that we
+ * must consider the effects of reduce_outer_joins() as well as
+ * remove_useless_joins(). Addition of a restriction clause could result in
+ * simplifying a FULL join into a LEFT join, which might allow join removal
+ * to happen against the right side of that join; but the same proof would
+ * fail in arms that didn't restrict the left side. We deal with this issue
+ * by not attempting union OR transformation if the query has any FULL joins.
+ *
+ *
+ * Portions Copyright (c) 1996-2018, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ * src/backend/optimizer/plan/planunionor.c
+ *
+ *-------------------------------------------------------------------------
+ */
+ #include "postgres.h"
+
+ #include "access/sysattr.h"
+ #include "catalog/pg_class.h"
+ #include "catalog/pg_operator.h"
+ #include "catalog/pg_type.h"
+ #include "miscadmin.h"
+ #include "nodes/makefuncs.h"
+ #include "optimizer/clauses.h"
+ #include "optimizer/cost.h"
+ #include "optimizer/pathnode.h"
+ #include "optimizer/planmain.h"
+ #include "optimizer/prep.h"
+ #include "optimizer/subselect.h"
+ #include "optimizer/tlist.h"
+ #include "optimizer/var.h"
+
+
+ static bool is_suitable_join_or_clause(BoolExpr *orclause, List **relids);
+ static bool is_query_safe_for_union_or_transform(PlannerInfo *root);
+ static List *create_union_or_subpaths(PlannerInfo *root, BoolExpr *orclause,
+ int n, List *armrelids);
+ static void union_or_qp_callback(PlannerInfo *root, void *extra);
+
+
+ /*
+ * split_join_or_clauses - create paths based on splitting join OR clauses
+ *
+ * This should be called by grouping_planner() just before it's ready to call
+ * query_planner(), because we generate simplified join paths by cloning the
+ * planner's state and invoking query_planner() on a modified version of
+ * the query parsetree. Thus, all preprocessing needed before query_planner()
+ * must already be done. Note however that we repeat reduce_outer_joins()
+ * because of the possibility that the simplified WHERE clause allows reduction
+ * of an outer join to inner-join form. That's okay for now, but maybe we
+ * should move the reduce_outer_joins() call into query_planner()?
+ *
+ * The result is a list (one entry per potential union OR path) of sublists of
+ * best paths for the inputs to the UNION step. Adding the UNION processing
+ * is retty mechanical, but we can't do it until we have a RelOptInfo for the
+ * top-level join rel.
+ */
+ List *
+ split_join_or_clauses(PlannerInfo *root)
+ {
+ List *results = NIL;
+ Query *parse = root->parse;
+ bool checked_query = false;
+ ListCell *lc;
+ int n;
+
+ /*
+ * At least for now, we restrict this optimization to plain SELECTs.
+ */
+ if (parse->commandType != CMD_SELECT ||
+ parse->rowMarks ||
+ parse->setOperations)
+ return NIL;
+
+ /*
+ * Reject if query contains any CTEs; copying them would break
+ * single-evaluation semantics. (In principle we could arrange for all
+ * UNION arms to read from a single instance of a CTE, but that's an
+ * improvement for another day, especially since we have no way to de-dup
+ * CTE outputs anyway.)
+ */
+ if (parse->cteList)
+ return NIL;
+
+ /*
+ * The query must reference multiple tables, else we certainly aren't
+ * going to find any suitable OR clauses. Do a quick check that there's
+ * more than one RTE.
+ */
+ if (list_length(parse->rtable) < 2)
+ return NIL;
+
+ /*
+ * Scan the top-level WHERE clause looking for suitable OR clauses, and
+ * for each one, generate paths for the UNION input sub-queries. There
+ * might be more than one suitable OR clause, in which case we can try the
+ * transformation for each one of them separately and add that list of
+ * paths to the results.
+ *
+ * XXX we should also search the JOIN/ON clauses of any top-level inner
+ * JOIN nodes, since those are semantically equivalent to WHERE. But it's
+ * hard to see how to do that without either copying the whole JOIN tree
+ * in advance or repeating the search after copying, and neither of those
+ * options seems attractive.
+ */
+ n = 0;
+ foreach(lc, (List *) parse->jointree->quals)
+ {
+ Node *qual = (Node *) lfirst(lc);
+ List *armrelids;
+
+ if (or_clause(qual) &&
+ is_suitable_join_or_clause((BoolExpr *) qual, &armrelids))
+ {
+ List *subpaths;
+
+ /*
+ * Check that the query as a whole is safe for this optimization.
+ * We only need to do this once, but it's somewhat expensive, so
+ * don't do it till we find a candidate OR clause.
+ */
+ if (!checked_query)
+ {
+ if (!is_query_safe_for_union_or_transform(root))
+ return NIL;
+ checked_query = true;
+ }
+ /* OK, transform the query and create a list of sub-paths */
+ subpaths = create_union_or_subpaths(root, (BoolExpr *) qual,
+ n, armrelids);
+ results = lappend(results, subpaths);
+ }
+ n++;
+ }
+
+ return results;
+ }
+
+ /*
+ * Make sure that a UNION subpath will emit the CTID columns for all its
+ * (surviving) baserels. This is called after we've done join removal in
+ * the UNION arm.
+ */
+ void
+ add_base_rel_ctids(PlannerInfo *root)
+ {
+ Relids allbaserels;
+ List *vars;
+ int brelid;
+
+ /* Find out the set of baserels that survived join removal */
+ allbaserels = get_relids_in_jointree((Node *) root->parse->jointree, false);
+ /* For each such rel, make a Var for its CTID column */
+ vars = NIL;
+ brelid = -1;
+ while ((brelid = bms_next_member(allbaserels, brelid)) >= 0)
+ {
+ Var *var;
+
+ var = makeVar(brelid,
+ SelfItemPointerAttributeNumber,
+ TIDOID,
+ -1,
+ InvalidOid,
+ 0);
+ vars = lappend(vars, var);
+ }
+ /* Add to rel tlists if not present, and mark as needed at top level */
+ add_vars_to_targetlist(root, vars, bms_make_singleton(0), false);
+ }
+
+ /*
+ * Finish constructing Paths representing the UNION implementation of join
+ * OR clause(s), and attach them to "joinrel", which is the final scan/join
+ * relation returned by query_planner() for the conventional implementation of
+ * the query. "union_or_subpaths" is the output of split_join_or_clauses().
+ */
+ void
+ finish_union_or_paths(PlannerInfo *root, RelOptInfo *joinrel,
+ List *union_or_subpaths)
+ {
+ ListCell *lc;
+
+ /* This loop iterates once per splittable OR clause */
+ foreach(lc, union_or_subpaths)
+ {
+ List *subpaths = (List *) lfirst(lc);
+ List *common_exprs;
+ PathTarget *common_target;
+ Path *appendpath;
+ List *uniq_operators;
+ List *uniq_exprs;
+ UniquePath *pathnode;
+ Path sort_path; /* dummy for result of cost_sort */
+ int numCols;
+ ListCell *lc2;
+
+ /*
+ * Join removal in the sub-queries might have resulted in different
+ * sub-paths returning different sets of Vars, in particular we might
+ * not see the full set of artificially-added CTID Vars coming out of
+ * each sub-path. Fortunately, we only need the ones that are
+ * available from every sub-path. Since Append can't project, we need
+ * to build a pathtarget containing only the commonly available Vars,
+ * and force each sub-path to return that target.
+ *
+ * This coding assumes that the commonly available Vars will appear in
+ * the same order in each subpath target, which should be true but
+ * it's surely an implementation artifact. If it stops being true, we
+ * could fall back on list_intersection(), but that'd be O(N^3).
+ */
+ common_exprs = (List *)
+ copyObject(((Path *) linitial(subpaths))->pathtarget->exprs);
+ for_each_cell(lc2, lnext(list_head(subpaths)))
+ {
+ Path *subpath = (Path *) lfirst(lc2);
+ ListCell *lcs;
+ ListCell *lcc;
+ ListCell *prevc;
+
+ lcs = list_head(subpath->pathtarget->exprs);
+ prevc = NULL;
+ lcc = list_head(common_exprs);
+ while (lcc)
+ {
+ ListCell *nextc = lnext(lcc);
+
+ if (lcs && equal(lfirst(lcs), lfirst(lcc)))
+ {
+ lcs = lnext(lcs);
+ prevc = lcc;
+ }
+ else
+ common_exprs = list_delete_cell(common_exprs, lcc, prevc);
+ lcc = nextc;
+ }
+ }
+ common_target = create_empty_pathtarget();
+ common_target->exprs = common_exprs;
+ set_pathtarget_cost_width(root, common_target);
+ /* Now forcibly apply this target to each subpath */
+ foreach(lc2, subpaths)
+ {
+ Path *subpath = (Path *) lfirst(lc2);
+
+ lfirst(lc2) = create_projection_path(root,
+ joinrel,
+ subpath,
+ common_target);
+ }
+
+ /*
+ * Generate Append path combining the sub-paths for this UNION. The
+ * Append path's pathtarget has to match what is actually coming out
+ * of the subpaths, since Append can't project.
+ */
+ appendpath = (Path *) create_append_path(root, joinrel, subpaths, NIL,
+ NULL, 0, false, NIL, -1);
+ appendpath->pathtarget = common_target;
+
+ /*
+ * Make the operator and expression lists needed for the Unique path.
+ * We need to unique-ify on every CTID that is commonly available from
+ * all the sub-paths. (See discussion at head of file.)
+ */
+ uniq_operators = uniq_exprs = NIL;
+ foreach(lc2, common_exprs)
+ {
+ Var *var = (Var *) lfirst(lc2);
+
+ if (IsA(var, Var) &&
+ var->varattno == SelfItemPointerAttributeNumber &&
+ var->varlevelsup == 0)
+ {
+ Assert(var->vartype == TIDOID);
+ uniq_operators = lappend_oid(uniq_operators, TIDEqualOperator);
+ uniq_exprs = lappend(uniq_exprs, var);
+ }
+ }
+ Assert(uniq_exprs != NIL);
+
+ /*
+ * Generate a Unique path representing the de-duplication step. For
+ * now, we can only consider sort+unique implementation, since we lack
+ * hashing support for type "tid".
+ *
+ * XXX maybe refactor to share some code with create_unique_path()?
+ */
+ pathnode = makeNode(UniquePath);
+
+ pathnode->path.pathtype = T_Unique;
+ pathnode->path.parent = joinrel;
+ pathnode->path.pathtarget = appendpath->pathtarget;
+ pathnode->path.param_info = appendpath->param_info;
+ pathnode->path.parallel_aware = false;
+ pathnode->path.parallel_safe = joinrel->consider_parallel &&
+ appendpath->parallel_safe;
+ pathnode->path.parallel_workers = appendpath->parallel_workers;
+
+ /*
+ * Treat the output as unsorted, since it almost certainly doesn't
+ * match any useful pathkeys.
+ */
+ pathnode->path.pathkeys = NIL;
+
+ pathnode->subpath = appendpath;
+ pathnode->in_operators = uniq_operators;
+ pathnode->uniq_exprs = uniq_exprs;
+
+ /* Estimate number of output rows */
+ pathnode->path.rows = appendpath->rows;
+ numCols = list_length(uniq_exprs);
+
+ /*
+ * Estimate cost for sort+unique implementation
+ */
+ cost_sort(&sort_path, root, NIL,
+ appendpath->total_cost,
+ appendpath->rows,
+ appendpath->pathtarget->width,
+ 0.0,
+ work_mem,
+ -1.0);
+
+ /*
+ * Charge one cpu_operator_cost per comparison per input tuple. We
+ * assume all columns get compared at most of the tuples. (XXX
+ * probably this is an overestimate.) This should agree with
+ * create_unique_path.
+ */
+ sort_path.total_cost += cpu_operator_cost * appendpath->rows * numCols;
+
+ pathnode->umethod = UNIQUE_PATH_SORT;
+
+ pathnode->path.startup_cost = sort_path.startup_cost;
+ pathnode->path.total_cost = sort_path.total_cost;
+
+ /* Attach it to the joinrel */
+ add_path(joinrel, (Path *) pathnode);
+ }
+
+ /* We need to refigure which is the cheapest path for the joinrel */
+ set_cheapest(joinrel);
+ }
+
+ /*
+ * Is this OR clause a suitable clause for splitting?
+ *
+ * Each of its arms must reference just one rel, and they must not all be
+ * the same rel.
+ * On success, pass back a list of the relids referenced by each OR arm,
+ * so we don't have to repeat the pull_varnos() work later.
+ */
+ static bool
+ is_suitable_join_or_clause(BoolExpr *orclause, List **relids)
+ {
+ bool ok = false;
+ List *relidlist = NIL;
+ int firstrelid = 0;
+ ListCell *lc;
+
+ *relids = NIL; /* prevent uninitialized-variable warnings */
+ foreach(lc, orclause->args)
+ {
+ Node *qual = (Node *) lfirst(lc);
+ Relids varnos = pull_varnos(qual);
+ int relid;
+
+ if (!bms_get_singleton_member(varnos, &relid))
+ return false; /* this arm fails the sine qua non */
+ if (relidlist == NIL)
+ firstrelid = relid;
+ else if (firstrelid != relid)
+ ok = true; /* arms reference more than one relid */
+ relidlist = lappend_int(relidlist, relid);
+ }
+ *relids = relidlist;
+ return ok;
+ }
+
+ /*
+ * Is query as a whole safe to apply union OR transformation to?
+ * This checks relatively-expensive conditions that we don't want to
+ * worry about until we've found a candidate OR clause.
+ */
+ static bool
+ is_query_safe_for_union_or_transform(PlannerInfo *root)
+ {
+ Query *parse = root->parse;
+ Relids allbaserels;
+ ListCell *lc;
+ int relid;
+
+ /*
+ * Must not have any volatile functions in FROM or WHERE (see notes at
+ * head of file).
+ */
+ if (contain_volatile_functions((Node *) parse->jointree))
+ return false;
+
+ /*
+ * We insist that all baserels used in the query be plain relations, so
+ * that we can use their ctids as unique row identifiers in the UNION
+ * step. One could imagine ways to relax this later, for instance by
+ * forcibly adding WITH ORDINALITY to function RTEs. We'd have to examine
+ * each RTE anyway, though, to check for volatile functions.
+ */
+ allbaserels = get_relids_in_jointree((Node *) parse->jointree, false);
+ relid = 0;
+ foreach(lc, parse->rtable)
+ {
+ RangeTblEntry *rte = (RangeTblEntry *) lfirst(lc);
+
+ relid++;
+
+ /* fail if query contains any FULL joins (see head of this file) */
+ if (rte->rtekind == RTE_JOIN && rte->jointype == JOIN_FULL)
+ return false;
+
+ /* otherwise, ignore RTEs that aren't referenced baserels */
+ if (!bms_is_member(relid, allbaserels))
+ continue;
+
+ /* fail if not plain rel */
+ if (rte->rtekind != RTE_RELATION)
+ return false;
+ /* fail if it doesn't have CTIDs */
+ if (rte->relkind != RELKIND_RELATION &&
+ rte->relkind != RELKIND_MATVIEW)
+ return false;
+
+ /* disallow TABLESAMPLE (might be okay if repeatable?) */
+ if (rte->tablesample)
+ return false;
+
+ /* check for volatiles in security barrier quals */
+ if (contain_volatile_functions((Node *) rte->securityQuals))
+ return false;
+ }
+
+ /* OK to proceed */
+ return true;
+ }
+
+ /*
+ * Split the query and the given OR clause into one UNION arm per relation
+ * mentioned in the OR clause, and make a list of best paths for the UNION
+ * arms. (Since the UNION step will lose any ordering or fast-start
+ * properties of the paths, there's no need to consider any but the
+ * cheapest-total path for each arm; hence it's okay to return just one path
+ * per arm.)
+ *
+ * "n" is the OR clause's index in the query's WHERE list.
+ * "armrelids" is the OR-arm-to-referenced-rel mapping.
+ */
+ static List *
+ create_union_or_subpaths(PlannerInfo *root, BoolExpr *orclause,
+ int n, List *armrelids)
+ {
+ List *subpaths = NIL;
+ Relids orrels;
+ int relid;
+ ListCell *lc;
+ ListCell *lc2;
+
+ /*
+ * There might be multiple OR arms referring to the same rel, which we
+ * should combine into a restriction OR clause. So first identify the set
+ * of rels used in the OR.
+ */
+ orrels = NULL;
+ foreach(lc, armrelids)
+ orrels = bms_add_member(orrels, lfirst_int(lc));
+
+ /* Now, for each such rel, generate a path for a UNION arm */
+ while ((relid = bms_first_member(orrels)) >= 0)
+ {
+ List *orarms;
+ PlannerInfo *subroot;
+ Query *parse;
+ List *subquery_quals;
+ bool hasOuterJoins;
+ RelOptInfo *final_rel;
+ Path *subpath;
+ int k;
+ ListCell *prev;
+
+ /* Extract the OR arms for this rel, making copies for safety */
+ orarms = NIL;
+ forboth(lc, orclause->args, lc2, armrelids)
+ {
+ Node *qual = (Node *) lfirst(lc);
+ int qualrelid = lfirst_int(lc2);
+
+ if (qualrelid == relid)
+ orarms = lappend(orarms, copyObject(qual));
+ }
+ Assert(orarms != NIL);
+ if (list_length(orarms) == 1)
+ {
+ /*
+ * When there's just a single arm for this rel (the typical case),
+ * it goes directly into the subquery's WHERE list. But it might
+ * be a sub-AND, in which case we must flatten it into a qual list
+ * to preserve AND/OR flatness.
+ */
+ orarms = make_ands_implicit((Expr *) linitial(orarms));
+ }
+ else
+ {
+ /*
+ * When there's more than one arm, convert back to an OR clause.
+ * No flatness worries here; the arms were already valid OR-list
+ * elements.
+ */
+ orarms = list_make1(make_orclause(orarms));
+ }
+
+ /* Clone the planner's state */
+ subroot = (PlannerInfo *) palloc(sizeof(PlannerInfo));
+ memcpy(subroot, root, sizeof(PlannerInfo));
+ subroot->parse = parse = (Query *) copyObject(root->parse);
+ /* Making copies of these might be overkill, but be safe */
+ subroot->processed_tlist = (List *) copyObject(root->processed_tlist);
+ subroot->append_rel_list = (List *) copyObject(root->append_rel_list);
+ /* Tell query_planner to expect full retrieval of UNION input */
+ subroot->tuple_fraction = 1.0;
+ subroot->limit_tuples = -1.0;
+
+ /*
+ * Remove the subquery's copy of the original OR clause, which we
+ * identify by its index in the WHERE clause list.
+ */
+ subquery_quals = (List *) parse->jointree->quals;
+ k = 0;
+ prev = NULL;
+ foreach(lc, subquery_quals)
+ {
+ if (k == n)
+ {
+ subquery_quals = list_delete_cell(subquery_quals, lc, prev);
+ break;
+ }
+ k++;
+ prev = lc;
+ }
+
+ /* And instead add the qual or quals we extracted from the OR clause */
+ subquery_quals = list_concat(subquery_quals, orarms);
+ parse->jointree->quals = (Node *) subquery_quals;
+
+ /*
+ * Ask for baserel CTIDs to be added to the output of the subquery. We
+ * only want CTIDs of rels that will survive join removal, so we can't
+ * add them now, as that would in itself prevent join removal.
+ */
+ subroot->needBaseTids = true;
+
+ /* Re-apply reduce_outer_joins() in case we can now reduce some */
+ /* (XXX would be better if this just got moved into query_planner) */
+ hasOuterJoins = false;
+ foreach(lc, parse->rtable)
+ {
+ RangeTblEntry *rte = (RangeTblEntry *) lfirst(lc);
+
+ if (rte->rtekind == RTE_JOIN)
+ {
+ if (IS_OUTER_JOIN(rte->jointype))
+ {
+ hasOuterJoins = true;
+ break;
+ }
+ }
+ }
+ if (hasOuterJoins)
+ reduce_outer_joins(subroot);
+
+ /* Plan the modified query */
+ final_rel = query_planner(subroot, subroot->processed_tlist,
+ union_or_qp_callback, NULL);
+
+ /*
+ * Get the cheapest-total path for the subquery; there's little value
+ * in considering any others.
+ */
+ subpath = final_rel->cheapest_total_path;
+ Assert(subpath);
+
+ /* Add cheapest-total path to subpaths list */
+ subpaths = lappend(subpaths, subpath);
+ }
+
+ return subpaths;
+ }
+
+ /*
+ * Compute query_pathkeys and other pathkeys during plan generation
+ */
+ static void
+ union_or_qp_callback(PlannerInfo *root, void *extra)
+ {
+ /*
+ * Since the output of the subquery is going to go through a UNION step
+ * that destroys ordering, there's little need to worry about what its
+ * output order is. Hence, don't bother telling it about pathkeys that
+ * might apply to these later execution steps.
+ */
+ root->group_pathkeys = NIL;
+ root->window_pathkeys = NIL;
+ root->distinct_pathkeys = NIL;
+ root->sort_pathkeys = NIL;
+ root->query_pathkeys = NIL;
+ }
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index c3f46a2..311f4f1 100644
*** a/src/backend/optimizer/prep/prepjointree.c
--- b/src/backend/optimizer/prep/prepjointree.c
*************** pull_up_simple_subquery(PlannerInfo *roo
*** 915,920 ****
--- 915,921 ----
subroot->minmax_aggs = NIL;
subroot->qual_security_level = 0;
subroot->inhTargetKind = INHKIND_NONE;
+ subroot->needBaseTids = false;
subroot->hasRecursion = false;
subroot->wt_param_id = -1;
subroot->non_recursive_path = NULL;
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 41caf87..f1105a5 100644
*** a/src/include/nodes/relation.h
--- b/src/include/nodes/relation.h
*************** typedef struct PlannerInfo
*** 322,327 ****
--- 322,328 ----
InheritanceKind inhTargetKind; /* indicates if the target relation is an
* inheritance child or partition or a
* partitioned table */
+ bool needBaseTids; /* true to force outputting baserel CTIDs */
bool hasJoinRTEs; /* true if any RTEs are RTE_JOIN kind */
bool hasLateralRTEs; /* true if any RTEs are marked LATERAL */
bool hasDeletedRTEs; /* true if any RTE was deleted from jointree */
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index c8ab028..5c0be2b 100644
*** a/src/include/optimizer/planmain.h
--- b/src/include/optimizer/planmain.h
*************** extern RelOptInfo *query_planner(Planner
*** 46,51 ****
--- 46,59 ----
extern void preprocess_minmax_aggregates(PlannerInfo *root, List *tlist);
/*
+ * prototypes for plan/planunionor.c
+ */
+ extern List *split_join_or_clauses(PlannerInfo *root);
+ extern void add_base_rel_ctids(PlannerInfo *root);
+ extern void finish_union_or_paths(PlannerInfo *root, RelOptInfo *joinrel,
+ List *union_or_subpaths);
+
+ /*
* prototypes for plan/createplan.c
*/
extern Plan *create_plan(PlannerInfo *root, Path *best_path);
Re: [HACKERS] Re: Improve OR conditions on joined columns (commonstar schema problem)
From
Peter Geoghegan
Date:
On Thu, Aug 23, 2018 at 11:10 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote: > Rebased up to HEAD, per cfbot nagging. Still no substantive change from > v2. I happened to have the opportunity to talk to Tom about this patch in person. I expressed some very general concerns that are worth repeating publicly. This patch adds an enhancement that is an example of a broader class of optimizer enhancement primarily aimed at making star-schema queries have more efficient plans, by arranging to use several independent nested loop joins based on a common pattern. Each nestloop join has one particular dimension table on the outer side, and the fact table on the inner side. The query plan is not so much a tree as it is a DAG (directed acyclic graph), because the fact table is visited multiple times. (There are already cases in Postgres in which the query plan is technically a DAG, actually, but it could be taken much further.) Aside from being inherently more efficient, DAG-like star schema plans are also *ideal* targets for parallel query. The executor can execute each nested loop join in a parallel worker with minimal contention -- the inner side of each nestloop join all probe a different fact table index to the others. It's almost like executing several different simple queries concurrently, with some serial processing at the end. Even that serial processing can sometimes be minimized by having some of the parallel workers use a Bloom filter in shared memory. Tom is already concerned that the optimization added by this patch may be too much of a special case, which is understandable. It may be that we're failing to identify some greater opportunity to add DAG-like plans for star schema queries. -- Peter Geoghegan
Re: [HACKERS] Re: Improve OR conditions on joined columns (commonstar schema problem)
From
Peter Geoghegan
Date:
On Thu, Aug 23, 2018 at 5:20 PM, Peter Geoghegan <pg@bowt.ie> wrote: > This patch adds an enhancement that is an example of a broader class > of optimizer enhancement primarily aimed at making star-schema queries > have more efficient plans, by arranging to use several independent > nested loop joins based on a common pattern. Each nestloop join has > one particular dimension table on the outer side, and the fact table > on the inner side. Correction: I meant that for each join, the outer side is a scan of some particular fact table index, while the inner side probes some particular dimension table's primary key, and evaluates the dimension's qual. -- Peter Geoghegan
Re: [HACKERS] Re: Improve OR conditions on joined columns (commonstar schema problem)
From
Noah Misch
Date:
On Sun, Feb 12, 2017 at 09:32:36AM -0800, Tom Lane wrote:
> It's not so much poor choices as the cost of the optimization attempt ---
> if there's a K-relation OR clause, this will increase the cost of planning
> by a factor approaching K+1, whether or not you get a better plan out of
> it. I ran the regression tests with some instrumentation and determined
> that this logic fires a dozen or two times, and fails to produce a plan
> that looks cheaper than the standard plan in any of those cases. So if we
> go down this road, not only do we need a GUC but I suspect it had better
> default to off; only people using star schemas are really likely to get a
> win out of it.
I benchmarked using the attached script. Highlights:
$ perl mk-bench-union-or.pl --dimensions=11 --tests=const | psql -X
# TRAP: FailedAssertion("!(uniq_exprs != ((List *) ((void *)0)))", File: "planunionor.c", Line: 335)
$ perl mk-bench-union-or.pl --dimensions=11 --tests=var --exhaustive --values-per-dimension=0 | psql -X
# TRAP: FailedAssertion("!(list_length(dest_tlist) == list_length(src_tlist))", File: "tlist.c", Line: 344)
$ perl mk-bench-union-or.pl --dimensions=7 --or-clauses=20 --exhaustive --tests=const,rowmark | psql -X
... (with planunionor.c plan)
Planning Time: 1902.013 ms
Execution Time: 291.629 ms
... (without planunionor.c plan)
Planning Time: 11.100 ms
Execution Time: 64.452 ms
# planning 170x slower, chosen plan 4.5x slower
I agree this warrants a GUC, but I propose a goal of making it fitting to
enable by default. The is_suitable_join_or_clause() test is a good indicator
of promising queries, and I suspect it's cheap enough to run all the time. As
a DBA, I'd struggle to predict when is_suitable_join_or_clause() will pass
while the optimization as a whole will lose; I would resort to testing each
important query both ways. In other words, the GUC would boil down to a
planner hint, not to a declaration about the table schema.
On Thu, Aug 23, 2018 at 02:10:46PM -0400, Tom Lane wrote:
> Rebased up to HEAD, per cfbot nagging. Still no substantive change from
> v2.
> + * is retty mechanical, but we can't do it until we have a RelOptInfo for the
Jim Nasby had pointed out this s/retty/pretty/ typo.
> + void
> + finish_union_or_paths(PlannerInfo *root, RelOptInfo *joinrel,
> + List *union_or_subpaths)
> + {
...
> + pathnode = makeNode(UniquePath);
...
> + /* Estimate number of output rows */
> + pathnode->path.rows = appendpath->rows;
If you're going to keep this highly-simplified estimate, please expand the
comment to say why it doesn't matter or what makes it hard to do better. The
non-planunionor.c path for the same query computes its own estimate of the
same underlying quantity. Though it may be too difficult in today's system,
one could copy the competing path's row count estimate here. Perhaps it
doesn't matter because higher-level processing already assumes equal row count
among competitors?
Attachment
Re: [HACKERS] Re: Improve OR conditions on joined columns (commonstar schema problem)
From
Michael Paquier
Date:
On Mon, Sep 03, 2018 at 06:59:10PM -0700, Noah Misch wrote: > If you're going to keep this highly-simplified estimate, please expand the > comment to say why it doesn't matter or what makes it hard to do better. The > non-planunionor.c path for the same query computes its own estimate of the > same underlying quantity. Though it may be too difficult in today's system, > one could copy the competing path's row count estimate here. Perhaps it > doesn't matter because higher-level processing already assumes equal row count > among competitors? As there has been no replies to Noah's review for one month, I am marking this patch as returned with feedback for now. -- Michael
Attachment
Re: [HACKERS] Re: Improve OR conditions on joined columns (common star schema problem)
From
Tom Lane
Date:
Michael Paquier <michael@paquier.xyz> writes:
> On Mon, Sep 03, 2018 at 06:59:10PM -0700, Noah Misch wrote:
>> If you're going to keep this highly-simplified estimate, please expand the
>> comment to say why it doesn't matter or what makes it hard to do better. The
>> non-planunionor.c path for the same query computes its own estimate of the
>> same underlying quantity. Though it may be too difficult in today's system,
>> one could copy the competing path's row count estimate here. Perhaps it
>> doesn't matter because higher-level processing already assumes equal row count
>> among competitors?
> As there has been no replies to Noah's review for one month, I am
> marking this patch as returned with feedback for now.
FWIW, my problem with this patch is that I remain unconvinced of the basic
correctness of the transform (specifically the unique-ification approach).
Noah's points would be important to address if we were moving the patch
towards commit, but I don't see much reason to put effort into it until
we can think of a way to prove whether that works.
regards, tom lane
Re: [HACKERS] Re: Improve OR conditions on joined columns (commonstar schema problem)
From
Noah Misch
Date:
On Mon, Oct 01, 2018 at 09:32:10PM -0400, Tom Lane wrote: > Michael Paquier <michael@paquier.xyz> writes: > > On Mon, Sep 03, 2018 at 06:59:10PM -0700, Noah Misch wrote: > >> If you're going to keep this highly-simplified estimate, please expand the > >> comment to say why it doesn't matter or what makes it hard to do better. The > >> non-planunionor.c path for the same query computes its own estimate of the > >> same underlying quantity. Though it may be too difficult in today's system, > >> one could copy the competing path's row count estimate here. Perhaps it > >> doesn't matter because higher-level processing already assumes equal row count > >> among competitors? > > > As there has been no replies to Noah's review for one month, I am > > marking this patch as returned with feedback for now. > > FWIW, my problem with this patch is that I remain unconvinced of the basic > correctness of the transform (specifically the unique-ification approach). > Noah's points would be important to address if we were moving the patch > towards commit, but I don't see much reason to put effort into it until > we can think of a way to prove whether that works. Not even effort to fix the assertion failures I reported?
Re: [HACKERS] Re: Improve OR conditions on joined columns (common star schema problem)
From
Tom Lane
Date:
Noah Misch <noah@leadboat.com> writes:
> On Mon, Oct 01, 2018 at 09:32:10PM -0400, Tom Lane wrote:
>> FWIW, my problem with this patch is that I remain unconvinced of the basic
>> correctness of the transform (specifically the unique-ification approach).
>> Noah's points would be important to address if we were moving the patch
>> towards commit, but I don't see much reason to put effort into it until
>> we can think of a way to prove whether that works.
> Not even effort to fix the assertion failures I reported?
If it seemed relevant to the proof-of-correctness problem, I would look
into it, but ...
regards, tom lane
Re: [HACKERS] Re: Improve OR conditions on joined columns (commonstar schema problem)
From
Noah Misch
Date:
On Tue, Oct 02, 2018 at 10:53:40AM -0400, Tom Lane wrote: > Noah Misch <noah@leadboat.com> writes: > > On Mon, Oct 01, 2018 at 09:32:10PM -0400, Tom Lane wrote: > >> FWIW, my problem with this patch is that I remain unconvinced of the basic > >> correctness of the transform (specifically the unique-ification approach). > >> Noah's points would be important to address if we were moving the patch > >> towards commit, but I don't see much reason to put effort into it until > >> we can think of a way to prove whether that works. > > > Not even effort to fix the assertion failures I reported? > > If it seemed relevant to the proof-of-correctness problem, I would look > into it, but ... I put some hours into theoretical study of the proof, and I didn't find any holes. When the planner removes "l0 LEFT JOIN r1", it does that because there's one output row per l0.ctid regardless of the rows of r1. Hence, deduplicating on (l0.ctid) is equivalent to deduplicating on (l0.ctid, r1.ctid). In the bad FULL JOIN case, (l0.ctid, r1.ctid) would be sufficient as a key, but we're out of luck because removing the join makes us have only l0.ctid for some tuples and only r1.ctid for other tuples. If PostgreSQL ever gets inner join removal, it would be harder to preserve this optimization in this form. At that point, perhaps we'd cost the path that retains the join for the benefit of $SUBJECT. Given the performance test results, $SUBJECT may already need a cost-based decision on whether to use it.
Re: [HACKERS] Re: Improve OR conditions on joined columns (common star schema problem)
From
Andy Fan
Date:
On Mon, Mar 18, 2019 at 8:09 AM Noah Misch <noah@leadboat.com> wrote:
On Tue, Oct 02, 2018 at 10:53:40AM -0400, Tom Lane wrote:
> Noah Misch <noah@leadboat.com> writes:
> > On Mon, Oct 01, 2018 at 09:32:10PM -0400, Tom Lane wrote:
> >> FWIW, my problem with this patch is that I remain unconvinced of the basic
> >> correctness of the transform (specifically the unique-ification approach).
> >> Noah's points would be important to address if we were moving the patch
> >> towards commit, but I don't see much reason to put effort into it until
> >> we can think of a way to prove whether that works.
>
> > Not even effort to fix the assertion failures I reported?
>
> If it seemed relevant to the proof-of-correctness problem, I would look
> into it, but ...
I put some hours into theoretical study of the proof, and I didn't find any
holes. When the planner removes "l0 LEFT JOIN r1", it does that because
there's one output row per l0.ctid regardless of the rows of r1. Hence,
deduplicating on (l0.ctid) is equivalent to deduplicating on (l0.ctid,
r1.ctid). In the bad FULL JOIN case, (l0.ctid, r1.ctid) would be sufficient
as a key, but we're out of luck because removing the join makes us have only
l0.ctid for some tuples and only r1.ctid for other tuples.
If PostgreSQL ever gets inner join removal, it would be harder to preserve
this optimization in this form. At that point, perhaps we'd cost the path
that retains the join for the benefit of $SUBJECT. Given the performance test
results, $SUBJECT may already need a cost-based decision on whether to use it.
As for the proof-of-correctness problem, I think the below strategy should be
easy to understand.
SELECT * FROM any_v WHERE (A OR B OR C).
=>
SELECT * FROM any_v WHERE A
UNION ALL
SELECT * FROM any_v WHERE B AND !A
UNION ALL
SELECT * FROM any_v WHERE C AND !A AND !(B AND !A);
where !(Expr) means (NOT (expr) OR (EXPR) IS NULL)
In this way, there is no duplicated data at the first. Oracle uses a similar
way like this[1].
- A shared planner info idea.
About the planning time case, suppose we have a query below.
SELECT * FROM t1, t2, ... t20 WHERE (t1.a = 1 or t2.a = 1) and xxx;
With the current strategy, t3 .. t20 would be planned many times, including base
relation like (t3.. t20) and joinrel like (t{3, 4}, t(3,4,5}, t(3,4,5,6}) and
so on. I guess all these relations would get the same result at every time. we
don't need to do that at every section of the Union ALL case. So an idea of
PlannerInfo A can access the planning result of PlannerInfo B comes, this idea
doesn't come in my mind for the first time, many cost based transformations may
need this.
Then I have the following POC in my mind.
PlannerInfo
{
PlannerInfo *shared_planner_info;
Relids or_relids; // this field can be improved later.
};
With this way, if we find a 'relids' is not related to or_relids. We can grab
the planning result from shared_planner_info (in this or-union case, we can set
that after we plan the first section of UNION).
Then I found this one would not work after planning time partition prune since
the relid would change. For example:
P (P1, P2) PARTITION BY A
Q (Q1, Q2) PARTITION BY A
SELECT * FROM t, p, q where (t.a = 1 or p.a = 1). So in the un-transformed
case, Q2 would have relid = 7. After the transform, Q2 probably has relid
= 6.
So basically, I have 4 questions now.
1. Would investing on the shared_planner_info idea be a good idea?
2. Without planning time prune, shall the above design work?
3. Currently I want to use relid to identify a resultset and pathlists which
have the planning time prune issue, should we consider other methods?
4. Any other suggestion about to resolve the 'duplicated planning case' besides
the shared_planner_info method?
easy to understand.
SELECT * FROM any_v WHERE (A OR B OR C).
=>
SELECT * FROM any_v WHERE A
UNION ALL
SELECT * FROM any_v WHERE B AND !A
UNION ALL
SELECT * FROM any_v WHERE C AND !A AND !(B AND !A);
where !(Expr) means (NOT (expr) OR (EXPR) IS NULL)
In this way, there is no duplicated data at the first. Oracle uses a similar
way like this[1].
- A shared planner info idea.
About the planning time case, suppose we have a query below.
SELECT * FROM t1, t2, ... t20 WHERE (t1.a = 1 or t2.a = 1) and xxx;
With the current strategy, t3 .. t20 would be planned many times, including base
relation like (t3.. t20) and joinrel like (t{3, 4}, t(3,4,5}, t(3,4,5,6}) and
so on. I guess all these relations would get the same result at every time. we
don't need to do that at every section of the Union ALL case. So an idea of
PlannerInfo A can access the planning result of PlannerInfo B comes, this idea
doesn't come in my mind for the first time, many cost based transformations may
need this.
Then I have the following POC in my mind.
PlannerInfo
{
PlannerInfo *shared_planner_info;
Relids or_relids; // this field can be improved later.
};
With this way, if we find a 'relids' is not related to or_relids. We can grab
the planning result from shared_planner_info (in this or-union case, we can set
that after we plan the first section of UNION).
Then I found this one would not work after planning time partition prune since
the relid would change. For example:
P (P1, P2) PARTITION BY A
Q (Q1, Q2) PARTITION BY A
SELECT * FROM t, p, q where (t.a = 1 or p.a = 1). So in the un-transformed
case, Q2 would have relid = 7. After the transform, Q2 probably has relid
= 6.
So basically, I have 4 questions now.
1. Would investing on the shared_planner_info idea be a good idea?
2. Without planning time prune, shall the above design work?
3. Currently I want to use relid to identify a resultset and pathlists which
have the planning time prune issue, should we consider other methods?
4. Any other suggestion about to resolve the 'duplicated planning case' besides
the shared_planner_info method?
Best Regards
Andy Fan (https://www.aliyun.com/)