public inbox for [email protected]
help / color / mirror / Atom feedFrom: Alexander Korotkov <[email protected]>
To: Andrei Lepikhov <[email protected]>
Cc: Tomas Vondra <[email protected]>
Cc: Andy Fan <[email protected]>
Cc: PostgreSQL-development <[email protected]>
Cc: Tom Lane <[email protected]>
Cc: a.rybakina <[email protected]>
Subject: Re: MergeJoin beats HashJoin in the case of multiple hash clauses
Date: Mon, 17 Feb 2025 02:34:26 +0200
Message-ID: <CAPpHfdszBt9vSNvKTLBjtAUq1-pta+nRqsiYcN=F-eGbh33hGQ@mail.gmail.com> (raw)
In-Reply-To: <[email protected]>
References: <[email protected]>
<CAKU4AWoKiogNir=ESrm6F9pUwYFDfmsoNG9w9k1MG3VUbKM0Dw@mail.gmail.com>
<[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
Hi, Andrei!
On Tue, Oct 8, 2024 at 8:00 AM Andrei Lepikhov <[email protected]> wrote:
> On 7/8/24 19:45, Andrei Lepikhov wrote:
> > On 3/11/2023 23:43, Tomas Vondra wrote:
> >> On 9/11/23 10:04, Lepikhov Andrei wrote:
> >> * Determine bucketsize fraction and MCV frequency for the inner
> >> * relation. We use the smallest bucketsize or MCV frequency estimated
> >> * for any individual hashclause; this is undoubtedly conservative.
> >>
> >> I'm sure this may lead to inflated cost for "good" cases (where the
> >> actual bucket size really is a product), which may push the optimizer to
> >> use the less efficient/slower join method.
> > Yes, It was contradictory idea, though.
> >> IMHO the only principled way forward is to get a better ndistinct
> >> estimate (which this implicitly does), perhaps by using extended
> >> statistics. I haven't tried, but I guess it'd need to extract the
> >> clauses for the inner side, and call estimate_num_groups() on it.
> > And I've done it. Sorry for so long response. This patch employs of
> > extended statistics for estimation of the HashJoin bucket_size. In
> > addition, I describe the idea in more convenient form here [1].
> > Obviously, it needs the only ndistinct to make a prediction that allows
> > to reduce computational cost of this statistic.
> Minor change to make cfbot happier.
Thank you for your work on this subject. I agree with the general
direction. While everyone has used conservative estimates for a long
time, it's better to change them only when we're sure about it.
However, I'm still not sure I get the conservatism.
if (innerbucketsize > thisbucketsize)
innerbucketsize = thisbucketsize;
if (innermcvfreq > thismcvfreq)
innermcvfreq = thismcvfreq;
IFAICS, even in the worst case (all columns are totally correlated),
the overall bucket size should be the smallest bucket size among
clauses (not the largest). And the same is true of MCV. As a mental
experiment, we can add a new clause to hash join, which is always true
because columns on both sides have the same value. In fact, it would
have almost no influence except for the cost of extracting additional
columns and the cost of executing additional operators. But in the
current model, this additional clause would completely ruin
thisbucketsize and thismcvfreq, making hash join extremely
unappealing. Should we still revise this to calculate minimum instead
of maximum?
I've slightly revised the patch. I've run pg_indent and renamed
s/saveList/origin_rinfos/g for better readability.
Also, the patch badly needs regression test coverage. We can't
include costs in expected outputs. But that could be some plans,
which previously were reliably merge joins but now become reliable
hash joins.
------
Regards,
Alexander Korotkov
Supabase
Attachments:
[application/octet-stream] v2-0001-Use-extended-statistics-for-precise-estimation-of.patch (8.3K, ../CAPpHfdszBt9vSNvKTLBjtAUq1-pta+nRqsiYcN=F-eGbh33hGQ@mail.gmail.com/2-v2-0001-Use-extended-statistics-for-precise-estimation-of.patch)
download | inline diff:
From 05aade32c8c50fcb748cc86ddb3bb25b73787c8c Mon Sep 17 00:00:00 2001
From: "Andrei V. Lepikhov" <[email protected]>
Date: Mon, 13 May 2024 16:15:02 +0700
Subject: [PATCH v2] Use extended statistics for precise estimation of bucket
size in hash join.
Recognizing the real-life complexity where columns in the table often have
functional dependencies, PostgreSQL's estimation of the number of distinct
values over a set of columns can be underestimated (or much rarely,
overestimated) when dealing with multi-clause JOIN.
In the case of hash join, it can end up with a small number of predicted hash
buckets and, as a result, picking non-optimal merge join.
To improve the situation, we introduce one additional stage of bucket size
estimation - having two or more join clauses estimator lookup for extended
statistics and use it for multicolumn estimation.
Clauses are grouped into lists, each containing expressions referencing the
same relation. The result of the multicolumn estimation made over such a list
is combined with others according to the caller's logic.
Clauses that are not estimated are returned to the caller for further
estimation.
---
src/backend/optimizer/path/costsize.c | 12 +-
src/backend/utils/adt/selfuncs.c | 176 ++++++++++++++++++++++++++
src/include/utils/selfuncs.h | 4 +
3 files changed, 191 insertions(+), 1 deletion(-)
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 73d78617009..256568d05a2 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -4339,9 +4339,19 @@ final_cost_hashjoin(PlannerInfo *root, HashPath *path,
}
else
{
+ List *otherclauses;
+
innerbucketsize = 1.0;
innermcvfreq = 1.0;
- foreach(hcl, hashclauses)
+
+ /* At first, try to estimate bucket size using extended statistics. */
+ otherclauses = estimate_multivariate_bucketsize(root,
+ inner_path->parent,
+ hashclauses,
+ &innerbucketsize);
+
+ /* Pass through the remaining clauses */
+ foreach(hcl, otherclauses)
{
RestrictInfo *restrictinfo = lfirst_node(RestrictInfo, hcl);
Selectivity thisbucketsize;
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index d3d1e485bb2..b826730acbe 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -3765,6 +3765,182 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
return numdistinct;
}
+/*
+ * Try to estimate the bucket size of the hash join inner side when the join
+ * condition contains two or more clauses by employing extended statistics.
+ *
+ * The main idea of this approach is that the distinct value generated by
+ * multivariate estimation on two or more columns would provide less bucket size
+ * than estimation on one separate column.
+ *
+ * IMPORTANT: It is crucial to synchronise the approach of combining different
+ * estimations with the caller's method.
+ * Return a list of clauses that didn't fetch any extended statistics.
+ */
+List *
+estimate_multivariate_bucketsize(PlannerInfo *root, RelOptInfo *inner,
+ List *hashclauses,
+ Selectivity *innerbucketsize)
+{
+ List *clauses = list_copy(hashclauses);
+ List *otherclauses = NIL;
+ double ndistinct = 1.0;
+
+ if (list_length(hashclauses) <= 1)
+
+ /*
+ * Nothing to do for a single clause. Could we employ univariate
+ * extended stat here?
+ */
+ return hashclauses;
+
+ while (clauses != NIL)
+ {
+ ListCell *lc;
+ int relid = -1;
+ List *varinfos = NIL;
+ List *origin_rinfos = NIL;
+ double mvndistinct;
+ List *origin_varinfos;
+ int group_relid = -1;
+ RelOptInfo *group_rel = NULL;
+ ListCell *lc1,
+ *lc2;
+
+ /*
+ * Find clauses, referencing the same single base relation and try to
+ * estimate such a group with extended statistics. Create varinfo for
+ * an approved clause, push it to otherclauses, if it can't be
+ * estimated here or ignore to process at the next iteration.
+ */
+ foreach(lc, clauses)
+ {
+ RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
+ Node *expr;
+ Relids relids;
+ GroupVarInfo *varinfo;
+
+ /*
+ * Find the inner side of the join which we need to estimate the
+ * number of buckets. Use outer_is_left because the
+ * clause_sides_match_join routine has called on hash clauses.
+ */
+ relids = rinfo->outer_is_left ?
+ rinfo->right_relids : rinfo->left_relids;
+ expr = rinfo->outer_is_left ?
+ get_rightop(rinfo->clause) : get_leftop(rinfo->clause);
+
+ if (bms_get_singleton_member(relids, &relid) &&
+ root->simple_rel_array[relid]->statlist != NIL)
+ {
+ /*
+ * This inner-side expression references only one relation.
+ * Extended statistics on this clause can exist.
+ */
+
+ if (group_relid < 0)
+ {
+ RangeTblEntry *rte = root->simple_rte_array[relid];
+
+ if (!rte || (rte->relkind != RELKIND_RELATION &&
+ rte->relkind != RELKIND_MATVIEW &&
+ rte->relkind != RELKIND_FOREIGN_TABLE &&
+ rte->relkind != RELKIND_PARTITIONED_TABLE))
+ {
+ /* Extended statistics can't exist in principle */
+ otherclauses = lappend(otherclauses, rinfo);
+ clauses = foreach_delete_current(clauses, lc);
+ continue;
+ }
+
+ group_relid = relid;
+ group_rel = root->simple_rel_array[relid];
+ }
+ else if (group_relid != relid)
+
+ /*
+ * Being in the group forming state we don't need other
+ * clauses.
+ */
+ continue;
+
+ varinfo = (GroupVarInfo *) palloc(sizeof(GroupVarInfo));
+ varinfo->var = expr;
+ varinfo->rel = root->simple_rel_array[relid];
+ varinfo->ndistinct = 0.0;
+ varinfo->isdefault = false;
+ varinfos = lappend(varinfos, varinfo);
+
+ /*
+ * Remember the link to RestrictInfo for the case the clause
+ * is failed to be estimated.
+ */
+ origin_rinfos = lappend(origin_rinfos, rinfo);
+ }
+ else
+ /* This clause can't be estimated with extended statistics */
+ otherclauses = lappend(otherclauses, rinfo);
+
+ clauses = foreach_delete_current(clauses, lc);
+ }
+
+ if (list_length(varinfos) < 2)
+ {
+ /*
+ * Multivariate statistics doesn't apply to single column except
+ * expressions, but it has not implemented yet.
+ */
+ otherclauses = list_concat(otherclauses, origin_rinfos);
+ list_free_deep(varinfos);
+ list_free(origin_rinfos);
+ continue;
+ }
+
+ Assert(group_rel != NULL);
+
+ /* Let's employ extended statistics. */
+ origin_varinfos = varinfos;
+ for (;;)
+ {
+ bool estimated = estimate_multivariate_ndistinct(root,
+ group_rel,
+ &varinfos,
+ &mvndistinct);
+
+ if (!estimated)
+ break;
+
+ /*
+ * We've got an estimation. Use ndistinct value in consistent way
+ * - according to the caller's logic (see final_cost_hashjoin).
+ */
+ if (ndistinct < mvndistinct)
+ ndistinct = mvndistinct;
+ Assert(ndistinct >= 1.0);
+ }
+
+ Assert(list_length(origin_varinfos) == list_length(origin_rinfos));
+
+ /*
+ * Remove already estimated clauses from the origin_rinfos
+ */
+ forboth(lc1, origin_varinfos, lc2, origin_rinfos)
+ {
+ GroupVarInfo *vinfo = lfirst(lc1);
+
+ if (!list_member_ptr(varinfos, vinfo))
+ /* Already estimated */
+ continue;
+
+ /* Can't be estimated here - push to the returning list */
+ otherclauses = lappend(otherclauses, lfirst(lc2));
+ }
+ }
+
+ *innerbucketsize = 1.0 / ndistinct;
+ return otherclauses;
+}
+
/*
* Estimate hash bucket statistics when the specified expression is used
* as a hash key for the given number of buckets.
diff --git a/src/include/utils/selfuncs.h b/src/include/utils/selfuncs.h
index b5e95c0ff61..c845da4c7cc 100644
--- a/src/include/utils/selfuncs.h
+++ b/src/include/utils/selfuncs.h
@@ -217,6 +217,10 @@ extern double estimate_num_groups(PlannerInfo *root, List *groupExprs,
double input_rows, List **pgset,
EstimationInfo *estinfo);
+extern List *estimate_multivariate_bucketsize(PlannerInfo *root,
+ RelOptInfo *inner,
+ List *hashclauses,
+ Selectivity *innerbucketsize);
extern void estimate_hash_bucket_stats(PlannerInfo *root,
Node *hashkey, double nbuckets,
Selectivity *mcv_freq,
--
2.39.5 (Apple Git-154)
view thread (4+ messages)
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected], [email protected], [email protected], [email protected], [email protected], [email protected]
Subject: Re: MergeJoin beats HashJoin in the case of multiple hash clauses
In-Reply-To: <CAPpHfdszBt9vSNvKTLBjtAUq1-pta+nRqsiYcN=F-eGbh33hGQ@mail.gmail.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox