parameterized-paths-1.patch
text/x-patch
Filename: parameterized-paths-1.patch
Type: text/x-patch
Part: 0
Patch
Same data as JSON:
GET /api/v1/attachments/:id/patch
the parsed metadata as JSON — format, series position, per-file stats; never the diff bytes.
API reference →
Format: unified
| File | + | − |
|---|---|---|
| doc/src/sgml/indexam.sgml | 0 | 0 |
| src/backend/nodes/bitmapset.c | 0 | 0 |
| src/backend/nodes/outfuncs.c | 0 | 0 |
| src/backend/optimizer/path/allpaths.c | 0 | 0 |
| src/backend/optimizer/path/costsize.c | 0 | 0 |
| src/backend/optimizer/path/indxpath.c | 0 | 0 |
| src/backend/optimizer/path/joinpath.c | 0 | 0 |
| src/backend/optimizer/path/orindxpath.c | 0 | 0 |
| src/backend/optimizer/path/pathkeys.c | 0 | 0 |
| src/backend/optimizer/plan/createplan.c | 0 | 0 |
| src/backend/optimizer/plan/planner.c | 0 | 0 |
| src/backend/optimizer/README | 0 | 0 |
| src/backend/optimizer/util/pathnode.c | 0 | 0 |
| src/backend/optimizer/util/restrictinfo.c | 0 | 0 |
| src/backend/utils/adt/selfuncs.c | 0 | 0 |
| src/include/nodes/bitmapset.h | 0 | 0 |
| src/include/nodes/relation.h | 0 | 0 |
| src/include/optimizer/cost.h | 0 | 0 |
| src/include/optimizer/pathnode.h | 0 | 0 |
| src/include/optimizer/paths.h | 0 | 0 |
| src/include/optimizer/restrictinfo.h | 0 | 0 |
diff --git a/doc/src/sgml/indexam.sgml b/doc/src/sgml/indexam.sgml
index 07c816c38f279b057eab32d7f4b9eb06f7b193d4..28f2ae162753e105fffc24b922881eae39da60c5 100644
*** a/doc/src/sgml/indexam.sgml
--- b/doc/src/sgml/indexam.sgml
*************** amcanreturn (Relation indexRelation);
*** 289,295 ****
void
amcostestimate (PlannerInfo *root,
IndexPath *path,
! RelOptInfo *outer_rel,
Cost *indexStartupCost,
Cost *indexTotalCost,
Selectivity *indexSelectivity,
--- 289,295 ----
void
amcostestimate (PlannerInfo *root,
IndexPath *path,
! double loop_count,
Cost *indexStartupCost,
Cost *indexTotalCost,
Selectivity *indexSelectivity,
*************** amrestrpos (IndexScanDesc scan);
*** 928,934 ****
void
amcostestimate (PlannerInfo *root,
IndexPath *path,
! RelOptInfo *outer_rel,
Cost *indexStartupCost,
Cost *indexTotalCost,
Selectivity *indexSelectivity,
--- 928,934 ----
void
amcostestimate (PlannerInfo *root,
IndexPath *path,
! double loop_count,
Cost *indexStartupCost,
Cost *indexTotalCost,
Selectivity *indexSelectivity,
*************** amcostestimate (PlannerInfo *root,
*** 958,973 ****
</varlistentry>
<varlistentry>
! <term><parameter>outer_rel</></term>
<listitem>
<para>
! If the index is being considered for use in a join inner indexscan,
! the planner's information about the outer side of the join. Otherwise
! <symbol>NULL</>. When non-<symbol>NULL</>, some of the qual clauses
! will be join clauses for joins
! with this rel rather than being simple restriction clauses. Also,
! the cost estimator should expect that the index scan will be repeated
! for each row of the outer rel.
</para>
</listitem>
</varlistentry>
--- 958,972 ----
</varlistentry>
<varlistentry>
! <term><parameter>loop_count</></term>
<listitem>
<para>
! The number of repetitions of the index scan that should be factored
! into the cost estimates. This will typically be greater than one when
! considering a parameterized scan for use in the inside of a nestloop
! join. Note that the cost estimates should still be for just one scan;
! a larger <parameter>loop_count</> means that it may be appropriate
! to allow for some caching effects across multiple scans.
</para>
</listitem>
</varlistentry>
*************** amcostestimate (PlannerInfo *root,
*** 1062,1069 ****
</para>
<para>
! In the join case, the returned numbers should be averages expected for
! any one scan of the index.
</para>
<procedure>
--- 1061,1068 ----
</para>
<para>
! When <parameter>loop_count</> is greater than one, the returned numbers
! should be averages expected for any one scan of the index.
</para>
<procedure>
*************** cost_qual_eval(&index_qual_cost, pat
*** 1121,1127 ****
</programlisting>
However, the above does not account for amortization of index reads
! across repeated index scans in the join case.
</para>
</step>
--- 1120,1126 ----
</programlisting>
However, the above does not account for amortization of index reads
! across repeated index scans.
</para>
</step>
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 3b5fb20964e7153a859bb639f15fd0be8bb8778b..4c904e03296051cf2c95fdcd3d4a029aea9dc142 100644
*** a/src/backend/nodes/bitmapset.c
--- b/src/backend/nodes/bitmapset.c
*************** bms_is_subset(const Bitmapset *a, const
*** 336,341 ****
--- 336,418 ----
}
/*
+ * bms_subset_compare - compare A and B for equality/subset relationships
+ *
+ * This is more efficient than testing bms_is_subset in both directions.
+ */
+ BMS_Comparison
+ bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
+ {
+ BMS_Comparison result;
+ int shortlen;
+ int longlen;
+ int i;
+
+ /* Handle cases where either input is NULL */
+ if (a == NULL)
+ {
+ if (b == NULL)
+ return BMS_EQUAL;
+ return bms_is_empty(b) ? BMS_EQUAL : BMS_SUBSET1;
+ }
+ if (b == NULL)
+ return bms_is_empty(a) ? BMS_EQUAL : BMS_SUBSET2;
+ /* Check common words */
+ result = BMS_EQUAL; /* status so far */
+ shortlen = Min(a->nwords, b->nwords);
+ for (i = 0; i < shortlen; i++)
+ {
+ bitmapword aword = a->words[i];
+ bitmapword bword = b->words[i];
+
+ if ((aword & ~bword) != 0)
+ {
+ /* a is not a subset of b */
+ if (result == BMS_SUBSET1)
+ return BMS_DIFFERENT;
+ result = BMS_SUBSET2;
+ }
+ if ((bword & ~aword) != 0)
+ {
+ /* b is not a subset of a */
+ if (result == BMS_SUBSET2)
+ return BMS_DIFFERENT;
+ result = BMS_SUBSET1;
+ }
+ }
+ /* Check extra words */
+ if (a->nwords > b->nwords)
+ {
+ longlen = a->nwords;
+ for (; i < longlen; i++)
+ {
+ if (a->words[i] != 0)
+ {
+ /* a is not a subset of b */
+ if (result == BMS_SUBSET1)
+ return BMS_DIFFERENT;
+ result = BMS_SUBSET2;
+ }
+ }
+ }
+ else if (a->nwords < b->nwords)
+ {
+ longlen = b->nwords;
+ for (; i < longlen; i++)
+ {
+ if (b->words[i] != 0)
+ {
+ /* b is not a subset of a */
+ if (result == BMS_SUBSET2)
+ return BMS_DIFFERENT;
+ result = BMS_SUBSET1;
+ }
+ }
+ }
+ return result;
+ }
+
+ /*
* bms_is_member - is X a member of A?
*/
bool
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 8bc19478357e66d3fe8723da693672939c401ae2..3df2d1e23b4cda966c9bd74c116ebb830291a172 100644
*** a/src/backend/nodes/outfuncs.c
--- b/src/backend/nodes/outfuncs.c
*************** _outPathInfo(StringInfo str, const Path
*** 1475,1483 ****
WRITE_ENUM_FIELD(pathtype, NodeTag);
appendStringInfo(str, " :parent_relids ");
_outBitmapset(str, node->parent->relids);
WRITE_FLOAT_FIELD(startup_cost, "%.2f");
WRITE_FLOAT_FIELD(total_cost, "%.2f");
- WRITE_NODE_FIELD(pathkeys);
}
/*
--- 1475,1486 ----
WRITE_ENUM_FIELD(pathtype, NodeTag);
appendStringInfo(str, " :parent_relids ");
_outBitmapset(str, node->parent->relids);
+ WRITE_BITMAPSET_FIELD(required_outer);
+ WRITE_NODE_FIELD(param_clauses);
+ WRITE_NODE_FIELD(pathkeys);
+ WRITE_FLOAT_FIELD(rows, "%.0f");
WRITE_FLOAT_FIELD(startup_cost, "%.2f");
WRITE_FLOAT_FIELD(total_cost, "%.2f");
}
/*
*************** _outIndexPath(StringInfo str, const Inde
*** 1515,1525 ****
WRITE_NODE_FIELD(indexqualcols);
WRITE_NODE_FIELD(indexorderbys);
WRITE_NODE_FIELD(indexorderbycols);
- WRITE_BOOL_FIELD(isjoininner);
WRITE_ENUM_FIELD(indexscandir, ScanDirection);
WRITE_FLOAT_FIELD(indextotalcost, "%.2f");
WRITE_FLOAT_FIELD(indexselectivity, "%.4f");
- WRITE_FLOAT_FIELD(rows, "%.0f");
}
static void
--- 1518,1526 ----
*************** _outBitmapHeapPath(StringInfo str, const
*** 1530,1537 ****
_outPathInfo(str, (const Path *) node);
WRITE_NODE_FIELD(bitmapqual);
- WRITE_BOOL_FIELD(isjoininner);
- WRITE_FLOAT_FIELD(rows, "%.0f");
}
static void
--- 1531,1536 ----
*************** _outUniquePath(StringInfo str, const Uni
*** 1628,1634 ****
WRITE_ENUM_FIELD(umethod, UniquePathMethod);
WRITE_NODE_FIELD(in_operators);
WRITE_NODE_FIELD(uniq_exprs);
- WRITE_FLOAT_FIELD(rows, "%.0f");
}
static void
--- 1627,1632 ----
diff --git a/src/backend/optimizer/README b/src/backend/optimizer/README
index aaa754cbb18e78823135bbc4a1acfbaa1f93c88f..15d631c1f8059756ecc6f3857759af1ac6b6e685 100644
*** a/src/backend/optimizer/README
--- b/src/backend/optimizer/README
*************** ways. All the Paths made for a given re
*** 78,87 ****
RelOptInfo.pathlist. (Actually, we discard Paths that are obviously
inferior alternatives before they ever get into the pathlist --- what
ends up in the pathlist is the cheapest way of generating each potentially
! useful sort ordering of the relation.) Also create a RelOptInfo.joininfo
! list including all the join clauses that involve this relation. For
! example, the WHERE clause "tab1.col1 = tab2.col1" generates entries in
! both tab1 and tab2's joininfo lists.
If we have only a single base relation in the query, we are done.
Otherwise we have to figure out how to join the base relations into a
--- 78,87 ----
RelOptInfo.pathlist. (Actually, we discard Paths that are obviously
inferior alternatives before they ever get into the pathlist --- what
ends up in the pathlist is the cheapest way of generating each potentially
! useful sort ordering and parameterization of the relation.) Also create a
! RelOptInfo.joininfo list including all the join clauses that involve this
! relation. For example, the WHERE clause "tab1.col1 = tab2.col1" generates
! entries in both tab1 and tab2's joininfo lists.
If we have only a single base relation in the query, we are done.
Otherwise we have to figure out how to join the base relations into a
*************** for it or the cheapest path with the des
*** 173,184 ****
than applying a sort to the cheapest other path).
If the query contains one-sided outer joins (LEFT or RIGHT joins), or
! IN or EXISTS WHERE clauses that were converted to joins, then some of
! the possible join orders may be illegal. These are excluded by having
! join_is_legal consult a side list of such "special" joins to see
! whether a proposed join is illegal. (The same consultation allows it
! to see which join style should be applied for a valid join, ie,
! JOIN_INNER, JOIN_LEFT, etc.)
Valid OUTER JOIN Optimizations
--- 173,184 ----
than applying a sort to the cheapest other path).
If the query contains one-sided outer joins (LEFT or RIGHT joins), or
! IN or EXISTS WHERE clauses that were converted to semijoins or antijoins,
! then some of the possible join orders may be illegal. These are excluded
! by having join_is_legal consult a side list of such "special" joins to see
! whether a proposed join is illegal. (The same consultation allows it to
! see which join style should be applied for a valid join, ie, JOIN_INNER,
! JOIN_LEFT, etc.)
Valid OUTER JOIN Optimizations
*************** multi-column index generates a list with
*** 526,537 ****
are two possible sort orders and two possible PathKey lists it can
generate.)
! Note that a bitmap scan or multi-pass indexscan (OR clause scan) has NIL
! pathkeys since we can say nothing about the overall order of its result.
! Also, an indexscan on an unordered type of index generates NIL pathkeys.
! However, we can always create a pathkey by doing an explicit sort. The
! pathkeys for a Sort plan's output just represent the sort key fields and
! the ordering operators used.
Things get more interesting when we consider joins. Suppose we do a
mergejoin between A and B using the mergeclause A.X = B.Y. The output
--- 526,536 ----
are two possible sort orders and two possible PathKey lists it can
generate.)
! Note that a bitmap scan has NIL pathkeys since we can say nothing about
! the overall order of its result. Also, an indexscan on an unordered type
! of index generates NIL pathkeys. However, we can always create a pathkey
! by doing an explicit sort. The pathkeys for a Sort plan's output just
! represent the sort key fields and the ordering operators used.
Things get more interesting when we consider joins. Suppose we do a
mergejoin between A and B using the mergeclause A.X = B.Y. The output
*************** Currently this happens only for queries
*** 668,671 ****
--- 667,753 ----
with different orderings, for which extra sorts are needed anyway.
+ Parameterized Paths
+ -------------------
+
+ The naive way to join two relations using a clause like WHERE A.X = B.Y
+ is to generate a nestloop plan like this:
+
+ NestLoop
+ Filter: A.X = B.Y
+ -> Seq Scan on A
+ -> Seq Scan on B
+
+ We can make this better by using a merge or hash join, but it still
+ requires scanning all of both input relations. If A is very small and B is
+ very large, but there is an index on B.Y, it can be enormously better to do
+ something like this:
+
+ NestLoop
+ -> Seq Scan on A
+ -> Index Scan using B_Y_IDX on B
+ Index Condition: B.Y = A.X
+
+ Here, we are expecting that for each row scanned from A, the nestloop
+ plan node will pass down the current value of A.X into the scan of B.
+ That allows the indexscan to treat A.X as a constant for any one
+ invocation, and thereby use it as an index key. This is the only plan type
+ that can avoid fetching all of B, and for small numbers of rows coming from
+ A, that will dominate every other consideration. (As A gets larger, this
+ gets less attractive, and eventually a merge or hash join will win instead.
+ So we have to cost out all the alternatives to decide what to do.)
+
+ It can be useful for the parameter value to be passed down through
+ intermediate layers of joins, for example:
+
+ NestLoop
+ -> Seq Scan on A
+ Hash Join
+ Join Condition: B.Y = C.W
+ -> Seq Scan on B
+ -> Index Scan using C_Z_IDX on C
+ Index Condition: C.Z = A.X
+
+ If all joins are plain inner joins then this is unnecessary, because
+ it's always possible to reorder the joins so that a parameter is used
+ immediately below the nestloop node that provides it. But in the
+ presence of outer joins, join reordering may not be possible, and then
+ this option can be critical. Before version 9.2, Postgres used ad-hoc
+ methods for planning and executing such queries, and those methods could
+ not handle passing parameters down through multiple join levels.
+
+ To plan such queries, we now use a notion of a "parameterized path",
+ which is a path that makes use of a join clause to a relation that's not
+ scanned by the path. In the example just above, we would construct a
+ path representing the possibility of doing this:
+
+ -> Index Scan using C_Z_IDX on C
+ Index Condition: C.Z = A.X
+
+ This path will be marked as being parameterized by relation A. (Note that
+ this is only one of the possible access paths for C; we'd still have a
+ plain unparameterized seqscan, and perhaps other possibilities.) The
+ parameterization marker does not prevent joining the path to B, so one of
+ the paths generated for the joinrel {B C} will represent
+
+ Hash Join
+ Join Condition: B.Y = C.W
+ -> Seq Scan on B
+ -> Index Scan using C_Z_IDX on C
+ Index Condition: C.Z = A.X
+
+ This path is still marked as being parameterized by A. When we attempt to
+ join {B C} to A to form the complete join tree, such a path can only be
+ used as the inner side of a nestloop join: it will be ignored for other
+ possible join types. So we will form a join path representing the query
+ plan shown above, and it will compete in the usual way with paths built
+ from non-parameterized scans.
+
+ To limit planning time, we have to avoid generating an unreasonably large
+ number of parameterized paths. We do this by only generating parameterized
+ relation scan paths for index scans, and then only for indexes for which
+ suitable join clauses are available. There are also heuristics in join
+ planning that try to limit the number of parameterized paths considered.
+
+
-- bjm & tgl
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index b085553a1adbfee633ae6399cf6e188ec465368a..df768f6bcb9abd4fe36a3ab856dac4c189326865 100644
*** a/src/backend/optimizer/path/allpaths.c
--- b/src/backend/optimizer/path/allpaths.c
*************** static void set_plain_rel_pathlist(Plann
*** 53,58 ****
--- 53,62 ----
RangeTblEntry *rte);
static void set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
Index rti, RangeTblEntry *rte);
+ static void generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel,
+ List *live_childrels,
+ List *all_child_pathkeys,
+ Relids required_outer);
static List *accumulate_append_subpath(List *subpaths, Path *path);
static void set_dummy_rel_pathlist(RelOptInfo *rel);
static void set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
*************** set_append_rel_pathlist(PlannerInfo *roo
*** 300,305 ****
--- 304,310 ----
List *live_childrels = NIL;
List *subpaths = NIL;
List *all_child_pathkeys = NIL;
+ List *all_child_outers = NIL;
double parent_rows;
double parent_size;
double *parent_attrsizes;
*************** set_append_rel_pathlist(PlannerInfo *roo
*** 326,333 ****
parent_attrsizes = (double *) palloc0(nattrs * sizeof(double));
/*
! * Generate access paths for each member relation, and pick the cheapest
! * path for each one.
*/
foreach(l, root->append_rel_list)
{
--- 331,340 ----
parent_attrsizes = (double *) palloc0(nattrs * sizeof(double));
/*
! * 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.
*/
foreach(l, root->append_rel_list)
{
*************** set_append_rel_pathlist(PlannerInfo *roo
*** 394,401 ****
{
/*
* This child need not be scanned, so we can omit it from the
! * appendrel. Mark it with a dummy cheapest-path though, in case
! * best_appendrel_indexscan() looks at it later.
*/
set_dummy_rel_pathlist(childrel);
continue;
--- 401,408 ----
{
/*
* This child need not be scanned, so we can omit it from the
! * appendrel. Mark it with a dummy cheapest-path though, for
! * safety.
*/
set_dummy_rel_pathlist(childrel);
continue;
*************** set_append_rel_pathlist(PlannerInfo *roo
*** 457,497 ****
subpaths = accumulate_append_subpath(subpaths,
childrel->cheapest_total_path);
! /* Remember which childrels are live, for MergeAppend logic below */
live_childrels = lappend(live_childrels, childrel);
/*
! * Collect a list of all the available path orderings for all the
! * children. We use this as a heuristic to indicate which sort
! * orderings we should build MergeAppend paths for.
*/
foreach(lcp, childrel->pathlist)
{
Path *childpath = (Path *) lfirst(lcp);
List *childkeys = childpath->pathkeys;
! ListCell *lpk;
! bool found = false;
!
! /* Ignore unsorted paths */
! if (childkeys == NIL)
! continue;
! /* Have we already seen this ordering? */
! foreach(lpk, all_child_pathkeys)
{
! List *existing_pathkeys = (List *) lfirst(lpk);
! if (compare_pathkeys(existing_pathkeys,
! childkeys) == PATHKEYS_EQUAL)
{
! found = true;
! break;
}
}
! if (!found)
{
! /* No, so add it to all_child_pathkeys */
! all_child_pathkeys = lappend(all_child_pathkeys, childkeys);
}
}
--- 464,534 ----
subpaths = accumulate_append_subpath(subpaths,
childrel->cheapest_total_path);
! /* Remember which childrels are live, for logic below */
live_childrels = lappend(live_childrels, childrel);
/*
! * Collect lists of all the available path orderings and
! * parameterizations for all the children. We use these as a
! * heuristic to indicate which sort orderings and parameterizations we
! * should build Append and MergeAppend paths for.
*/
foreach(lcp, childrel->pathlist)
{
Path *childpath = (Path *) lfirst(lcp);
List *childkeys = childpath->pathkeys;
! Relids childouter = childpath->required_outer;
! /* Unsorted paths don't contribute to pathkey list */
! if (childkeys != NIL)
{
! ListCell *lpk;
! bool found = false;
! /* Have we already seen this ordering? */
! foreach(lpk, all_child_pathkeys)
{
! List *existing_pathkeys = (List *) lfirst(lpk);
!
! if (compare_pathkeys(existing_pathkeys,
! childkeys) == PATHKEYS_EQUAL)
! {
! found = true;
! break;
! }
! }
! if (!found)
! {
! /* No, so add it to all_child_pathkeys */
! all_child_pathkeys = lappend(all_child_pathkeys,
! childkeys);
}
}
!
! /* Unparameterized paths don't contribute to param-set list */
! /* XXX should fix indxpath,c to avoid bogus paths */
! if (childouter && !bms_is_member(rel->relid, childouter))
{
! ListCell *lco;
! bool found = false;
!
! /* Have we already seen this param set? */
! foreach(lco, all_child_outers)
! {
! Relids existing_outers = (Relids) lfirst(lco);
!
! if (bms_equal(existing_outers, childouter))
! {
! found = true;
! break;
! }
! }
! if (!found)
! {
! /* No, so add it to all_child_outers */
! all_child_outers = lappend(all_child_outers,
! childouter);
! }
}
}
*************** set_append_rel_pathlist(PlannerInfo *roo
*** 562,583 ****
pfree(parent_attrsizes);
/*
! * Next, build an unordered Append path for the rel. (Note: this is
! * correct even if we have zero or one live subpath due to constraint
! * exclusion.)
*/
add_path(rel, (Path *) create_append_path(rel, subpaths));
/*
! * Next, build MergeAppend paths based on the collected list of child
! * pathkeys. We consider both cheapest-startup and cheapest-total cases,
! * ie, for each interesting ordering, collect all the cheapest startup
! * subpaths and all the cheapest total paths, and build a MergeAppend path
! * for each list.
*/
! foreach(l, all_child_pathkeys)
{
! List *pathkeys = (List *) lfirst(l);
List *startup_subpaths = NIL;
List *total_subpaths = NIL;
bool startup_neq_total = false;
--- 599,679 ----
pfree(parent_attrsizes);
/*
! * Next, build an unordered, unparameterized Append path for the rel.
! * (Note: this is correct even if we have zero or one live subpath due to
! * constraint exclusion.)
*/
add_path(rel, (Path *) create_append_path(rel, subpaths));
/*
! * Build unparameterized MergeAppend paths based on the collected list of
! * child pathkeys.
*/
! generate_mergeappend_paths(root, rel, live_childrels,
! all_child_pathkeys, NULL);
!
! /*
! * Build Append and MergeAppend paths for each parameterization seen
! * among the child rels. (This may look pretty expensive, but in most
! * cases of practical interest, the child relations will tend to expose
! * the same parameterizations and pathkeys, so that not that many cases
! * actually get considered here.)
! */
! foreach(l, all_child_outers)
{
! Relids required_outer = (Relids) lfirst(l);
! ListCell *lcr;
!
! /* Select the child paths for an Append with this parameterization */
! subpaths = NIL;
! foreach(lcr, live_childrels)
! {
! RelOptInfo *childrel = (RelOptInfo *) lfirst(lcr);
! Path *cheapest_total;
!
! cheapest_total =
! get_cheapest_path_for_pathkeys(childrel->pathlist,
! NIL,
! required_outer,
! TOTAL_COST);
! Assert(cheapest_total != NULL);
!
! subpaths = accumulate_append_subpath(subpaths, cheapest_total);
! }
! add_path(rel, (Path *) create_append_path(rel, subpaths));
!
! /* And build parameterized MergeAppend paths */
! generate_mergeappend_paths(root, rel, live_childrels,
! all_child_pathkeys, required_outer);
! }
!
! /* Select cheapest paths */
! set_cheapest(rel);
! }
!
! /*
! * generate_mergeappend_paths
! * Generate MergeAppend paths for an append relation
! *
! * Generate a path for each ordering (pathkey list) appearing in
! * all_child_pathkeys. If required_outer isn't NULL, accept paths having
! * those relations as required outer relations.
! *
! * We consider both cheapest-startup and cheapest-total cases, ie, for each
! * interesting ordering, collect all the cheapest startup subpaths and all the
! * cheapest total paths, and build a MergeAppend path for each case.
! */
! static void
! generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel,
! List *live_childrels,
! List *all_child_pathkeys,
! Relids required_outer)
! {
! ListCell *lcp;
!
! foreach(lcp, all_child_pathkeys)
! {
! List *pathkeys = (List *) lfirst(lcp);
List *startup_subpaths = NIL;
List *total_subpaths = NIL;
bool startup_neq_total = false;
*************** set_append_rel_pathlist(PlannerInfo *roo
*** 594,608 ****
cheapest_startup =
get_cheapest_path_for_pathkeys(childrel->pathlist,
pathkeys,
STARTUP_COST);
cheapest_total =
get_cheapest_path_for_pathkeys(childrel->pathlist,
pathkeys,
TOTAL_COST);
/*
* If we can't find any paths with the right order just add the
! * cheapest-total path; we'll have to sort it.
*/
if (cheapest_startup == NULL)
cheapest_startup = childrel->cheapest_total_path;
--- 690,707 ----
cheapest_startup =
get_cheapest_path_for_pathkeys(childrel->pathlist,
pathkeys,
+ required_outer,
STARTUP_COST);
cheapest_total =
get_cheapest_path_for_pathkeys(childrel->pathlist,
pathkeys,
+ required_outer,
TOTAL_COST);
/*
* If we can't find any paths with the right order just add the
! * cheapest-total path; we'll have to sort it. XXX should use
! * cheapest path for required_outer.
*/
if (cheapest_startup == NULL)
cheapest_startup = childrel->cheapest_total_path;
*************** set_append_rel_pathlist(PlannerInfo *roo
*** 634,642 ****
total_subpaths,
pathkeys));
}
-
- /* Select cheapest path */
- set_cheapest(rel);
}
/*
--- 733,738 ----
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index e1c070ea92c625ffa9593d26dbab369dcd566b55..e51faac9a91609e89b2a0e1680fc62b3f4f57b50 100644
*** a/src/backend/optimizer/path/costsize.c
--- b/src/backend/optimizer/path/costsize.c
***************
*** 40,46 ****
* path's result. A caller can estimate the cost of fetching a partial
* result by interpolating between startup_cost and total_cost. In detail:
* actual_cost = startup_cost +
! * (total_cost - startup_cost) * tuples_to_fetch / path->parent->rows;
* Note that a base relation's rows count (and, by extension, plan_rows for
* plan nodes below the LIMIT node) are set without regard to any LIMIT, so
* that this equation works properly. (Also, these routines guarantee not to
--- 40,46 ----
* path's result. A caller can estimate the cost of fetching a partial
* result by interpolating between startup_cost and total_cost. In detail:
* actual_cost = startup_cost +
! * (total_cost - startup_cost) * tuples_to_fetch / path->rows;
* Note that a base relation's rows count (and, by extension, plan_rows for
* plan nodes below the LIMIT node) are set without regard to any LIMIT, so
* that this equation works properly. (Also, these routines guarantee not to
***************
*** 48,58 ****
* applied as a top-level plan node.
*
* For largely historical reasons, most of the routines in this module use
! * the passed result Path only to store their startup_cost and total_cost
! * results into. All the input data they need is passed as separate
* parameters, even though much of it could be extracted from the Path.
* An exception is made for the cost_XXXjoin() routines, which expect all
! * the non-cost fields of the passed XXXPath to be filled in, and similarly
* cost_index() assumes the passed IndexPath is valid except for its output
* values.
*
--- 48,58 ----
* applied as a top-level plan node.
*
* For largely historical reasons, most of the routines in this module use
! * the passed result Path only to store their results (rows, startup_cost and
! * total_cost) into. All the input data they need is passed as separate
* parameters, even though much of it could be extracted from the Path.
* An exception is made for the cost_XXXjoin() routines, which expect all
! * the other fields of the passed XXXPath to be filled in, and similarly
* cost_index() assumes the passed IndexPath is valid except for its output
* values.
*
***************
*** 90,104 ****
#define LOG2(x) (log(x) / 0.693147180559945)
- /*
- * Some Paths return less than the nominal number of rows of their parent
- * relations; join nodes need to do this to get the correct input count:
- */
- #define PATH_ROWS(path) \
- (IsA(path, UniquePath) ? \
- ((UniquePath *) (path))->rows : \
- (path)->parent->rows)
-
double seq_page_cost = DEFAULT_SEQ_PAGE_COST;
double random_page_cost = DEFAULT_RANDOM_PAGE_COST;
--- 90,95 ----
*************** static bool adjust_semi_join(PlannerInfo
*** 141,146 ****
--- 132,145 ----
bool *indexed_join_quals);
static double approx_tuple_count(PlannerInfo *root, JoinPath *path,
List *quals);
+ static void set_joinpath_size_estimate(PlannerInfo *root, JoinPath *path,
+ SpecialJoinInfo *sjinfo,
+ List *restrictlist);
+ static double calc_joinrel_size_estimate(PlannerInfo *root,
+ double outer_rows,
+ double inner_rows,
+ SpecialJoinInfo *sjinfo,
+ List *restrictlist);
static void set_rel_width(PlannerInfo *root, RelOptInfo *rel);
static double relation_byte_size(double tuples, int width);
static double page_size(double tuples, int width);
*************** cost_seqscan(Path *path, PlannerInfo *ro
*** 184,189 ****
--- 183,191 ----
Assert(baserel->relid > 0);
Assert(baserel->rtekind == RTE_RELATION);
+ /* For now, at least, seqscans are never parameterized */
+ path->rows = baserel->rows;
+
if (!enable_seqscan)
startup_cost += disable_cost;
*************** cost_seqscan(Path *path, PlannerInfo *ro
*** 212,225 ****
*
* 'path' describes the indexscan under consideration, and is complete
* except for the fields to be set by this routine
! * 'outer_rel' is the outer relation when we are considering using the index
! * scan as the inside of a nestloop join (hence, some of the indexquals
! * are join clauses, and we should expect repeated scans of the index);
! * NULL for a plain index scan
*
! * In addition to startup_cost and total_cost, cost_index() sets the path's
! * indextotalcost and indexselectivity fields. These values are needed if
! * the IndexPath is used in a BitmapIndexScan.
*
* NOTE: path->indexquals must contain only clauses usable as index
* restrictions. Any additional quals evaluated as qpquals may reduce the
--- 214,225 ----
*
* 'path' describes the indexscan under consideration, and is complete
* except for the fields to be set by this routine
! * 'loop_count' is the number of repetitions of the indexscan to factor into
! * estimates of caching behavior
*
! * In addition to rows, startup_cost and total_cost, cost_index() sets the
! * path's indextotalcost and indexselectivity fields. These values will be
! * needed if the IndexPath is used in a BitmapIndexScan.
*
* NOTE: path->indexquals must contain only clauses usable as index
* restrictions. Any additional quals evaluated as qpquals may reduce the
*************** cost_seqscan(Path *path, PlannerInfo *ro
*** 227,233 ****
* we have to fetch from the table, so they don't reduce the scan cost.
*/
void
! cost_index(IndexPath *path, PlannerInfo *root, RelOptInfo *outer_rel)
{
IndexOptInfo *index = path->indexinfo;
RelOptInfo *baserel = index->rel;
--- 227,233 ----
* we have to fetch from the table, so they don't reduce the scan cost.
*/
void
! cost_index(IndexPath *path, PlannerInfo *root, double loop_count)
{
IndexOptInfo *index = path->indexinfo;
RelOptInfo *baserel = index->rel;
*************** cost_index(IndexPath *path, PlannerInfo
*** 253,258 ****
--- 253,299 ----
Assert(baserel->relid > 0);
Assert(baserel->rtekind == RTE_RELATION);
+ /* Estimate the number of rows returned by the indexscan */
+ if (path->path.required_outer)
+ {
+ /*
+ * The estimate should be less than baserel->rows because of the
+ * additional selectivity of the join clauses. Since indexclauses may
+ * contain both restriction and join clauses, we have to do a set
+ * union to get the full set of clauses that must be considered to
+ * compute the correct selectivity. (Without the union operation, we
+ * might have some restriction clauses appearing twice, which'd
+ * mislead clauselist_selectivity into double-counting their
+ * selectivity. However, since RestrictInfo nodes aren't copied when
+ * linking them into different lists, it should be sufficient to use
+ * pointer comparison to remove duplicates.)
+ *
+ * Note that we force the clauses to be treated as non-join clauses
+ * during selectivity estimation.
+ */
+ List *allclauses;
+
+ allclauses = list_union_ptr(baserel->baserestrictinfo,
+ path->indexclauses);
+ path->path.rows = baserel->tuples *
+ clauselist_selectivity(root,
+ allclauses,
+ baserel->relid, /* do not use 0! */
+ JOIN_INNER,
+ NULL);
+ if (path->path.rows > baserel->rows)
+ path->path.rows = baserel->rows;
+ path->path.rows = clamp_row_est(path->path.rows);
+ }
+ else
+ {
+ /*
+ * The number of rows is the same as the parent rel's estimate, since
+ * this isn't a parameterized path.
+ */
+ path->path.rows = baserel->rows;
+ }
+
if (!enable_indexscan)
startup_cost += disable_cost;
/* we don't need to check enable_indexonlyscan; indxpath.c does that */
*************** cost_index(IndexPath *path, PlannerInfo
*** 266,272 ****
OidFunctionCall7(index->amcostestimate,
PointerGetDatum(root),
PointerGetDatum(path),
! PointerGetDatum(outer_rel),
PointerGetDatum(&indexStartupCost),
PointerGetDatum(&indexTotalCost),
PointerGetDatum(&indexSelectivity),
--- 307,313 ----
OidFunctionCall7(index->amcostestimate,
PointerGetDatum(root),
PointerGetDatum(path),
! Float8GetDatum(loop_count),
PointerGetDatum(&indexStartupCost),
PointerGetDatum(&indexTotalCost),
PointerGetDatum(&indexSelectivity),
*************** cost_index(IndexPath *path, PlannerInfo
*** 319,325 ****
* that this query will fetch; but it's not clear how to do better.
*----------
*/
! if (outer_rel != NULL && outer_rel->rows > 1)
{
/*
* For repeated indexscans, the appropriate estimate for the
--- 360,366 ----
* that this query will fetch; but it's not clear how to do better.
*----------
*/
! if (loop_count > 1)
{
/*
* For repeated indexscans, the appropriate estimate for the
*************** cost_index(IndexPath *path, PlannerInfo
*** 329,337 ****
* pro-rate the costs for one scan. In this case we assume all the
* fetches are random accesses.
*/
! double num_scans = outer_rel->rows;
!
! pages_fetched = index_pages_fetched(tuples_fetched * num_scans,
baserel->pages,
(double) index->pages,
root);
--- 370,376 ----
* pro-rate the costs for one scan. In this case we assume all the
* fetches are random accesses.
*/
! pages_fetched = index_pages_fetched(tuples_fetched * loop_count,
baserel->pages,
(double) index->pages,
root);
*************** cost_index(IndexPath *path, PlannerInfo
*** 339,345 ****
if (indexonly)
pages_fetched = ceil(pages_fetched * (1.0 - baserel->allvisfrac));
! max_IO_cost = (pages_fetched * spc_random_page_cost) / num_scans;
/*
* In the perfectly correlated case, the number of pages touched by
--- 378,384 ----
if (indexonly)
pages_fetched = ceil(pages_fetched * (1.0 - baserel->allvisfrac));
! max_IO_cost = (pages_fetched * spc_random_page_cost) / loop_count;
/*
* In the perfectly correlated case, the number of pages touched by
*************** cost_index(IndexPath *path, PlannerInfo
*** 353,359 ****
*/
pages_fetched = ceil(indexSelectivity * (double) baserel->pages);
! pages_fetched = index_pages_fetched(pages_fetched * num_scans,
baserel->pages,
(double) index->pages,
root);
--- 392,398 ----
*/
pages_fetched = ceil(indexSelectivity * (double) baserel->pages);
! pages_fetched = index_pages_fetched(pages_fetched * loop_count,
baserel->pages,
(double) index->pages,
root);
*************** cost_index(IndexPath *path, PlannerInfo
*** 361,367 ****
if (indexonly)
pages_fetched = ceil(pages_fetched * (1.0 - baserel->allvisfrac));
! min_IO_cost = (pages_fetched * spc_random_page_cost) / num_scans;
}
else
{
--- 400,406 ----
if (indexonly)
pages_fetched = ceil(pages_fetched * (1.0 - baserel->allvisfrac));
! min_IO_cost = (pages_fetched * spc_random_page_cost) / loop_count;
}
else
{
*************** cost_index(IndexPath *path, PlannerInfo
*** 417,423 ****
startup_cost += baserel->baserestrictcost.startup;
cpu_per_tuple = cpu_tuple_cost + baserel->baserestrictcost.per_tuple;
! if (outer_rel == NULL)
{
QualCost index_qual_cost;
--- 456,462 ----
startup_cost += baserel->baserestrictcost.startup;
cpu_per_tuple = cpu_tuple_cost + baserel->baserestrictcost.per_tuple;
! if (path->path.required_outer == NULL)
{
QualCost index_qual_cost;
*************** get_indexpath_pages(Path *bitmapqual)
*** 578,594 ****
*
* 'baserel' is the relation to be scanned
* 'bitmapqual' is a tree of IndexPaths, BitmapAndPaths, and BitmapOrPaths
! * 'outer_rel' is the outer relation when we are considering using the bitmap
! * scan as the inside of a nestloop join (hence, some of the indexquals
! * are join clauses, and we should expect repeated scans of the table);
! * NULL for a plain bitmap scan
*
! * Note: if this is a join inner path, the component IndexPaths in bitmapqual
! * should have been costed accordingly.
*/
void
cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel,
! Path *bitmapqual, RelOptInfo *outer_rel)
{
Cost startup_cost = 0;
Cost run_cost = 0;
--- 617,631 ----
*
* 'baserel' is the relation to be scanned
* 'bitmapqual' is a tree of IndexPaths, BitmapAndPaths, and BitmapOrPaths
! * 'loop_count' is the number of repetitions of the indexscan to factor into
! * estimates of caching behavior
*
! * Note: the component IndexPaths in bitmapqual should have been costed
! * using the same loop_count.
*/
void
cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel,
! Path *bitmapqual, double loop_count)
{
Cost startup_cost = 0;
Cost run_cost = 0;
*************** cost_bitmap_heap_scan(Path *path, Planne
*** 607,612 ****
--- 644,677 ----
Assert(baserel->relid > 0);
Assert(baserel->rtekind == RTE_RELATION);
+ /* Estimate the number of rows returned by the bitmap scan */
+ if (path->required_outer)
+ {
+ /*
+ * The estimate should be less than baserel->rows because of the
+ * additional selectivity of the join clauses. We make use of the
+ * selectivity estimated for the bitmap to do this; this isn't really
+ * quite right since there may be restriction conditions not included
+ * in the bitmap ...
+ */
+ Cost indexTotalCost;
+ Selectivity indexSelectivity;
+
+ cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity);
+ path->rows = baserel->tuples * indexSelectivity;
+ if (path->rows > baserel->rows)
+ path->rows = baserel->rows;
+ path->rows = clamp_row_est(path->rows);
+ }
+ else
+ {
+ /*
+ * The number of rows is the same as the parent rel's estimate, since
+ * this isn't a parameterized path.
+ */
+ path->rows = baserel->rows;
+ }
+
if (!enable_bitmapscan)
startup_cost += disable_cost;
*************** cost_bitmap_heap_scan(Path *path, Planne
*** 630,636 ****
T = (baserel->pages > 1) ? (double) baserel->pages : 1.0;
! if (outer_rel != NULL && outer_rel->rows > 1)
{
/*
* For repeated bitmap scans, scale up the number of tuples fetched in
--- 695,701 ----
T = (baserel->pages > 1) ? (double) baserel->pages : 1.0;
! if (loop_count > 1)
{
/*
* For repeated bitmap scans, scale up the number of tuples fetched in
*************** cost_bitmap_heap_scan(Path *path, Planne
*** 638,650 ****
* estimate the number of pages fetched by all the scans. Then
* pro-rate for one scan.
*/
! double num_scans = outer_rel->rows;
!
! pages_fetched = index_pages_fetched(tuples_fetched * num_scans,
baserel->pages,
get_indexpath_pages(bitmapqual),
root);
! pages_fetched /= num_scans;
}
else
{
--- 703,713 ----
* estimate the number of pages fetched by all the scans. Then
* pro-rate for one scan.
*/
! pages_fetched = index_pages_fetched(tuples_fetched * loop_count,
baserel->pages,
get_indexpath_pages(bitmapqual),
root);
! pages_fetched /= loop_count;
}
else
{
*************** cost_bitmap_tree_node(Path *path, Cost *
*** 711,717 ****
* scan doesn't look to be the same cost as an indexscan to retrieve a
* single tuple.
*/
! *cost += 0.1 * cpu_operator_cost * ((IndexPath *) path)->rows;
}
else if (IsA(path, BitmapAndPath))
{
--- 774,780 ----
* scan doesn't look to be the same cost as an indexscan to retrieve a
* single tuple.
*/
! *cost += 0.1 * cpu_operator_cost * path->rows;
}
else if (IsA(path, BitmapAndPath))
{
*************** cost_bitmap_and_node(BitmapAndPath *path
*** 772,777 ****
--- 835,841 ----
totalCost += 100.0 * cpu_operator_cost;
}
path->bitmapselectivity = selec;
+ path->path.rows = path->path.parent->rows; /* not really used */
path->path.startup_cost = totalCost;
path->path.total_cost = totalCost;
}
*************** cost_bitmap_or_node(BitmapOrPath *path,
*** 817,822 ****
--- 881,887 ----
totalCost += 100.0 * cpu_operator_cost;
}
path->bitmapselectivity = Min(selec, 1.0);
+ path->path.rows = path->path.parent->rows; /* not really used */
path->path.startup_cost = totalCost;
path->path.total_cost = totalCost;
}
*************** cost_tidscan(Path *path, PlannerInfo *ro
*** 842,847 ****
--- 907,915 ----
Assert(baserel->relid > 0);
Assert(baserel->rtekind == RTE_RELATION);
+ /* For now, tidscans are never parameterized */
+ path->rows = baserel->rows;
+
/* Count how many tuples we expect to retrieve */
ntuples = 0;
foreach(l, tidquals)
*************** cost_subqueryscan(Path *path, RelOptInfo
*** 923,928 ****
--- 991,999 ----
Assert(baserel->relid > 0);
Assert(baserel->rtekind == RTE_SUBQUERY);
+ /* subqueryscans are never parameterized */
+ path->rows = baserel->rows;
+
/*
* Cost of path is cost of evaluating the subplan, plus cost of evaluating
* any restriction clauses that will be attached to the SubqueryScan node,
*************** cost_functionscan(Path *path, PlannerInf
*** 957,962 ****
--- 1028,1036 ----
rte = planner_rt_fetch(baserel->relid, root);
Assert(rte->rtekind == RTE_FUNCTION);
+ /* functionscans are never parameterized */
+ path->rows = baserel->rows;
+
/*
* Estimate costs of executing the function expression.
*
*************** cost_valuesscan(Path *path, PlannerInfo
*** 998,1003 ****
--- 1072,1080 ----
Assert(baserel->relid > 0);
Assert(baserel->rtekind == RTE_VALUES);
+ /* valuesscans are never parameterized */
+ path->rows = baserel->rows;
+
/*
* For now, estimate list evaluation cost at one operator eval per list
* (probably pretty bogus, but is it worth being smarter?)
*************** cost_ctescan(Path *path, PlannerInfo *ro
*** 1034,1039 ****
--- 1111,1119 ----
Assert(baserel->relid > 0);
Assert(baserel->rtekind == RTE_CTE);
+ /* ctescans are never parameterized */
+ path->rows = baserel->rows;
+
/* Charge one CPU tuple cost per row for tuplestore manipulation */
cpu_per_tuple = cpu_tuple_cost;
*************** cost_sort(Path *path, PlannerInfo *root,
*** 1152,1157 ****
--- 1232,1239 ----
if (!enable_sort)
startup_cost += disable_cost;
+ path->rows = tuples;
+
/*
* We want to be sure the cost of a sort is never estimated as zero, even
* if passed-in tuple count is zero. Besides, mustn't do log(0)...
*************** cost_material(Path *path,
*** 1320,1325 ****
--- 1402,1409 ----
double nbytes = relation_byte_size(tuples, width);
long work_mem_bytes = work_mem * 1024L;
+ path->rows = tuples;
+
/*
* Whether spilling or not, charge 2x cpu_operator_cost per tuple to
* reflect bookkeeping overhead. (This rate must be more than what
*************** cost_agg(Path *path, PlannerInfo *root,
*** 1369,1374 ****
--- 1453,1459 ----
Cost input_startup_cost, Cost input_total_cost,
double input_tuples)
{
+ double output_tuples;
Cost startup_cost;
Cost total_cost;
AggClauseCosts dummy_aggcosts;
*************** cost_agg(Path *path, PlannerInfo *root,
*** 1411,1416 ****
--- 1496,1502 ----
startup_cost += aggcosts->finalCost;
/* we aren't grouping */
total_cost = startup_cost + cpu_tuple_cost;
+ output_tuples = 1;
}
else if (aggstrategy == AGG_SORTED)
{
*************** cost_agg(Path *path, PlannerInfo *root,
*** 1423,1428 ****
--- 1509,1515 ----
total_cost += (cpu_operator_cost * numGroupCols) * input_tuples;
total_cost += aggcosts->finalCost * numGroups;
total_cost += cpu_tuple_cost * numGroups;
+ output_tuples = numGroups;
}
else
{
*************** cost_agg(Path *path, PlannerInfo *root,
*** 1434,1441 ****
--- 1521,1530 ----
total_cost = startup_cost;
total_cost += aggcosts->finalCost * numGroups;
total_cost += cpu_tuple_cost * numGroups;
+ output_tuples = numGroups;
}
+ path->rows = output_tuples;
path->startup_cost = startup_cost;
path->total_cost = total_cost;
}
*************** cost_windowagg(Path *path, PlannerInfo *
*** 1498,1503 ****
--- 1587,1593 ----
total_cost += cpu_operator_cost * (numPartCols + numOrderCols) * input_tuples;
total_cost += cpu_tuple_cost * input_tuples;
+ path->rows = input_tuples;
path->startup_cost = startup_cost;
path->total_cost = total_cost;
}
*************** cost_group(Path *path, PlannerInfo *root
*** 1528,1587 ****
*/
total_cost += cpu_operator_cost * input_tuples * numGroupCols;
path->startup_cost = startup_cost;
path->total_cost = total_cost;
}
/*
- * If a nestloop's inner path is an indexscan, be sure to use its estimated
- * output row count, which may be lower than the restriction-clause-only row
- * count of its parent. (We don't include this case in the PATH_ROWS macro
- * because it applies *only* to a nestloop's inner relation.) We have to
- * be prepared to recurse through Append or MergeAppend nodes in case of an
- * appendrel. (It's not clear MergeAppend can be seen here, but we may as
- * well handle it if so.)
- */
- static double
- nestloop_inner_path_rows(Path *path)
- {
- double result;
-
- if (IsA(path, IndexPath))
- result = ((IndexPath *) path)->rows;
- else if (IsA(path, BitmapHeapPath))
- result = ((BitmapHeapPath *) path)->rows;
- else if (IsA(path, AppendPath))
- {
- ListCell *l;
-
- result = 0;
- foreach(l, ((AppendPath *) path)->subpaths)
- {
- result += nestloop_inner_path_rows((Path *) lfirst(l));
- }
- }
- else if (IsA(path, MergeAppendPath))
- {
- ListCell *l;
-
- result = 0;
- foreach(l, ((MergeAppendPath *) path)->subpaths)
- {
- result += nestloop_inner_path_rows((Path *) lfirst(l));
- }
- }
- else
- result = PATH_ROWS(path);
-
- return result;
- }
-
- /*
* cost_nestloop
* Determines and returns the cost of joining two relations using the
* nested loop algorithm.
*
! * 'path' is already filled in except for the cost fields
* 'sjinfo' is extra info about the join for selectivity estimation
*/
void
--- 1618,1634 ----
*/
total_cost += cpu_operator_cost * input_tuples * numGroupCols;
+ path->rows = numGroups;
path->startup_cost = startup_cost;
path->total_cost = total_cost;
}
/*
* cost_nestloop
* Determines and returns the cost of joining two relations using the
* nested loop algorithm.
*
! * 'path' is already filled in except for the rows and cost fields
* 'sjinfo' is extra info about the join for selectivity estimation
*/
void
*************** cost_nestloop(NestPath *path, PlannerInf
*** 1597,1609 ****
Cost inner_rescan_run_cost;
Cost cpu_per_tuple;
QualCost restrict_qual_cost;
! double outer_path_rows = PATH_ROWS(outer_path);
! double inner_path_rows = nestloop_inner_path_rows(inner_path);
double ntuples;
Selectivity outer_match_frac;
Selectivity match_count;
bool indexed_join_quals;
if (!enable_nestloop)
startup_cost += disable_cost;
--- 1644,1676 ----
Cost inner_rescan_run_cost;
Cost cpu_per_tuple;
QualCost restrict_qual_cost;
! double outer_path_rows = outer_path->rows;
! double inner_path_rows = inner_path->rows;
double ntuples;
Selectivity outer_match_frac;
Selectivity match_count;
bool indexed_join_quals;
+ /* Estimate the number of rows returned by the join */
+ if (path->path.required_outer)
+ {
+ List *jclauses;
+
+ /*
+ * The nestloop is (still) parameterized because of upper-level join
+ * clauses used by the input paths. So the rowcount estimate should
+ * be less than the joinrel's row count because of the additional
+ * selectivity of those join clauses. To estimate the size we need
+ * to know which of the joinrestrictinfo clauses nominally associated
+ * with the join have been applied in the inner input path.
+ */
+ jclauses = select_nonredundant_join_clauses(path->joinrestrictinfo,
+ path->innerjoinpath->param_clauses);
+ set_joinpath_size_estimate(root, path, sjinfo, jclauses);
+ }
+ else
+ path->path.rows = path->path.parent->rows;
+
if (!enable_nestloop)
startup_cost += disable_cost;
*************** cost_nestloop(NestPath *path, PlannerInf
*** 1729,1735 ****
* no possibility of wanting to keep both paths. So it seems best to make
* the decision here and record it in the path's materialize_inner field.
*
! * 'path' is already filled in except for the cost fields and materialize_inner
* 'sjinfo' is extra info about the join for selectivity estimation
*
* Notes: path's mergeclauses should be a subset of the joinrestrictinfo list;
--- 1796,1803 ----
* no possibility of wanting to keep both paths. So it seems best to make
* the decision here and record it in the path's materialize_inner field.
*
! * 'path' is already filled in except for the rows and cost fields and
! * materialize_inner
* 'sjinfo' is extra info about the join for selectivity estimation
*
* Notes: path's mergeclauses should be a subset of the joinrestrictinfo list;
*************** cost_mergejoin(MergePath *path, PlannerI
*** 1753,1760 ****
mat_inner_cost;
QualCost merge_qual_cost;
QualCost qp_qual_cost;
! double outer_path_rows = PATH_ROWS(outer_path);
! double inner_path_rows = PATH_ROWS(inner_path);
double outer_rows,
inner_rows,
outer_skip_rows,
--- 1821,1828 ----
mat_inner_cost;
QualCost merge_qual_cost;
QualCost qp_qual_cost;
! double outer_path_rows = outer_path->rows;
! double inner_path_rows = inner_path->rows;
double outer_rows,
inner_rows,
outer_skip_rows,
*************** cost_mergejoin(MergePath *path, PlannerI
*** 1768,1773 ****
--- 1836,1844 ----
innerendsel;
Path sort_path; /* dummy for result of cost_sort */
+ set_joinpath_size_estimate(root, &path->jpath, sjinfo,
+ path->jpath.joinrestrictinfo);
+
/* Protect some assumptions below that rowcounts aren't zero or NaN */
if (outer_path_rows <= 0 || isnan(outer_path_rows))
outer_path_rows = 1;
*************** cached_scansel(PlannerInfo *root, Restri
*** 2152,2158 ****
* Determines and returns the cost of joining two relations using the
* hash join algorithm.
*
! * 'path' is already filled in except for the cost fields
* 'sjinfo' is extra info about the join for selectivity estimation
*
* Note: path's hashclauses should be a subset of the joinrestrictinfo list
--- 2223,2229 ----
* Determines and returns the cost of joining two relations using the
* hash join algorithm.
*
! * 'path' is already filled in except for the rows and cost fields
* 'sjinfo' is extra info about the join for selectivity estimation
*
* Note: path's hashclauses should be a subset of the joinrestrictinfo list
*************** cost_hashjoin(HashPath *path, PlannerInf
*** 2169,2176 ****
QualCost hash_qual_cost;
QualCost qp_qual_cost;
double hashjointuples;
! double outer_path_rows = PATH_ROWS(outer_path);
! double inner_path_rows = PATH_ROWS(inner_path);
int num_hashclauses = list_length(hashclauses);
int numbuckets;
int numbatches;
--- 2240,2247 ----
QualCost hash_qual_cost;
QualCost qp_qual_cost;
double hashjointuples;
! double outer_path_rows = outer_path->rows;
! double inner_path_rows = inner_path->rows;
int num_hashclauses = list_length(hashclauses);
int numbuckets;
int numbatches;
*************** cost_hashjoin(HashPath *path, PlannerInf
*** 2181,2186 ****
--- 2252,2260 ----
Selectivity match_count;
ListCell *hcl;
+ set_joinpath_size_estimate(root, &path->jpath, sjinfo,
+ path->jpath.joinrestrictinfo);
+
if (!enable_hashjoin)
startup_cost += disable_cost;
*************** cost_rescan(PlannerInfo *root, Path *pat
*** 2545,2552 ****
* cpu_tuple_cost per tuple, unless the result is large enough
* to spill to disk.
*/
! Cost run_cost = cpu_tuple_cost * path->parent->rows;
! double nbytes = relation_byte_size(path->parent->rows,
path->parent->width);
long work_mem_bytes = work_mem * 1024L;
--- 2619,2626 ----
* cpu_tuple_cost per tuple, unless the result is large enough
* to spill to disk.
*/
! Cost run_cost = cpu_tuple_cost * path->rows;
! double nbytes = relation_byte_size(path->rows,
path->parent->width);
long work_mem_bytes = work_mem * 1024L;
*************** cost_rescan(PlannerInfo *root, Path *pat
*** 2572,2579 ****
* the run_cost charge in cost_sort, and also see comments in
* cost_material before you change it.)
*/
! Cost run_cost = cpu_operator_cost * path->parent->rows;
! double nbytes = relation_byte_size(path->parent->rows,
path->parent->width);
long work_mem_bytes = work_mem * 1024L;
--- 2646,2653 ----
* the run_cost charge in cost_sort, and also see comments in
* cost_material before you change it.)
*/
! Cost run_cost = cpu_operator_cost * path->rows;
! double nbytes = relation_byte_size(path->rows,
path->parent->width);
long work_mem_bytes = work_mem * 1024L;
*************** cost_qual_eval_walker(Node *node, cost_q
*** 2850,2856 ****
* We should therefore adjust some of the cost components for this effect.
* This function computes some estimates needed for these adjustments.
*
! * 'path' is already filled in except for the cost fields
* 'sjinfo' is extra info about the join for selectivity estimation
*
* Returns TRUE if this is a SEMI or ANTI join, FALSE if not.
--- 2924,2930 ----
* We should therefore adjust some of the cost components for this effect.
* This function computes some estimates needed for these adjustments.
*
! * 'path' is already filled in except for the rows and cost fields
* 'sjinfo' is extra info about the join for selectivity estimation
*
* Returns TRUE if this is a SEMI or ANTI join, FALSE if not.
*************** adjust_semi_join(PlannerInfo *root, Join
*** 2954,2962 ****
* nselec * inner_rows / jselec.
*
* Note: it is correct to use the inner rel's "rows" count here, not
! * PATH_ROWS(), even if the inner path under consideration is an inner
! * indexscan. This is because we have included all the join clauses in
! * the selectivity estimate, even ones used in an inner indexscan.
*/
if (jselec > 0) /* protect against zero divide */
{
--- 3028,3036 ----
* nselec * inner_rows / jselec.
*
* Note: it is correct to use the inner rel's "rows" count here, not
! * innerjoinpath->rows, even if the inner path under consideration is
! * parameterized. This is because we have included all the join clauses
! * in the selectivity estimate, even ones used in an inner indexscan.
*/
if (jselec > 0) /* protect against zero divide */
{
*************** adjust_semi_join(PlannerInfo *root, Join
*** 2981,2989 ****
{
List *nrclauses;
! nrclauses = select_nonredundant_join_clauses(root,
! path->joinrestrictinfo,
! path->innerjoinpath);
*indexed_join_quals = (nrclauses == NIL);
}
else
--- 3055,3063 ----
{
List *nrclauses;
! nrclauses =
! select_nonredundant_join_clauses(path->joinrestrictinfo,
! path->innerjoinpath->param_clauses);
*indexed_join_quals = (nrclauses == NIL);
}
else
*************** static double
*** 3025,3032 ****
approx_tuple_count(PlannerInfo *root, JoinPath *path, List *quals)
{
double tuples;
! double outer_tuples = path->outerjoinpath->parent->rows;
! double inner_tuples = path->innerjoinpath->parent->rows;
SpecialJoinInfo sjinfo;
Selectivity selec = 1.0;
ListCell *l;
--- 3099,3106 ----
approx_tuple_count(PlannerInfo *root, JoinPath *path, List *quals)
{
double tuples;
! double outer_tuples = path->outerjoinpath->rows;
! double inner_tuples = path->innerjoinpath->rows;
SpecialJoinInfo sjinfo;
Selectivity selec = 1.0;
ListCell *l;
*************** set_joinrel_size_estimates(PlannerInfo *
*** 3123,3128 ****
--- 3197,3251 ----
SpecialJoinInfo *sjinfo,
List *restrictlist)
{
+ rel->rows = calc_joinrel_size_estimate(root,
+ outer_rel->rows,
+ inner_rel->rows,
+ sjinfo,
+ restrictlist);
+ }
+
+ /*
+ * set_joinpath_size_estimate
+ * Set the rows estimate for the given join path.
+ *
+ * If the join is not parameterized by any joinclauses from higher joins, the
+ * estimate is the same as previously computed by set_joinrel_size_estimates.
+ * Otherwise, we estimate afresh using the identical logic, but with the rows
+ * estimates from the input paths (which are typically less than their rels'
+ * regular row estimates) and the restriction clauses actually being applied
+ * at the join.
+ */
+ static void
+ set_joinpath_size_estimate(PlannerInfo *root, JoinPath *path,
+ SpecialJoinInfo *sjinfo,
+ List *restrictlist)
+ {
+ if (path->path.required_outer)
+ {
+ path->path.rows = calc_joinrel_size_estimate(root,
+ path->outerjoinpath->rows,
+ path->innerjoinpath->rows,
+ sjinfo,
+ restrictlist);
+ /* For safety, make sure result is not more than the base estimate */
+ if (path->path.rows > path->path.parent->rows)
+ path->path.rows = path->path.parent->rows;
+ }
+ else
+ path->path.rows = path->path.parent->rows;
+ }
+
+ /*
+ * calc_joinrel_size_estimate
+ * Workhorse for set_joinrel_size_estimates and set_joinpath_size_estimate
+ */
+ static double
+ calc_joinrel_size_estimate(PlannerInfo *root,
+ double outer_rows,
+ double inner_rows,
+ SpecialJoinInfo *sjinfo,
+ List *restrictlist)
+ {
JoinType jointype = sjinfo->jointype;
Selectivity jselec;
Selectivity pselec;
*************** set_joinrel_size_estimates(PlannerInfo *
*** 3197,3224 ****
switch (jointype)
{
case JOIN_INNER:
! nrows = outer_rel->rows * inner_rel->rows * jselec;
break;
case JOIN_LEFT:
! nrows = outer_rel->rows * inner_rel->rows * jselec;
! if (nrows < outer_rel->rows)
! nrows = outer_rel->rows;
nrows *= pselec;
break;
case JOIN_FULL:
! nrows = outer_rel->rows * inner_rel->rows * jselec;
! if (nrows < outer_rel->rows)
! nrows = outer_rel->rows;
! if (nrows < inner_rel->rows)
! nrows = inner_rel->rows;
nrows *= pselec;
break;
case JOIN_SEMI:
! nrows = outer_rel->rows * jselec;
/* pselec not used */
break;
case JOIN_ANTI:
! nrows = outer_rel->rows * (1.0 - jselec);
nrows *= pselec;
break;
default:
--- 3320,3347 ----
switch (jointype)
{
case JOIN_INNER:
! nrows = outer_rows * inner_rows * jselec;
break;
case JOIN_LEFT:
! nrows = outer_rows * inner_rows * jselec;
! if (nrows < outer_rows)
! nrows = outer_rows;
nrows *= pselec;
break;
case JOIN_FULL:
! nrows = outer_rows * inner_rows * jselec;
! if (nrows < outer_rows)
! nrows = outer_rows;
! if (nrows < inner_rows)
! nrows = inner_rows;
nrows *= pselec;
break;
case JOIN_SEMI:
! nrows = outer_rows * jselec;
/* pselec not used */
break;
case JOIN_ANTI:
! nrows = outer_rows * (1.0 - jselec);
nrows *= pselec;
break;
default:
*************** set_joinrel_size_estimates(PlannerInfo *
*** 3228,3234 ****
break;
}
! rel->rows = clamp_row_est(nrows);
}
/*
--- 3351,3357 ----
break;
}
! return clamp_row_est(nrows);
}
/*
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 11ee2317376b03d443d7ec25c745f51497d8a808..5f42407a6f8a782e1c311ca76fdf4b7b8895ed7e 100644
*** a/src/backend/optimizer/path/indxpath.c
--- b/src/backend/optimizer/path/indxpath.c
*************** typedef struct
*** 73,90 ****
static List *find_usable_indexes(PlannerInfo *root, RelOptInfo *rel,
List *clauses, List *outer_clauses,
! bool istoplevel, RelOptInfo *outer_rel,
SaOpControl saop_control, ScanTypeControl scantype);
static List *find_saop_paths(PlannerInfo *root, RelOptInfo *rel,
List *clauses, List *outer_clauses,
! bool istoplevel, RelOptInfo *outer_rel);
static Path *choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel,
! List *paths, RelOptInfo *outer_rel);
static int path_usage_comparator(const void *a, const void *b);
static Cost bitmap_scan_cost_est(PlannerInfo *root, RelOptInfo *rel,
! Path *ipath, RelOptInfo *outer_rel);
static Cost bitmap_and_cost_est(PlannerInfo *root, RelOptInfo *rel,
! List *paths, RelOptInfo *outer_rel);
static PathClauseUsage *classify_index_clause_usage(Path *path,
List **clauselist);
static void find_indexpath_quals(Path *bitmapqual, List **quals, List **preds);
--- 73,95 ----
static List *find_usable_indexes(PlannerInfo *root, RelOptInfo *rel,
List *clauses, List *outer_clauses,
! bool istoplevel,
! Relids outer_relids, double outer_rows,
SaOpControl saop_control, ScanTypeControl scantype);
static List *find_saop_paths(PlannerInfo *root, RelOptInfo *rel,
List *clauses, List *outer_clauses,
! bool istoplevel,
! Relids outer_relids, double outer_rows);
static Path *choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel,
! List *paths,
! Relids outer_relids, double outer_rows);
static int path_usage_comparator(const void *a, const void *b);
static Cost bitmap_scan_cost_est(PlannerInfo *root, RelOptInfo *rel,
! Path *ipath,
! Relids outer_relids, double outer_rows);
static Cost bitmap_and_cost_est(PlannerInfo *root, RelOptInfo *rel,
! List *paths,
! Relids outer_relids, double outer_rows);
static PathClauseUsage *classify_index_clause_usage(Path *path,
List **clauselist);
static void find_indexpath_quals(Path *bitmapqual, List **quals, List **preds);
*************** static Expr *match_clause_to_ordering_op
*** 118,125 ****
static Relids indexable_outerrelids(PlannerInfo *root, RelOptInfo *rel);
static bool matches_any_index(RestrictInfo *rinfo, RelOptInfo *rel,
Relids outer_relids);
static List *find_clauses_for_join(PlannerInfo *root, RelOptInfo *rel,
! Relids outer_relids, bool isouterjoin);
static bool match_boolean_index_clause(Node *clause, int indexcol,
IndexOptInfo *index);
static bool match_special_index_operator(Expr *clause,
--- 123,132 ----
static Relids indexable_outerrelids(PlannerInfo *root, RelOptInfo *rel);
static bool matches_any_index(RestrictInfo *rinfo, RelOptInfo *rel,
Relids outer_relids);
+ static void find_parameterized_indexscans(PlannerInfo *root, RelOptInfo *rel,
+ Relids outer_relids, double outer_rows);
static List *find_clauses_for_join(PlannerInfo *root, RelOptInfo *rel,
! Relids outer_relids);
static bool match_boolean_index_clause(Node *clause, int indexcol,
IndexOptInfo *index);
static bool match_special_index_operator(Expr *clause,
*************** static Const *string_to_const(const char
*** 152,172 ****
*
* There are two basic kinds of index scans. A "plain" index scan uses
* only restriction clauses (possibly none at all) in its indexqual,
! * so it can be applied in any context. An "innerjoin" index scan uses
* join clauses (plus restriction clauses, if available) in its indexqual.
! * Therefore it can only be used as the inner relation of a nestloop
! * join against an outer rel that includes all the other rels mentioned
! * in its join clauses. In that context, values for the other rels'
* attributes are available and fixed during any one scan of the indexpath.
*
! * An IndexPath is generated and submitted to add_path() for each plain index
! * scan this routine deems potentially interesting for the current query.
! *
! * We also determine the set of other relids that participate in join
! * clauses that could be used with each index. The actually best innerjoin
! * path will be generated for each outer relation later on, but knowing the
! * set of potential otherrels allows us to identify equivalent outer relations
! * and avoid repeated computation.
*
* 'rel' is the relation for which we want to generate index paths
*
--- 159,175 ----
*
* There are two basic kinds of index scans. A "plain" index scan uses
* only restriction clauses (possibly none at all) in its indexqual,
! * so it can be applied in any context. A "parameterized" index scan uses
* join clauses (plus restriction clauses, if available) in its indexqual.
! * When joining such a scan to one of the relations supplying the other
! * variables used in its indexqual, the parameterized scan must appear as
! * the inner relation of a nestloop join; it can't be used on the outer side,
! * nor in a merge or hash join. In that context, values for the other rels'
* attributes are available and fixed during any one scan of the indexpath.
*
! * An IndexPath is generated and submitted to add_path() for each plain or
! * parameterized index scan this routine deems potentially interesting for
! * the current query.
*
* 'rel' is the relation for which we want to generate index paths
*
*************** create_index_paths(PlannerInfo *root, Re
*** 178,183 ****
--- 181,188 ----
List *indexpaths;
List *bitindexpaths;
ListCell *l;
+ Index rti;
+ double min_rowcount;
/* Skip the whole mess if no indexes */
if (rel->indexlist == NIL)
*************** create_index_paths(PlannerInfo *root, Re
*** 191,196 ****
--- 196,203 ----
* indexes of this rel, and generate the set of all other relids that
* participate in such join clauses. We'll use this set later to
* recognize outer rels that are equivalent for joining purposes.
+ *
+ * XXX index_outer_relids could now be a local variable in this routine
*/
rel->index_outer_relids = indexable_outerrelids(root, rel);
*************** create_index_paths(PlannerInfo *root, Re
*** 200,206 ****
*/
indexpaths = find_usable_indexes(root, rel,
rel->baserestrictinfo, NIL,
! true, NULL, SAOP_PER_AM, ST_ANYSCAN);
/*
* Submit all the ones that can form plain IndexScan plans to add_path.
--- 207,215 ----
*/
indexpaths = find_usable_indexes(root, rel,
rel->baserestrictinfo, NIL,
! true,
! NULL, 1.0,
! SAOP_PER_AM, ST_ANYSCAN);
/*
* Submit all the ones that can form plain IndexScan plans to add_path.
*************** create_index_paths(PlannerInfo *root, Re
*** 233,239 ****
*/
indexpaths = generate_bitmap_or_paths(root, rel,
rel->baserestrictinfo, NIL,
! NULL);
bitindexpaths = list_concat(bitindexpaths, indexpaths);
/*
--- 242,248 ----
*/
indexpaths = generate_bitmap_or_paths(root, rel,
rel->baserestrictinfo, NIL,
! NULL, 1.0);
bitindexpaths = list_concat(bitindexpaths, indexpaths);
/*
*************** create_index_paths(PlannerInfo *root, Re
*** 243,249 ****
*/
indexpaths = find_saop_paths(root, rel,
rel->baserestrictinfo, NIL,
! true, NULL);
bitindexpaths = list_concat(bitindexpaths, indexpaths);
/*
--- 252,259 ----
*/
indexpaths = find_saop_paths(root, rel,
rel->baserestrictinfo, NIL,
! true,
! NULL, 1.0);
bitindexpaths = list_concat(bitindexpaths, indexpaths);
/*
*************** create_index_paths(PlannerInfo *root, Re
*** 255,264 ****
Path *bitmapqual;
BitmapHeapPath *bpath;
! bitmapqual = choose_bitmap_and(root, rel, bitindexpaths, NULL);
! bpath = create_bitmap_heap_path(root, rel, bitmapqual, NULL);
add_path(rel, (Path *) bpath);
}
}
--- 265,333 ----
Path *bitmapqual;
BitmapHeapPath *bpath;
! bitmapqual = choose_bitmap_and(root, rel, bitindexpaths, NULL, 1.0);
! bpath = create_bitmap_heap_path(root, rel, bitmapqual, NULL, 1.0);
add_path(rel, (Path *) bpath);
}
+
+ /*
+ * Now consider parameterized indexscans (those using join clauses).
+ *
+ * No need to do anything if there are no potentially useful joinclauses.
+ */
+ if (bms_is_empty(rel->index_outer_relids))
+ return;
+
+ /*
+ * The hard part here is to determine which sets of available join
+ * clauses to use, especially in the presence of ECs that can generate
+ * multiple redundant clauses. For the moment we consider two cases:
+ *
+ * 1) indexscans with a single other baserel as the source of parameters
+ *
+ * 2) indexscans with all potentially useful other baserels as the
+ * source of parameters.
+ *
+ * This must get improved soon --- in particular, case (2) can easily
+ * generate redundant, poorly-costed plans when there are ECs relating
+ * this rel to two or more others.
+ */
+ min_rowcount = -1;
+ for (rti = 1; rti < root->simple_rel_array_size; rti++)
+ {
+ RelOptInfo *outer_rel = root->simple_rel_array[rti];
+
+ /* there may be empty slots corresponding to non-baserel RTEs */
+ if (outer_rel == NULL)
+ continue;
+
+ Assert(outer_rel->relid == rti); /* sanity check on array */
+
+ /* ignore RTEs that are "other rels" */
+ if (outer_rel->reloptkind != RELOPT_BASEREL)
+ continue;
+
+ /* can't join to self, of course */
+ if (outer_rel == rel)
+ continue;
+ Assert(outer_rel->relid != rel->relid);
+
+ /* ignore if no potentially useful join clauses */
+ if (!bms_overlap(rel->index_outer_relids, outer_rel->relids))
+ continue;
+
+ /* try to build index paths joining to just this rel */
+ find_parameterized_indexscans(root, rel,
+ outer_rel->relids, outer_rel->rows);
+
+ /* remember smallest row count estimate among these rels */
+ if (min_rowcount < 0 || min_rowcount > outer_rel->rows)
+ min_rowcount = outer_rel->rows;
+ }
+
+ /* try to build index paths joining to all other useful rels */
+ find_parameterized_indexscans(root, rel,
+ rel->index_outer_relids, min_rowcount);
}
*************** create_index_paths(PlannerInfo *root, Re
*** 291,311 ****
* 'outer_clauses' is the list of additional upper-level clauses
* 'istoplevel' is true if clauses are the rel's top-level restriction list
* (outer_clauses must be NIL when this is true)
! * 'outer_rel' is the outer side of the join if forming an inner indexscan
! * (so some of the given clauses are join clauses); NULL if not
* 'saop_control' indicates whether ScalarArrayOpExpr clauses can be used
* 'scantype' indicates whether we need plain or bitmap scan support
*
! * Note: check_partial_indexes() must have been run previously.
*----------
*/
static List *
find_usable_indexes(PlannerInfo *root, RelOptInfo *rel,
List *clauses, List *outer_clauses,
! bool istoplevel, RelOptInfo *outer_rel,
SaOpControl saop_control, ScanTypeControl scantype)
{
- Relids outer_relids = outer_rel ? outer_rel->relids : NULL;
bool possibly_useful_pathkeys = has_useful_pathkeys(root, rel);
List *result = NIL;
List *all_clauses = NIL; /* not computed till needed */
--- 360,381 ----
* 'outer_clauses' is the list of additional upper-level clauses
* 'istoplevel' is true if clauses are the rel's top-level restriction list
* (outer_clauses must be NIL when this is true)
! * 'outer_relids' lists rels whose Vars can be used as parameters
! * 'outer_rows' is the number of loop repetitions to expect
* 'saop_control' indicates whether ScalarArrayOpExpr clauses can be used
* 'scantype' indicates whether we need plain or bitmap scan support
*
! * Note: outer_clauses and outer_relids/outer_rows refer to two different
! * concepts of "outer". Should probably rename...
*----------
*/
static List *
find_usable_indexes(PlannerInfo *root, RelOptInfo *rel,
List *clauses, List *outer_clauses,
! bool istoplevel,
! Relids outer_relids, double outer_rows,
SaOpControl saop_control, ScanTypeControl scantype)
{
bool possibly_useful_pathkeys = has_useful_pathkeys(root, rel);
List *result = NIL;
List *all_clauses = NIL; /* not computed till needed */
*************** find_usable_indexes(PlannerInfo *root, R
*** 426,432 ****
*/
index_is_ordered = (index->sortopfamily != NULL);
if (index_is_ordered && possibly_useful_pathkeys &&
! istoplevel && outer_rel == NULL)
{
index_pathkeys = build_index_pathkeys(root, index,
ForwardScanDirection);
--- 496,502 ----
*/
index_is_ordered = (index->sortopfamily != NULL);
if (index_is_ordered && possibly_useful_pathkeys &&
! istoplevel && outer_relids == NULL)
{
index_pathkeys = build_index_pathkeys(root, index,
ForwardScanDirection);
*************** find_usable_indexes(PlannerInfo *root, R
*** 436,442 ****
orderbyclausecols = NIL;
}
else if (index->amcanorderbyop && possibly_useful_pathkeys &&
! istoplevel && outer_rel == NULL && scantype != ST_BITMAPSCAN)
{
/* see if we can generate ordering operators for query_pathkeys */
match_pathkeys_to_index(index, root->query_pathkeys,
--- 506,513 ----
orderbyclausecols = NIL;
}
else if (index->amcanorderbyop && possibly_useful_pathkeys &&
! istoplevel && outer_relids == NULL &&
! scantype != ST_BITMAPSCAN)
{
/* see if we can generate ordering operators for query_pathkeys */
match_pathkeys_to_index(index, root->query_pathkeys,
*************** find_usable_indexes(PlannerInfo *root, R
*** 479,485 ****
ForwardScanDirection :
NoMovementScanDirection,
index_only_scan,
! outer_rel);
result = lappend(result, ipath);
}
--- 550,557 ----
ForwardScanDirection :
NoMovementScanDirection,
index_only_scan,
! outer_relids,
! outer_rows);
result = lappend(result, ipath);
}
*************** find_usable_indexes(PlannerInfo *root, R
*** 488,494 ****
* Again, this is only interesting at top level.
*/
if (index_is_ordered && possibly_useful_pathkeys &&
! istoplevel && outer_rel == NULL)
{
index_pathkeys = build_index_pathkeys(root, index,
BackwardScanDirection);
--- 560,566 ----
* Again, this is only interesting at top level.
*/
if (index_is_ordered && possibly_useful_pathkeys &&
! istoplevel && outer_relids == NULL)
{
index_pathkeys = build_index_pathkeys(root, index,
BackwardScanDirection);
*************** find_usable_indexes(PlannerInfo *root, R
*** 504,510 ****
useful_pathkeys,
BackwardScanDirection,
index_only_scan,
! outer_rel);
result = lappend(result, ipath);
}
}
--- 576,583 ----
useful_pathkeys,
BackwardScanDirection,
index_only_scan,
! outer_relids,
! outer_rows);
result = lappend(result, ipath);
}
}
*************** find_usable_indexes(PlannerInfo *root, R
*** 525,531 ****
static List *
find_saop_paths(PlannerInfo *root, RelOptInfo *rel,
List *clauses, List *outer_clauses,
! bool istoplevel, RelOptInfo *outer_rel)
{
bool have_saop = false;
ListCell *l;
--- 598,605 ----
static List *
find_saop_paths(PlannerInfo *root, RelOptInfo *rel,
List *clauses, List *outer_clauses,
! bool istoplevel,
! Relids outer_relids, double outer_rows)
{
bool have_saop = false;
ListCell *l;
*************** find_saop_paths(PlannerInfo *root, RelOp
*** 550,556 ****
return find_usable_indexes(root, rel,
clauses, outer_clauses,
! istoplevel, outer_rel,
SAOP_REQUIRE, ST_BITMAPSCAN);
}
--- 624,630 ----
return find_usable_indexes(root, rel,
clauses, outer_clauses,
! istoplevel, outer_relids, outer_rows,
SAOP_REQUIRE, ST_BITMAPSCAN);
}
*************** find_saop_paths(PlannerInfo *root, RelOp
*** 563,575 ****
*
* outer_clauses is a list of additional clauses that can be assumed true
* for the purpose of generating indexquals, but are not to be searched for
! * ORs. (See find_usable_indexes() for motivation.) outer_rel is the outer
! * side when we are considering a nestloop inner indexpath.
*/
List *
generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
List *clauses, List *outer_clauses,
! RelOptInfo *outer_rel)
{
List *result = NIL;
List *all_clauses;
--- 637,650 ----
*
* outer_clauses is a list of additional clauses that can be assumed true
* for the purpose of generating indexquals, but are not to be searched for
! * ORs. (See find_usable_indexes() for motivation.) outer_relids is the set
! * of relids on the outer side when we are considering a parameterized path,
! * and outer_rows is the loop count to expect.
*/
List *
generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
List *clauses, List *outer_clauses,
! Relids outer_relids, double outer_rows)
{
List *result = NIL;
List *all_clauses;
*************** generate_bitmap_or_paths(PlannerInfo *ro
*** 612,618 ****
andargs,
all_clauses,
false,
! outer_rel,
SAOP_ALLOW,
ST_BITMAPSCAN);
/* Recurse in case there are sub-ORs */
--- 687,694 ----
andargs,
all_clauses,
false,
! outer_relids,
! outer_rows,
SAOP_ALLOW,
ST_BITMAPSCAN);
/* Recurse in case there are sub-ORs */
*************** generate_bitmap_or_paths(PlannerInfo *ro
*** 620,626 ****
generate_bitmap_or_paths(root, rel,
andargs,
all_clauses,
! outer_rel));
}
else
{
--- 696,703 ----
generate_bitmap_or_paths(root, rel,
andargs,
all_clauses,
! outer_relids,
! outer_rows));
}
else
{
*************** generate_bitmap_or_paths(PlannerInfo *ro
*** 630,636 ****
list_make1(orarg),
all_clauses,
false,
! outer_rel,
SAOP_ALLOW,
ST_BITMAPSCAN);
}
--- 707,714 ----
list_make1(orarg),
all_clauses,
false,
! outer_relids,
! outer_rows,
SAOP_ALLOW,
ST_BITMAPSCAN);
}
*************** generate_bitmap_or_paths(PlannerInfo *ro
*** 649,655 ****
* OK, pick the most promising AND combination, and add it to
* pathlist.
*/
! bitmapqual = choose_bitmap_and(root, rel, indlist, outer_rel);
pathlist = lappend(pathlist, bitmapqual);
}
--- 727,734 ----
* OK, pick the most promising AND combination, and add it to
* pathlist.
*/
! bitmapqual = choose_bitmap_and(root, rel, indlist,
! outer_relids, outer_rows);
pathlist = lappend(pathlist, bitmapqual);
}
*************** generate_bitmap_or_paths(PlannerInfo *ro
*** 681,687 ****
*/
static Path *
choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel,
! List *paths, RelOptInfo *outer_rel)
{
int npaths = list_length(paths);
PathClauseUsage **pathinfoarray;
--- 760,767 ----
*/
static Path *
choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel,
! List *paths,
! Relids outer_relids, double outer_rows)
{
int npaths = list_length(paths);
PathClauseUsage **pathinfoarray;
*************** choose_bitmap_and(PlannerInfo *root, Rel
*** 729,735 ****
* reduces the total cost. Perhaps someday that code will be smarter and
* we can remove this limitation. (But note that this also defends
* against flat-out duplicate input paths, which can happen because
! * best_inner_indexscan will find the same OR join clauses that
* create_or_index_quals has pulled OR restriction clauses out of.)
*
* For the same reason, we reject AND combinations in which an index
--- 809,815 ----
* reduces the total cost. Perhaps someday that code will be smarter and
* we can remove this limitation. (But note that this also defends
* against flat-out duplicate input paths, which can happen because
! * find_parameterized_indexscans will find the same OR join clauses that
* create_or_index_quals has pulled OR restriction clauses out of.)
*
* For the same reason, we reject AND combinations in which an index
*************** choose_bitmap_and(PlannerInfo *root, Rel
*** 807,813 ****
pathinfo = pathinfoarray[i];
paths = list_make1(pathinfo->path);
! costsofar = bitmap_scan_cost_est(root, rel, pathinfo->path, outer_rel);
qualsofar = list_concat(list_copy(pathinfo->quals),
list_copy(pathinfo->preds));
clauseidsofar = bms_copy(pathinfo->clauseids);
--- 887,894 ----
pathinfo = pathinfoarray[i];
paths = list_make1(pathinfo->path);
! costsofar = bitmap_scan_cost_est(root, rel, pathinfo->path,
! outer_relids, outer_rows);
qualsofar = list_concat(list_copy(pathinfo->quals),
list_copy(pathinfo->preds));
clauseidsofar = bms_copy(pathinfo->clauseids);
*************** choose_bitmap_and(PlannerInfo *root, Rel
*** 841,847 ****
}
/* tentatively add new path to paths, so we can estimate cost */
paths = lappend(paths, pathinfo->path);
! newcost = bitmap_and_cost_est(root, rel, paths, outer_rel);
if (newcost < costsofar)
{
/* keep new path in paths, update subsidiary variables */
--- 922,929 ----
}
/* tentatively add new path to paths, so we can estimate cost */
paths = lappend(paths, pathinfo->path);
! newcost = bitmap_and_cost_est(root, rel, paths,
! outer_relids, outer_rows);
if (newcost < costsofar)
{
/* keep new path in paths, update subsidiary variables */
*************** path_usage_comparator(const void *a, con
*** 914,926 ****
*/
static Cost
bitmap_scan_cost_est(PlannerInfo *root, RelOptInfo *rel,
! Path *ipath, RelOptInfo *outer_rel)
{
! Path bpath;
! cost_bitmap_heap_scan(&bpath, root, rel, ipath, outer_rel);
! return bpath.total_cost;
}
/*
--- 996,1018 ----
*/
static Cost
bitmap_scan_cost_est(PlannerInfo *root, RelOptInfo *rel,
! Path *ipath,
! Relids outer_relids, double outer_rows)
{
! BitmapHeapPath bpath;
! /* Set up a dummy BitmapHeapPath */
! bpath.path.type = T_BitmapHeapPath;
! bpath.path.pathtype = T_BitmapHeapScan;
! bpath.path.parent = rel;
! bpath.path.required_outer = outer_relids;
! bpath.path.param_clauses = NIL; /* not needed for cost estimate */
! bpath.path.pathkeys = NIL;
! bpath.bitmapqual = ipath;
! cost_bitmap_heap_scan((Path *) &bpath, root, rel, ipath, outer_rows);
!
! return bpath.path.total_cost;
}
/*
*************** bitmap_scan_cost_est(PlannerInfo *root,
*** 929,949 ****
*/
static Cost
bitmap_and_cost_est(PlannerInfo *root, RelOptInfo *rel,
! List *paths, RelOptInfo *outer_rel)
{
BitmapAndPath apath;
! Path bpath;
/* Set up a dummy BitmapAndPath */
apath.path.type = T_BitmapAndPath;
apath.path.parent = rel;
apath.bitmapquals = paths;
cost_bitmap_and_node(&apath, root);
/* Now we can do cost_bitmap_heap_scan */
! cost_bitmap_heap_scan(&bpath, root, rel, (Path *) &apath, outer_rel);
! return bpath.total_cost;
}
--- 1021,1056 ----
*/
static Cost
bitmap_and_cost_est(PlannerInfo *root, RelOptInfo *rel,
! List *paths,
! Relids outer_relids, double outer_rows)
{
BitmapAndPath apath;
! BitmapHeapPath bpath;
/* Set up a dummy BitmapAndPath */
apath.path.type = T_BitmapAndPath;
+ apath.path.pathtype = T_BitmapAnd;
apath.path.parent = rel;
+ apath.path.required_outer = outer_relids;
+ apath.path.param_clauses = NIL; /* not needed for cost estimate */
+ apath.path.pathkeys = NIL;
apath.bitmapquals = paths;
+
cost_bitmap_and_node(&apath, root);
+ /* Set up a dummy BitmapHeapPath */
+ bpath.path.type = T_BitmapHeapPath;
+ bpath.path.pathtype = T_BitmapHeapScan;
+ bpath.path.parent = rel;
+ bpath.path.required_outer = outer_relids;
+ bpath.path.param_clauses = NIL; /* not needed for cost estimate */
+ bpath.path.pathkeys = NIL;
+ bpath.bitmapqual = (Path *) &apath;
+
/* Now we can do cost_bitmap_heap_scan */
! cost_bitmap_heap_scan((Path *) &bpath, root, rel, (Path *) &apath, outer_rows);
! return bpath.path.total_cost;
}
*************** match_clauses_to_index(IndexOptInfo *ind
*** 1285,1291 ****
* to the caller-specified outer_relids relations (which had better not
* include the relation whose index is being tested). outer_relids should
* be NULL when checking simple restriction clauses, and the outer side
! * of the join when building a join inner scan. Other than that, the
* only thing we don't like is volatile functions.
*
* Note: in most cases we already know that the clause as a whole uses
--- 1392,1398 ----
* to the caller-specified outer_relids relations (which had better not
* include the relation whose index is being tested). outer_relids should
* be NULL when checking simple restriction clauses, and the outer side
! * of the join when building a parameterized path. Other than that, the
* only thing we don't like is volatile functions.
*
* Note: in most cases we already know that the clause as a whole uses
*************** eclass_matches_any_index(EquivalenceClas
*** 2013,2121 ****
/*
! * best_inner_indexscan
! * Finds the best available inner indexscans for a nestloop join
! * with the given rel on the inside and the given outer_rel outside.
! *
! * *cheapest_startup gets the path with least startup cost
! * *cheapest_total gets the path with least total cost (often the same path)
! * Both are set to NULL if there are no possible inner indexscans.
! *
! * We ignore ordering considerations, since a nestloop's inner scan's order
! * is uninteresting. Hence startup cost and total cost are the only figures
! * of merit to consider.
*
! * Note: create_index_paths() must have been run previously for this rel,
! * else the results will always be NULL.
*/
! void
! best_inner_indexscan(PlannerInfo *root, RelOptInfo *rel,
! RelOptInfo *outer_rel, JoinType jointype,
! Path **cheapest_startup, Path **cheapest_total)
{
- Relids outer_relids;
- bool isouterjoin;
List *clause_list;
- List *indexpaths;
List *bitindexpaths;
List *allindexpaths;
ListCell *l;
- InnerIndexscanInfo *info;
- MemoryContext oldcontext;
-
- /* Initialize results for failure returns */
- *cheapest_startup = *cheapest_total = NULL;
-
- /*
- * Nestloop only supports inner, left, semi, and anti joins.
- */
- switch (jointype)
- {
- case JOIN_INNER:
- case JOIN_SEMI:
- isouterjoin = false;
- break;
- case JOIN_LEFT:
- case JOIN_ANTI:
- isouterjoin = true;
- break;
- default:
- return;
- }
-
- /*
- * If there are no indexable joinclauses for this rel, exit quickly.
- */
- if (bms_is_empty(rel->index_outer_relids))
- return;
-
- /*
- * Otherwise, we have to do path selection in the main planning context,
- * so that any created path can be safely attached to the rel's cache of
- * best inner paths. (This is not currently an issue for normal planning,
- * but it is an issue for GEQO planning.)
- */
- oldcontext = MemoryContextSwitchTo(root->planner_cxt);
-
- /*
- * Intersect the given outer relids with index_outer_relids to find the
- * set of outer relids actually relevant for this rel. If there are none,
- * again we can fail immediately.
- */
- outer_relids = bms_intersect(rel->index_outer_relids, outer_rel->relids);
- if (bms_is_empty(outer_relids))
- {
- bms_free(outer_relids);
- MemoryContextSwitchTo(oldcontext);
- return;
- }
-
- /*
- * Look to see if we already computed the result for this set of relevant
- * outerrels. (We include the isouterjoin status in the cache lookup key
- * for safety. In practice I suspect this is not necessary because it
- * should always be the same for a given combination of rels.)
- *
- * NOTE: because we cache on outer_relids rather than outer_rel->relids,
- * we will report the same paths and hence path cost for joins with
- * different sets of irrelevant rels on the outside. Now that cost_index
- * is sensitive to outer_rel->rows, this is not really right. However the
- * error is probably not large. Is it worth establishing a separate cache
- * entry for each distinct outer_rel->relids set to get this right?
- */
- foreach(l, rel->index_inner_paths)
- {
- info = (InnerIndexscanInfo *) lfirst(l);
- if (bms_equal(info->other_relids, outer_relids) &&
- info->isouterjoin == isouterjoin)
- {
- bms_free(outer_relids);
- MemoryContextSwitchTo(oldcontext);
- *cheapest_startup = info->cheapest_startup_innerpath;
- *cheapest_total = info->cheapest_total_innerpath;
- return;
- }
- }
/*
* Find all the relevant restriction and join clauses.
--- 2120,2140 ----
/*
! * find_parameterized_indexscans
! * Create paths for parameterized indexscans of the given rel
! * with the given outer_relids on the outside of the nestloop,
! * using outer_rows as the loop count for cost estimates.
*
! * The paths are added to the rel's pathlist via add_path().
*/
! static void
! find_parameterized_indexscans(PlannerInfo *root, RelOptInfo *rel,
! Relids outer_relids, double outer_rows)
{
List *clause_list;
List *bitindexpaths;
List *allindexpaths;
ListCell *l;
/*
* Find all the relevant restriction and join clauses.
*************** best_inner_indexscan(PlannerInfo *root,
*** 2124,2134 ****
* that could be plain indexscans, ie, they don't require the join context
* at all. This may seem redundant, but we need to include those scans in
* the input given to choose_bitmap_and() to be sure we find optimal AND
! * combinations of join and non-join scans. Also, even if the "best inner
! * indexscan" is just a plain indexscan, it will have a different cost
! * estimate because of cache effects.
*/
! clause_list = find_clauses_for_join(root, rel, outer_relids, isouterjoin);
/*
* Find all the index paths that are usable for this join, except for
--- 2143,2151 ----
* that could be plain indexscans, ie, they don't require the join context
* at all. This may seem redundant, but we need to include those scans in
* the input given to choose_bitmap_and() to be sure we find optimal AND
! * combinations of join and non-join scans.
*/
! clause_list = find_clauses_for_join(root, rel, outer_relids);
/*
* Find all the index paths that are usable for this join, except for
*************** best_inner_indexscan(PlannerInfo *root,
*** 2136,2156 ****
*/
allindexpaths = find_usable_indexes(root, rel,
clause_list, NIL,
! false, outer_rel,
SAOP_PER_AM,
ST_ANYSCAN);
/*
! * Include the ones that are usable as plain indexscans in indexpaths, and
! * include the ones that are usable as bitmap scans in bitindexpaths.
*/
! indexpaths = bitindexpaths = NIL;
foreach(l, allindexpaths)
{
IndexPath *ipath = (IndexPath *) lfirst(l);
if (ipath->indexinfo->amhasgettuple)
! indexpaths = lappend(indexpaths, ipath);
if (ipath->indexinfo->amhasgetbitmap)
bitindexpaths = lappend(bitindexpaths, ipath);
--- 2153,2174 ----
*/
allindexpaths = find_usable_indexes(root, rel,
clause_list, NIL,
! false,
! outer_relids, outer_rows,
SAOP_PER_AM,
ST_ANYSCAN);
/*
! * Send the ones that are usable as plain indexscans to add_path(), and
! * remember the ones that are usable as bitmap scans in bitindexpaths.
*/
! bitindexpaths = NIL;
foreach(l, allindexpaths)
{
IndexPath *ipath = (IndexPath *) lfirst(l);
if (ipath->indexinfo->amhasgettuple)
! add_path(rel, (Path *) ipath);
if (ipath->indexinfo->amhasgetbitmap)
bitindexpaths = lappend(bitindexpaths, ipath);
*************** best_inner_indexscan(PlannerInfo *root,
*** 2163,2169 ****
bitindexpaths = list_concat(bitindexpaths,
generate_bitmap_or_paths(root, rel,
clause_list, NIL,
! outer_rel));
/*
* Likewise, generate paths using executor-managed ScalarArrayOpExpr
--- 2181,2188 ----
bitindexpaths = list_concat(bitindexpaths,
generate_bitmap_or_paths(root, rel,
clause_list, NIL,
! outer_relids,
! outer_rows));
/*
* Likewise, generate paths using executor-managed ScalarArrayOpExpr
*************** best_inner_indexscan(PlannerInfo *root,
*** 2173,2179 ****
bitindexpaths = list_concat(bitindexpaths,
find_saop_paths(root, rel,
clause_list, NIL,
! false, outer_rel));
/*
* If we found anything usable, generate a BitmapHeapPath for the most
--- 2192,2199 ----
bitindexpaths = list_concat(bitindexpaths,
find_saop_paths(root, rel,
clause_list, NIL,
! false,
! outer_relids, outer_rows));
/*
* If we found anything usable, generate a BitmapHeapPath for the most
*************** best_inner_indexscan(PlannerInfo *root,
*** 2184,2221 ****
Path *bitmapqual;
BitmapHeapPath *bpath;
! bitmapqual = choose_bitmap_and(root, rel, bitindexpaths, outer_rel);
! bpath = create_bitmap_heap_path(root, rel, bitmapqual, outer_rel);
! indexpaths = lappend(indexpaths, bpath);
! }
!
! /*
! * Now choose the cheapest members of indexpaths.
! */
! if (indexpaths != NIL)
! {
! *cheapest_startup = *cheapest_total = (Path *) linitial(indexpaths);
!
! for_each_cell(l, lnext(list_head(indexpaths)))
! {
! Path *path = (Path *) lfirst(l);
!
! if (compare_path_costs(path, *cheapest_startup, STARTUP_COST) < 0)
! *cheapest_startup = path;
! if (compare_path_costs(path, *cheapest_total, TOTAL_COST) < 0)
! *cheapest_total = path;
! }
}
-
- /* Cache the results --- whether positive or negative */
- info = makeNode(InnerIndexscanInfo);
- info->other_relids = outer_relids;
- info->isouterjoin = isouterjoin;
- info->cheapest_startup_innerpath = *cheapest_startup;
- info->cheapest_total_innerpath = *cheapest_total;
- rel->index_inner_paths = lcons(info, rel->index_inner_paths);
-
- MemoryContextSwitchTo(oldcontext);
}
/*
--- 2204,2215 ----
Path *bitmapqual;
BitmapHeapPath *bpath;
! bitmapqual = choose_bitmap_and(root, rel, bitindexpaths,
! outer_relids, outer_rows);
! bpath = create_bitmap_heap_path(root, rel, bitmapqual,
! outer_relids, outer_rows);
! add_path(rel, (Path *) bpath);
}
}
/*
*************** best_inner_indexscan(PlannerInfo *root,
*** 2230,2236 ****
*/
static List *
find_clauses_for_join(PlannerInfo *root, RelOptInfo *rel,
! Relids outer_relids, bool isouterjoin)
{
List *clause_list = NIL;
Relids join_relids;
--- 2224,2230 ----
*/
static List *
find_clauses_for_join(PlannerInfo *root, RelOptInfo *rel,
! Relids outer_relids)
{
List *clause_list = NIL;
Relids join_relids;
*************** find_clauses_for_join(PlannerInfo *root,
*** 2248,2259 ****
{
RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
- /* Can't use pushed-down join clauses in outer join */
- if (isouterjoin && rinfo->is_pushed_down)
- continue;
if (!bms_is_subset(rinfo->required_relids, join_relids))
continue;
clause_list = lappend(clause_list, rinfo);
}
--- 2242,2264 ----
{
RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
if (!bms_is_subset(rinfo->required_relids, join_relids))
continue;
+ /*
+ * We must ignore clauses for which the target rel is in
+ * nullable_relids; that means there's an outer join below the clause
+ * and so it can't be enforced at the relation scan level.
+ *
+ * Note: unlike create_or_index_quals(), we can accept clauses that
+ * are marked !is_pushed_down (ie they are themselves outer-join
+ * clauses). This is OK because any path generated with these clauses
+ * could only be used in the inside of a nestloop join, which will be
+ * the nullable side.
+ */
+ if (bms_is_member(rel->relid, rinfo->nullable_relids))
+ continue;
+
clause_list = lappend(clause_list, rinfo);
}
*************** find_clauses_for_join(PlannerInfo *root,
*** 2261,2270 ****
/*
* Also check to see if any EquivalenceClasses can produce a relevant
! * joinclause. Since all such clauses are effectively pushed-down, this
! * doesn't apply to outer joins.
*/
! if (!isouterjoin && rel->has_eclass_joins)
clause_list = list_concat(clause_list,
find_eclass_clauses_for_index_join(root,
rel,
--- 2266,2274 ----
/*
* Also check to see if any EquivalenceClasses can produce a relevant
! * joinclause.
*/
! if (rel->has_eclass_joins)
clause_list = list_concat(clause_list,
find_eclass_clauses_for_index_join(root,
rel,
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 65caeb86c9bd419e3485bbe889f44e559235083a..0353d6e01df39240f055a612e458538af0654843 100644
*** a/src/backend/optimizer/path/joinpath.c
--- b/src/backend/optimizer/path/joinpath.c
*************** static void hash_inner_and_outer(Planner
*** 34,41 ****
RelOptInfo *outerrel, RelOptInfo *innerrel,
List *restrictlist,
JoinType jointype, SpecialJoinInfo *sjinfo);
- static Path *best_appendrel_indexscan(PlannerInfo *root, RelOptInfo *rel,
- RelOptInfo *outer_rel, JoinType jointype);
static List *select_mergejoin_clauses(PlannerInfo *root,
RelOptInfo *joinrel,
RelOptInfo *outerrel,
--- 34,39 ----
*************** match_unsorted_outer(PlannerInfo *root,
*** 367,375 ****
Path *inner_cheapest_startup = innerrel->cheapest_startup_path;
Path *inner_cheapest_total = innerrel->cheapest_total_path;
Path *matpath = NULL;
! Path *index_cheapest_startup = NULL;
! Path *index_cheapest_total = NULL;
! ListCell *l;
/*
* Nestloop only supports inner, left, semi, and anti joins. Also, if we
--- 365,371 ----
Path *inner_cheapest_startup = innerrel->cheapest_startup_path;
Path *inner_cheapest_total = innerrel->cheapest_total_path;
Path *matpath = NULL;
! ListCell *lc1;
/*
* Nestloop only supports inner, left, semi, and anti joins. Also, if we
*************** match_unsorted_outer(PlannerInfo *root,
*** 428,455 ****
!ExecMaterializesOutput(inner_cheapest_total->pathtype))
matpath = (Path *)
create_material_path(innerrel, inner_cheapest_total);
-
- /*
- * Get the best innerjoin indexpaths (if any) for this outer rel.
- * They're the same for all outer paths.
- */
- if (innerrel->reloptkind != RELOPT_JOINREL)
- {
- if (IsA(inner_cheapest_total, AppendPath))
- index_cheapest_total = best_appendrel_indexscan(root,
- innerrel,
- outerrel,
- jointype);
- else if (innerrel->rtekind == RTE_RELATION)
- best_inner_indexscan(root, innerrel, outerrel, jointype,
- &index_cheapest_startup,
- &index_cheapest_total);
- }
}
! foreach(l, outerrel->pathlist)
{
! Path *outerpath = (Path *) lfirst(l);
List *merge_pathkeys;
List *mergeclauses;
List *innersortkeys;
--- 424,434 ----
!ExecMaterializesOutput(inner_cheapest_total->pathtype))
matpath = (Path *)
create_material_path(innerrel, inner_cheapest_total);
}
! foreach(lc1, outerrel->pathlist)
{
! Path *outerpath = (Path *) lfirst(lc1);
List *merge_pathkeys;
List *mergeclauses;
List *innersortkeys;
*************** match_unsorted_outer(PlannerInfo *root,
*** 460,467 ****
int sortkeycnt;
/*
* If we need to unique-ify the outer path, it's pointless to consider
! * any but the cheapest outer.
*/
if (save_jointype == JOIN_UNIQUE_OUTER)
{
--- 439,452 ----
int sortkeycnt;
/*
+ * We cannot use an outer path that is parameterized by the inner rel.
+ */
+ if (bms_overlap(outerpath->required_outer, innerrel->relids))
+ continue;
+
+ /*
* If we need to unique-ify the outer path, it's pointless to consider
! * any but the cheapest outer. (XXX what about parameterized outers?)
*/
if (save_jointype == JOIN_UNIQUE_OUTER)
{
*************** match_unsorted_outer(PlannerInfo *root,
*** 480,493 ****
merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
outerpath->pathkeys);
! if (nestjoinOK)
{
/*
! * Always consider a nestloop join with this outer and
! * cheapest-total-cost inner. When appropriate, also consider
! * using the materialized form of the cheapest inner, the
! * cheapest-startup-cost inner path, and the cheapest innerjoin
! * indexpaths.
*/
add_path(joinrel, (Path *)
create_nestloop_path(root,
--- 465,475 ----
merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
outerpath->pathkeys);
! if (save_jointype == JOIN_UNIQUE_INNER)
{
/*
! * Consider nestloop join, but only with the unique-ified cheapest
! * inner path
*/
add_path(joinrel, (Path *)
create_nestloop_path(root,
*************** match_unsorted_outer(PlannerInfo *root,
*** 498,503 ****
--- 480,516 ----
inner_cheapest_total,
restrictlist,
merge_pathkeys));
+ }
+ else if (nestjoinOK)
+ {
+ /*
+ * Consider nestloop joins using this outer path and various
+ * available paths for the inner relation. We always consider the
+ * cheapest-total-cost and cheapest-startup-cost inner paths, as
+ * well as parameterized inner paths (even if they are not
+ * parameterized by this particular outer rel).
+ */
+ ListCell *lc2;
+
+ foreach(lc2, innerrel->pathlist)
+ {
+ Path *innerpath = (Path *) lfirst(lc2);
+
+ if (innerpath == inner_cheapest_total ||
+ innerpath == inner_cheapest_startup ||
+ innerpath->required_outer)
+ add_path(joinrel, (Path *)
+ create_nestloop_path(root,
+ joinrel,
+ jointype,
+ sjinfo,
+ outerpath,
+ innerpath,
+ restrictlist,
+ merge_pathkeys));
+ }
+
+ /* Also consider materialized form of the cheapest inner path */
if (matpath != NULL)
add_path(joinrel, (Path *)
create_nestloop_path(root,
*************** match_unsorted_outer(PlannerInfo *root,
*** 508,544 ****
matpath,
restrictlist,
merge_pathkeys));
- if (inner_cheapest_startup != inner_cheapest_total)
- add_path(joinrel, (Path *)
- create_nestloop_path(root,
- joinrel,
- jointype,
- sjinfo,
- outerpath,
- inner_cheapest_startup,
- restrictlist,
- merge_pathkeys));
- if (index_cheapest_total != NULL)
- add_path(joinrel, (Path *)
- create_nestloop_path(root,
- joinrel,
- jointype,
- sjinfo,
- outerpath,
- index_cheapest_total,
- restrictlist,
- merge_pathkeys));
- if (index_cheapest_startup != NULL &&
- index_cheapest_startup != index_cheapest_total)
- add_path(joinrel, (Path *)
- create_nestloop_path(root,
- joinrel,
- jointype,
- sjinfo,
- outerpath,
- index_cheapest_startup,
- restrictlist,
- merge_pathkeys));
}
/* Can't do anything else if outer path needs to be unique'd */
--- 521,526 ----
*************** match_unsorted_outer(PlannerInfo *root,
*** 654,659 ****
--- 636,642 ----
trialsortkeys = list_truncate(trialsortkeys, sortkeycnt);
innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
trialsortkeys,
+ NULL,
TOTAL_COST);
if (innerpath != NULL &&
(cheapest_total_inner == NULL ||
*************** match_unsorted_outer(PlannerInfo *root,
*** 690,695 ****
--- 673,679 ----
/* Same on the basis of cheapest startup cost ... */
innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist,
trialsortkeys,
+ NULL,
STARTUP_COST);
if (innerpath != NULL &&
(cheapest_startup_inner == NULL ||
*************** hash_inner_and_outer(PlannerInfo *root,
*** 854,928 ****
}
/*
- * best_appendrel_indexscan
- * Finds the best available set of inner indexscans for a nestloop join
- * with the given append relation on the inside and the given outer_rel
- * outside. Returns an AppendPath comprising the best inner scans, or
- * NULL if there are no possible inner indexscans.
- *
- * Note that we currently consider only cheapest-total-cost. It's not
- * very clear what cheapest-startup-cost might mean for an AppendPath.
- */
- static Path *
- best_appendrel_indexscan(PlannerInfo *root, RelOptInfo *rel,
- RelOptInfo *outer_rel, JoinType jointype)
- {
- int parentRTindex = rel->relid;
- List *append_paths = NIL;
- bool found_indexscan = false;
- ListCell *l;
-
- foreach(l, root->append_rel_list)
- {
- AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);
- int childRTindex;
- RelOptInfo *childrel;
- Path *index_cheapest_startup;
- Path *index_cheapest_total;
-
- /* append_rel_list contains all append rels; ignore others */
- if (appinfo->parent_relid != parentRTindex)
- continue;
-
- childRTindex = appinfo->child_relid;
- childrel = find_base_rel(root, childRTindex);
- Assert(childrel->reloptkind == RELOPT_OTHER_MEMBER_REL);
-
- /*
- * Check to see if child was rejected by constraint exclusion. If so,
- * it will have a cheapest_total_path that's a "dummy" path.
- */
- if (IS_DUMMY_PATH(childrel->cheapest_total_path))
- continue; /* OK, we can ignore it */
-
- /*
- * Get the best innerjoin indexpaths (if any) for this child rel.
- */
- best_inner_indexscan(root, childrel, outer_rel, jointype,
- &index_cheapest_startup, &index_cheapest_total);
-
- /*
- * If no luck on an indexpath for this rel, we'll still consider an
- * Append substituting the cheapest-total inner path. However we must
- * find at least one indexpath, else there's not going to be any
- * improvement over the base path for the appendrel.
- */
- if (index_cheapest_total)
- found_indexscan = true;
- else
- index_cheapest_total = childrel->cheapest_total_path;
-
- append_paths = lappend(append_paths, index_cheapest_total);
- }
-
- if (!found_indexscan)
- return NULL;
-
- /* Form and return the completed Append path. */
- return (Path *) create_append_path(rel, append_paths);
- }
-
- /*
* select_mergejoin_clauses
* Select mergejoin clauses that are usable for a particular join.
* Returns a list of RestrictInfo nodes for those clauses.
--- 838,843 ----
diff --git a/src/backend/optimizer/path/orindxpath.c b/src/backend/optimizer/path/orindxpath.c
index d4cc567892da164fae658ef9baed253f7e2bf0bd..0b6c21dd9c2e7b0fc2a48487a033a5181b0bf85d 100644
*** a/src/backend/optimizer/path/orindxpath.c
--- b/src/backend/optimizer/path/orindxpath.c
*************** create_or_index_quals(PlannerInfo *root,
*** 123,129 ****
orpaths = generate_bitmap_or_paths(root, rel,
list_make1(rinfo),
rel->baserestrictinfo,
! NULL);
/* Locate the cheapest OR path */
foreach(k, orpaths)
--- 123,129 ----
orpaths = generate_bitmap_or_paths(root, rel,
list_make1(rinfo),
rel->baserestrictinfo,
! NULL, 1.0);
/* Locate the cheapest OR path */
foreach(k, orpaths)
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 0ebdead6c84d48baf8f8c0fc93f2775e56ec3a2a..44ac629a9cf4b95e5c5ca7c7ef7c7c350fc8cc53 100644
*** a/src/backend/optimizer/path/pathkeys.c
--- b/src/backend/optimizer/path/pathkeys.c
*************** pathkeys_contained_in(List *keys1, List
*** 403,416 ****
/*
* get_cheapest_path_for_pathkeys
* Find the cheapest path (according to the specified criterion) that
! * satisfies the given pathkeys. Return NULL if no such path.
*
* 'paths' is a list of possible paths that all generate the same relation
* 'pathkeys' represents a required ordering (already canonicalized!)
* 'cost_criterion' is STARTUP_COST or TOTAL_COST
*/
Path *
get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
CostSelector cost_criterion)
{
Path *matched_path = NULL;
--- 403,419 ----
/*
* get_cheapest_path_for_pathkeys
* Find the cheapest path (according to the specified criterion) that
! * satisfies the given pathkeys and parameterization.
! * Return NULL if no such path.
*
* 'paths' is a list of possible paths that all generate the same relation
* 'pathkeys' represents a required ordering (already canonicalized!)
+ * 'required_outer' denotes allowable outer relations for parameterized paths
* 'cost_criterion' is STARTUP_COST or TOTAL_COST
*/
Path *
get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
+ Relids required_outer,
CostSelector cost_criterion)
{
Path *matched_path = NULL;
*************** get_cheapest_path_for_pathkeys(List *pat
*** 428,434 ****
compare_path_costs(matched_path, path, cost_criterion) <= 0)
continue;
! if (pathkeys_contained_in(pathkeys, path->pathkeys))
matched_path = path;
}
return matched_path;
--- 431,438 ----
compare_path_costs(matched_path, path, cost_criterion) <= 0)
continue;
! if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
! bms_is_subset(path->required_outer, required_outer))
matched_path = path;
}
return matched_path;
*************** get_cheapest_fractional_path_for_pathkey
*** 459,464 ****
--- 463,472 ----
{
Path *path = (Path *) lfirst(l);
+ /* XXX for now, consider only unparameterized paths */
+ if (path->required_outer)
+ continue;
+
/*
* Since cost comparison is a lot cheaper than pathkey comparison, do
* that first.
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index e41d2a6eb99a48cf47e2f95e2c4863f58e9098c2..975147f2f820c10fa661261b59c8b67e617690df 100644
*** a/src/backend/optimizer/plan/createplan.c
--- b/src/backend/optimizer/plan/createplan.c
*************** create_unique_plan(PlannerInfo *root, Un
*** 932,938 ****
long numGroups;
Oid *groupOperators;
! numGroups = (long) Min(best_path->rows, (double) LONG_MAX);
/*
* Get the hashable equality operators for the Agg node to use.
--- 932,938 ----
long numGroups;
Oid *groupOperators;
! numGroups = (long) Min(best_path->path.rows, (double) LONG_MAX);
/*
* Get the hashable equality operators for the Agg node to use.
*************** create_unique_plan(PlannerInfo *root, Un
*** 1018,1024 ****
}
/* Adjust output size estimate (other fields should be OK already) */
! plan->plan_rows = best_path->rows;
return plan;
}
--- 1018,1024 ----
}
/* Adjust output size estimate (other fields should be OK already) */
! plan->plan_rows = best_path->path.rows;
return plan;
}
*************** create_indexscan_plan(PlannerInfo *root,
*** 1112,1118 ****
fixed_indexorderbys = fix_indexorderby_references(root, best_path);
/*
! * If this is an innerjoin scan, the indexclauses will contain join
* clauses that are not present in scan_clauses (since the passed-in value
* is just the rel's baserestrictinfo list). We must add these clauses to
* scan_clauses to ensure they get checked. In most cases we will remove
--- 1112,1118 ----
fixed_indexorderbys = fix_indexorderby_references(root, best_path);
/*
! * If this is a parameterized scan, the indexclauses will contain join
* clauses that are not present in scan_clauses (since the passed-in value
* is just the rel's baserestrictinfo list). We must add these clauses to
* scan_clauses to ensure they get checked. In most cases we will remove
*************** create_indexscan_plan(PlannerInfo *root,
*** 1122,1128 ****
* Note: pointer comparison should be enough to determine RestrictInfo
* matches.
*/
! if (best_path->isjoininner)
scan_clauses = list_union_ptr(scan_clauses, best_path->indexclauses);
/*
--- 1122,1128 ----
* Note: pointer comparison should be enough to determine RestrictInfo
* matches.
*/
! if (best_path->path.required_outer)
scan_clauses = list_union_ptr(scan_clauses, best_path->indexclauses);
/*
*************** create_indexscan_plan(PlannerInfo *root,
*** 1189,1195 ****
* it'd break the comparisons to predicates above ... (or would it? Those
* wouldn't have outer refs)
*/
! if (best_path->isjoininner)
{
stripped_indexquals = (List *)
replace_nestloop_params(root, (Node *) stripped_indexquals);
--- 1189,1195 ----
* it'd break the comparisons to predicates above ... (or would it? Those
* wouldn't have outer refs)
*/
! if (best_path->path.required_outer)
{
stripped_indexquals = (List *)
replace_nestloop_params(root, (Node *) stripped_indexquals);
*************** create_indexscan_plan(PlannerInfo *root,
*** 1221,1228 ****
best_path->indexscandir);
copy_path_costsize(&scan_plan->plan, &best_path->path);
- /* use the indexscan-specific rows estimate, not the parent rel's */
- scan_plan->plan.plan_rows = best_path->rows;
return scan_plan;
}
--- 1221,1226 ----
*************** create_bitmap_scan_plan(PlannerInfo *roo
*** 1258,1271 ****
scan_clauses = extract_actual_clauses(scan_clauses, false);
/*
! * If this is a innerjoin scan, the indexclauses will contain join clauses
* that are not present in scan_clauses (since the passed-in value is just
* the rel's baserestrictinfo list). We must add these clauses to
* scan_clauses to ensure they get checked. In most cases we will remove
* the join clauses again below, but if a join clause contains a special
* operator, we need to make sure it gets into the scan_clauses.
*/
! if (best_path->isjoininner)
{
scan_clauses = list_concat_unique(scan_clauses, bitmapqualorig);
}
--- 1256,1269 ----
scan_clauses = extract_actual_clauses(scan_clauses, false);
/*
! * If this is a parameterized scan, the indexclauses will contain join clauses
* that are not present in scan_clauses (since the passed-in value is just
* the rel's baserestrictinfo list). We must add these clauses to
* scan_clauses to ensure they get checked. In most cases we will remove
* the join clauses again below, but if a join clause contains a special
* operator, we need to make sure it gets into the scan_clauses.
*/
! if (best_path->path.required_outer)
{
scan_clauses = list_concat_unique(scan_clauses, bitmapqualorig);
}
*************** create_bitmap_scan_plan(PlannerInfo *roo
*** 1328,1335 ****
baserelid);
copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
- /* use the indexscan-specific rows estimate, not the parent rel's */
- scan_plan->scan.plan.plan_rows = best_path->rows;
return scan_plan;
}
--- 1326,1331 ----
*************** create_bitmap_subplan(PlannerInfo *root,
*** 1510,1516 ****
* Replace outer-relation variables with nestloop params, but only
* after doing the above comparisons to index predicates.
*/
! if (ipath->isjoininner)
{
*qual = (List *)
replace_nestloop_params(root, (Node *) *qual);
--- 1506,1512 ----
* Replace outer-relation variables with nestloop params, but only
* after doing the above comparisons to index predicates.
*/
! if (ipath->path.required_outer)
{
*qual = (List *)
replace_nestloop_params(root, (Node *) *qual);
*************** create_nestloop_plan(PlannerInfo *root,
*** 1883,1896 ****
ListCell *next;
/*
! * If the inner path is a nestloop inner indexscan, it might be using some
! * of the join quals as index quals, in which case we don't have to check
! * them again at the join node. Remove any join quals that are redundant.
*/
joinrestrictclauses =
! select_nonredundant_join_clauses(root,
! joinrestrictclauses,
! best_path->innerjoinpath);
/* Sort join qual clauses into best execution order */
joinrestrictclauses = order_qual_clauses(root, joinrestrictclauses);
--- 1879,1891 ----
ListCell *next;
/*
! * If the inner path is parameterized, it might have already used some of
! * the join quals, in which case we don't have to check them again at the
! * join node. Remove any join quals that are redundant.
*/
joinrestrictclauses =
! select_nonredundant_join_clauses(joinrestrictclauses,
! best_path->innerjoinpath->param_clauses);
/* Sort join qual clauses into best execution order */
joinrestrictclauses = order_qual_clauses(root, joinrestrictclauses);
*************** copy_path_costsize(Plan *dest, Path *src
*** 2885,2891 ****
{
dest->startup_cost = src->startup_cost;
dest->total_cost = src->total_cost;
! dest->plan_rows = src->parent->rows;
dest->plan_width = src->parent->width;
}
else
--- 2880,2886 ----
{
dest->startup_cost = src->startup_cost;
dest->total_cost = src->total_cost;
! dest->plan_rows = src->rows;
dest->plan_width = src->parent->width;
}
else
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index b66a508c22da934e96771c99a0a5010dc6c64177..921262948bb8cc5b42c32170c447a0d8008bea34 100644
*** a/src/backend/optimizer/plan/planner.c
--- b/src/backend/optimizer/plan/planner.c
*************** plan_cluster_use_sort(Oid tableOid, Oid
*** 3297,3303 ****
/* Estimate the cost of index scan */
indexScanPath = create_index_path(root, indexInfo,
NIL, NIL, NIL, NIL, NIL,
! ForwardScanDirection, false, NULL);
return (seqScanAndSortPath.total_cost < indexScanPath->path.total_cost);
}
--- 3297,3304 ----
/* Estimate the cost of index scan */
indexScanPath = create_index_path(root, indexInfo,
NIL, NIL, NIL, NIL, NIL,
! ForwardScanDirection, false,
! NULL, 1.0);
return (seqScanAndSortPath.total_cost < indexScanPath->path.total_cost);
}
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 0ca161a31dc99a3ee7384f47dde75e3fcd628cb5..ace8ca020b34b1b89a9af1542e34c272b4b3495f 100644
*** a/src/backend/optimizer/util/pathnode.c
--- b/src/backend/optimizer/util/pathnode.c
***************
*** 23,28 ****
--- 23,29 ----
#include "optimizer/cost.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
+ #include "optimizer/restrictinfo.h"
#include "optimizer/tlist.h"
#include "parser/parsetree.h"
#include "utils/lsyscache.h"
*************** compare_fractional_path_costs(Path *path
*** 166,171 ****
--- 167,174 ----
* Find the minimum-cost paths from among a relation's paths,
* and save them in the rel's cheapest-path fields.
*
+ * Only unparameterized paths are considered candidates.
+ *
* This is normally called only after we've finished constructing the path
* list for the rel node.
*
*************** compare_fractional_path_costs(Path *path
*** 177,199 ****
void
set_cheapest(RelOptInfo *parent_rel)
{
- List *pathlist = parent_rel->pathlist;
- ListCell *p;
Path *cheapest_startup_path;
Path *cheapest_total_path;
Assert(IsA(parent_rel, RelOptInfo));
! if (pathlist == NIL)
! elog(ERROR, "could not devise a query plan for the given query");
!
! cheapest_startup_path = cheapest_total_path = (Path *) linitial(pathlist);
! for_each_cell(p, lnext(list_head(pathlist)))
{
Path *path = (Path *) lfirst(p);
int cmp;
cmp = compare_path_costs(cheapest_startup_path, path, STARTUP_COST);
if (cmp > 0 ||
(cmp == 0 &&
--- 180,208 ----
void
set_cheapest(RelOptInfo *parent_rel)
{
Path *cheapest_startup_path;
Path *cheapest_total_path;
+ ListCell *p;
Assert(IsA(parent_rel, RelOptInfo));
! cheapest_startup_path = cheapest_total_path = NULL;
! foreach(p, parent_rel->pathlist)
{
Path *path = (Path *) lfirst(p);
int cmp;
+ /* We only consider unparameterized paths here */
+ if (path->required_outer)
+ continue;
+
+ if (cheapest_total_path == NULL)
+ {
+ cheapest_startup_path = cheapest_total_path = path;
+ continue;
+ }
+
cmp = compare_path_costs(cheapest_startup_path, path, STARTUP_COST);
if (cmp > 0 ||
(cmp == 0 &&
*************** set_cheapest(RelOptInfo *parent_rel)
*** 209,214 ****
--- 218,226 ----
cheapest_total_path = path;
}
+ if (cheapest_total_path == NULL)
+ elog(ERROR, "could not devise a query plan for the given query");
+
parent_rel->cheapest_startup_path = cheapest_startup_path;
parent_rel->cheapest_total_path = cheapest_total_path;
parent_rel->cheapest_unique_path = NULL; /* computed only if needed */
*************** set_cheapest(RelOptInfo *parent_rel)
*** 219,229 ****
* Consider a potential implementation path for the specified parent rel,
* and add it to the rel's pathlist if it is worthy of consideration.
* A path is worthy if it has either a better sort order (better pathkeys)
! * or cheaper cost (on either dimension) than any of the existing old paths.
*
* We also remove from the rel's pathlist any old paths that are dominated
! * by new_path --- that is, new_path is both cheaper and at least as well
! * ordered.
*
* The pathlist is kept sorted by TOTAL_COST metric, with cheaper paths
* at the front. No code depends on that for correctness; it's simply
--- 231,242 ----
* Consider a potential implementation path for the specified parent rel,
* and add it to the rel's pathlist if it is worthy of consideration.
* A path is worthy if it has either a better sort order (better pathkeys)
! * or cheaper cost (on either dimension) than any of the existing old paths
! * that have the same or subset required_outer rels.
*
* We also remove from the rel's pathlist any old paths that are dominated
! * by new_path --- that is, new_path is cheaper, at least as well ordered,
! * and requires no outer rels not required by old path.
*
* The pathlist is kept sorted by TOTAL_COST metric, with cheaper paths
* at the front. No code depends on that for correctness; it's simply
*************** add_path(RelOptInfo *parent_rel, Path *n
*** 287,334 ****
/*
* If the two paths compare differently for startup and total cost,
* then we want to keep both, and we can skip the (much slower)
! * comparison of pathkeys. If they compare the same, proceed with the
! * pathkeys comparison. Note: this test relies on the fact that
! * compare_fuzzy_path_costs will only return 0 if both costs are
! * effectively equal (and, therefore, there's no need to call it twice
! * in that case).
*/
if (costcmp == 0 ||
costcmp == compare_fuzzy_path_costs(new_path, old_path,
STARTUP_COST))
{
! switch (compare_pathkeys(new_path->pathkeys, old_path->pathkeys))
{
! case PATHKEYS_EQUAL:
! if (costcmp < 0)
! remove_old = true; /* new dominates old */
! else if (costcmp > 0)
! accept_new = false; /* old dominates new */
! else
! {
! /*
! * Same pathkeys, and fuzzily the same cost, so keep
! * just one --- but we'll do an exact cost comparison
! * to decide which.
! */
! if (compare_path_costs(new_path, old_path,
! TOTAL_COST) < 0)
! remove_old = true; /* new dominates old */
else
! accept_new = false; /* old equals or dominates new */
! }
! break;
! case PATHKEYS_BETTER1:
! if (costcmp <= 0)
! remove_old = true; /* new dominates old */
! break;
! case PATHKEYS_BETTER2:
! if (costcmp >= 0)
! accept_new = false; /* old dominates new */
! break;
! case PATHKEYS_DIFFERENT:
! /* keep both paths, since they have different ordering */
! break;
}
}
--- 300,369 ----
/*
* If the two paths compare differently for startup and total cost,
* then we want to keep both, and we can skip the (much slower)
! * comparisons of pathkeys and required_outer rels. If they compare
! * the same, proceed with the other comparisons. Note: this test
! * relies on the fact that compare_fuzzy_path_costs will only return 0
! * if both costs are effectively equal (and, therefore, there's no
! * need to call it twice in that case).
*/
if (costcmp == 0 ||
costcmp == compare_fuzzy_path_costs(new_path, old_path,
STARTUP_COST))
{
! BMS_Comparison outercmp;
!
! /*
! * Compare required outer rels. If neither set is a subset of the
! * other, neither path can dominate the other, so we keep both.
! */
! outercmp = bms_subset_compare(new_path->required_outer,
! old_path->required_outer);
! if (outercmp != BMS_DIFFERENT)
{
! switch (compare_pathkeys(new_path->pathkeys,
! old_path->pathkeys))
! {
! case PATHKEYS_EQUAL:
! if (costcmp < 0)
! {
! if (outercmp != BMS_SUBSET2)
! remove_old = true; /* new dominates old */
! }
! else if (costcmp > 0)
! {
! if (outercmp != BMS_SUBSET1)
! accept_new = false; /* old dominates new */
! }
! else if (outercmp == BMS_SUBSET1)
! remove_old = true; /* new dominates old */
! else if (outercmp == BMS_SUBSET2)
! accept_new = false; /* old dominates new */
else
! {
! /*
! * Same pathkeys and outer rels, and fuzzily the
! * same cost, so keep just one --- but we'll do an
! * exact cost comparison to decide which.
! */
! if (compare_path_costs(new_path, old_path,
! TOTAL_COST) < 0)
! remove_old = true; /* new dominates old */
! else
! accept_new = false; /* old equals or dominates new */
! }
! break;
! case PATHKEYS_BETTER1:
! if (costcmp <= 0 && outercmp != BMS_SUBSET2)
! remove_old = true; /* new dominates old */
! break;
! case PATHKEYS_BETTER2:
! if (costcmp >= 0 && outercmp != BMS_SUBSET1)
! accept_new = false; /* old dominates new */
! break;
! case PATHKEYS_DIFFERENT:
! /* keep both, since they have different ordering */
! break;
! }
}
}
*************** create_seqscan_path(PlannerInfo *root, R
*** 398,403 ****
--- 433,440 ----
pathnode->pathtype = T_SeqScan;
pathnode->parent = rel;
+ pathnode->required_outer = NULL;
+ pathnode->param_clauses = NIL;
pathnode->pathkeys = NIL; /* seqscan has unordered result */
cost_seqscan(pathnode, root, rel);
*************** create_seqscan_path(PlannerInfo *root, R
*** 423,430 ****
* for an ordered index, or NoMovementScanDirection for
* an unordered index.
* 'indexonly' is true if an index-only scan is wanted.
! * 'outer_rel' is the outer relation if this is a join inner indexscan path.
! * (pathkeys and indexscandir are ignored if so.) NULL if not.
*
* Returns the new path node.
*/
--- 460,468 ----
* for an ordered index, or NoMovementScanDirection for
* an unordered index.
* 'indexonly' is true if an index-only scan is wanted.
! * 'required_outer' is the set of outer relids referenced in indexclauses.
! * 'loop_count' is the number of repetitions of the indexscan to factor into
! * estimates of caching behavior.
*
* Returns the new path node.
*/
*************** create_index_path(PlannerInfo *root,
*** 438,465 ****
List *pathkeys,
ScanDirection indexscandir,
bool indexonly,
! RelOptInfo *outer_rel)
{
IndexPath *pathnode = makeNode(IndexPath);
RelOptInfo *rel = index->rel;
List *indexquals,
*indexqualcols;
- /*
- * For a join inner scan, there's no point in marking the path with any
- * pathkeys, since it will only ever be used as the inner path of a
- * nestloop, and so its ordering does not matter. For the same reason we
- * don't really care what order it's scanned in. (We could expect the
- * caller to supply the correct values, but it's easier to force it here.)
- */
- if (outer_rel != NULL)
- {
- pathkeys = NIL;
- indexscandir = NoMovementScanDirection;
- }
-
pathnode->path.pathtype = indexonly ? T_IndexOnlyScan : T_IndexScan;
pathnode->path.parent = rel;
pathnode->path.pathkeys = pathkeys;
/* Convert clauses to indexquals the executor can handle */
--- 476,509 ----
List *pathkeys,
ScanDirection indexscandir,
bool indexonly,
! Relids required_outer,
! double loop_count)
{
IndexPath *pathnode = makeNode(IndexPath);
RelOptInfo *rel = index->rel;
List *indexquals,
*indexqualcols;
pathnode->path.pathtype = indexonly ? T_IndexOnlyScan : T_IndexScan;
pathnode->path.parent = rel;
+ pathnode->path.required_outer = required_outer;
+ if (required_outer)
+ {
+ /* Identify index clauses that are join clauses */
+ List *jclauses = NIL;
+ ListCell *lc;
+
+ foreach(lc, indexclauses)
+ {
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
+
+ if (!bms_is_subset(rinfo->required_relids, rel->relids))
+ jclauses = lappend(jclauses, rinfo);
+ }
+ pathnode->path.param_clauses = jclauses;
+ }
+ else
+ pathnode->path.param_clauses = NIL;
pathnode->path.pathkeys = pathkeys;
/* Convert clauses to indexquals the executor can handle */
*************** create_index_path(PlannerInfo *root,
*** 473,522 ****
pathnode->indexqualcols = indexqualcols;
pathnode->indexorderbys = indexorderbys;
pathnode->indexorderbycols = indexorderbycols;
-
- pathnode->isjoininner = (outer_rel != NULL);
pathnode->indexscandir = indexscandir;
! if (outer_rel != NULL)
! {
! /*
! * We must compute the estimated number of output rows for the
! * indexscan. This is less than rel->rows because of the additional
! * selectivity of the join clauses. Since indexclauses may contain
! * both restriction and join clauses, we have to do a set union to get
! * the full set of clauses that must be considered to compute the
! * correct selectivity. (Without the union operation, we might have
! * some restriction clauses appearing twice, which'd mislead
! * clauselist_selectivity into double-counting their selectivity.
! * However, since RestrictInfo nodes aren't copied when linking them
! * into different lists, it should be sufficient to use pointer
! * comparison to remove duplicates.)
! *
! * Note that we force the clauses to be treated as non-join clauses
! * during selectivity estimation.
! */
! List *allclauses;
!
! allclauses = list_union_ptr(rel->baserestrictinfo, indexclauses);
! pathnode->rows = rel->tuples *
! clauselist_selectivity(root,
! allclauses,
! rel->relid, /* do not use 0! */
! JOIN_INNER,
! NULL);
! /* Like costsize.c, force estimate to be at least one row */
! pathnode->rows = clamp_row_est(pathnode->rows);
! }
! else
! {
! /*
! * The number of rows is the same as the parent rel's estimate, since
! * this isn't a join inner indexscan.
! */
! pathnode->rows = rel->rows;
! }
!
! cost_index(pathnode, root, outer_rel);
return pathnode;
}
--- 517,525 ----
pathnode->indexqualcols = indexqualcols;
pathnode->indexorderbys = indexorderbys;
pathnode->indexorderbycols = indexorderbycols;
pathnode->indexscandir = indexscandir;
! cost_index(pathnode, root, loop_count);
return pathnode;
}
*************** create_index_path(PlannerInfo *root,
*** 526,580 ****
* Creates a path node for a bitmap scan.
*
* 'bitmapqual' is a tree of IndexPath, BitmapAndPath, and BitmapOrPath nodes.
*
! * If this is a join inner indexscan path, 'outer_rel' is the outer relation,
! * and all the component IndexPaths should have been costed accordingly.
*/
BitmapHeapPath *
create_bitmap_heap_path(PlannerInfo *root,
RelOptInfo *rel,
Path *bitmapqual,
! RelOptInfo *outer_rel)
{
BitmapHeapPath *pathnode = makeNode(BitmapHeapPath);
pathnode->path.pathtype = T_BitmapHeapScan;
pathnode->path.parent = rel;
! pathnode->path.pathkeys = NIL; /* always unordered */
!
! pathnode->bitmapqual = bitmapqual;
! pathnode->isjoininner = (outer_rel != NULL);
!
! if (pathnode->isjoininner)
{
! /*
! * We must compute the estimated number of output rows for the
! * indexscan. This is less than rel->rows because of the additional
! * selectivity of the join clauses. We make use of the selectivity
! * estimated for the bitmap to do this; this isn't really quite right
! * since there may be restriction conditions not included in the
! * bitmap ...
! */
! Cost indexTotalCost;
! Selectivity indexSelectivity;
! cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity);
! pathnode->rows = rel->tuples * indexSelectivity;
! if (pathnode->rows > rel->rows)
! pathnode->rows = rel->rows;
! /* Like costsize.c, force estimate to be at least one row */
! pathnode->rows = clamp_row_est(pathnode->rows);
}
else
! {
! /*
! * The number of rows is the same as the parent rel's estimate, since
! * this isn't a join inner indexscan.
! */
! pathnode->rows = rel->rows;
! }
! cost_bitmap_heap_scan(&pathnode->path, root, rel, bitmapqual, outer_rel);
return pathnode;
}
--- 529,579 ----
* Creates a path node for a bitmap scan.
*
* 'bitmapqual' is a tree of IndexPath, BitmapAndPath, and BitmapOrPath nodes.
+ * 'required_outer' is the set of outer relids referenced in indexclauses.
+ * 'loop_count' is the number of repetitions of the indexscan to factor into
+ * estimates of caching behavior.
*
! * required_outer and loop_count should match the values used when creating
! * the component IndexPaths.
*/
BitmapHeapPath *
create_bitmap_heap_path(PlannerInfo *root,
RelOptInfo *rel,
Path *bitmapqual,
! Relids required_outer,
! double loop_count)
{
BitmapHeapPath *pathnode = makeNode(BitmapHeapPath);
pathnode->path.pathtype = T_BitmapHeapScan;
pathnode->path.parent = rel;
! pathnode->path.required_outer = required_outer;
! if (required_outer)
{
! /* Identify index clauses that are join clauses */
! List *jclauses = NIL;
! List *bitmapclauses;
! ListCell *lc;
! bitmapclauses = make_restrictinfo_from_bitmapqual(bitmapqual,
! true,
! false);
! foreach(lc, bitmapclauses)
! {
! RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
!
! if (!bms_is_subset(rinfo->required_relids, rel->relids))
! jclauses = lappend(jclauses, rinfo);
! }
! pathnode->path.param_clauses = jclauses;
}
else
! pathnode->path.param_clauses = NIL;
! pathnode->path.pathkeys = NIL; /* always unordered */
! pathnode->bitmapqual = bitmapqual;
!
! cost_bitmap_heap_scan(&pathnode->path, root, rel, bitmapqual, loop_count);
return pathnode;
}
*************** create_bitmap_and_path(PlannerInfo *root
*** 592,597 ****
--- 591,598 ----
pathnode->path.pathtype = T_BitmapAnd;
pathnode->path.parent = rel;
+ pathnode->path.required_outer = NULL;
+ pathnode->path.param_clauses = NIL;
pathnode->path.pathkeys = NIL; /* always unordered */
pathnode->bitmapquals = bitmapquals;
*************** create_bitmap_or_path(PlannerInfo *root,
*** 615,620 ****
--- 616,623 ----
pathnode->path.pathtype = T_BitmapOr;
pathnode->path.parent = rel;
+ pathnode->path.required_outer = NULL;
+ pathnode->path.param_clauses = NIL;
pathnode->path.pathkeys = NIL; /* always unordered */
pathnode->bitmapquals = bitmapquals;
*************** create_tidscan_path(PlannerInfo *root, R
*** 636,641 ****
--- 639,646 ----
pathnode->path.pathtype = T_TidScan;
pathnode->path.parent = rel;
+ pathnode->path.required_outer = NULL;
+ pathnode->path.param_clauses = NIL;
pathnode->path.pathkeys = NIL;
pathnode->tidquals = tidquals;
*************** create_append_path(RelOptInfo *rel, List
*** 660,685 ****
pathnode->path.pathtype = T_Append;
pathnode->path.parent = rel;
pathnode->path.pathkeys = NIL; /* result is always considered
* unsorted */
pathnode->subpaths = subpaths;
/*
! * Compute cost as sum of subplan costs. We charge nothing extra for the
! * Append itself, which perhaps is too optimistic, but since it doesn't do
! * any selection or projection, it is a pretty cheap node.
*
! * If you change this, see also make_append().
*/
pathnode->path.startup_cost = 0;
pathnode->path.total_cost = 0;
foreach(l, subpaths)
{
Path *subpath = (Path *) lfirst(l);
if (l == list_head(subpaths)) /* first node? */
pathnode->path.startup_cost = subpath->startup_cost;
pathnode->path.total_cost += subpath->total_cost;
}
return pathnode;
--- 665,712 ----
pathnode->path.pathtype = T_Append;
pathnode->path.parent = rel;
+ pathnode->path.required_outer = NULL; /* updated below */
+ pathnode->path.param_clauses = NIL; /* XXX see below */
pathnode->path.pathkeys = NIL; /* result is always considered
* unsorted */
pathnode->subpaths = subpaths;
/*
! * We don't bother with inventing a cost_append(), but just do it here.
*
! * Compute rows and costs as sums of subplan rows and costs. We charge
! * nothing extra for the Append itself, which perhaps is too optimistic,
! * but since it doesn't do any selection or projection, it is a pretty
! * cheap node. If you change this, see also make_append().
! *
! * We also compute the correct required_outer set, namely the union of
! * the input paths' requirements.
! *
! * XXX We should also compute a proper param_clauses list, but that
! * will require identifying which joinclauses are enforced by all the
! * subplans, as well as locating the original parent RestrictInfo from
! * which they were generated. For the moment we punt and leave the list
! * as NIL. This will result in uselessly rechecking such joinclauses
! * at the parameter-supplying nestloop join, which is slightly annoying,
! * as well as overestimating the sizes of any intermediate joins, which
! * is significantly more annoying.
*/
+ pathnode->path.rows = 0;
pathnode->path.startup_cost = 0;
pathnode->path.total_cost = 0;
foreach(l, subpaths)
{
Path *subpath = (Path *) lfirst(l);
+ pathnode->path.rows += subpath->rows;
+
if (l == list_head(subpaths)) /* first node? */
pathnode->path.startup_cost = subpath->startup_cost;
pathnode->path.total_cost += subpath->total_cost;
+
+ pathnode->path.required_outer =
+ bms_add_members(pathnode->path.required_outer,
+ subpath->required_outer);
}
return pathnode;
*************** create_merge_append_path(PlannerInfo *ro
*** 703,708 ****
--- 730,737 ----
pathnode->path.pathtype = T_MergeAppend;
pathnode->path.parent = rel;
+ pathnode->path.required_outer = NULL; /* updated below */
+ pathnode->path.param_clauses = NIL; /* XXX see below */
pathnode->path.pathkeys = pathkeys;
pathnode->subpaths = subpaths;
*************** create_merge_append_path(PlannerInfo *ro
*** 735,747 ****
}
}
! /* Add up all the costs of the input paths */
input_startup_cost = 0;
input_total_cost = 0;
foreach(l, subpaths)
{
Path *subpath = (Path *) lfirst(l);
if (pathkeys_contained_in(pathkeys, subpath->pathkeys))
{
/* Subpath is adequately ordered, we won't need to sort it */
--- 764,785 ----
}
}
! /*
! * Add up the sizes and costs of the input paths, and also compute the
! * real required_outer value.
! *
! * XXX as in create_append_path(), we should compute param_clauses but
! * it will require more work.
! */
! pathnode->path.rows = 0;
input_startup_cost = 0;
input_total_cost = 0;
foreach(l, subpaths)
{
Path *subpath = (Path *) lfirst(l);
+ pathnode->path.rows += subpath->rows;
+
if (pathkeys_contained_in(pathkeys, subpath->pathkeys))
{
/* Subpath is adequately ordered, we won't need to sort it */
*************** create_merge_append_path(PlannerInfo *ro
*** 765,770 ****
--- 803,812 ----
input_startup_cost += sort_path.startup_cost;
input_total_cost += sort_path.total_cost;
}
+
+ pathnode->path.required_outer =
+ bms_add_members(pathnode->path.required_outer,
+ subpath->required_outer);
}
/* Now we can compute total costs of the MergeAppend */
*************** create_result_path(List *quals)
*** 788,797 ****
pathnode->path.pathtype = T_Result;
pathnode->path.parent = NULL;
pathnode->path.pathkeys = NIL;
pathnode->quals = quals;
! /* Ideally should define cost_result(), but I'm too lazy */
pathnode->path.startup_cost = 0;
pathnode->path.total_cost = cpu_tuple_cost;
--- 830,842 ----
pathnode->path.pathtype = T_Result;
pathnode->path.parent = NULL;
+ pathnode->path.required_outer = NULL;
+ pathnode->path.param_clauses = NIL;
pathnode->path.pathkeys = NIL;
pathnode->quals = quals;
! /* Hardly worth defining a cost_result() function ... just do it */
! pathnode->path.rows = 1;
pathnode->path.startup_cost = 0;
pathnode->path.total_cost = cpu_tuple_cost;
*************** create_material_path(RelOptInfo *rel, Pa
*** 817,823 ****
pathnode->path.pathtype = T_Material;
pathnode->path.parent = rel;
!
pathnode->path.pathkeys = subpath->pathkeys;
pathnode->subpath = subpath;
--- 862,869 ----
pathnode->path.pathtype = T_Material;
pathnode->path.parent = rel;
! pathnode->path.required_outer = subpath->required_outer;
! pathnode->path.param_clauses = subpath->param_clauses;
pathnode->path.pathkeys = subpath->pathkeys;
pathnode->subpath = subpath;
*************** create_material_path(RelOptInfo *rel, Pa
*** 825,831 ****
cost_material(&pathnode->path,
subpath->startup_cost,
subpath->total_cost,
! rel->rows,
rel->width);
return pathnode;
--- 871,877 ----
cost_material(&pathnode->path,
subpath->startup_cost,
subpath->total_cost,
! subpath->rows,
rel->width);
return pathnode;
*************** create_unique_path(PlannerInfo *root, Re
*** 874,880 ****
/*
* We must ensure path struct and subsidiary data are allocated in main
* planning context; otherwise GEQO memory management causes trouble.
- * (Compare best_inner_indexscan().)
*/
oldcontext = MemoryContextSwitchTo(root->planner_cxt);
--- 920,925 ----
*************** create_unique_path(PlannerInfo *root, Re
*** 1026,1031 ****
--- 1071,1078 ----
pathnode->path.pathtype = T_Unique;
pathnode->path.parent = rel;
+ pathnode->path.required_outer = subpath->required_outer;
+ pathnode->path.param_clauses = subpath->param_clauses;
/*
* Assume the output is unsorted, since we don't necessarily have pathkeys
*************** create_unique_path(PlannerInfo *root, Re
*** 1048,1054 ****
uniq_exprs, in_operators))
{
pathnode->umethod = UNIQUE_PATH_NOOP;
! pathnode->rows = rel->rows;
pathnode->path.startup_cost = subpath->startup_cost;
pathnode->path.total_cost = subpath->total_cost;
pathnode->path.pathkeys = subpath->pathkeys;
--- 1095,1101 ----
uniq_exprs, in_operators))
{
pathnode->umethod = UNIQUE_PATH_NOOP;
! pathnode->path.rows = rel->rows;
pathnode->path.startup_cost = subpath->startup_cost;
pathnode->path.total_cost = subpath->total_cost;
pathnode->path.pathkeys = subpath->pathkeys;
*************** create_unique_path(PlannerInfo *root, Re
*** 1081,1087 ****
sub_tlist_colnos, in_operators))
{
pathnode->umethod = UNIQUE_PATH_NOOP;
! pathnode->rows = rel->rows;
pathnode->path.startup_cost = subpath->startup_cost;
pathnode->path.total_cost = subpath->total_cost;
pathnode->path.pathkeys = subpath->pathkeys;
--- 1128,1134 ----
sub_tlist_colnos, in_operators))
{
pathnode->umethod = UNIQUE_PATH_NOOP;
! pathnode->path.rows = rel->rows;
pathnode->path.startup_cost = subpath->startup_cost;
pathnode->path.total_cost = subpath->total_cost;
pathnode->path.pathkeys = subpath->pathkeys;
*************** create_unique_path(PlannerInfo *root, Re
*** 1095,1101 ****
}
/* Estimate number of output rows */
! pathnode->rows = estimate_num_groups(root, uniq_exprs, rel->rows);
numCols = list_length(uniq_exprs);
if (all_btree)
--- 1142,1148 ----
}
/* Estimate number of output rows */
! pathnode->path.rows = estimate_num_groups(root, uniq_exprs, rel->rows);
numCols = list_length(uniq_exprs);
if (all_btree)
*************** create_unique_path(PlannerInfo *root, Re
*** 1128,1139 ****
*/
int hashentrysize = rel->width + 64;
! if (hashentrysize * pathnode->rows > work_mem * 1024L)
all_hash = false; /* don't try to hash */
else
cost_agg(&agg_path, root,
AGG_HASHED, NULL,
! numCols, pathnode->rows,
subpath->startup_cost,
subpath->total_cost,
rel->rows);
--- 1175,1186 ----
*/
int hashentrysize = rel->width + 64;
! if (hashentrysize * pathnode->path.rows > work_mem * 1024L)
all_hash = false; /* don't try to hash */
else
cost_agg(&agg_path, root,
AGG_HASHED, NULL,
! numCols, pathnode->path.rows,
subpath->startup_cost,
subpath->total_cost,
rel->rows);
*************** create_subqueryscan_path(RelOptInfo *rel
*** 1366,1371 ****
--- 1413,1420 ----
pathnode->pathtype = T_SubqueryScan;
pathnode->parent = rel;
+ pathnode->required_outer = NULL;
+ pathnode->param_clauses = NIL;
pathnode->pathkeys = pathkeys;
cost_subqueryscan(pathnode, rel);
*************** create_functionscan_path(PlannerInfo *ro
*** 1385,1390 ****
--- 1434,1441 ----
pathnode->pathtype = T_FunctionScan;
pathnode->parent = rel;
+ pathnode->required_outer = NULL;
+ pathnode->param_clauses = NIL;
pathnode->pathkeys = NIL; /* for now, assume unordered result */
cost_functionscan(pathnode, root, rel);
*************** create_valuesscan_path(PlannerInfo *root
*** 1404,1409 ****
--- 1455,1462 ----
pathnode->pathtype = T_ValuesScan;
pathnode->parent = rel;
+ pathnode->required_outer = NULL;
+ pathnode->param_clauses = NIL;
pathnode->pathkeys = NIL; /* result is always unordered */
cost_valuesscan(pathnode, root, rel);
*************** create_ctescan_path(PlannerInfo *root, R
*** 1423,1428 ****
--- 1476,1483 ----
pathnode->pathtype = T_CteScan;
pathnode->parent = rel;
+ pathnode->required_outer = NULL;
+ pathnode->param_clauses = NIL;
pathnode->pathkeys = NIL; /* XXX for now, result is always unordered */
cost_ctescan(pathnode, root, rel);
*************** create_worktablescan_path(PlannerInfo *r
*** 1442,1447 ****
--- 1497,1504 ----
pathnode->pathtype = T_WorkTableScan;
pathnode->parent = rel;
+ pathnode->required_outer = NULL;
+ pathnode->param_clauses = NIL;
pathnode->pathkeys = NIL; /* result is always unordered */
/* Cost is the same as for a regular CTE scan */
*************** create_foreignscan_path(PlannerInfo *roo
*** 1465,1470 ****
--- 1522,1529 ----
pathnode->path.pathtype = T_ForeignScan;
pathnode->path.parent = rel;
+ pathnode->path.required_outer = NULL;
+ pathnode->path.param_clauses = NIL;
pathnode->path.pathkeys = NIL; /* result is always unordered */
/* Get FDW's callback info */
*************** create_foreignscan_path(PlannerInfo *roo
*** 1479,1484 ****
--- 1538,1544 ----
pathnode->fdwplan = fdwplan;
/* use costs estimated by FDW */
+ pathnode->path.rows = rel->rows;
pathnode->path.startup_cost = fdwplan->startup_cost;
pathnode->path.total_cost = fdwplan->total_cost;
*************** create_nestloop_path(PlannerInfo *root,
*** 1514,1519 ****
--- 1574,1608 ----
pathnode->path.pathtype = T_NestLoop;
pathnode->path.parent = joinrel;
+ /* inner_path can require rels from outer path, but not vice versa */
+ Assert(!bms_overlap(outer_path->required_outer,
+ inner_path->parent->relids));
+ pathnode->path.required_outer =
+ bms_del_members(bms_union(outer_path->required_outer,
+ inner_path->required_outer),
+ outer_path->parent->relids);
+ /* maintain invariant that required_outer is exactly NULL if empty */
+ if (bms_is_empty(pathnode->path.required_outer))
+ pathnode->path.required_outer = NULL;
+ if (pathnode->path.required_outer)
+ {
+ /* Identify parameter clauses not yet applied here */
+ List *jclauses;
+ ListCell *lc;
+
+ /* LHS clauses could not be satisfied here */
+ jclauses = list_copy(outer_path->param_clauses);
+ foreach(lc, inner_path->param_clauses)
+ {
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
+
+ if (!bms_is_subset(rinfo->required_relids, joinrel->relids))
+ jclauses = lappend(jclauses, rinfo);
+ }
+ pathnode->path.param_clauses = jclauses;
+ }
+ else
+ pathnode->path.param_clauses = NIL;
pathnode->jointype = jointype;
pathnode->outerjoinpath = outer_path;
pathnode->innerjoinpath = inner_path;
*************** create_mergejoin_path(PlannerInfo *root,
*** 1570,1575 ****
--- 1659,1674 ----
pathnode->jpath.path.pathtype = T_MergeJoin;
pathnode->jpath.path.parent = joinrel;
+ /* neither path can require rels from the other */
+ Assert(!bms_overlap(outer_path->required_outer,
+ inner_path->parent->relids));
+ Assert(!bms_overlap(inner_path->required_outer,
+ outer_path->parent->relids));
+ pathnode->jpath.path.required_outer =
+ bms_union(outer_path->required_outer, inner_path->required_outer);
+ pathnode->jpath.path.param_clauses =
+ list_concat(list_copy(outer_path->param_clauses),
+ inner_path->param_clauses);
pathnode->jpath.jointype = jointype;
pathnode->jpath.outerjoinpath = outer_path;
pathnode->jpath.innerjoinpath = inner_path;
*************** create_hashjoin_path(PlannerInfo *root,
*** 1612,1617 ****
--- 1711,1726 ----
pathnode->jpath.path.pathtype = T_HashJoin;
pathnode->jpath.path.parent = joinrel;
+ /* neither path can require rels from the other */
+ Assert(!bms_overlap(outer_path->required_outer,
+ inner_path->parent->relids));
+ Assert(!bms_overlap(inner_path->required_outer,
+ outer_path->parent->relids));
+ pathnode->jpath.path.required_outer =
+ bms_union(outer_path->required_outer, inner_path->required_outer);
+ pathnode->jpath.path.param_clauses =
+ list_concat(list_copy(outer_path->param_clauses),
+ inner_path->param_clauses);
pathnode->jpath.jointype = jointype;
pathnode->jpath.outerjoinpath = outer_path;
pathnode->jpath.innerjoinpath = inner_path;
diff --git a/src/backend/optimizer/util/restrictinfo.c b/src/backend/optimizer/util/restrictinfo.c
index d9c96020f14d650987f2b470da397dfa2ac17cb1..7d03d91f5d3b6f90de576021542fea9b21ca4122 100644
*** a/src/backend/optimizer/util/restrictinfo.c
--- b/src/backend/optimizer/util/restrictinfo.c
*************** static Expr *make_sub_restrictinfos(Expr
*** 33,40 ****
bool pseudoconstant,
Relids required_relids,
Relids nullable_relids);
- static List *select_nonredundant_join_list(List *restrictinfo_list,
- List *reference_list);
static bool join_clause_is_redundant(RestrictInfo *rinfo,
List *reference_list);
--- 33,38 ----
*************** extract_actual_join_clauses(List *restri
*** 623,633 ****
/*
* select_nonredundant_join_clauses
*
* Given a list of RestrictInfo clauses that are to be applied in a join,
! * select the ones that are not redundant with any clause that's enforced
! * by the inner_path. This is used for nestloop joins, wherein any clause
! * being used in an inner indexscan need not be checked again at the join.
*
* "Redundant" means either equal() or derived from the same EquivalenceClass.
* We have to check the latter because indxpath.c may select different derived
--- 621,634 ----
/*
* select_nonredundant_join_clauses
+ * Select the members of restrictinfo_list that are not redundant with
+ * any member of reference_list.
*
* Given a list of RestrictInfo clauses that are to be applied in a join,
! * select the ones that are not redundant with any clause that's listed in
! * reference_list. This is used, for example, to avoid checking joinclauses
! * again at a nestloop join when they've already been enforced by a
! * parameterized inner path.
*
* "Redundant" means either equal() or derived from the same EquivalenceClass.
* We have to check the latter because indxpath.c may select different derived
*************** extract_actual_join_clauses(List *restri
*** 637,714 ****
* restrictinfo_list; that should have been handled elsewhere.
*/
List *
! select_nonredundant_join_clauses(PlannerInfo *root,
! List *restrictinfo_list,
! Path *inner_path)
! {
! if (IsA(inner_path, IndexPath))
! {
! /*
! * Check the index quals to see if any of them are join clauses.
! *
! * We can skip this if the index path is an ordinary indexpath and not
! * a special innerjoin path, since it then wouldn't be using any join
! * clauses.
! */
! IndexPath *innerpath = (IndexPath *) inner_path;
!
! if (innerpath->isjoininner)
! restrictinfo_list =
! select_nonredundant_join_list(restrictinfo_list,
! innerpath->indexclauses);
! }
! else if (IsA(inner_path, BitmapHeapPath))
! {
! /*
! * Same deal for bitmapped index scans.
! *
! * Note: both here and above, we ignore any implicit index
! * restrictions associated with the use of partial indexes. This is
! * OK because we're only trying to prove we can dispense with some
! * join quals; failing to prove that doesn't result in an incorrect
! * plan. It's quite unlikely that a join qual could be proven
! * redundant by an index predicate anyway. (Also, if we did manage to
! * prove it, we'd have to have a special case for update targets; see
! * notes about EvalPlanQual testing in create_indexscan_plan().)
! */
! BitmapHeapPath *innerpath = (BitmapHeapPath *) inner_path;
!
! if (innerpath->isjoininner)
! {
! List *bitmapclauses;
!
! bitmapclauses =
! make_restrictinfo_from_bitmapqual(innerpath->bitmapqual,
! true,
! false);
! restrictinfo_list =
! select_nonredundant_join_list(restrictinfo_list,
! bitmapclauses);
! }
! }
!
! /*
! * XXX the inner path of a nestloop could also be an append relation whose
! * elements use join quals. However, they might each use different quals;
! * we could only remove join quals that are enforced by all the appendrel
! * members. For the moment we don't bother to try.
! */
!
! return restrictinfo_list;
! }
!
! /*
! * select_nonredundant_join_list
! * Select the members of restrictinfo_list that are not redundant with
! * any member of reference_list. See above for more info.
! */
! static List *
! select_nonredundant_join_list(List *restrictinfo_list,
! List *reference_list)
{
List *result = NIL;
ListCell *item;
foreach(item, restrictinfo_list)
{
RestrictInfo *rinfo = (RestrictInfo *) lfirst(item);
--- 638,653 ----
* restrictinfo_list; that should have been handled elsewhere.
*/
List *
! select_nonredundant_join_clauses(List *restrictinfo_list,
! List *reference_list)
{
List *result = NIL;
ListCell *item;
+ /* Quick out if nothing could be removed */
+ if (reference_list == NIL)
+ return restrictinfo_list;
+
foreach(item, restrictinfo_list)
{
RestrictInfo *rinfo = (RestrictInfo *) lfirst(item);
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index da638f885aa5c381220f0e53688dd48d52cd86bf..09c9240490218b0525389465d6f4db6d46498cff 100644
*** a/src/backend/utils/adt/selfuncs.c
--- b/src/backend/utils/adt/selfuncs.c
*************** string_to_bytea_const(const char *str, s
*** 5971,5977 ****
static void
genericcostestimate(PlannerInfo *root,
IndexPath *path,
! RelOptInfo *outer_rel,
double numIndexTuples,
Cost *indexStartupCost,
Cost *indexTotalCost,
--- 5971,5977 ----
static void
genericcostestimate(PlannerInfo *root,
IndexPath *path,
! double loop_count,
double numIndexTuples,
Cost *indexStartupCost,
Cost *indexTotalCost,
*************** genericcostestimate(PlannerInfo *root,
*** 6119,6134 ****
* Note that we are counting pages not tuples anymore, so we take N = T =
* index size, as if there were one "tuple" per page.
*/
! if (outer_rel != NULL && outer_rel->rows > 1)
! {
! num_outer_scans = outer_rel->rows;
! num_scans = num_sa_scans * num_outer_scans;
! }
! else
! {
! num_outer_scans = 1;
! num_scans = num_sa_scans;
! }
if (num_scans > 1)
{
--- 6119,6126 ----
* Note that we are counting pages not tuples anymore, so we take N = T =
* index size, as if there were one "tuple" per page.
*/
! num_outer_scans = loop_count;
! num_scans = num_sa_scans * num_outer_scans;
if (num_scans > 1)
{
*************** btcostestimate(PG_FUNCTION_ARGS)
*** 6234,6240 ****
{
PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
IndexPath *path = (IndexPath *) PG_GETARG_POINTER(1);
! RelOptInfo *outer_rel = (RelOptInfo *) PG_GETARG_POINTER(2);
Cost *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
Cost *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
--- 6226,6232 ----
{
PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
IndexPath *path = (IndexPath *) PG_GETARG_POINTER(1);
! double loop_count = PG_GETARG_FLOAT8(2);
Cost *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
Cost *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
*************** btcostestimate(PG_FUNCTION_ARGS)
*** 6410,6416 ****
numIndexTuples = rint(numIndexTuples / num_sa_scans);
}
! genericcostestimate(root, path, outer_rel,
numIndexTuples,
indexStartupCost, indexTotalCost,
indexSelectivity, indexCorrelation);
--- 6402,6408 ----
numIndexTuples = rint(numIndexTuples / num_sa_scans);
}
! genericcostestimate(root, path, loop_count,
numIndexTuples,
indexStartupCost, indexTotalCost,
indexSelectivity, indexCorrelation);
*************** hashcostestimate(PG_FUNCTION_ARGS)
*** 6527,6539 ****
{
PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
IndexPath *path = (IndexPath *) PG_GETARG_POINTER(1);
! RelOptInfo *outer_rel = (RelOptInfo *) PG_GETARG_POINTER(2);
Cost *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
Cost *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
double *indexCorrelation = (double *) PG_GETARG_POINTER(6);
! genericcostestimate(root, path, outer_rel, 0.0,
indexStartupCost, indexTotalCost,
indexSelectivity, indexCorrelation);
--- 6519,6531 ----
{
PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
IndexPath *path = (IndexPath *) PG_GETARG_POINTER(1);
! double loop_count = PG_GETARG_FLOAT8(2);
Cost *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
Cost *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
double *indexCorrelation = (double *) PG_GETARG_POINTER(6);
! genericcostestimate(root, path, loop_count, 0.0,
indexStartupCost, indexTotalCost,
indexSelectivity, indexCorrelation);
*************** gistcostestimate(PG_FUNCTION_ARGS)
*** 6545,6557 ****
{
PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
IndexPath *path = (IndexPath *) PG_GETARG_POINTER(1);
! RelOptInfo *outer_rel = (RelOptInfo *) PG_GETARG_POINTER(2);
Cost *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
Cost *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
double *indexCorrelation = (double *) PG_GETARG_POINTER(6);
! genericcostestimate(root, path, outer_rel, 0.0,
indexStartupCost, indexTotalCost,
indexSelectivity, indexCorrelation);
--- 6537,6549 ----
{
PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
IndexPath *path = (IndexPath *) PG_GETARG_POINTER(1);
! double loop_count = PG_GETARG_FLOAT8(2);
Cost *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
Cost *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
double *indexCorrelation = (double *) PG_GETARG_POINTER(6);
! genericcostestimate(root, path, loop_count, 0.0,
indexStartupCost, indexTotalCost,
indexSelectivity, indexCorrelation);
*************** spgcostestimate(PG_FUNCTION_ARGS)
*** 6563,6575 ****
{
PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
IndexPath *path = (IndexPath *) PG_GETARG_POINTER(1);
! RelOptInfo *outer_rel = (RelOptInfo *) PG_GETARG_POINTER(2);
Cost *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
Cost *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
double *indexCorrelation = (double *) PG_GETARG_POINTER(6);
! genericcostestimate(root, path, outer_rel, 0.0,
indexStartupCost, indexTotalCost,
indexSelectivity, indexCorrelation);
--- 6555,6567 ----
{
PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
IndexPath *path = (IndexPath *) PG_GETARG_POINTER(1);
! double loop_count = PG_GETARG_FLOAT8(2);
Cost *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
Cost *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
double *indexCorrelation = (double *) PG_GETARG_POINTER(6);
! genericcostestimate(root, path, loop_count, 0.0,
indexStartupCost, indexTotalCost,
indexSelectivity, indexCorrelation);
*************** gincostestimate(PG_FUNCTION_ARGS)
*** 6884,6890 ****
{
PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
IndexPath *path = (IndexPath *) PG_GETARG_POINTER(1);
! RelOptInfo *outer_rel = (RelOptInfo *) PG_GETARG_POINTER(2);
Cost *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
Cost *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
--- 6876,6882 ----
{
PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
IndexPath *path = (IndexPath *) PG_GETARG_POINTER(1);
! double loop_count = PG_GETARG_FLOAT8(2);
Cost *indexStartupCost = (Cost *) PG_GETARG_POINTER(3);
Cost *indexTotalCost = (Cost *) PG_GETARG_POINTER(4);
Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5);
*************** gincostestimate(PG_FUNCTION_ARGS)
*** 7051,7060 ****
}
/* Will we have more than one iteration of a nestloop scan? */
! if (outer_rel != NULL && outer_rel->rows > 1)
! outer_scans = outer_rel->rows;
! else
! outer_scans = 1;
/*
* Compute cost to begin scan, first of all, pay attention to pending list.
--- 7043,7049 ----
}
/* Will we have more than one iteration of a nestloop scan? */
! outer_scans = loop_count;
/*
* Compute cost to begin scan, first of all, pay attention to pending list.
diff --git a/src/include/nodes/bitmapset.h b/src/include/nodes/bitmapset.h
index 8fdbd72d3525ddde33d24051e228005be4ec9527..bcca70d2b9817ca0d05f2a90e0c898ff0c48b1b6 100644
*** a/src/include/nodes/bitmapset.h
--- b/src/include/nodes/bitmapset.h
*************** typedef struct Bitmapset
*** 36,41 ****
--- 36,50 ----
} Bitmapset; /* VARIABLE LENGTH STRUCT */
+ /* result of bms_subset_compare */
+ typedef enum
+ {
+ BMS_EQUAL, /* sets are equal */
+ BMS_SUBSET1, /* first set is a subset of the second */
+ BMS_SUBSET2, /* second set is a subset of the first */
+ BMS_DIFFERENT /* neither set is a subset of the other */
+ } BMS_Comparison;
+
/* result of bms_membership */
typedef enum
{
*************** extern Bitmapset *bms_union(const Bitmap
*** 58,63 ****
--- 67,73 ----
extern Bitmapset *bms_intersect(const Bitmapset *a, const Bitmapset *b);
extern Bitmapset *bms_difference(const Bitmapset *a, const Bitmapset *b);
extern bool bms_is_subset(const Bitmapset *a, const Bitmapset *b);
+ extern BMS_Comparison bms_subset_compare(const Bitmapset *a, const Bitmapset *b);
extern bool bms_is_member(int x, const Bitmapset *a);
extern bool bms_overlap(const Bitmapset *a, const Bitmapset *b);
extern bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b);
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 94657d2aaa1aacc4ee04160833298c7af7e585fa..27cbef5e3823099e5a92971e5e6cd95b6beb3587 100644
*** a/src/include/nodes/relation.h
--- b/src/include/nodes/relation.h
*************** typedef struct EquivalenceMember
*** 609,615 ****
* BTGreaterStrategyNumber (for DESC). We assume that all ordering-capable
* index types will use btree-compatible strategy numbers.
*/
-
typedef struct PathKey
{
NodeTag type;
--- 609,614 ----
*************** typedef struct PathKey
*** 625,650 ****
* simple plan types that we don't need any extra information in the path for.
* For other path types it is the first component of a larger struct.
*
! * Note: "pathtype" is the NodeTag of the Plan node we could build from this
! * Path. It is partially redundant with the Path's NodeTag, but allows us
! * to use the same Path type for multiple Plan types where there is no need
! * to distinguish the Plan type during path processing.
*/
-
typedef struct Path
{
NodeTag type;
NodeTag pathtype; /* tag identifying scan/join method */
-
RelOptInfo *parent; /* the relation this path can build */
!
/* estimated execution costs for path (see costsize.c for more info) */
Cost startup_cost; /* cost expended before fetching any tuples */
Cost total_cost; /* total cost (assuming all tuples fetched) */
-
- List *pathkeys; /* sort ordering of path's output */
- /* pathkeys is a List of PathKey nodes; see above */
} Path;
/*----------
--- 624,667 ----
* simple plan types that we don't need any extra information in the path for.
* For other path types it is the first component of a larger struct.
*
! * "pathtype" is the NodeTag of the Plan node we could build from this Path.
! * It is partially redundant with the Path's NodeTag, but allows us to use
! * the same Path type for multiple Plan types when there is no need to
! * distinguish the Plan type during path processing.
! *
! * "required_outer", if not NULL, contains the relids of one or more relations
! * that must provide parameter values to each scan of this path, because the
! * path relies on join clauses using those rels. That means this path can only
! * be joined to those rels by means of nestloop joins with this path on the
! * inside. Note: for a normal unparameterized path, required_outer must be
! * NULL, not an empty-but-not-null Bitmapset.
! *
! * "param_clauses" is a List of RestrictInfo nodes, containing the join
! * clauses used by a parameterized path. Ideally param_clauses should be NIL
! * if and only if required_outer is NULL. XXX for the moment, however, we do
! * not compute param_clauses for Append and MergeAppend paths, so the list
! * is inaccurate in those paths and possibly paths above them.
! *
! * "pathkeys" is a List of PathKey nodes (see above), describing the sort
! * ordering of the path's output rows.
! *
! * "rows" is the same as parent->rows in simple paths, but in parameterized
! * paths and UniquePaths it can be less than parent->rows, reflecting the
! * fact that we've filtered by extra join conditions or removed duplicates.
*/
typedef struct Path
{
NodeTag type;
NodeTag pathtype; /* tag identifying scan/join method */
RelOptInfo *parent; /* the relation this path can build */
! Relids required_outer; /* rels supplying parameters used by path */
! List *param_clauses; /* join clauses that use such parameters */
! List *pathkeys; /* sort ordering of path's output */
! double rows; /* estimated number of result tuples */
/* estimated execution costs for path (see costsize.c for more info) */
Cost startup_cost; /* cost expended before fetching any tuples */
Cost total_cost; /* total cost (assuming all tuples fetched) */
} Path;
/*----------
*************** typedef struct Path
*** 685,696 ****
* ORDER BY expression is meant to be used with. (There is no restriction
* on which index column each ORDER BY can be used with.)
*
- * 'isjoininner' is TRUE if the path is a nestloop inner scan (that is,
- * some of the index conditions are join rather than restriction clauses).
- * Note that the path costs will be calculated differently from a plain
- * indexscan in this case, and in addition there's a special 'rows' value
- * different from the parent RelOptInfo's (see below).
- *
* 'indexscandir' is one of:
* ForwardScanDirection: forward scan of an ordered index
* BackwardScanDirection: backward scan of an ordered index
--- 702,707 ----
*************** typedef struct Path
*** 703,714 ****
* we need not recompute them when considering using the same index in a
* bitmap index/heap scan (see BitmapHeapPath). The costs of the IndexPath
* itself represent the costs of an IndexScan or IndexOnlyScan plan type.
- *
- * 'rows' is the estimated result tuple count for the indexscan. This
- * is the same as path.parent->rows for a simple indexscan, but it is
- * different for a nestloop inner scan, because the additional indexquals
- * coming from join clauses make the scan more selective than the parent
- * rel's restrict clauses alone would do.
*----------
*/
typedef struct IndexPath
--- 714,719 ----
*************** typedef struct IndexPath
*** 720,730 ****
List *indexqualcols;
List *indexorderbys;
List *indexorderbycols;
- bool isjoininner;
ScanDirection indexscandir;
Cost indextotalcost;
Selectivity indexselectivity;
- double rows; /* estimated number of result tuples */
} IndexPath;
/*
--- 725,733 ----
*************** typedef struct IndexPath
*** 743,758 ****
* always represent the costs to use it as a regular (or index-only)
* IndexScan. The costs of a BitmapIndexScan can be computed using the
* IndexPath's indextotalcost and indexselectivity.
- *
- * BitmapHeapPaths can be nestloop inner indexscans. The isjoininner and
- * rows fields serve the same purpose as for plain IndexPaths.
*/
typedef struct BitmapHeapPath
{
Path path;
Path *bitmapqual; /* IndexPath, BitmapAndPath, BitmapOrPath */
- bool isjoininner; /* T if it's a nestloop inner scan */
- double rows; /* estimated number of result tuples */
} BitmapHeapPath;
/*
--- 746,756 ----
*************** typedef struct UniquePath
*** 885,891 ****
UniquePathMethod umethod;
List *in_operators; /* equality operators of the IN clause */
List *uniq_exprs; /* expressions to be made unique */
- double rows; /* estimated number of result tuples */
} UniquePath;
/*
--- 883,888 ----
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index 1786d5e93607846acf70aab80093163442700a13..3b093dfd9cae9c5ce59a563de127815b40f946d0 100644
*** a/src/include/optimizer/cost.h
--- b/src/include/optimizer/cost.h
*************** extern double index_pages_fetched(double
*** 68,76 ****
double index_pages, PlannerInfo *root);
extern void cost_seqscan(Path *path, PlannerInfo *root, RelOptInfo *baserel);
extern void cost_index(IndexPath *path, PlannerInfo *root,
! RelOptInfo *outer_rel);
extern void cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel,
! Path *bitmapqual, RelOptInfo *outer_rel);
extern void cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root);
extern void cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root);
extern void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec);
--- 68,76 ----
double index_pages, PlannerInfo *root);
extern void cost_seqscan(Path *path, PlannerInfo *root, RelOptInfo *baserel);
extern void cost_index(IndexPath *path, PlannerInfo *root,
! double loop_count);
extern void cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel,
! Path *bitmapqual, double loop_count);
extern void cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root);
extern void cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root);
extern void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec);
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index 3bc1b27384c0c6d9d06e13068f8be085b7abb18c..c4ae7a9d556b743a77419f8f080960ddb310b13a 100644
*** a/src/include/optimizer/pathnode.h
--- b/src/include/optimizer/pathnode.h
*************** extern IndexPath *create_index_path(Plan
*** 37,47 ****
List *pathkeys,
ScanDirection indexscandir,
bool indexonly,
! RelOptInfo *outer_rel);
extern BitmapHeapPath *create_bitmap_heap_path(PlannerInfo *root,
RelOptInfo *rel,
Path *bitmapqual,
! RelOptInfo *outer_rel);
extern BitmapAndPath *create_bitmap_and_path(PlannerInfo *root,
RelOptInfo *rel,
List *bitmapquals);
--- 37,49 ----
List *pathkeys,
ScanDirection indexscandir,
bool indexonly,
! Relids required_outer,
! double loop_count);
extern BitmapHeapPath *create_bitmap_heap_path(PlannerInfo *root,
RelOptInfo *rel,
Path *bitmapqual,
! Relids required_outer,
! double loop_count);
extern BitmapAndPath *create_bitmap_and_path(PlannerInfo *root,
RelOptInfo *rel,
List *bitmapquals);
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 76d7b77fc1d782f8812d7308baa1e357db9ca5c6..e3a085fdff13e6ca9c6d4a498522a69171d18b42 100644
*** a/src/include/optimizer/paths.h
--- b/src/include/optimizer/paths.h
*************** extern void debug_print_rel(PlannerInfo
*** 45,54 ****
extern void create_index_paths(PlannerInfo *root, RelOptInfo *rel);
extern List *generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
List *clauses, List *outer_clauses,
! RelOptInfo *outer_rel);
! extern void best_inner_indexscan(PlannerInfo *root, RelOptInfo *rel,
! RelOptInfo *outer_rel, JoinType jointype,
! Path **cheapest_startup, Path **cheapest_total);
extern bool relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
List *restrictlist,
List *exprlist, List *oprlist);
--- 45,51 ----
extern void create_index_paths(PlannerInfo *root, RelOptInfo *rel);
extern List *generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
List *clauses, List *outer_clauses,
! Relids outer_relids, double outer_rows);
extern bool relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
List *restrictlist,
List *exprlist, List *oprlist);
*************** extern List *canonicalize_pathkeys(Plann
*** 153,158 ****
--- 150,156 ----
extern PathKeysComparison compare_pathkeys(List *keys1, List *keys2);
extern bool pathkeys_contained_in(List *keys1, List *keys2);
extern Path *get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
+ Relids required_outer,
CostSelector cost_criterion);
extern Path *get_cheapest_fractional_path_for_pathkeys(List *paths,
List *pathkeys,
diff --git a/src/include/optimizer/restrictinfo.h b/src/include/optimizer/restrictinfo.h
index 157f58e5fa8a4a3d3956750a9fd4e509a5084dfb..34977f9b95cbf5b96502100b5c1b695e74b3a58a 100644
*** a/src/include/optimizer/restrictinfo.h
--- b/src/include/optimizer/restrictinfo.h
*************** extern List *extract_actual_clauses(List
*** 40,47 ****
extern void extract_actual_join_clauses(List *restrictinfo_list,
List **joinquals,
List **otherquals);
! extern List *select_nonredundant_join_clauses(PlannerInfo *root,
! List *restrictinfo_list,
! Path *inner_path);
#endif /* RESTRICTINFO_H */
--- 40,46 ----
extern void extract_actual_join_clauses(List *restrictinfo_list,
List **joinquals,
List **otherquals);
! extern List *select_nonredundant_join_clauses(List *restrictinfo_list,
! List *reference_list);
#endif /* RESTRICTINFO_H */