public inbox for [email protected]
help / color / mirror / Atom feedFrom: prankware <[email protected]>
To: [email protected]
Cc: Laurenz Albe <[email protected]>
Cc: [email protected]
Subject: Re: COALESCE patch
Date: Fri, 10 Jul 2026 15:54:27 +0300
Message-ID: <CAF=hKRDQRfXjpfqA_53Y_VNYY5YzFk1mswTHZ1kdBU6Dwj4vpA@mail.gmail.com> (raw)
In-Reply-To: <[email protected]>
References: <CAF=hKRBhFDzdSomCM5XGFzRBpEAmh-fQyt-6vb4Ji0pZs=--7A@mail.gmail.com>
<CAF=hKRCX9sf5Occjdft51sWwztW_MyRN-bnVvs05yeCbBLMPNQ@mail.gmail.com>
<[email protected]>
Thanks for the review — the test cases were very helpful.
You're right that v1 didn't improve the coalesce(col, const) case. The
reason is that a comparison of two constants got the default 0.005
instead of its real result, and joins with a constant on both sides
were skipped entirely.
v2 (attached) fixes both, and these four examples now estimate close
to the actual row counts.
Regards,
Egor Savelev,
Tantor Labs LLC,
https://tantorlabs.com
пт, 10 июл. 2026 г. в 12:27, Laurenz Albe <[email protected]>:
>
> On Tue, 2026-06-30 at 16:48 +0300, prankware wrote:
>
> > The planner ignores column statistics when an equality has a COALESCE
> > expression on one side. For a clause like COALESCE(a, b) = $1, or a join on
> > COALESCE(t1.a, t1.b) = COALESCE(t2.c, t2.d), there are no statistics on the
> > COALESCE node itself, so eqsel() and eqjoinsel() return the generic 0.005
> > estimate while the per-column stats for a, b, c and d sit unused. The only way
> > around this today is an expression index or extended statistics on that exact
> > expression, which doesn't scale across many different COALESCE clauses.
> > estimate_hash_bucket_stats() has the same gap: a COALESCE hash key gets a
> > default ndistinct and therefore a default bucket size. Since these expressions
> > are common in joins and filters over nullable or fallback columns, the default
> > estimate can be far enough off to flip the join order or join method.
> >
> > The idea is to estimate straight from the existing per-column stats, with no
> > extra statistics object. COALESCE(arg_1, ..., arg_n) returns arg_i only when
> > arg_1 .. arg_{i-1} are all NULL, so the chance of reaching branch i is the
> > product of stanullfrac over the earlier branches. Selectivity of
> > COALESCE(l_1..l_M) = COALESCE(r_1..r_N) is then the sum over branch pairs of
> > P(reach l_i) * P(reach r_j) * sel(l_i = r_j), and each sel(l_i = r_j) is a
> > recursive call back into eqsel()/eqjoinsel(). A non-COALESCE side is treated as
> > a one-branch list, so scalar COALESCE(a, b) = const falls out of the same code,
> > and the same decomposition feeds estimate_hash_bucket_stats(). If any branch is
> > missing stats, the code bails and today's behavior is unchanged.
> >
> > Feedback is welcome.
>
> I think the idea is good, and the performance cost is incurred only when
> coalesce() expressions are present. I am a bit worried about the execution
> time for queries that join two tables over lengthy coalesce clauses, as the
> cost is O(n*m) because of the sum. But I think that such queries are extremely
> rare, so I don't worry too much.
>
> I found that the estimates are good if I use expressions like
> "coalesce(col1, col2)" in my query, but the estimates are as bad as before
> with the common case of "coalesce(col, constant)":
>
> CREATE TABLE b (col1 integer);
>
> /* three quarters NULL, the rest evenly distributed */
> INSERT INTO b
> SELECT CASE WHEN random() >= 0.75 THEN random() * 1000 + 1 END
> FROM generate_series(1, 10000);
>
> VACUUM (ANALYZE) b;
>
> /* force a hash join regardless of the estimates */
> SET work_mem = '512MB';
> SET enable_mergejoin = off;
> SET enable_nestloop = off;
>
>
> EXPLAIN (ANALYZE, SUMMARY OFF, BUFFERS OFF)
> SELECT *
> FROM b AS b1
> JOIN b AS b2 ON coalesce(b1.col1, 0) = coalesce(b2.col1, 0);
>
> Hash Join (... rows=500000 ...) (actual ... rows=55125006.00 ...)
> Hash Cond: (COALESCE(b1.col1, 0) = COALESCE(b2.col1, 0))
> -> Seq Scan on b b1 (... rows=10000 ...) (actual ... rows=10000.00 ..)
> -> Hash (... rows=10000 ...) (actual ... rows=10000.00 ...)
> Buckets: 16384 Batches: 1 Memory Usage: 451kB
> -> Seq Scan on b b2 (... rows=10000 ...) (actual ... rows=10000.00 ...)
>
> EXPLAIN (ANALYZE, SUMMARY OFF, BUFFERS OFF)
> SELECT *
> FROM b AS b1
> JOIN b AS b2 ON coalesce(b1.col1, 0) = coalesce(b2.col1, 1);
>
> Hash Join (... rows=500000 ...) (actual ... rows=16654.00 ...)
> Hash Cond: (COALESCE(b1.col1, 0) = COALESCE(b2.col1, 1))
> -> Seq Scan on b b1 (... rows=10000 ...) (actual ... rows=10000.00 ...)
> -> Hash (... rows=10000 ...) (actual ... rows=10000.00 ...)
> Buckets: 16384 Batches: 1 Memory Usage: 451kB
> -> Seq Scan on b b2 (... rows=10000 ...) (actual ... rows=10000.00 ...)
>
>
> EXPLAIN (ANALYZE, SUMMARY OFF, BUFFERS OFF)
> SELECT * FROM b WHERE coalesce(col1, 0) = 0;
>
> Seq Scan on b (... rows=40 ...) (actual ... rows=7424.00 ...)
> Filter: (COALESCE(col1, 0) = 0)
> Rows Removed by Filter: 2576
>
> EXPLAIN (ANALYZE, SUMMARY OFF, BUFFERS OFF)
> SELECT * FROM b WHERE coalesce(col1, 1) = 0;
>
> Seq Scan on b (... rows=40 ...) (actual ... rows=0.00 ...)
> Filter: (COALESCE(col1, 1) = 0)
> Rows Removed by Filter: 10000
>
>
> I think that the patch would be much more useful if it could improve
> such estimates.
>
> Yours,
> Laurenz Albe
Attachments:
[text/x-patch] v2-0001-Coalesce-eqsel-eqjoinsel.patch (13.1K, ../CAF=hKRDQRfXjpfqA_53Y_VNYY5YzFk1mswTHZ1kdBU6Dwj4vpA@mail.gmail.com/2-v2-0001-Coalesce-eqsel-eqjoinsel.patch)
download | inline diff:
From 553eb9b30376a59e06a91a41ada6d9c6b7bd5a4d Mon Sep 17 00:00:00 2001
From: prankware <[email protected]>
Date: Fri, 10 Jul 2026 13:31:07 +0300
Subject: [PATCH v2] Coalesce eqsel eqjoinsel
---
src/backend/utils/adt/selfuncs.c | 474 +++++++++++++++++++++++++++++--
1 file changed, 444 insertions(+), 30 deletions(-)
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index 4ee70ef0b70..7e305da357e 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -304,6 +304,288 @@ eqsel(PG_FUNCTION_ARGS)
PG_RETURN_FLOAT8((float8) eqsel_internal(fcinfo, false));
}
+/*
+ * Extract the estimable branches of a CoalesceExpr. Strips RelabelType,
+ * skips NULL-constant branches, and stops at the first non-NULL Const
+ * (setting *terminates_with_const). Returns false if the expression
+ * is constant or no branches remain.
+ */
+static bool
+match_coalesce_join_side(Node *side,
+ List **stripped_args,
+ bool *terminates_with_const)
+{
+ CoalesceExpr *c;
+ ListCell *lc;
+ List *result = NIL;
+
+ *terminates_with_const = false;
+ *stripped_args = NIL;
+
+ if (side == NULL || !IsA(side, CoalesceExpr))
+ return false;
+
+ c = (CoalesceExpr *) side;
+
+ if (list_length(c->args) < 2)
+ return false;
+
+ foreach(lc, c->args)
+ {
+ Node *arg = (Node *) lfirst(lc);
+
+ /* strip RelabelType */
+ while (arg && IsA(arg, RelabelType))
+ arg = (Node *) ((RelabelType *) arg)->arg;
+
+ /* leading Const makes COALESCE itself constant */
+ if (arg == NULL || (lc == list_head(c->args) && IsA(arg, Const)))
+ {
+ list_free(result);
+ return false;
+ }
+
+ if (IsA(arg, Const))
+ {
+ if (((Const *) arg)->consttype != c->coalescetype)
+ {
+ list_free(result);
+ return false;
+ }
+
+ /* NULL Const is skipped */
+ if (!((Const *) arg)->constisnull)
+ {
+ result = lappend(result, arg);
+ *terminates_with_const = true;
+ break;
+ }
+ }
+ else
+ {
+ if (exprType(arg) != c->coalescetype)
+ {
+ list_free(result);
+ return false;
+ }
+ result = lappend(result, arg);
+ }
+ }
+
+ if (result == NIL)
+ return false;
+
+ *stripped_args = result;
+ return true;
+}
+
+/*
+ * Fill prefix_probs[i] = Prod_{j<i} stanullfrac(args[j]) for a stripped
+ * COALESCE arg list. Returns false if any non-Const arg lacks statistics.
+ */
+static bool
+get_coalesce_prefix_probs(PlannerInfo *root, List *args, double *prefix_probs)
+{
+ ListCell *lc;
+ int i = 0;
+ double prefix = 1.0;
+
+ foreach(lc, args)
+ {
+ Node *arg = (Node *) lfirst(lc);
+
+ prefix_probs[i++] = prefix;
+
+ /* nothing to fold for the last arg or a Const */
+ if (lnext(args, lc) == NULL || IsA(arg, Const))
+ continue;
+
+ {
+ VariableStatData vd;
+ double p_i;
+
+ examine_variable(root, arg, 0, &vd);
+ if (!HeapTupleIsValid(vd.statsTuple))
+ {
+ ReleaseVariableStats(vd);
+ return false;
+ }
+ p_i = ((Form_pg_statistic) GETSTRUCT(vd.statsTuple))->stanullfrac;
+ ReleaseVariableStats(vd);
+
+ if (p_i < 0.0 || p_i > 1.0)
+ return false;
+
+ prefix *= p_i;
+ }
+ }
+
+ return true;
+}
+
+/*
+ * Common guts of eqsel/eqjoinsel when one or both operands are CoalesceExpr.
+ * Computes:
+ *
+ * sel(COALESCE(l_1,...,l_M) = COALESCE(r_1,...,r_N)) =
+ * Sum_{i,j} P_L(reach i) * P_R(reach j) * sel(l_i = r_j)
+ *
+ * where P(reach i) = Prod_{j<i} stanullfrac(arg_j). A non-COALESCE operand
+ * is treated as a single-element list.
+ */
+static bool
+try_coalesce_eq(PG_FUNCTION_ARGS, double *selec_out)
+{
+ PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
+ Oid operator = PG_GETARG_OID(1);
+ List *args = (List *) PG_GETARG_POINTER(2);
+ bool is_eqjoin = (fcinfo->flinfo != NULL &&
+ fcinfo->flinfo->fn_oid == F_EQJOINSEL);
+ SpecialJoinInfo *sjinfo = is_eqjoin ?
+ (SpecialJoinInfo *) PG_GETARG_POINTER(4) : NULL;
+ int eqsel_varRelid = is_eqjoin ? 0 : PG_GETARG_INT32(3);
+ Oid collation = PG_GET_COLLATION();
+ Node *left;
+ Node *right;
+ List *left_args = NIL;
+ List *right_args = NIL;
+ bool left_is_coalesce;
+ bool right_is_coalesce;
+ bool left_term_const = false;
+ bool right_term_const = false;
+ double *left_prefix;
+ double *right_prefix;
+ double acc_selec = 0.0;
+ ListCell *llc;
+ int li;
+
+ if (list_length(args) != 2)
+ return false;
+
+ left = (Node *) linitial(args);
+ right = (Node *) lsecond(args);
+
+ left_is_coalesce = match_coalesce_join_side(left, &left_args,
+ &left_term_const);
+ right_is_coalesce = match_coalesce_join_side(right, &right_args,
+ &right_term_const);
+
+ if (!left_is_coalesce && !right_is_coalesce)
+ return false;
+
+ /* one side is a CoalesceExpr that match_coalesce_join_side rejected */
+ if ((left_is_coalesce && !right_is_coalesce && IsA(right, CoalesceExpr)) ||
+ (right_is_coalesce && !left_is_coalesce && IsA(left, CoalesceExpr)))
+ {
+ list_free(left_args);
+ list_free(right_args);
+ return false;
+ }
+
+ if (!left_is_coalesce)
+ {
+ left_args = list_make1(left);
+ left_term_const = IsA(left, Const);
+ }
+ if (!right_is_coalesce)
+ {
+ right_args = list_make1(right);
+ right_term_const = IsA(right, Const);
+ }
+
+ left_prefix = (double *) palloc(sizeof(double) * list_length(left_args));
+ right_prefix = (double *) palloc(sizeof(double) * list_length(right_args));
+
+ if (!get_coalesce_prefix_probs(root, left_args, left_prefix) ||
+ !get_coalesce_prefix_probs(root, right_args, right_prefix))
+ {
+ pfree(left_prefix);
+ pfree(right_prefix);
+ list_free(left_args);
+ list_free(right_args);
+ return false;
+ }
+
+ li = 0;
+ foreach(llc, left_args)
+ {
+ Node *larg = (Node *) lfirst(llc);
+ bool lconst = IsA(larg, Const);
+ ListCell *rlc;
+ int ri = 0;
+
+ if (left_prefix[li] < 1.0e-12)
+ break;
+
+ foreach(rlc, right_args)
+ {
+ Node *rarg = (Node *) lfirst(rlc);
+ bool rconst = IsA(rarg, Const);
+ Selectivity contrib;
+
+ if (right_prefix[ri] < 1.0e-12)
+ break;
+
+ if (lconst && rconst)
+ {
+ Const *lc = (Const *) larg;
+ Const *rc = (Const *) rarg;
+
+ if (lc->constisnull || rc->constisnull)
+ contrib = 0.0;
+ else
+ contrib = DatumGetBool(OidFunctionCall2Coll(get_opcode(operator),
+ collation,
+ lc->constvalue,
+ rc->constvalue)) ? 1.0 : 0.0;
+ }
+ else
+ {
+ List *sub_args = list_make2(copyObject(larg),
+ copyObject(rarg));
+
+ if (!is_eqjoin || lconst || rconst)
+ {
+ contrib = DatumGetFloat8(DirectFunctionCall4Coll(eqsel,
+ collation,
+ PointerGetDatum(root),
+ ObjectIdGetDatum(operator),
+ PointerGetDatum(sub_args),
+ Int32GetDatum(eqsel_varRelid)));
+ }
+ else
+ {
+ contrib = DatumGetFloat8(DirectFunctionCall5Coll(eqjoinsel,
+ collation,
+ PointerGetDatum(root),
+ ObjectIdGetDatum(operator),
+ PointerGetDatum(sub_args),
+ Int16GetDatum(JOIN_INNER),
+ PointerGetDatum(sjinfo)));
+ }
+
+ list_free(sub_args);
+ }
+
+ CLAMP_PROBABILITY(contrib);
+ acc_selec += left_prefix[li] * right_prefix[ri] * contrib;
+
+ ri++;
+ }
+
+ li++;
+ }
+
+ pfree(left_prefix);
+ pfree(right_prefix);
+ list_free(left_args);
+ list_free(right_args);
+
+ CLAMP_PROBABILITY(acc_selec);
+ *selec_out = acc_selec;
+ return true;
+}
+
/*
* Common code for eqsel() and neqsel()
*/
@@ -320,6 +602,9 @@ eqsel_internal(PG_FUNCTION_ARGS, bool negate)
bool varonleft;
double selec;
+ if (try_coalesce_eq(fcinfo, &selec))
+ return selec;
+
/*
* When asked about <>, we do the estimation using the corresponding =
* operator, then convert to <> via "1.0 - eq_selectivity - nullfrac".
@@ -2420,6 +2705,9 @@ eqjoinsel(PG_FUNCTION_ARGS)
bool join_is_reversed;
RelOptInfo *inner_rel;
+ if (try_coalesce_eq(fcinfo, &selec))
+ PG_RETURN_FLOAT8((float8) selec);
+
get_join_variables(root, args, sjinfo,
&vardata1, &vardata2, &join_is_reversed);
@@ -4376,6 +4664,154 @@ estimate_multivariate_bucketsize(PlannerInfo *root, RelOptInfo *inner,
return otherclauses;
}
+/*
+ * Most-common-value frequency for vardata. Falls back to 1/ntuples when
+ * only a histogram slot is present. Returns 0.0 if no statistics are
+ * available.
+ */
+static void
+get_variable_mcv_freq(VariableStatData *vardata, Selectivity *mcv_freq)
+{
+ AttStatsSlot sslot;
+
+ *mcv_freq = 0.0;
+
+ if (!HeapTupleIsValid(vardata->statsTuple))
+ return;
+
+ if (get_attstatsslot(&sslot, vardata->statsTuple,
+ STATISTIC_KIND_MCV, InvalidOid,
+ ATTSTATSSLOT_NUMBERS))
+ {
+ if (sslot.nnumbers > 0)
+ *mcv_freq = sslot.numbers[0];
+ free_attstatsslot(&sslot);
+ }
+ else if (get_attstatsslot(&sslot, vardata->statsTuple,
+ STATISTIC_KIND_HISTOGRAM, InvalidOid,
+ 0))
+ {
+ /* no MCVs but histogram present: column is likely unique */
+ if (vardata->rel && vardata->rel->tuples > 0)
+ *mcv_freq = 1.0 / vardata->rel->tuples;
+ }
+}
+
+/*
+ * Estimate bucket stats for a CoalesceExpr hashkey when examine_variable()
+ * returned a default ndistinct. Uses per-branch ndistinct and mcv_freq,
+ * weighted by null fall-through probability.
+ */
+static bool
+hash_bucket_stats_coalesce_dispatch(PlannerInfo *root,
+ Node *hashkey,
+ double nbuckets,
+ Selectivity *mcv_freq,
+ Selectivity *bucketsize_frac)
+{
+ List *stripped_args;
+ bool terminates_with_const;
+ double *prefix;
+ int nargs;
+ int i;
+ ListCell *lc;
+ double nd_mix = 0.0;
+ Selectivity mcv_mix = 0.0;
+ double rel_rows_proxy = 0.0;
+ double rel_tuples_proxy = 0.0;
+ double estfract;
+
+ if (!match_coalesce_join_side(hashkey, &stripped_args, &terminates_with_const))
+ return false;
+
+ nargs = list_length(stripped_args);
+ prefix = (double *) palloc(sizeof(double) * nargs);
+
+ if (!get_coalesce_prefix_probs(root, stripped_args, prefix))
+ {
+ pfree(prefix);
+ list_free(stripped_args);
+ return false;
+ }
+
+ i = 0;
+ foreach(lc, stripped_args)
+ {
+ Node *arg = (Node *) lfirst(lc);
+
+ if (IsA(arg, Const))
+ {
+ mcv_mix = Max(mcv_mix, prefix[i]);
+ if (prefix[i] > 0.0)
+ nd_mix += 1.0;
+ }
+ else
+ {
+ VariableStatData vd;
+ double nd_i;
+ bool isdefault;
+ Selectivity mcv_i;
+
+ examine_variable(root, arg, 0, &vd);
+ nd_i = get_variable_numdistinct(&vd, &isdefault);
+
+ if (isdefault)
+ {
+ ReleaseVariableStats(vd);
+ pfree(prefix);
+ list_free(stripped_args);
+ return false;
+ }
+
+ get_variable_mcv_freq(&vd, &mcv_i);
+
+ nd_mix = Max(nd_mix, nd_i);
+ mcv_mix = Max(mcv_mix, prefix[i] * mcv_i);
+
+ if (i == 0 && vd.rel && vd.rel->tuples > 0)
+ {
+ rel_rows_proxy = vd.rel->rows;
+ rel_tuples_proxy = vd.rel->tuples;
+ }
+
+ ReleaseVariableStats(vd);
+ }
+
+ i++;
+ }
+
+ pfree(prefix);
+ list_free(stripped_args);
+
+ if (rel_tuples_proxy > 0.0)
+ {
+ nd_mix *= rel_rows_proxy / rel_tuples_proxy;
+ nd_mix = clamp_row_est(nd_mix);
+ }
+
+ if (nd_mix <= 0.0)
+ return false;
+
+ if (nd_mix > nbuckets)
+ estfract = 1.0 / nbuckets;
+ else
+ estfract = 1.0 / nd_mix;
+
+ CLAMP_PROBABILITY(mcv_mix);
+ *mcv_freq = Max(*mcv_freq, mcv_mix);
+ CLAMP_PROBABILITY(*mcv_freq);
+ estfract = Max(estfract, *mcv_freq);
+
+ if (estfract < 1.0e-6)
+ estfract = 1.0e-6;
+ else if (estfract > 1.0)
+ estfract = 1.0;
+
+ *bucketsize_frac = (Selectivity) estfract;
+
+ return true;
+}
+
/*
* Estimate hash bucket statistics when the specified expression is used
* as a hash key for the given number of buckets.
@@ -4429,43 +4865,21 @@ estimate_hash_bucket_stats(PlannerInfo *root, Node *hashkey, double nbuckets,
double estfract,
ndistinct;
bool isdefault;
- AttStatsSlot sslot;
examine_variable(root, hashkey, 0, &vardata);
- /* Initialize *mcv_freq to "unknown" */
- *mcv_freq = 0.0;
-
- /* Look up the frequency of the most common value, if available */
- if (HeapTupleIsValid(vardata.statsTuple))
- {
- if (get_attstatsslot(&sslot, vardata.statsTuple,
- STATISTIC_KIND_MCV, InvalidOid,
- ATTSTATSSLOT_NUMBERS))
- {
- /*
- * The first MCV stat is for the most common value.
- */
- if (sslot.nnumbers > 0)
- *mcv_freq = sslot.numbers[0];
- free_attstatsslot(&sslot);
- }
- else if (get_attstatsslot(&sslot, vardata.statsTuple,
- STATISTIC_KIND_HISTOGRAM, InvalidOid,
- 0))
- {
- /*
- * If there are no recorded MCVs, but we do have a histogram, then
- * assume that ANALYZE determined that the column is unique.
- */
- if (vardata.rel && vardata.rel->tuples > 0)
- *mcv_freq = 1.0 / vardata.rel->tuples;
- }
- }
+ get_variable_mcv_freq(&vardata, mcv_freq);
/* Get number of distinct values */
ndistinct = get_variable_numdistinct(&vardata, &isdefault);
+ if (isdefault && hash_bucket_stats_coalesce_dispatch(root, hashkey, nbuckets,
+ mcv_freq, bucketsize_frac))
+ {
+ ReleaseVariableStats(vardata);
+ return;
+ }
+
/*
* If ndistinct isn't real, punt. We normally return 0.1, but if the
* mcv_freq is known to be even higher than that, use it instead.
base-commit: dfce19c2300ab00a8c41386e49dfdd6a3c8edae9
--
2.43.0
view thread (43+ 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]
Subject: Re: COALESCE patch
In-Reply-To: <CAF=hKRDQRfXjpfqA_53Y_VNYY5YzFk1mswTHZ1kdBU6Dwj4vpA@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