* core.c
* Routines copied from PostgreSQL core distribution.
*
+
+ * The main purpose of this files is having access to static functions in core.
+ * Another purpose is tweaking functions behavior by replacing part of them by
+ * macro definitions. See at the end of pg_hint_plan.c for details. Anyway,
+ * this file *must* contain required functions without making any change.
+ *
+ * This file contains the following functions from corresponding files.
+ *
* src/backend/optimizer/path/allpaths.c
+ *
+ * static functions:
+ * set_plain_rel_pathlist()
* set_append_rel_pathlist()
+ * add_paths_to_append_rel()
* generate_mergeappend_paths()
* get_cheapest_parameterized_child_path()
* accumulate_append_subpath()
- * standard_join_search()
+ *
+ * public functions:
+ * standard_join_search(): This funcion is not static. The reason for
+ * including this function is make_rels_by_clause_joins. In order to
+ * avoid generating apparently unwanted join combination, we decided to
+ * change the behavior of make_join_rel, which is called under this
+ * function.
*
* src/backend/optimizer/path/joinrels.c
- * join_search_one_level()
+ *
+ * public functions:
+ * join_search_one_level(): We have to modify this to call my definition of
+ * make_rels_by_clause_joins.
+ *
+ * static functions:
* make_rels_by_clause_joins()
* make_rels_by_clauseless_joins()
* join_is_legal()
* mark_dummy_rel()
* restriction_is_constant_false()
*
- * Portions Copyright (c) 1996-2014, PostgreSQL Global Development Group
+ *
+ * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
*-------------------------------------------------------------------------
*/
+
+/*
+ * set_plain_rel_pathlist
+ * Build access paths for a plain relation (no subquery, no inheritance)
+ */
+static void
+set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
+{
+ Relids required_outer;
+
+ /*
+ * We don't support pushing join clauses into the quals of a seqscan, but
+ * it could still have required parameterization due to LATERAL refs in
+ * its tlist.
+ */
+ required_outer = rel->lateral_relids;
+
+ /* Consider sequential scan */
+ add_path(rel, create_seqscan_path(root, rel, required_outer, 0));
+
+ /* If appropriate, consider parallel sequential scan */
+ if (rel->consider_parallel && required_outer == NULL)
+ create_plain_partial_paths(root, rel);
+
+ /* Consider index scans */
+ create_index_paths(root, rel);
+
+ /* Consider TID scans */
+ create_tidscan_paths(root, rel);
+}
+
+
/*
* set_append_rel_pathlist
* Build access paths for an "append relation"
{
int parentRTindex = rti;
List *live_childrels = NIL;
- List *subpaths = NIL;
- bool subpaths_valid = true;
- List *all_child_pathkeys = NIL;
- List *all_child_outers = NIL;
ListCell *l;
/*
* Generate access paths for each member relation, and remember the
- * cheapest path for each one. Also, identify all pathkeys (orderings)
- * and parameterizations (required_outer sets) available for the member
- * relations.
+ * non-dummy children.
*/
foreach(l, root->append_rel_list)
{
int childRTindex;
RangeTblEntry *childRTE;
RelOptInfo *childrel;
- ListCell *lcp;
/* append_rel_list contains all append rels; ignore others */
if (appinfo->parent_relid != parentRTindex)
childrel = root->simple_rel_array[childRTindex];
/*
+ * If set_append_rel_size() decided the parent appendrel was
+ * parallel-unsafe at some point after visiting this child rel, we
+ * need to propagate the unsafety marking down to the child, so that
+ * we don't generate useless partial paths for it.
+ */
+ if (!rel->consider_parallel)
+ childrel->consider_parallel = false;
+
+ /*
* Compute the child's access paths.
*/
set_rel_pathlist(root, childrel, childRTindex, childRTE);
* Child is live, so add it to the live_childrels list for use below.
*/
live_childrels = lappend(live_childrels, childrel);
+ }
+
+ /* Add paths to the "append" relation. */
+ add_paths_to_append_rel(root, rel, live_childrels);
+}
+
+/*
+ * add_paths_to_append_rel
+ * Generate paths for given "append" relation given the set of non-dummy
+ * child rels.
+ *
+ * The function collects all parameterizations and orderings supported by the
+ * non-dummy children. For every such parameterization or ordering, it creates
+ * an append path collecting one path from each non-dummy child with given
+ * parameterization or ordering. Similarly it collects partial paths from
+ * non-dummy children to create partial append paths.
+ */
+static void
+add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,
+ List *live_childrels)
+{
+ List *subpaths = NIL;
+ bool subpaths_valid = true;
+ List *partial_subpaths = NIL;
+ bool partial_subpaths_valid = true;
+ List *all_child_pathkeys = NIL;
+ List *all_child_outers = NIL;
+ ListCell *l;
+ List *partitioned_rels = NIL;
+ RangeTblEntry *rte;
+
+ rte = planner_rt_fetch(rel->relid, root);
+ if (rte->relkind == RELKIND_PARTITIONED_TABLE)
+ {
+ partitioned_rels = get_partitioned_child_rels(root, rel->relid);
+ /* The root partitioned table is included as a child rel */
+ Assert(list_length(partitioned_rels) >= 1);
+ }
+
+ /*
+ * For every non-dummy child, remember the cheapest path. Also, identify
+ * all pathkeys (orderings) and parameterizations (required_outer sets)
+ * available for the non-dummy member relations.
+ */
+ foreach(l, live_childrels)
+ {
+ RelOptInfo *childrel = lfirst(l);
+ ListCell *lcp;
/*
* If child has an unparameterized cheapest-total path, add that to
else
subpaths_valid = false;
+ /* Same idea, but for a partial plan. */
+ if (childrel->partial_pathlist != NIL)
+ partial_subpaths = accumulate_append_subpath(partial_subpaths,
+ linitial(childrel->partial_pathlist));
+ else
+ partial_subpaths_valid = false;
+
/*
* Collect lists of all the available path orderings and
* parameterizations for all the children. We use these as a
* if we have zero or one live subpath due to constraint exclusion.)
*/
if (subpaths_valid)
- add_path(rel, (Path *) create_append_path(rel, subpaths, NULL));
+ add_path(rel, (Path *) create_append_path(rel, subpaths, NULL, 0,
+ partitioned_rels));
+
+ /*
+ * Consider an append of partial unordered, unparameterized partial paths.
+ */
+ if (partial_subpaths_valid)
+ {
+ AppendPath *appendpath;
+ ListCell *lc;
+ int parallel_workers = 0;
+
+ /*
+ * Decide on the number of workers to request for this append path.
+ * For now, we just use the maximum value from among the members. It
+ * might be useful to use a higher number if the Append node were
+ * smart enough to spread out the workers, but it currently isn't.
+ */
+ foreach(lc, partial_subpaths)
+ {
+ Path *path = lfirst(lc);
+
+ parallel_workers = Max(parallel_workers, path->parallel_workers);
+ }
+ Assert(parallel_workers > 0);
+
+ /* Generate a partial append path. */
+ appendpath = create_append_path(rel, partial_subpaths, NULL,
+ parallel_workers, partitioned_rels);
+ add_partial_path(rel, (Path *) appendpath);
+ }
/*
* Also build unparameterized MergeAppend paths based on the collected
*/
if (subpaths_valid)
generate_mergeappend_paths(root, rel, live_childrels,
- all_child_pathkeys);
+ all_child_pathkeys,
+ partitioned_rels);
/*
* Build Append paths for each parameterization seen among the child rels.
if (subpaths_valid)
add_path(rel, (Path *)
- create_append_path(rel, subpaths, required_outer));
+ create_append_path(rel, subpaths, required_outer, 0,
+ partitioned_rels));
}
-
- /* Select cheapest paths */
- set_cheapest(rel);
}
+
/*
* generate_mergeappend_paths
* Generate MergeAppend paths for an append relation
static void
generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel,
List *live_childrels,
- List *all_child_pathkeys)
+ List *all_child_pathkeys,
+ List *partitioned_rels)
{
ListCell *lcp;
get_cheapest_path_for_pathkeys(childrel->pathlist,
pathkeys,
NULL,
- STARTUP_COST);
+ STARTUP_COST,
+ false);
cheapest_total =
get_cheapest_path_for_pathkeys(childrel->pathlist,
pathkeys,
NULL,
- TOTAL_COST);
+ TOTAL_COST,
+ false);
/*
* If we can't find any paths with the right order just use the
rel,
startup_subpaths,
pathkeys,
- NULL));
+ NULL,
+ partitioned_rels));
if (startup_neq_total)
add_path(rel, (Path *) create_merge_append_path(root,
rel,
total_subpaths,
pathkeys,
- NULL));
+ NULL,
+ partitioned_rels));
}
}
+
/*
* get_cheapest_parameterized_child_path
* Get cheapest path for this relation that has exactly the requested
cheapest = get_cheapest_path_for_pathkeys(rel->pathlist,
NIL,
required_outer,
- TOTAL_COST);
+ TOTAL_COST,
+ false);
Assert(cheapest != NULL);
if (bms_equal(PATH_REQ_OUTER(cheapest), required_outer))
return cheapest;
return cheapest;
}
+
/*
* accumulate_append_subpath
* Add a subpath to the list being built for an Append or MergeAppend
return lappend(subpaths, path);
}
+
/*
* standard_join_search
* Find possible joinpaths for a query by successively finding ways
join_search_one_level(root, lev);
/*
- * Do cleanup work on each just-processed rel.
+ * Run generate_gather_paths() for each just-processed joinrel. We
+ * could not do this earlier because both regular and partial paths
+ * can get added to a particular joinrel at multiple times within
+ * join_search_one_level. After that, we're done creating paths for
+ * the joinrel, so run set_cheapest().
*/
foreach(lc, root->join_rel_level[lev])
{
rel = (RelOptInfo *) lfirst(lc);
+ /* Create GatherPaths for any useful partial paths for rel */
+ generate_gather_paths(root, rel);
+
/* Find and save the cheapest paths for this rel */
set_cheapest(rel);
}
/*
+ * create_plain_partial_paths
+ * Build partial access paths for parallel scan of a plain relation
+ */
+static void
+create_plain_partial_paths(PlannerInfo *root, RelOptInfo *rel)
+{
+ int parallel_workers;
+
+ parallel_workers = compute_parallel_worker(rel, rel->pages, -1);
+
+ /* If any limit was set to zero, the user doesn't want a parallel scan. */
+ if (parallel_workers <= 0)
+ return;
+
+ /* Add an unordered partial path based on a parallel sequential scan. */
+ add_partial_path(rel, create_seqscan_path(root, rel, NULL, parallel_workers));
+}
+
+
+/*
* join_search_one_level
* Consider ways to produce join relations containing exactly 'level'
* jointree items. (This is one step of the dynamic-programming method
*/
if (joinrels[level] == NIL &&
root->join_info_list == NIL &&
- root->lateral_info_list == NIL)
+ !root->hasLateralRTEs)
elog(ERROR, "failed to build any %d-way joins", level);
}
}
+
/*
* make_rels_by_clause_joins
* Build joins between the given relation 'old_rel' and other relations
}
}
+
/*
* make_rels_by_clauseless_joins
* Given a relation 'old_rel' and a list of other relations
}
}
+
/*
* join_is_legal
* Determine whether a proposed join is legal given the query's
SpecialJoinInfo *match_sjinfo;
bool reversed;
bool unique_ified;
- bool is_valid_inner;
- bool lateral_fwd;
- bool lateral_rev;
+ bool must_be_leftjoin;
ListCell *l;
/*
/*
* If we have any special joins, the proposed join might be illegal; and
* in any case we have to determine its join type. Scan the join info
- * list for conflicts.
+ * list for matches and conflicts.
*/
match_sjinfo = NULL;
reversed = false;
unique_ified = false;
- is_valid_inner = true;
+ must_be_leftjoin = false;
foreach(l, root->join_info_list)
{
* If one input contains min_lefthand and the other contains
* min_righthand, then we can perform the SJ at this join.
*
- * Barf if we get matches to more than one SJ (is that possible?)
+ * Reject if we get matches to more than one SJ; that implies we're
+ * considering something that's not really valid.
*/
if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
bms_is_subset(sjinfo->min_righthand, rel2->relids))
}
else
{
- /*----------
- * Otherwise, the proposed join overlaps the RHS but isn't
- * a valid implementation of this SJ. It might still be
- * a legal join, however. If both inputs overlap the RHS,
- * assume that it's OK. Since the inputs presumably got past
- * this function's checks previously, they can't overlap the
- * LHS and their violations of the RHS boundary must represent
- * SJs that have been determined to commute with this one.
- * We have to allow this to work correctly in cases like
- * (a LEFT JOIN (b JOIN (c LEFT JOIN d)))
- * when the c/d join has been determined to commute with the join
- * to a, and hence d is not part of min_righthand for the upper
- * join. It should be legal to join b to c/d but this will appear
- * as a violation of the upper join's RHS.
- * Furthermore, if one input overlaps the RHS and the other does
- * not, we should still allow the join if it is a valid
- * implementation of some other SJ. We have to allow this to
- * support the associative identity
- * (a LJ b on Pab) LJ c ON Pbc = a LJ (b LJ c ON Pbc) on Pab
- * since joining B directly to C violates the lower SJ's RHS.
- * We assume that make_outerjoininfo() set things up correctly
- * so that we'll only match to some SJ if the join is valid.
- * Set flag here to check at bottom of loop.
- *----------
+ /*
+ * Otherwise, the proposed join overlaps the RHS but isn't a valid
+ * implementation of this SJ. But don't panic quite yet: the RHS
+ * violation might have occurred previously, in one or both input
+ * relations, in which case we must have previously decided that
+ * it was OK to commute some other SJ with this one. If we need
+ * to perform this join to finish building up the RHS, rejecting
+ * it could lead to not finding any plan at all. (This can occur
+ * because of the heuristics elsewhere in this file that postpone
+ * clauseless joins: we might not consider doing a clauseless join
+ * within the RHS until after we've performed other, validly
+ * commutable SJs with one or both sides of the clauseless join.)
+ * This consideration boils down to the rule that if both inputs
+ * overlap the RHS, we can allow the join --- they are either
+ * fully within the RHS, or represent previously-allowed joins to
+ * rels outside it.
*/
- if (sjinfo->jointype != JOIN_SEMI &&
- bms_overlap(rel1->relids, sjinfo->min_righthand) &&
+ if (bms_overlap(rel1->relids, sjinfo->min_righthand) &&
bms_overlap(rel2->relids, sjinfo->min_righthand))
- {
- /* seems OK */
- Assert(!bms_overlap(joinrelids, sjinfo->min_lefthand));
- }
- else
- is_valid_inner = false;
+ continue; /* assume valid previous violation of RHS */
+
+ /*
+ * The proposed join could still be legal, but only if we're
+ * allowed to associate it into the RHS of this SJ. That means
+ * this SJ must be a LEFT join (not SEMI or ANTI, and certainly
+ * not FULL) and the proposed join must not overlap the LHS.
+ */
+ if (sjinfo->jointype != JOIN_LEFT ||
+ bms_overlap(joinrelids, sjinfo->min_lefthand))
+ return false; /* invalid join path */
+
+ /*
+ * To be valid, the proposed join must be a LEFT join; otherwise
+ * it can't associate into this SJ's RHS. But we may not yet have
+ * found the SpecialJoinInfo matching the proposed join, so we
+ * can't test that yet. Remember the requirement for later.
+ */
+ must_be_leftjoin = true;
}
}
/*
- * Fail if violated some SJ's RHS and didn't match to another SJ. However,
- * "matching" to a semijoin we are implementing by unique-ification
- * doesn't count (think: it's really an inner join).
+ * Fail if violated any SJ's RHS and didn't match to a LEFT SJ: the
+ * proposed join can't associate into an SJ's RHS.
+ *
+ * Also, fail if the proposed join's predicate isn't strict; we're
+ * essentially checking to see if we can apply outer-join identity 3, and
+ * that's a requirement. (This check may be redundant with checks in
+ * make_outerjoininfo, but I'm not quite sure, and it's cheap to test.)
*/
- if (!is_valid_inner &&
- (match_sjinfo == NULL || unique_ified))
+ if (must_be_leftjoin &&
+ (match_sjinfo == NULL ||
+ match_sjinfo->jointype != JOIN_LEFT ||
+ !match_sjinfo->lhs_strict))
return false; /* invalid join path */
/*
* We also have to check for constraints imposed by LATERAL references.
- * The proposed rels could each contain lateral references to the other,
- * in which case the join is impossible. If there are lateral references
- * in just one direction, then the join has to be done with a nestloop
- * with the lateral referencer on the inside. If the join matches an SJ
- * that cannot be implemented by such a nestloop, the join is impossible.
*/
- lateral_fwd = lateral_rev = false;
- foreach(l, root->lateral_info_list)
+ if (root->hasLateralRTEs)
{
- LateralJoinInfo *ljinfo = (LateralJoinInfo *) lfirst(l);
+ bool lateral_fwd;
+ bool lateral_rev;
+ Relids join_lateral_rels;
- if (bms_is_subset(ljinfo->lateral_rhs, rel2->relids) &&
- bms_overlap(ljinfo->lateral_lhs, rel1->relids))
+ /*
+ * The proposed rels could each contain lateral references to the
+ * other, in which case the join is impossible. If there are lateral
+ * references in just one direction, then the join has to be done with
+ * a nestloop with the lateral referencer on the inside. If the join
+ * matches an SJ that cannot be implemented by such a nestloop, the
+ * join is impossible.
+ *
+ * Also, if the lateral reference is only indirect, we should reject
+ * the join; whatever rel(s) the reference chain goes through must be
+ * joined to first.
+ *
+ * Another case that might keep us from building a valid plan is the
+ * implementation restriction described by have_dangerous_phv().
+ */
+ lateral_fwd = bms_overlap(rel1->relids, rel2->lateral_relids);
+ lateral_rev = bms_overlap(rel2->relids, rel1->lateral_relids);
+ if (lateral_fwd && lateral_rev)
+ return false; /* have lateral refs in both directions */
+ if (lateral_fwd)
{
/* has to be implemented as nestloop with rel1 on left */
- if (lateral_rev)
- return false; /* have lateral refs in both directions */
- lateral_fwd = true;
- if (!bms_is_subset(ljinfo->lateral_lhs, rel1->relids))
- return false; /* rel1 can't compute the required parameter */
if (match_sjinfo &&
- (reversed || match_sjinfo->jointype == JOIN_FULL))
+ (reversed ||
+ unique_ified ||
+ match_sjinfo->jointype == JOIN_FULL))
return false; /* not implementable as nestloop */
+ /* check there is a direct reference from rel2 to rel1 */
+ if (!bms_overlap(rel1->relids, rel2->direct_lateral_relids))
+ return false; /* only indirect refs, so reject */
+ /* check we won't have a dangerous PHV */
+ if (have_dangerous_phv(root, rel1->relids, rel2->lateral_relids))
+ return false; /* might be unable to handle required PHV */
}
- if (bms_is_subset(ljinfo->lateral_rhs, rel1->relids) &&
- bms_overlap(ljinfo->lateral_lhs, rel2->relids))
+ else if (lateral_rev)
{
/* has to be implemented as nestloop with rel2 on left */
- if (lateral_fwd)
- return false; /* have lateral refs in both directions */
- lateral_rev = true;
- if (!bms_is_subset(ljinfo->lateral_lhs, rel2->relids))
- return false; /* rel2 can't compute the required parameter */
if (match_sjinfo &&
- (!reversed || match_sjinfo->jointype == JOIN_FULL))
+ (!reversed ||
+ unique_ified ||
+ match_sjinfo->jointype == JOIN_FULL))
return false; /* not implementable as nestloop */
+ /* check there is a direct reference from rel1 to rel2 */
+ if (!bms_overlap(rel2->relids, rel1->direct_lateral_relids))
+ return false; /* only indirect refs, so reject */
+ /* check we won't have a dangerous PHV */
+ if (have_dangerous_phv(root, rel2->relids, rel1->lateral_relids))
+ return false; /* might be unable to handle required PHV */
+ }
+
+ /*
+ * LATERAL references could also cause problems later on if we accept
+ * this join: if the join's minimum parameterization includes any rels
+ * that would have to be on the inside of an outer join with this join
+ * rel, then it's never going to be possible to build the complete
+ * query using this join. We should reject this join not only because
+ * it'll save work, but because if we don't, the clauseless-join
+ * heuristics might think that legality of this join means that some
+ * other join rel need not be formed, and that could lead to failure
+ * to find any plan at all. We have to consider not only rels that
+ * are directly on the inner side of an OJ with the joinrel, but also
+ * ones that are indirectly so, so search to find all such rels.
+ */
+ join_lateral_rels = min_join_parameterization(root, joinrelids,
+ rel1, rel2);
+ if (join_lateral_rels)
+ {
+ Relids join_plus_rhs = bms_copy(joinrelids);
+ bool more;
+
+ do
+ {
+ more = false;
+ foreach(l, root->join_info_list)
+ {
+ SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
+
+ if (bms_overlap(sjinfo->min_lefthand, join_plus_rhs) &&
+ !bms_is_subset(sjinfo->min_righthand, join_plus_rhs))
+ {
+ join_plus_rhs = bms_add_members(join_plus_rhs,
+ sjinfo->min_righthand);
+ more = true;
+ }
+ /* full joins constrain both sides symmetrically */
+ if (sjinfo->jointype == JOIN_FULL &&
+ bms_overlap(sjinfo->min_righthand, join_plus_rhs) &&
+ !bms_is_subset(sjinfo->min_lefthand, join_plus_rhs))
+ {
+ join_plus_rhs = bms_add_members(join_plus_rhs,
+ sjinfo->min_lefthand);
+ more = true;
+ }
+ }
+ } while (more);
+ if (bms_overlap(join_plus_rhs, join_lateral_rels))
+ return false; /* will not be able to join to some RHS rel */
}
}
return true;
}
+
/*
* has_join_restriction
* Detect whether the specified relation has join-order restrictions,
* due to being inside an outer join or an IN (sub-SELECT),
- * or participating in any LATERAL references.
+ * or participating in any LATERAL references or multi-rel PHVs.
*
* Essentially, this tests whether have_join_order_restriction() could
* succeed with this rel and some other one. It's OK if we sometimes
{
ListCell *l;
- foreach(l, root->lateral_info_list)
+ if (rel->lateral_relids != NULL || rel->lateral_referencers != NULL)
+ return true;
+
+ foreach(l, root->placeholder_list)
{
- LateralJoinInfo *ljinfo = (LateralJoinInfo *) lfirst(l);
+ PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
- if (bms_is_subset(ljinfo->lateral_rhs, rel->relids) ||
- bms_overlap(ljinfo->lateral_lhs, rel->relids))
+ if (bms_is_subset(rel->relids, phinfo->ph_eval_at) &&
+ !bms_equal(rel->relids, phinfo->ph_eval_at))
return true;
}
return false;
}
+
/*
* is_dummy_rel --- has relation been proven empty?
*/
return IS_DUMMY_REL(rel);
}
+
/*
* Mark a relation as proven empty.
*
/* Evict any previously chosen paths */
rel->pathlist = NIL;
+ rel->partial_pathlist = NIL;
/* Set up the dummy path */
- add_path(rel, (Path *) create_append_path(rel, NIL, NULL));
+ add_path(rel, (Path *) create_append_path(rel, NIL, NULL, 0, NIL));
/* Set or update cheapest_total_path and related fields */
set_cheapest(rel);
MemoryContextSwitchTo(oldcontext);
}
+
/*
* restriction_is_constant_false --- is a restrictlist just FALSE?
*
*/
foreach(lc, restrictlist)
{
- RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
+ RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
- Assert(IsA(rinfo, RestrictInfo));
if (only_pushed_down && !rinfo->is_pushed_down)
continue;