Re: HashJoin w/option to unique-ify inner rel
Re: HashJoin w/option to unique-ify inner rel
От:
Tom Lane <tgl@sss.pgh.pa.us>
Дата:
I wrote:
> ... So it appears to me that instead of taking an average-case correction
> as is done in this patch and the old coding, we have to explicitly model
> the matched-tuple and unmatched-tuple cases separately.
I've applied the attached patch that does things this way. I did not do
anything about improving the detailed modeling of hash-bucket searching
as Robert suggested in some later messages. I think that's probably
worth looking at, but it's a second-order consideration --- this patch
already seems to bring the estimates for semi/antijoins much closer
to reality.
I am a bit concerned about the extra time spent on repeated selectivity
estimates. It might not matter too much since it's only done for semi
and anti joins which aren't that common. It would be good though if
someone who has a lot of such joins could test CVS HEAD and see if
performance has gotten worse (Kevin?). We could refactor things to
reduce the duplication of effort but I'd prefer to leave that sort of
thing to 8.5.
BTW, if you're reading the patch in detail, the changes outside
costsize.c are just refactoring to allow costsize.c to use some
code that was formerly buried in createplan.c. The changes in
costsize.c use the same basic selectivity calculation as in my
patch of two weeks ago, but apply the results differently as per
our discussion.
regards, tom lane
Index: src/backend/optimizer/path/costsize.c
===================================================================
RCS file: /cvsroot/pgsql/src/backend/optimizer/path/costsize.c,v
retrieving revision 1.207
diff -c -r1.207 costsize.c
*** src/backend/optimizer/path/costsize.c 17 Apr 2009 15:33:33 -0000 1.207
--- src/backend/optimizer/path/costsize.c 9 May 2009 22:45:48 -0000
***************
*** 71,76 ****
--- 71,77 ----
#include "optimizer/pathnode.h"
#include "optimizer/placeholder.h"
#include "optimizer/planmain.h"
+ #include "optimizer/restrictinfo.h"
#include "parser/parsetree.h"
#include "utils/lsyscache.h"
#include "utils/selfuncs.h"
***************
*** 119,124 ****
--- 120,130 ----
RestrictInfo *rinfo,
PathKey *pathkey);
static bool cost_qual_eval_walker(Node *node, cost_qual_eval_context *context);
+ static bool adjust_semi_join(PlannerInfo *root, JoinPath *path,
+ SpecialJoinInfo *sjinfo,
+ Selectivity *outer_match_frac,
+ Selectivity *match_count,
+ bool *indexed_join_quals);
static double approx_tuple_count(PlannerInfo *root, JoinPath *path,
List *quals);
static void set_rel_width(PlannerInfo *root, RelOptInfo *rel);
***************
*** 1394,1404 ****
--- 1400,1414 ----
Path *inner_path = path->innerjoinpath;
Cost startup_cost = 0;
Cost run_cost = 0;
+ Cost inner_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;
***************
*** 1428,1440 ****
*/
run_cost += (outer_path_rows - 1) * inner_path->startup_cost;
}
! run_cost += outer_path_rows *
! (inner_path->total_cost - inner_path->startup_cost);
! /*
! * Compute number of tuples processed (not number emitted!)
! */
! ntuples = outer_path_rows * inner_path_rows;
/* CPU costs */
cost_qual_eval(&restrict_qual_cost, path->joinrestrictinfo, root);
--- 1438,1503 ----
*/
run_cost += (outer_path_rows - 1) * inner_path->startup_cost;
}
! inner_run_cost = inner_path->total_cost - inner_path->startup_cost;
! if (adjust_semi_join(root, path, sjinfo,
! &outer_match_frac,
! &match_count,
! &indexed_join_quals))
! {
! double outer_matched_rows;
! Selectivity inner_scan_frac;
!
! /*
! * SEMI or ANTI join: executor will stop after first match.
! *
! * For an outer-rel row that has at least one match, we can expect the
! * inner scan to stop after a fraction 1/(match_count+1) of the inner
! * rows, if the matches are evenly distributed. Since they probably
! * aren't quite evenly distributed, we apply a fuzz factor of 2.0 to
! * that fraction. (If we used a larger fuzz factor, we'd have to
! * clamp inner_scan_frac to at most 1.0; but since match_count is at
! * least 1, no such clamp is needed now.)
! */
! outer_matched_rows = rint(outer_path_rows * outer_match_frac);
! inner_scan_frac = 2.0 / (match_count + 1.0);
!
! /* Add inner run cost for outer tuples having matches */
! run_cost += outer_matched_rows * inner_run_cost * inner_scan_frac;
!
! /* Compute number of tuples processed (not number emitted!) */
! ntuples = outer_matched_rows * inner_path_rows * inner_scan_frac;
!
! /*
! * For unmatched outer-rel rows, there are two cases. If the inner
! * path is an indexscan using all the joinquals as indexquals, then
! * an unmatched row results in an indexscan returning no rows, which
! * is probably quite cheap. We estimate this case as the same cost
! * to return the first tuple of a nonempty scan. Otherwise, the
! * executor will have to scan the whole inner rel; not so cheap.
! */
! if (indexed_join_quals)
! {
! run_cost += (outer_path_rows - outer_matched_rows) *
! inner_run_cost / inner_path_rows;
! /* We won't be evaluating any quals at all for these rows */
! }
! else
! {
! run_cost += (outer_path_rows - outer_matched_rows) *
! inner_run_cost;
! ntuples += (outer_path_rows - outer_matched_rows) *
! inner_path_rows;
! }
! }
! else
! {
! /* Normal case; we'll scan whole input rel for each outer row */
! run_cost += outer_path_rows * inner_run_cost;
!
! /* Compute number of tuples processed (not number emitted!) */
! ntuples = outer_path_rows * inner_path_rows;
! }
/* CPU costs */
cost_qual_eval(&restrict_qual_cost, path->joinrestrictinfo, root);
***************
*** 1731,1736 ****
--- 1794,1802 ----
* cpu_tuple_cost plus the cost of evaluating additional restriction
* clauses that are to be applied at the join. (This is pessimistic since
* not all of the quals may get evaluated at each tuple.)
+ *
+ * Note: we could adjust for SEMI/ANTI joins skipping some qual evaluations
+ * here, but it's probably not worth the trouble.
*/
startup_cost += qp_qual_cost.startup;
cpu_per_tuple = cpu_tuple_cost + qp_qual_cost.per_tuple;
***************
*** 1824,1829 ****
--- 1890,1897 ----
int num_skew_mcvs;
double virtualbuckets;
Selectivity innerbucketsize;
+ Selectivity outer_match_frac;
+ Selectivity match_count;
ListCell *hcl;
if (!enable_hashjoin)
***************
*** 1838,1849 ****
qp_qual_cost.startup -= hash_qual_cost.startup;
qp_qual_cost.per_tuple -= hash_qual_cost.per_tuple;
- /*
- * Get approx # tuples passing the hashquals. We use approx_tuple_count
- * here because we need an estimate done with JOIN_INNER semantics.
- */
- hashjointuples = approx_tuple_count(root, &path->jpath, hashclauses);
-
/* cost of source data */
startup_cost += outer_path->startup_cost;
run_cost += outer_path->total_cost - outer_path->startup_cost;
--- 1906,1911 ----
***************
*** 1970,1987 ****
/* CPU costs */
! /*
! * The number of tuple comparisons needed is the number of outer tuples
! * times the typical number of tuples in a hash bucket, which is the inner
! * relation size times its bucketsize fraction. At each one, we need to
! * evaluate the hashjoin quals. But actually, charging the full qual eval
! * cost at each tuple is pessimistic, since we don't evaluate the quals
! * unless the hash values match exactly. For lack of a better idea, halve
! * the cost estimate to allow for that.
! */
! startup_cost += hash_qual_cost.startup;
! run_cost += hash_qual_cost.per_tuple *
! outer_path_rows * clamp_row_est(inner_path_rows * innerbucketsize) * 0.5;
/*
* For each tuple that gets through the hashjoin proper, we charge
--- 2032,2109 ----
/* CPU costs */
! if (adjust_semi_join(root, &path->jpath, sjinfo,
! &outer_match_frac,
! &match_count,
! NULL))
! {
! double outer_matched_rows;
! Selectivity inner_scan_frac;
!
! /*
! * SEMI or ANTI join: executor will stop after first match.
! *
! * For an outer-rel row that has at least one match, we can expect the
! * bucket scan to stop after a fraction 1/(match_count+1) of the
! * bucket's rows, if the matches are evenly distributed. Since they
! * probably aren't quite evenly distributed, we apply a fuzz factor of
! * 2.0 to that fraction. (If we used a larger fuzz factor, we'd have
! * to clamp inner_scan_frac to at most 1.0; but since match_count is
! * at least 1, no such clamp is needed now.)
! */
! outer_matched_rows = rint(outer_path_rows * outer_match_frac);
! inner_scan_frac = 2.0 / (match_count + 1.0);
!
! startup_cost += hash_qual_cost.startup;
! run_cost += hash_qual_cost.per_tuple * outer_matched_rows *
! clamp_row_est(inner_path_rows * innerbucketsize * inner_scan_frac) * 0.5;
!
! /*
! * For unmatched outer-rel rows, the picture is quite a lot different.
! * In the first place, there is no reason to assume that these rows
! * preferentially hit heavily-populated buckets; instead assume they
! * are uncorrelated with the inner distribution and so they see an
! * average bucket size of inner_path_rows / virtualbuckets. In the
! * second place, it seems likely that they will have few if any
! * exact hash-code matches and so very few of the tuples in the
! * bucket will actually require eval of the hash quals. We don't
! * have any good way to estimate how many will, but for the moment
! * assume that the effective cost per bucket entry is one-tenth what
! * it is for matchable tuples.
! */
! run_cost += hash_qual_cost.per_tuple *
! (outer_path_rows - outer_matched_rows) *
! clamp_row_est(inner_path_rows / virtualbuckets) * 0.05;
!
! /* Get # of tuples that will pass the basic join */
! if (path->jpath.jointype == JOIN_SEMI)
! hashjointuples = outer_matched_rows;
! else
! hashjointuples = outer_path_rows - outer_matched_rows;
! }
! else
! {
! /*
! * The number of tuple comparisons needed is the number of outer
! * tuples times the typical number of tuples in a hash bucket, which
! * is the inner relation size times its bucketsize fraction. At each
! * one, we need to evaluate the hashjoin quals. But actually,
! * charging the full qual eval cost at each tuple is pessimistic,
! * since we don't evaluate the quals unless the hash values match
! * exactly. For lack of a better idea, halve the cost estimate to
! * allow for that.
! */
! startup_cost += hash_qual_cost.startup;
! run_cost += hash_qual_cost.per_tuple * outer_path_rows *
! clamp_row_est(inner_path_rows * innerbucketsize) * 0.5;
!
! /*
! * Get approx # tuples passing the hashquals. We use
! * approx_tuple_count here because we need an estimate done with
! * JOIN_INNER semantics.
! */
! hashjointuples = approx_tuple_count(root, &path->jpath, hashclauses);
! }
/*
* For each tuple that gets through the hashjoin proper, we charge
***************
*** 2321,2326 ****
--- 2443,2598 ----
/*
+ * adjust_semi_join
+ * Estimate how much of the inner input a SEMI or ANTI join
+ * can be expected to scan.
+ *
+ * In a hash or nestloop SEMI/ANTI join, the executor will stop scanning
+ * inner rows as soon as it finds a match to the current outer row.
+ * 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.
+ *
+ * Output parameters (set only in TRUE-result case):
+ * *outer_match_frac is set to the fraction of the outer tuples that are
+ * expected to have at least one match.
+ * *match_count is set to the average number of matches expected for
+ * outer tuples that have at least one match.
+ * *indexed_join_quals is set to TRUE if all the joinquals are used as
+ * inner index quals, FALSE if not.
+ *
+ * indexed_join_quals can be passed as NULL if that information is not
+ * relevant (it is only useful for the nestloop case).
+ */
+ static bool
+ adjust_semi_join(PlannerInfo *root, JoinPath *path, SpecialJoinInfo *sjinfo,
+ Selectivity *outer_match_frac,
+ Selectivity *match_count,
+ bool *indexed_join_quals)
+ {
+ JoinType jointype = path->jointype;
+ Selectivity jselec;
+ Selectivity nselec;
+ Selectivity avgmatch;
+ SpecialJoinInfo norm_sjinfo;
+ List *joinquals;
+ ListCell *l;
+
+ /* Fall out if it's not JOIN_SEMI or JOIN_ANTI */
+ if (jointype != JOIN_SEMI && jointype != JOIN_ANTI)
+ return false;
+
+ /*
+ * Note: it's annoying to repeat this selectivity estimation on each call,
+ * when the joinclause list will be the same for all path pairs
+ * implementing a given join. clausesel.c will save us from the worst
+ * effects of this by caching at the RestrictInfo level; but perhaps it'd
+ * be worth finding a way to cache the results at a higher level.
+ */
+
+ /*
+ * In an ANTI join, we must ignore clauses that are "pushed down",
+ * since those won't affect the match logic. In a SEMI join, we do not
+ * distinguish joinquals from "pushed down" quals, so just use the whole
+ * restrictinfo list.
+ */
+ if (jointype == JOIN_ANTI)
+ {
+ joinquals = NIL;
+ foreach(l, path->joinrestrictinfo)
+ {
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
+
+ Assert(IsA(rinfo, RestrictInfo));
+ if (!rinfo->is_pushed_down)
+ joinquals = lappend(joinquals, rinfo);
+ }
+ }
+ else
+ joinquals = path->joinrestrictinfo;
+
+ /*
+ * Get the JOIN_SEMI or JOIN_ANTI selectivity of the join clauses.
+ */
+ jselec = clauselist_selectivity(root,
+ joinquals,
+ 0,
+ jointype,
+ sjinfo);
+
+ /*
+ * Also get the normal inner-join selectivity of the join clauses.
+ */
+ norm_sjinfo.type = T_SpecialJoinInfo;
+ norm_sjinfo.min_lefthand = path->outerjoinpath->parent->relids;
+ norm_sjinfo.min_righthand = path->innerjoinpath->parent->relids;
+ norm_sjinfo.syn_lefthand = path->outerjoinpath->parent->relids;
+ norm_sjinfo.syn_righthand = path->innerjoinpath->parent->relids;
+ norm_sjinfo.jointype = JOIN_INNER;
+ /* we don't bother trying to make the remaining fields valid */
+ norm_sjinfo.lhs_strict = false;
+ norm_sjinfo.delay_upper_joins = false;
+ norm_sjinfo.join_quals = NIL;
+
+ nselec = clauselist_selectivity(root,
+ joinquals,
+ 0,
+ JOIN_INNER,
+ &norm_sjinfo);
+
+ /* Avoid leaking a lot of ListCells */
+ if (jointype == JOIN_ANTI)
+ list_free(joinquals);
+
+ /*
+ * jselec can be interpreted as the fraction of outer-rel rows that have
+ * any matches (this is true for both SEMI and ANTI cases). And nselec
+ * is the fraction of the Cartesian product that matches. So, the
+ * average number of matches for each outer-rel row that has at least
+ * one match is 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 */
+ {
+ avgmatch = nselec * path->innerjoinpath->parent->rows / jselec;
+ /* Clamp to sane range */
+ avgmatch = Max(1.0, avgmatch);
+ }
+ else
+ avgmatch = 1.0;
+
+ *outer_match_frac = jselec;
+ *match_count = avgmatch;
+
+ /*
+ * If requested, check whether the inner path uses all the joinquals
+ * as indexquals. (If that's true, we can assume that an unmatched
+ * outer tuple is cheap to process, whereas otherwise it's probably
+ * expensive.)
+ */
+ if (indexed_join_quals)
+ {
+ List *nrclauses;
+
+ nrclauses = select_nonredundant_join_clauses(root,
+ path->joinrestrictinfo,
+ path->innerjoinpath);
+ *indexed_join_quals = (nrclauses == NIL);
+ }
+
+ return true;
+ }
+
+
+ /*
* approx_tuple_count
* Quick-and-dirty estimation of the number of join rows passing
* a set of qual conditions.
Index: src/backend/optimizer/plan/createplan.c
===================================================================
RCS file: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v
retrieving revision 1.258
diff -c -r1.258 createplan.c
*** src/backend/optimizer/plan/createplan.c 19 Apr 2009 19:46:33 -0000 1.258
--- src/backend/optimizer/plan/createplan.c 9 May 2009 22:45:48 -0000
***************
*** 1562,1623 ****
List *otherclauses;
NestLoop *join_plan;
! if (IsA(best_path->innerjoinpath, IndexPath))
! {
! /*
! * An index is being used to reduce the number of tuples scanned in
! * the inner relation. If there are join clauses being used with the
! * index, we may remove those join clauses from the list of clauses
! * that have to be checked as qpquals at the join node.
! *
! * We can also remove any join clauses that are redundant with those
! * being used in the index scan; this check is needed because
! * find_eclass_clauses_for_index_join() may emit different clauses
! * than generate_join_implied_equalities() did.
! *
! * 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 *) best_path->innerjoinpath;
!
! if (innerpath->isjoininner)
! joinrestrictclauses =
! select_nonredundant_join_clauses(root,
! joinrestrictclauses,
! innerpath->indexclauses);
! }
! else if (IsA(best_path->innerjoinpath, 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 is the right way to proceed because adding more quals to
! * the stuff we got from the original query would just make it harder
! * to detect duplication. (Also, to change this we'd have to be wary
! * of UPDATE/DELETE/SELECT FOR UPDATE target relations; see notes
! * above about EvalPlanQual.)
! */
! BitmapHeapPath *innerpath = (BitmapHeapPath *) best_path->innerjoinpath;
!
! if (innerpath->isjoininner)
! {
! List *bitmapclauses;
!
! bitmapclauses =
! make_restrictinfo_from_bitmapqual(innerpath->bitmapqual,
! true,
! false);
! joinrestrictclauses =
! select_nonredundant_join_clauses(root,
! joinrestrictclauses,
! bitmapclauses);
! }
! }
/* Sort join qual clauses into best execution order */
joinrestrictclauses = order_qual_clauses(root, joinrestrictclauses);
--- 1562,1577 ----
List *otherclauses;
NestLoop *join_plan;
! /*
! * 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);
Index: src/backend/optimizer/util/restrictinfo.c
===================================================================
RCS file: /cvsroot/pgsql/src/backend/optimizer/util/restrictinfo.c,v
retrieving revision 1.58
diff -c -r1.58 restrictinfo.c
*** src/backend/optimizer/util/restrictinfo.c 16 Apr 2009 20:42:16 -0000 1.58
--- src/backend/optimizer/util/restrictinfo.c 9 May 2009 22:45:48 -0000
***************
*** 35,42 ****
bool pseudoconstant,
Relids required_relids,
Relids nullable_relids);
! static bool join_clause_is_redundant(PlannerInfo *root,
! RestrictInfo *rinfo,
List *reference_list);
--- 35,43 ----
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);
***************
*** 545,570 ****
}
}
/*
* 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 in the
! * reference_list. This is used only for nestloop-with-inner-indexscan
! * joins: any clauses being checked by the index should be removed from
! * the qpquals list.
*
* "Redundant" means either equal() or derived from the same EquivalenceClass.
* We have to check the latter because indxqual.c may select different derived
* clauses than were selected by generate_join_implied_equalities().
*
! * Note that we assume the given restrictinfo_list has already been checked
! * for local redundancies, so we don't check again.
*/
List *
select_nonredundant_join_clauses(PlannerInfo *root,
List *restrictinfo_list,
! List *reference_list)
{
List *result = NIL;
ListCell *item;
--- 546,636 ----
}
}
+
/*
* 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 indxqual.c may select different derived
* clauses than were selected by generate_join_implied_equalities().
*
! * Note that we are *not* checking for local redundancies within the given
! * 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;
***************
*** 574,580 ****
RestrictInfo *rinfo = (RestrictInfo *) lfirst(item);
/* drop it if redundant with any reference clause */
! if (join_clause_is_redundant(root, rinfo, reference_list))
continue;
/* otherwise, add it to result list */
--- 640,646 ----
RestrictInfo *rinfo = (RestrictInfo *) lfirst(item);
/* drop it if redundant with any reference clause */
! if (join_clause_is_redundant(rinfo, reference_list))
continue;
/* otherwise, add it to result list */
***************
*** 589,596 ****
* Test whether rinfo is redundant with any clause in reference_list.
*/
static bool
! join_clause_is_redundant(PlannerInfo *root,
! RestrictInfo *rinfo,
List *reference_list)
{
ListCell *refitem;
--- 655,661 ----
* Test whether rinfo is redundant with any clause in reference_list.
*/
static bool
! join_clause_is_redundant(RestrictInfo *rinfo,
List *reference_list)
{
ListCell *refitem;
Index: src/include/optimizer/restrictinfo.h
===================================================================
RCS file: /cvsroot/pgsql/src/include/optimizer/restrictinfo.h,v
retrieving revision 1.43
diff -c -r1.43 restrictinfo.h
*** src/include/optimizer/restrictinfo.h 16 Apr 2009 20:42:16 -0000 1.43
--- src/include/optimizer/restrictinfo.h 9 May 2009 22:45:48 -0000
***************
*** 39,44 ****
List **otherquals);
extern List *select_nonredundant_join_clauses(PlannerInfo *root,
List *restrictinfo_list,
! List *reference_list);
#endif /* RESTRICTINFO_H */
--- 39,44 ----
List **otherquals);
extern List *select_nonredundant_join_clauses(PlannerInfo *root,
List *restrictinfo_list,
! Path *inner_path);
#endif /* RESTRICTINFO_H */
Re: HashJoin w/option to unique-ify inner rel
От:
Tom Lane <tgl@sss.pgh.pa.us>
Дата:
Robert Haas writes:
> Upon further review, it appears that a big part of this problem is
> that cost_hashjoin() doesn't understand that it needs cost semi-joins
> differently from inner or left joins.
> ...
> The planner costs the semi-join as two orders of magnitude more
> expensive than the hash-join-over-hash-aggregate, but in reality the
> semi join is only marginally slower. The planner thinks we're going
> to end up wasting a lot of time walking down long hash chains and it's
> just not true. b contains lots of duplicates but they all hash to the
> same buckets, and when an a-value hashes to that bucket it's probably
> because we've got a match, and because it's a semi-join, finding one
> match is a sufficient excuse to skip the rest of the bucket..
I spent today poking at this problem, without much success. I had
thought that the solution was basically to re-introduce something
comparable to the "joininfactor" correction that was used in 8.3 and
previous branches. However, that attempt (attached for the archives)
crashed and burned miserably. In the attached patch, we estimate the
number of outer tuples that have some match (as opposed to no match at
all) and the average number of matches for each tuple that has some
match. These estimates seem to be pretty good, at least in the simple
test case I'm using. However, it then combines the numbers into a
single work-savings factor averaged across all outer tuples:
+ /*
+ * For an outer-rel row that has no match, the executor will have to scan
+ * the whole input relation to prove that. Remembering the meaning of
+ * jselec, we therefore estimate the average scan fraction over all
+ * outer-rel rows thus:
+ */
+ scanfrac = jselec * matchfrac + (1.0 - jselec) /* times 1.0 */ ;
and it turns out this is basically missing the point altogether. The
above comment is correct in the case where we're doing a nestloop with
simple seqscan on the inner relation: we're going to have to do the
maximum amount of work for any unmatched outer tuple. But in the
hashjoin case, as you noted, it's quite likely that an unmatched outer
will result in a probe into an empty hashbucket and thus expend minimum
rather than maximum work.
The case where we are doing a nestloop with inner indexscan (using the
join clause as index condition) also costs far less than this equation
suggests. A no-match outer tuple will result in an indexscan that
selects no tuples, not one that selects lots of tuples we then have to
ignore.
BTW, the pre-8.4 coding basically applied the equivalent of "matchfrac"
for all tuples, thus getting something like the right answer for matched
tuples but being entirely bogus for unmatched ones. However, in these
cases where unmatched tuples are cheap to process, this ended up being
a fairly reasonable estimate anyway. But it was completely wrong for
cases where unmatched tuples are expensive, which is why I'd tried to
rip it out (we have had complaints about such cases in the past).
So it appears to me that instead of taking an average-case correction
as is done in this patch and the old coding, we have to explicitly model
the matched-tuple and unmatched-tuple cases separately. For hashjoins,
what I think we should do is estimate the bucket scanning cost for
unmatched tuples assuming a perfectly uniform bucket distribution,
rather than the worst-case bucket size that's used in the current code
(and is a reasonable estimate for matched tuples). This is to reflect
the fact that an unmatched outer tuple might or might not hit a
populated bucket, and which bucket it hits is probably uncorrelated with
the distribution of the inner tuples.
The problem seems to be a lot messier to solve for nestloop joins.
We have to detect whether the inner path is an indexscan using the
semijoin clause as an index qual --- if it is not, then the correct
thing is to model unmatched tuples as expensive. If it is, then I think
we can take the cost of unmatched tuples as about equal to the cost of
retrieving a single row from an indexscan with matches (which we can get
by interpolating in the path's given costs). The problem here is that the
current representation of these path structures doesn't make it cheap to
determine which joinclauses are being used as index quals. Currently
that's okay because we only do it once at the end (in createplan.c) but
if we need the information during path searching it's got to be fairly
cheap to get. So some rejiggering of the Path representation seems
called for.
I wouldn't blink at doing this during development phase, but it's a
larger change than I'd really like to be making during beta. OTOH,
what we have got now is a definite regression from the pre-8.4 behavior,
especially in the cases where unmatched tuples are cheap. Maybe there's
not much choice but to fix it now.
Comments?
regards, tom lane
Index: costsize.c
===================================================================
RCS file: /cvsroot/pgsql/src/backend/optimizer/path/costsize.c,v
retrieving revision 1.207
diff -c -r1.207 costsize.c
*** costsize.c 17 Apr 2009 15:33:33 -0000 1.207
--- costsize.c 24 Apr 2009 22:44:36 -0000
***************
*** 119,124 ****
--- 119,126 ----
RestrictInfo *rinfo,
PathKey *pathkey);
static bool cost_qual_eval_walker(Node *node, cost_qual_eval_context *context);
+ static Selectivity semi_join_fraction(JoinPath *path, PlannerInfo *root,
+ SpecialJoinInfo *sjinfo);
static double approx_tuple_count(PlannerInfo *root, JoinPath *path,
List *quals);
static void set_rel_width(PlannerInfo *root, RelOptInfo *rel);
***************
*** 1399,1408 ****
--- 1401,1414 ----
double outer_path_rows = PATH_ROWS(outer_path);
double inner_path_rows = nestloop_inner_path_rows(inner_path);
double ntuples;
+ Selectivity semi_fraction;
if (!enable_nestloop)
startup_cost += disable_cost;
+ /* Estimate cost savings fraction for JOIN_SEMI/ANTI cases */
+ semi_fraction = semi_join_fraction(path, root, sjinfo);
+
/* cost of source data */
/*
***************
*** 1429,1440 ****
run_cost += (outer_path_rows - 1) * inner_path->startup_cost;
}
run_cost += outer_path_rows *
! (inner_path->total_cost - inner_path->startup_cost);
/*
* Compute number of tuples processed (not number emitted!)
*/
! ntuples = outer_path_rows * inner_path_rows;
/* CPU costs */
cost_qual_eval(&restrict_qual_cost, path->joinrestrictinfo, root);
--- 1435,1446 ----
run_cost += (outer_path_rows - 1) * inner_path->startup_cost;
}
run_cost += outer_path_rows *
! (inner_path->total_cost - inner_path->startup_cost) * semi_fraction;
/*
* Compute number of tuples processed (not number emitted!)
*/
! ntuples = outer_path_rows * inner_path_rows * semi_fraction;
/* CPU costs */
cost_qual_eval(&restrict_qual_cost, path->joinrestrictinfo, root);
***************
*** 1485,1490 ****
--- 1491,1497 ----
outerendsel,
innerstartsel,
innerendsel;
+ Selectivity semi_fraction;
Path sort_path; /* dummy for result of cost_sort */
/* Protect some assumptions below that rowcounts aren't zero */
***************
*** 1496,1501 ****
--- 1503,1511 ----
if (!enable_mergejoin)
startup_cost += disable_cost;
+ /* Estimate cost savings fraction for JOIN_SEMI/ANTI cases */
+ semi_fraction = semi_join_fraction(&path->jpath, root, sjinfo);
+
/*
* Compute cost of the mergequals and qpquals (other restriction clauses)
* separately.
***************
*** 1718,1723 ****
--- 1728,1735 ----
* The number of tuple comparisons needed is approximately number of outer
* rows plus number of inner rows plus number of rescanned tuples (can we
* refine this?). At each one, we need to evaluate the mergejoin quals.
+ * NOTE: semi/anti join mode does not save any work here, so do NOT apply
+ * semi_fraction.
*/
startup_cost += merge_qual_cost.startup;
startup_cost += merge_qual_cost.per_tuple *
***************
*** 1730,1740 ****
* For each tuple that gets through the mergejoin proper, we charge
* cpu_tuple_cost plus the cost of evaluating additional restriction
* clauses that are to be applied at the join. (This is pessimistic since
! * not all of the quals may get evaluated at each tuple.)
*/
startup_cost += qp_qual_cost.startup;
cpu_per_tuple = cpu_tuple_cost + qp_qual_cost.per_tuple;
! run_cost += cpu_per_tuple * mergejointuples;
path->jpath.path.startup_cost = startup_cost;
path->jpath.path.total_cost = startup_cost + run_cost;
--- 1742,1753 ----
* For each tuple that gets through the mergejoin proper, we charge
* cpu_tuple_cost plus the cost of evaluating additional restriction
* clauses that are to be applied at the join. (This is pessimistic since
! * not all of the quals may get evaluated at each tuple.) Here we should
! * apply semi_fraction, since mergejointuples doesn't account for that.
*/
startup_cost += qp_qual_cost.startup;
cpu_per_tuple = cpu_tuple_cost + qp_qual_cost.per_tuple;
! run_cost += cpu_per_tuple * mergejointuples * semi_fraction;
path->jpath.path.startup_cost = startup_cost;
path->jpath.path.total_cost = startup_cost + run_cost;
***************
*** 1824,1834 ****
--- 1837,1851 ----
int num_skew_mcvs;
double virtualbuckets;
Selectivity innerbucketsize;
+ Selectivity semi_fraction;
ListCell *hcl;
if (!enable_hashjoin)
startup_cost += disable_cost;
+ /* Estimate cost savings fraction for JOIN_SEMI/ANTI cases */
+ semi_fraction = semi_join_fraction(&path->jpath, root, sjinfo);
+
/*
* Compute cost of the hashquals and qpquals (other restriction clauses)
* separately.
***************
*** 1972,1987 ****
/*
* The number of tuple comparisons needed is the number of outer tuples
! * times the typical number of tuples in a hash bucket, which is the inner
! * relation size times its bucketsize fraction. At each one, we need to
! * evaluate the hashjoin quals. But actually, charging the full qual eval
! * cost at each tuple is pessimistic, since we don't evaluate the quals
! * unless the hash values match exactly. For lack of a better idea, halve
! * the cost estimate to allow for that.
*/
startup_cost += hash_qual_cost.startup;
run_cost += hash_qual_cost.per_tuple *
! outer_path_rows * clamp_row_est(inner_path_rows * innerbucketsize) * 0.5;
/*
* For each tuple that gets through the hashjoin proper, we charge
--- 1989,2005 ----
/*
* The number of tuple comparisons needed is the number of outer tuples
! * times the typical number of tuples in a hash bucket (which is the inner
! * relation size times its bucketsize fraction) times the semi_fraction.
! * At each tuple, we need to evaluate the hashjoin quals. But actually,
! * charging the full qual eval cost at each tuple is pessimistic, since we
! * don't evaluate the quals unless the hash values match exactly. For
! * lack of a better idea, halve the cost estimate to allow for that.
*/
startup_cost += hash_qual_cost.startup;
run_cost += hash_qual_cost.per_tuple *
! outer_path_rows * clamp_row_est(inner_path_rows * innerbucketsize) *
! semi_fraction * 0.5;
/*
* For each tuple that gets through the hashjoin proper, we charge
***************
*** 1991,1997 ****
*/
startup_cost += qp_qual_cost.startup;
cpu_per_tuple = cpu_tuple_cost + qp_qual_cost.per_tuple;
! run_cost += cpu_per_tuple * hashjointuples;
path->jpath.path.startup_cost = startup_cost;
path->jpath.path.total_cost = startup_cost + run_cost;
--- 2009,2015 ----
*/
startup_cost += qp_qual_cost.startup;
cpu_per_tuple = cpu_tuple_cost + qp_qual_cost.per_tuple;
! run_cost += cpu_per_tuple * hashjointuples * semi_fraction;
path->jpath.path.startup_cost = startup_cost;
path->jpath.path.total_cost = startup_cost + run_cost;
***************
*** 2321,2326 ****
--- 2339,2483 ----
/*
+ * semi_join_fraction
+ * Determines the fraction of the inner input that a SEMI or ANTI join
+ * can be expected to scan.
+ *
+ * In a hash or nestloop SEMI/ANTI join, the executor will stop scanning
+ * inner rows as soon as it finds a match to the current outer row.
+ * We should therefore adjust some of the cost components for this effect.
+ * This function computes the fraction of the inner relation that can be
+ * expected to be scanned on average. (In a hash join, this can be taken
+ * as the fraction of the selected hash bucket, not of the whole relation,
+ * but the calculation here is the same.) Mergejoins only avoid evaluating
+ * otherquals, so the effect is much weaker for them, but it still exists.
+ *
+ * 'path' is already filled in except for the cost fields
+ * 'sjinfo' is extra info about the join for selectivity estimation
+ */
+ static Selectivity
+ semi_join_fraction(JoinPath *path, PlannerInfo *root, SpecialJoinInfo *sjinfo)
+ {
+ Selectivity scanfrac;
+ Selectivity matchfrac;
+ Selectivity avgmatch;
+ Selectivity jselec;
+ Selectivity nselec;
+ SpecialJoinInfo norm_sjinfo;
+ JoinType jointype = path->jointype;
+ List *joinquals;
+ ListCell *l;
+
+ /* Return 1.0 whenever it's not JOIN_SEMI or JOIN_ANTI */
+ if (jointype != JOIN_SEMI && jointype != JOIN_ANTI)
+ return 1.0;
+
+ /*
+ * Note: it's annoying to repeat this selectivity estimation on each call,
+ * when the joinclause list will be the same for all path pairs
+ * implementing a given join. clausesel.c will save us from the worst
+ * effects of this by caching at the RestrictInfo level; but perhaps it'd
+ * be worth finding a way to cache the results at a higher level.
+ */
+
+ /*
+ * In an ANTI join, we must ignore clauses that are "pushed down",
+ * since those won't affect the match logic. In a SEMI join, we do not
+ * distinguish joinquals from "pushed down" quals, so just use the whole
+ * restrictinfo list.
+ */
+ if (jointype == JOIN_ANTI)
+ {
+ joinquals = NIL;
+ foreach(l, path->joinrestrictinfo)
+ {
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
+
+ Assert(IsA(rinfo, RestrictInfo));
+ if (!rinfo->is_pushed_down)
+ joinquals = lappend(joinquals, rinfo);
+ }
+ }
+ else
+ joinquals = path->joinrestrictinfo;
+
+ /*
+ * Get the JOIN_SEMI or JOIN_ANTI selectivity of the join clauses.
+ */
+ jselec = clauselist_selectivity(root,
+ joinquals,
+ 0,
+ jointype,
+ sjinfo);
+
+ /*
+ * Also get the normal inner-join selectivity of the join clauses.
+ */
+ norm_sjinfo.type = T_SpecialJoinInfo;
+ norm_sjinfo.min_lefthand = path->outerjoinpath->parent->relids;
+ norm_sjinfo.min_righthand = path->innerjoinpath->parent->relids;
+ norm_sjinfo.syn_lefthand = path->outerjoinpath->parent->relids;
+ norm_sjinfo.syn_righthand = path->innerjoinpath->parent->relids;
+ norm_sjinfo.jointype = JOIN_INNER;
+ /* we don't bother trying to make the remaining fields valid */
+ norm_sjinfo.lhs_strict = false;
+ norm_sjinfo.delay_upper_joins = false;
+ norm_sjinfo.join_quals = NIL;
+
+ nselec = clauselist_selectivity(root,
+ joinquals,
+ 0,
+ JOIN_INNER,
+ &norm_sjinfo);
+
+ /* Avoid leaking a lot of ListCells */
+ if (jointype == JOIN_ANTI)
+ list_free(joinquals);
+
+ /*
+ * jselec can be interpreted as the fraction of outer-rel rows that have
+ * any matches (this is true for both SEMI and ANTI cases). And nselec
+ * is the fraction of the Cartesian product that matches. So, the
+ * average number of matches for each outer-rel row that has at least
+ * one match is 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 */
+ avgmatch = nselec * path->innerjoinpath->parent->rows / jselec;
+ else
+ avgmatch = 0;
+
+ /*
+ * For an outer-rel row that has at least one match, we can expect the
+ * inner scan to stop after a fraction 1/(avgmatch+1) of the inner rows,
+ * if the matches are evenly distributed. Since they probably aren't
+ * quite evenly distributed, we apply a fuzz factor of 2.0 to that
+ * fraction (but, of course, clamping at an upper limit of 1.0).
+ */
+ matchfrac = 2.0 / (avgmatch + 1.0);
+ matchfrac = Min(1.0, matchfrac);
+
+ /*
+ * For an outer-rel row that has no match, the executor will have to scan
+ * the whole input relation to prove that. Remembering the meaning of
+ * jselec, we therefore estimate the average scan fraction over all
+ * outer-rel rows thus:
+ */
+ scanfrac = jselec * matchfrac + (1.0 - jselec) /* times 1.0 */ ;
+
+ /* clamp the result to sane range in case of roundoff errors */
+ scanfrac = Max(scanfrac, 0.0);
+ scanfrac = Min(scanfrac, 1.0);
+
+ return scanfrac;
+ }
+
+
+ /*
* approx_tuple_count
* Quick-and-dirty estimation of the number of join rows passing
* a set of qual conditions.
Re: HashJoin w/option to unique-ify inner rel
От:
Robert Haas <robertmhaas@gmail.com>
Дата:
On Sat, Apr 25, 2009 at 6:42 AM, Grzegorz Jaskiewicz wrote: > On 25 Apr 2009, at 04:52, Robert Haas wrote: >> blow the hash-join plan out of the water anyway... but Stephen Frost >> was telling me at JDcon East that he sometimes sets it to something >> like 8GB when he's the only user on his apparently-quite-awesome >> hardware...) > > For the record, because most queries have 5-6 joins here, I always set it up > to 32MB on production. We don't have more than 100-150 connections, so it > plays well on normal 32bit machine with 4GB. > > If what you wrote about hash-join is confirmed by others, than I am pretty > much +100 for fixing it. > > (just my penny). You may find the attached patch interesting to play around with. It changes the NTUP_PER_BUCKET into a GUC called hash_load, and adds EXPLAIN support to show the number of buckets and batches. This is just for experimentation: I'm not in favor of adding Yet Another Thing for users to tune, but if you try it out, you will see (I think) that changing hash_load has a dramatic effect on the estimated cost of a hash join but a much less dramatic effect on the actual run-time. ...Robert
