Add support for (Var op Var) clause in extended MCV statistics
Hi hackers,
I'd like to submit a patch that improves the estimated rows for queries
containing (Var op Var) clauses by applying extended MCV statistics.
*New functions:*
* mcv_clauselist_selectivity_var_op_var() - calculates the selectivity
for (Var op Var) clauses.
* is_opclause_var_op_var() - Checks whether a clause is of the (Var op
Var) form.
*Implementation Details:*
* A new 'if' statement was added to the 'clause_selectivity_ext()'
function to handle (Var op Var) clauses. This allows the process to
locate matching MCV extended statistics and calculate selectivity
using the newly introduced function.
* Additionally, I added 'if' statement
in statext_is_compatible_clause_internal() function to determine
which columns are included in the clause, find matching extended
statistics, and then calculate selectivity through the new function.
I did the same in mcv_get_match_bitmap() to check what values are
true for (Var op Var).
* To support this, I created a new enum type to differentiate between
OR/AND and (Var op Var) clauses.
*Examples:*
create table t (a int, b int);
insert into t select mod(i,10), mod(i,10)+1 from
generate_series(1,100000) s(i);
analyze t;
explain select * from t where a < b;
`
Estimated: 33333
Actual: 100000
explain select * from t where a > b;
`
Estimated: 33333
Actual: 100000
create statistics s (mcv) on a,b from t;
analyze t;
explain select * from t where a < b;
`
Estimated without patch: 33333
Estimated with patch: 100000
Actual: 100000
explain select * from t where a > b;
`
Estimated without patch: 33333
Estimated with patch: 100000
Actual: 100000
If you want to see more examples, see regress tests in the patch.
*Previous thread:*
This feature was originally developed two years ago in [1]/messages/by-id/9e0a12e0-c05f-b193-ed3d-fe88bc1e5fe1@enterprisedb.com, and at that
time, the approach was almost the same. My implementation uses dedicated
functions and 'if' statements directly for better readability and
maintainability. Additionally, there was a bug in the previous approach
that has been resolved with my patch. Here’s an example of the bug and
its fix:
CREATE TABLE foo (a int, b int);
INSERT INTO foo SELECT x/10+1, x FROM generate_series(1,10000) g(x);
ANALYZE foo;
EXPLAIN ANALYZE SELECT * FROM foo WHERE a = 1 OR (b > 0 AND b < 10);
`
Estimated: 18
Actual: 9
CREATE STATISTICS foo_s (mcv) ON a,b FROM foo;
ANALYZE foo;
EXPLAIN ANALYZE SELECT * FROM foo WHERE a = 1 OR (b > 0 AND b < 10);
`
Estimated previous patch: 18
Estimated current patch: 9
Actual: 9
[1]: /messages/by-id/9e0a12e0-c05f-b193-ed3d-fe88bc1e5fe1@enterprisedb.com
/messages/by-id/9e0a12e0-c05f-b193-ed3d-fe88bc1e5fe1@enterprisedb.com
I look forward to any feedback or suggestions from the community.
Best regars,
Ilia Evdokimov
Tantor Labs LLC.
Attachments:
v1-Add-support-for-Var-op-Var-clause-in-extended-MCV-st.patchtext/x-patch; charset=UTF-8; name=v1-Add-support-for-Var-op-Var-clause-in-extended-MCV-st.patchDownload
From fd468972f0ce27291523a28fdf0d9966c2fdf6e1 Mon Sep 17 00:00:00 2001
From: Ilia Evdokimov <ilya.evdokimov@tantorlabs.ru>
Date: Sat, 10 Aug 2024 14:35:25 +0300
Subject: [PATCH] Add support for (Var op Var) clause in extended MCV
statistics
Added a new leaf to the existing clauses tree, allowing the calculation
of selectivity specifically for (Var op Var) clauses. The new function
for this selectivity calculation has been integratedinto
the extended statistics mechanism, ensuring accurate application
during query planning.
---
src/backend/optimizer/path/clausesel.c | 25 +-
src/backend/statistics/README | 6 +-
src/backend/statistics/README.mcv | 6 +-
src/backend/statistics/extended_stats.c | 108 +++-
src/backend/statistics/mcv.c | 184 ++++--
.../statistics/extended_stats_internal.h | 6 +
src/include/statistics/statistics.h | 11 +-
src/test/regress/expected/stats_ext.out | 553 ++++++++++++++++++
src/test/regress/sql/stats_ext.sql | 166 ++++++
9 files changed, 982 insertions(+), 83 deletions(-)
diff --git a/src/backend/optimizer/path/clausesel.c b/src/backend/optimizer/path/clausesel.c
index 0ab021c1e8..eec6c6182c 100644
--- a/src/backend/optimizer/path/clausesel.c
+++ b/src/backend/optimizer/path/clausesel.c
@@ -152,7 +152,7 @@ clauselist_selectivity_ext(PlannerInfo *root,
*/
s1 = statext_clauselist_selectivity(root, clauses, varRelid,
jointype, sjinfo, rel,
- &estimatedclauses, false);
+ &estimatedclauses, AND_TYPE);
}
/*
@@ -384,7 +384,7 @@ clauselist_selectivity_or(PlannerInfo *root,
*/
s1 = statext_clauselist_selectivity(root, clauses, varRelid,
jointype, sjinfo, rel,
- &estimatedclauses, true);
+ &estimatedclauses, OR_TYPE);
}
/*
@@ -691,6 +691,7 @@ clause_selectivity_ext(PlannerInfo *root,
Selectivity s1 = 0.5; /* default for any unhandled clause type */
RestrictInfo *rinfo = NULL;
bool cacheable = false;
+ Node *src = clause;
if (clause == NULL) /* can this still happen? */
return s1;
@@ -832,6 +833,7 @@ clause_selectivity_ext(PlannerInfo *root,
{
OpExpr *opclause = (OpExpr *) clause;
Oid opno = opclause->opno;
+ List *clauses = list_make1(src);
if (treat_as_join_clause(root, clause, rinfo, varRelid, sjinfo))
{
@@ -842,6 +844,25 @@ clause_selectivity_ext(PlannerInfo *root,
jointype,
sjinfo);
}
+ else if(use_extended_stats)
+ {
+ /* Check whether clauses are from one relation */
+ RelOptInfo *rel = find_single_rel_for_clauses(root, clauses);
+ Bitmapset *estimatedclauses = NULL;
+ if (rel && rel->rtekind == RTE_RELATION && rel->statlist != NIL)
+ s1 = statext_clauselist_selectivity(root, clauses, varRelid,
+ jointype, sjinfo, rel,
+ &estimatedclauses, VAR_OP_VAR_TYPE);
+
+ if (bms_num_members(estimatedclauses) != 1)
+ {
+ /* If there is no multi-column MCV statistics */
+ s1 = restriction_selectivity(root, opno,
+ opclause->args,
+ opclause->inputcollid,
+ varRelid);
+ }
+ }
else
{
/* Estimate selectivity for a restriction clause. */
diff --git a/src/backend/statistics/README b/src/backend/statistics/README
index 13a97a3566..d33b039aad 100644
--- a/src/backend/statistics/README
+++ b/src/backend/statistics/README
@@ -28,11 +28,7 @@ Each type of statistics may be used to estimate some subset of clause types.
(a) functional dependencies - equality clauses (AND), possibly IS NULL
- (b) MCV lists - equality and inequality clauses (AND, OR, NOT), IS [NOT] NULL
-
-Currently, only OpExprs in the form Var op Const, or Const op Var are
-supported, however it's feasible to expand the code later to also estimate the
-selectivities on clauses such as Var op Var.
+ (b) MCV lists - equality and inequality clauses (AND, OR, NOT), IS [NOT] NULL, Var op Var
Complex clauses
diff --git a/src/backend/statistics/README.mcv b/src/backend/statistics/README.mcv
index a918fb5634..0ba169b26c 100644
--- a/src/backend/statistics/README.mcv
+++ b/src/backend/statistics/README.mcv
@@ -39,12 +39,10 @@ Currently MCV lists support estimation of the following clause types:
(b) inequality clauses WHERE (a < 1) AND (b >= 2)
(c) NULL clauses WHERE (a IS NULL) AND (b IS NOT NULL)
(d) OR clauses WHERE (a < 1) OR (b >= 2)
-
-It's possible to add support for additional clauses, for example:
-
(e) multi-var clauses WHERE (a > b)
-and possibly others. These are tasks for the future, not yet implemented.
+It's possible to add support for additional clauses, and possibly others.
+These are tasks for the future, not yet implemented.
Hashed MCV (not yet implemented)
diff --git a/src/backend/statistics/extended_stats.c b/src/backend/statistics/extended_stats.c
index 99fdf208db..cb7d6d04ce 100644
--- a/src/backend/statistics/extended_stats.c
+++ b/src/backend/statistics/extended_stats.c
@@ -1309,8 +1309,10 @@ choose_best_statistics(List *stats, char requiredkind, bool inh,
* (d) ScalarArrayOpExprs of the form (Var/Expr op ANY (Const)) or
* (Var/Expr op ALL (Const))
*
+ * (e) (Var op Var)
+ *
* In the future, the range of supported clauses may be expanded to more
- * complex cases, for example (Var op Var).
+ * complex cases.
*
* Arguments:
* clause: (sub)clause to be inspected (bare clause, not a RestrictInfo)
@@ -1365,15 +1367,13 @@ statext_is_compatible_clause_internal(PlannerInfo *root, Node *clause,
RangeTblEntry *rte = root->simple_rte_array[relid];
OpExpr *expr = (OpExpr *) clause;
Node *clause_expr;
+ Node *clause_expr_left = NULL,
+ *clause_expr_right = NULL;
/* Only expressions with two arguments are considered compatible. */
if (list_length(expr->args) != 2)
return false;
- /* Check if the expression has the right shape */
- if (!examine_opclause_args(expr->args, &clause_expr, NULL, NULL))
- return false;
-
/*
* If it's not one of the supported operators ("=", "<", ">", etc.),
* just ignore the clause, as it's not compatible with MCV lists.
@@ -1411,14 +1411,27 @@ statext_is_compatible_clause_internal(PlannerInfo *root, Node *clause,
!get_func_leakproof(get_opcode(expr->opno)))
return false;
- /* Check (Var op Const) or (Const op Var) clauses by recursing. */
- if (IsA(clause_expr, Var))
- return statext_is_compatible_clause_internal(root, clause_expr,
+ if (examine_opclause_args(expr->args, &clause_expr, NULL, NULL))
+ {
+ /* Check (Var op Const) or (Const op Var) clauses by recursing. */
+ if (IsA(clause_expr, Var))
+ return statext_is_compatible_clause_internal(root, clause_expr,
relid, attnums, exprs);
- /* Otherwise we have (Expr op Const) or (Const op Expr). */
- *exprs = lappend(*exprs, clause_expr);
- return true;
+ /* Otherwise we have (Expr op Const) or (Const op Expr). */
+ *exprs = lappend(*exprs, clause_expr);
+ return true;
+ }
+ else if (is_opclause_var_op_var(expr->args, &clause_expr_left, &clause_expr_right))
+ {
+ /* Check (Var op Var) clauses by recursing. */
+ if (!statext_is_compatible_clause_internal(root, clause_expr_left, relid, attnums, exprs))
+ return false;
+ if (!statext_is_compatible_clause_internal(root, clause_expr_right, relid, attnums, exprs))
+ return false;
+
+ return true;
+ }
}
/* Var/Expr IN Array */
@@ -1716,13 +1729,13 @@ static Selectivity
statext_mcv_clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid,
JoinType jointype, SpecialJoinInfo *sjinfo,
RelOptInfo *rel, Bitmapset **estimatedclauses,
- bool is_or)
+ enum ClauseType clause_type)
{
ListCell *l;
Bitmapset **list_attnums; /* attnums extracted from the clause */
List **list_exprs; /* expressions matched to any statistic */
int listidx;
- Selectivity sel = (is_or) ? 0.0 : 1.0;
+ Selectivity sel = (clause_type == OR_TYPE) ? 0.0 : 1.0;
RangeTblEntry *rte = planner_rt_fetch(rel->relid, root);
/* check if there's any stats that might be useful for us. */
@@ -1857,7 +1870,7 @@ statext_mcv_clauselist_selectivity(PlannerInfo *root, List *clauses, int varReli
list_exprs[listidx] = NULL;
}
- if (is_or)
+ if (clause_type == OR_TYPE)
{
bool *or_matches = NULL;
Selectivity simple_or_sel = 0.0,
@@ -1957,7 +1970,7 @@ statext_mcv_clauselist_selectivity(PlannerInfo *root, List *clauses, int varReli
*/
sel = sel + stat_sel - sel * stat_sel;
}
- else /* Implicitly-ANDed list of clauses */
+ else if (clause_type == AND_TYPE)
{
Selectivity simple_sel,
mcv_sel,
@@ -1991,6 +2004,16 @@ statext_mcv_clauselist_selectivity(PlannerInfo *root, List *clauses, int varReli
/* Factor this into the overall result */
sel *= stat_sel;
}
+ else if (clause_type == VAR_OP_VAR_TYPE)
+ {
+ /*
+ * Multi-column estimate using MCV statistics, along with base and
+ * total selectivities.
+ */
+ sel = mcv_clauselist_selectivity_var_op_var(root, stat, stat_clauses,
+ varRelid, jointype, sjinfo,
+ rel);
+ }
}
return sel;
@@ -2004,19 +2027,19 @@ Selectivity
statext_clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid,
JoinType jointype, SpecialJoinInfo *sjinfo,
RelOptInfo *rel, Bitmapset **estimatedclauses,
- bool is_or)
+ enum ClauseType clause_type)
{
Selectivity sel;
/* First, try estimating clauses using a multivariate MCV list. */
sel = statext_mcv_clauselist_selectivity(root, clauses, varRelid, jointype,
- sjinfo, rel, estimatedclauses, is_or);
+ sjinfo, rel, estimatedclauses, clause_type);
/*
* Functional dependencies only work for clauses connected by AND, so for
* OR clauses we're done.
*/
- if (is_or)
+ if (clause_type == OR_TYPE)
return sel;
/*
@@ -2102,6 +2125,55 @@ examine_opclause_args(List *args, Node **exprp, Const **cstp,
return true;
}
+/*
+ * is_opclause_var_op_var
+ * Split an operator expression's arguments into Var and Var parts.
+ *
+ * Attempts to match the arguments to (Var op Var), possibly with
+ * a RelabelType on top. When the expression matches this
+ * form, returns true, otherwise returns false.
+ *
+ * Optionally returns pointers to the extracted Var nodes, when passed
+ * non-null pointers (exprp_left, exprp_right).
+ */
+bool
+is_opclause_var_op_var(List *args, Node **exprp_left, Node **exprp_right)
+{
+ Node *leftop,
+ *rightop;
+ Node *expr_left,
+ *expr_right;
+
+
+ /* enforced by statext_is_compatible_clause_internal */
+ Assert(list_length(args) == 2);
+
+ leftop = linitial(args);
+ rightop = lsecond(args);
+
+ if (IsA(leftop, RelabelType))
+ leftop = (Node *) ((RelabelType *) leftop)->arg;
+
+ if (IsA(rightop, RelabelType))
+ rightop = (Node *) ((RelabelType *) rightop)->arg;
+
+ if (IsA(rightop, Var) && IsA(leftop, Var))
+ {
+ expr_left = (Node *) leftop;
+ expr_right = (Node *) rightop;
+ }
+ else
+ return false;
+
+ /* return pointers to the extracted parts if requested */
+ if (exprp_left && exprp_right)
+ {
+ *exprp_left = expr_left;
+ *exprp_right = expr_right;
+ }
+
+ return true;
+}
/*
* Compute statistics about expressions of a relation.
diff --git a/src/backend/statistics/mcv.c b/src/backend/statistics/mcv.c
index b0e9aead84..2e2c028e0f 100644
--- a/src/backend/statistics/mcv.c
+++ b/src/backend/statistics/mcv.c
@@ -1610,6 +1610,7 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
Assert(mcvlist->nitems <= STATS_MCVLIST_MAX_ITEMS);
matches = palloc(sizeof(bool) * mcvlist->nitems);
+
memset(matches, !is_or, sizeof(bool) * mcvlist->nitems);
/*
@@ -1639,72 +1640,110 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
bool expronleft;
int idx;
Oid collid;
+ Node *clause_expr_left,
+ *clause_expr_right;
fmgr_info(get_opcode(expr->opno), &opproc);
/* extract the var/expr and const from the expression */
- if (!examine_opclause_args(expr->args, &clause_expr, &cst, &expronleft))
- elog(ERROR, "incompatible clause");
+ if (examine_opclause_args(expr->args, &clause_expr, &cst, &expronleft))
+ {
+ /* match the attribute/expression to a dimension of the statistic */
+ idx = mcv_match_expression(clause_expr, keys, exprs, &collid);
- /* match the attribute/expression to a dimension of the statistic */
- idx = mcv_match_expression(clause_expr, keys, exprs, &collid);
+ /*
+ * Walk through the MCV items and evaluate the current clause. We
+ * can skip items that were already ruled out, and terminate if
+ * there are no remaining MCV items that might possibly match.
+ */
+ for (int i = 0; i < mcvlist->nitems; i++)
+ {
+ bool match = true;
+ MCVItem *item = &mcvlist->items[i];
- /*
- * Walk through the MCV items and evaluate the current clause. We
- * can skip items that were already ruled out, and terminate if
- * there are no remaining MCV items that might possibly match.
- */
- for (int i = 0; i < mcvlist->nitems; i++)
+ Assert(idx >= 0);
+
+ /*
+ * When the MCV item or the Const value is NULL we can treat
+ * this as a mismatch. We must not call the operator because
+ * of strictness.
+ */
+ if (item->isnull[idx] || cst->constisnull)
+ {
+ matches[i] = RESULT_MERGE(matches[i], is_or, false);
+ continue;
+ }
+
+ /*
+ * Skip MCV items that can't change result in the bitmap. Once
+ * the value gets false for AND-lists, or true for OR-lists,
+ * we don't need to look at more clauses.
+ */
+ if (RESULT_IS_FINAL(matches[i], is_or))
+ continue;
+
+ /*
+ * First check whether the constant is below the lower
+ * boundary (in that case we can skip the bucket, because
+ * there's no overlap).
+ *
+ * We don't store collations used to build the statistics, but
+ * we can use the collation for the attribute itself, as
+ * stored in varcollid. We do reset the statistics after a
+ * type change (including collation change), so this is OK.
+ * For expressions, we use the collation extracted from the
+ * expression itself.
+ */
+ if (expronleft)
+ match = DatumGetBool(FunctionCall2Coll(&opproc,
+ collid,
+ item->values[idx],
+ cst->constvalue));
+ else
+ match = DatumGetBool(FunctionCall2Coll(&opproc,
+ collid,
+ cst->constvalue,
+ item->values[idx]));
+
+ /* update the match bitmap with the result */
+ matches[i] = RESULT_MERGE(matches[i], is_or, match);
+ }
+ }
+ else if(is_opclause_var_op_var(expr->args, &clause_expr_left, &clause_expr_right))
{
- bool match = true;
- MCVItem *item = &mcvlist->items[i];
+ /* extract the var/expr and const from the expression */
+ int idx_left = mcv_match_expression(clause_expr_left, keys, exprs, &collid);
+ int idx_right = mcv_match_expression(clause_expr_right, keys, exprs, &collid);
- Assert(idx >= 0);
+ Assert((idx_left >= 0) && (idx_left < bms_num_members(keys) + list_length(exprs)));
+ Assert((idx_right >= 0) && (idx_right < bms_num_members(keys) + list_length(exprs)));
- /*
- * When the MCV item or the Const value is NULL we can treat
- * this as a mismatch. We must not call the operator because
- * of strictness.
- */
- if (item->isnull[idx] || cst->constisnull)
+ for (int i = 0; i < mcvlist->nitems; i++)
{
- matches[i] = RESULT_MERGE(matches[i], is_or, false);
- continue;
- }
+ MCVItem *item = &mcvlist->items[i];
- /*
- * Skip MCV items that can't change result in the bitmap. Once
- * the value gets false for AND-lists, or true for OR-lists,
- * we don't need to look at more clauses.
- */
- if (RESULT_IS_FINAL(matches[i], is_or))
- continue;
+ /*
+ * When either of the MCV items is NULL we can treat this
+ * as a mismatch. We must not call the operator because
+ * of strictness.
+ */
+ if (item->isnull[idx_left] || item->isnull[idx_right])
+ {
+ matches[i] = false;
+ continue;
+ }
- /*
- * First check whether the constant is below the lower
- * boundary (in that case we can skip the bucket, because
- * there's no overlap).
- *
- * We don't store collations used to build the statistics, but
- * we can use the collation for the attribute itself, as
- * stored in varcollid. We do reset the statistics after a
- * type change (including collation change), so this is OK.
- * For expressions, we use the collation extracted from the
- * expression itself.
- */
- if (expronleft)
- match = DatumGetBool(FunctionCall2Coll(&opproc,
- collid,
- item->values[idx],
- cst->constvalue));
- else
- match = DatumGetBool(FunctionCall2Coll(&opproc,
+ /*
+ * We don't store collations used to build the statistics,
+ * but we can use the collation for the attribute itself,
+ * as stored in varcollid. We do reset the statistics after
+ * a type change (including collation change), so this is OK.
+ */
+ matches[i] = DatumGetBool(FunctionCall2Coll(&opproc,
collid,
- cst->constvalue,
- item->values[idx]));
-
- /* update the match bitmap with the result */
- matches[i] = RESULT_MERGE(matches[i], is_or, match);
+ item->values[idx_left],
+ item->values[idx_right]));
+ }
}
}
else if (IsA(clause, ScalarArrayOpExpr))
@@ -2083,6 +2122,45 @@ mcv_clauselist_selectivity(PlannerInfo *root, StatisticExtInfo *stat,
return s;
}
+/*
+ * mcv_clauselist_selectivity_var_op_var
+ * Use MCV statistics to estimate the selectivity of (Var op Var) clause.
+ *
+ * This determines which MCV items match clause and returns the sum of
+ * the frequencies of those items.
+ */
+Selectivity
+mcv_clauselist_selectivity_var_op_var(PlannerInfo *root, StatisticExtInfo *stat,
+ List *clauses, int varRelid,
+ JoinType jointype, SpecialJoinInfo *sjinfo,
+ RelOptInfo *rel)
+{
+ int i;
+ MCVList *mcv;
+ Selectivity s = 0.0;
+ RangeTblEntry *rte = root->simple_rte_array[rel->relid];
+
+ /* match/mismatch bitmap for each MCV item */
+ bool *matches = NULL;
+
+ /* load the MCV list stored in the statistics object */
+ mcv = statext_mcv_load(stat->statOid, rte->inh);
+
+ /* build a match bitmap for the clause */
+ matches = mcv_get_match_bitmap(root, clauses, stat->keys, stat->exprs,
+ mcv, false);
+
+ /* sum frequencies for all the matching MCV items */
+ for (i = 0; i < mcv->nitems; i++)
+ {
+ if (matches[i] != false)
+ {
+ s += mcv->items[i].frequency;
+ }
+ }
+
+ return s;
+}
/*
* mcv_clause_selectivity_or
diff --git a/src/include/statistics/extended_stats_internal.h b/src/include/statistics/extended_stats_internal.h
index 8eed9b338d..66b8b0d0b6 100644
--- a/src/include/statistics/extended_stats_internal.h
+++ b/src/include/statistics/extended_stats_internal.h
@@ -127,4 +127,10 @@ extern Selectivity mcv_clause_selectivity_or(PlannerInfo *root,
Selectivity *overlap_basesel,
Selectivity *totalsel);
+extern Selectivity mcv_clauselist_selectivity_var_op_var(PlannerInfo *root,
+ StatisticExtInfo *stat,
+ List *clauses, int varRelid,
+ JoinType jointype, SpecialJoinInfo *sjinfo,
+ RelOptInfo *rel);
+
#endif /* EXTENDED_STATS_INTERNAL_H */
diff --git a/src/include/statistics/statistics.h b/src/include/statistics/statistics.h
index 7f2bf18716..d36b866436 100644
--- a/src/include/statistics/statistics.h
+++ b/src/include/statistics/statistics.h
@@ -94,6 +94,14 @@ typedef struct MCVList
MCVItem items[FLEXIBLE_ARRAY_MEMBER]; /* array of MCV items */
} MCVList;
+/* Clause types of MCV lists */
+typedef enum ClauseType
+{
+ OR_TYPE, /* OR-clause */
+ AND_TYPE, /* AND-clause */
+ VAR_OP_VAR_TYPE, /* Var op Var */
+} ClauseType;
+
extern MVNDistinct *statext_ndistinct_load(Oid mvoid, bool inh);
extern MVDependencies *statext_dependencies_load(Oid mvoid, bool inh);
extern MCVList *statext_mcv_load(Oid mvoid, bool inh);
@@ -118,7 +126,7 @@ extern Selectivity statext_clauselist_selectivity(PlannerInfo *root,
SpecialJoinInfo *sjinfo,
RelOptInfo *rel,
Bitmapset **estimatedclauses,
- bool is_or);
+ enum ClauseType clause_type);
extern bool has_stats_of_kind(List *stats, char requiredkind);
extern StatisticExtInfo *choose_best_statistics(List *stats, char requiredkind,
bool inh,
@@ -126,5 +134,6 @@ extern StatisticExtInfo *choose_best_statistics(List *stats, char requiredkind,
List **clause_exprs,
int nclauses);
extern HeapTuple statext_expressions_load(Oid stxoid, bool inh, int idx);
+extern bool is_opclause_var_op_var(List *args, Node **exprp_left, Node **exprp_right);
#endif /* STATISTICS_H */
diff --git a/src/test/regress/expected/stats_ext.out b/src/test/regress/expected/stats_ext.out
index 8c4da95508..5a76ddbc72 100644
--- a/src/test/regress/expected/stats_ext.out
+++ b/src/test/regress/expected/stats_ext.out
@@ -2005,6 +2005,42 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = 1 OR b = '
343 | 200
(1 row)
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = c');
+ estimated | actual
+-----------+--------
+ 25 | 1250
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a != c');
+ estimated | actual
+-----------+--------
+ 4975 | 3750
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a > c');
+ estimated | actual
+-----------+--------
+ 1667 | 3750
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a >= c');
+ estimated | actual
+-----------+--------
+ 1667 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a < c');
+ estimated | actual
+-----------+--------
+ 1667 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a <= c');
+ estimated | actual
+-----------+--------
+ 1667 | 1250
+(1 row)
+
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a IN (1, 2, 51, 52) AND b IN ( ''1'', ''2'')');
estimated | actual
-----------+--------
@@ -2158,6 +2194,42 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = 1 OR b = '
200 | 200
(1 row)
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = c');
+ estimated | actual
+-----------+--------
+ 1250 | 1250
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a != c');
+ estimated | actual
+-----------+--------
+ 3750 | 3750
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a > c');
+ estimated | actual
+-----------+--------
+ 3750 | 3750
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a >= c');
+ estimated | actual
+-----------+--------
+ 5000 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a < c');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a <= c');
+ estimated | actual
+-----------+--------
+ 1250 | 1250
+(1 row)
+
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a IN (1, 2, 51, 52) AND b IN ( ''1'', ''2'')');
estimated | actual
-----------+--------
@@ -2573,6 +2645,109 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a IS NULL AND
3750 | 2500
(1 row)
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = c');
+ estimated | actual
+-----------+--------
+ 25 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a != c');
+ estimated | actual
+-----------+--------
+ 4975 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a > c');
+ estimated | actual
+-----------+--------
+ 1667 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a >= c');
+ estimated | actual
+-----------+--------
+ 1667 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a < c');
+ estimated | actual
+-----------+--------
+ 1667 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a <= c');
+ estimated | actual
+-----------+--------
+ 1667 | 0
+(1 row)
+
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b = d');
+ estimated | actual
+-----------+--------
+ 25 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b != d');
+ estimated | actual
+-----------+--------
+ 4975 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b < d');
+ estimated | actual
+-----------+--------
+ 1667 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b <= d');
+ estimated | actual
+-----------+--------
+ 1667 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b > d');
+ estimated | actual
+-----------+--------
+ 1667 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b >= d');
+ estimated | actual
+-----------+--------
+ 1667 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b != d');
+ estimated | actual
+-----------+--------
+ 4975 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b < d');
+ estimated | actual
+-----------+--------
+ 1667 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b <= d');
+ estimated | actual
+-----------+--------
+ 1667 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b > d');
+ estimated | actual
+-----------+--------
+ 1667 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b >= d');
+ estimated | actual
+-----------+--------
+ 1667 | 2500
+(1 row)
+
-- create statistics
CREATE STATISTICS mcv_lists_stats (mcv) ON a, b, d FROM mcv_lists;
ANALYZE mcv_lists;
@@ -2606,6 +2781,72 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a IS NULL AND
2500 | 2500
(1 row)
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b = d');
+ estimated | actual
+-----------+--------
+ 2500 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b != d');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b < d');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b <= d');
+ estimated | actual
+-----------+--------
+ 2500 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b > d');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b >= d');
+ estimated | actual
+-----------+--------
+ 2500 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b != d');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b < d');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b <= d');
+ estimated | actual
+-----------+--------
+ 2500 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b > d');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b >= d');
+ estimated | actual
+-----------+--------
+ 2500 | 2500
+(1 row)
+
-- mcv with pass-by-ref fixlen types, e.g. uuid
CREATE TABLE mcv_lists_uuid (
a UUID,
@@ -2700,6 +2941,78 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a AND
1094 | 0
(1 row)
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a = b');
+ estimated | actual
+-----------+--------
+ 9950 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a != b');
+ estimated | actual
+-----------+--------
+ 50 | 7500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a < b');
+ estimated | actual
+-----------+--------
+ 3333 | 10000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a <= b');
+ estimated | actual
+-----------+--------
+ 3333 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a > b');
+ estimated | actual
+-----------+--------
+ 3333 | 7500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a >= b');
+ estimated | actual
+-----------+--------
+ 3333 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a = b AND b = c');
+ estimated | actual
+-----------+--------
+ 50 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a != b AND b != c');
+ estimated | actual
+-----------+--------
+ 50 | 1250
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a < b AND b < c');
+ estimated | actual
+-----------+--------
+ 1111 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a <= b AND b <= c');
+ estimated | actual
+-----------+--------
+ 1111 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a > b AND b > c');
+ estimated | actual
+-----------+--------
+ 1111 | 1250
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a >= b AND b >= c');
+ estimated | actual
+-----------+--------
+ 1111 | 0
+(1 row)
+
CREATE STATISTICS mcv_lists_bool_stats (mcv) ON a, b, c
FROM mcv_lists_bool;
ANALYZE mcv_lists_bool;
@@ -2727,6 +3040,78 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a AND
1 | 0
(1 row)
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a = b');
+ estimated | actual
+-----------+--------
+ 2500 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a != b');
+ estimated | actual
+-----------+--------
+ 7500 | 7500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a < b');
+ estimated | actual
+-----------+--------
+ 10000 | 10000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a <= b');
+ estimated | actual
+-----------+--------
+ 2500 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a > b');
+ estimated | actual
+-----------+--------
+ 7500 | 7500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a >= b');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a = b AND b = c');
+ estimated | actual
+-----------+--------
+ 8750 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a != b AND b != c');
+ estimated | actual
+-----------+--------
+ 7500 | 1250
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a < b AND b < c');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a <= b AND b <= c');
+ estimated | actual
+-----------+--------
+ 8750 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a > b AND b > c');
+ estimated | actual
+-----------+--------
+ 1250 | 1250
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a >= b AND b >= c');
+ estimated | actual
+-----------+--------
+ 10000 | 0
+(1 row)
+
-- mcv covering just a small fraction of data
CREATE TABLE mcv_lists_partial (
a INT,
@@ -2914,6 +3299,90 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = 0 OR
2649 | 1572
(1 row)
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = b AND c = d');
+ estimated | actual
+-----------+--------
+ 1 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a != b AND c != d');
+ estimated | actual
+-----------+--------
+ 4950 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a < b AND c > d');
+ estimated | actual
+-----------+--------
+ 556 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b AND c >= d');
+ estimated | actual
+-----------+--------
+ 556 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = b OR c = d');
+ estimated | actual
+-----------+--------
+ 50 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a != b OR c != d');
+ estimated | actual
+-----------+--------
+ 5000 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a < b OR c > d');
+ estimated | actual
+-----------+--------
+ 2778 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b OR c >= d');
+ estimated | actual
+-----------+--------
+ 2778 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b AND d >= c');
+ estimated | actual
+-----------+--------
+ 556 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b OR d >= c');
+ estimated | actual
+-----------+--------
+ 2778 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a < b');
+ estimated | actual
+-----------+--------
+ 1667 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a > b');
+ estimated | actual
+-----------+--------
+ 1667 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b');
+ estimated | actual
+-----------+--------
+ 1667 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a >= b');
+ estimated | actual
+-----------+--------
+ 1667 | 5000
+(1 row)
+
-- create separate MCV statistics
CREATE STATISTICS mcv_lists_multi_1 (mcv) ON a, b FROM mcv_lists_multi;
CREATE STATISTICS mcv_lists_multi_2 (mcv) ON c, d FROM mcv_lists_multi;
@@ -2960,6 +3429,90 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = 0 OR
1571 | 1572
(1 row)
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = b AND c = d');
+ estimated | actual
+-----------+--------
+ 5000 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a != b AND c != d');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a < b AND c > d');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b AND c >= d');
+ estimated | actual
+-----------+--------
+ 5000 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = b OR c = d');
+ estimated | actual
+-----------+--------
+ 5000 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a != b OR c != d');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a < b OR c > d');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b OR c >= d');
+ estimated | actual
+-----------+--------
+ 5000 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b AND d >= c');
+ estimated | actual
+-----------+--------
+ 5000 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b OR d >= c');
+ estimated | actual
+-----------+--------
+ 5000 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a < b');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a > b');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b');
+ estimated | actual
+-----------+--------
+ 5000 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a >= b');
+ estimated | actual
+-----------+--------
+ 5000 | 5000
+(1 row)
+
DROP TABLE mcv_lists_multi;
-- statistics on integer expressions
CREATE TABLE expr_stats (a int, b int, c int);
diff --git a/src/test/regress/sql/stats_ext.sql b/src/test/regress/sql/stats_ext.sql
index 0c08a6cc42..34513224ed 100644
--- a/src/test/regress/sql/stats_ext.sql
+++ b/src/test/regress/sql/stats_ext.sql
@@ -999,6 +999,18 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = 1 OR b = '
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = 1 OR b = ''1'' OR c = 1 OR d IS NOT NULL');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a != c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a > c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a >= c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a < c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a <= c');
+
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a IN (1, 2, 51, 52) AND b IN ( ''1'', ''2'')');
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a IN (1, 2, 51, 52, NULL) AND b IN ( ''1'', ''2'', NULL)');
@@ -1054,6 +1066,18 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = 1 OR b = '
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = 1 OR b = ''1'' OR c = 1 OR d IS NOT NULL');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a != c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a > c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a >= c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a < c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a <= c');
+
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a IN (1, 2, 51, 52) AND b IN ( ''1'', ''2'')');
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a IN (1, 2, 51, 52, NULL) AND b IN ( ''1'', ''2'', NULL)');
@@ -1255,6 +1279,40 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = 1 OR b = '
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a IS NULL AND (b = ''x'' OR d = ''x'')');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a != c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a > c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a >= c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a < c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a <= c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b = d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b != d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b < d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b <= d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b > d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b >= d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b != d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b < d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b <= d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b > d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b >= d');
+
-- create statistics
CREATE STATISTICS mcv_lists_stats (mcv) ON a, b, d FROM mcv_lists;
@@ -1273,6 +1331,28 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = 1 OR b = '
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a IS NULL AND (b = ''x'' OR d = ''x'')');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b = d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b != d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b < d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b <= d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b > d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b >= d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b != d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b < d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b <= d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b > d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b >= d');
+
-- mcv with pass-by-ref fixlen types, e.g. uuid
CREATE TABLE mcv_lists_uuid (
a UUID,
@@ -1348,6 +1428,30 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a AND
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a AND b AND NOT c');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a = b');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a != b');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a < b');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a <= b');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a > b');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a >= b');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a = b AND b = c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a != b AND b != c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a < b AND b < c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a <= b AND b <= c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a > b AND b > c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a >= b AND b >= c');
+
CREATE STATISTICS mcv_lists_bool_stats (mcv) ON a, b, c
FROM mcv_lists_bool;
@@ -1361,6 +1465,30 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a AND
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a AND b AND NOT c');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a = b');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a != b');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a < b');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a <= b');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a > b');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a >= b');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a = b AND b = c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a != b AND b != c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a < b AND b < c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a <= b AND b <= c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a > b AND b > c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a >= b AND b >= c');
+
-- mcv covering just a small fraction of data
CREATE TABLE mcv_lists_partial (
a INT,
@@ -1461,6 +1589,25 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = 0 AN
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE (a = 0 AND b = 0) OR (c = 0 AND d = 0)');
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = 0 OR b = 0 OR c = 0 OR d = 0');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = b AND c = d');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a != b AND c != d');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a < b AND c > d');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b AND c >= d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = b OR c = d');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a != b OR c != d');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a < b OR c > d');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b OR c >= d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b AND d >= c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b OR d >= c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a < b');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a > b');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a >= b');
+
-- create separate MCV statistics
CREATE STATISTICS mcv_lists_multi_1 (mcv) ON a, b FROM mcv_lists_multi;
CREATE STATISTICS mcv_lists_multi_2 (mcv) ON c, d FROM mcv_lists_multi;
@@ -1475,6 +1622,25 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = 0 AN
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE (a = 0 AND b = 0) OR (c = 0 AND d = 0)');
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = 0 OR b = 0 OR c = 0 OR d = 0');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = b AND c = d');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a != b AND c != d');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a < b AND c > d');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b AND c >= d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = b OR c = d');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a != b OR c != d');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a < b OR c > d');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b OR c >= d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b AND d >= c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b OR d >= c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a < b');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a > b');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a >= b');
+
DROP TABLE mcv_lists_multi;
--
2.34.1
Another issue mentioned in [1]/messages/by-id/7C0F91B5-8A43-428B-8D31-556458720305@enterprisedb.com involves cases where the clause is in the
form (A op A). In my view, this isn't related to the current patch, as
it can be addressed by rewriting the clause, similar to transforming A =
A into A IS NOT NULL. This adjustment would result in more accurate
estimation.
[1]: /messages/by-id/7C0F91B5-8A43-428B-8D31-556458720305@enterprisedb.com
/messages/by-id/7C0F91B5-8A43-428B-8D31-556458720305@enterprisedb.com
Ilia Evdokimov,
Tantor Labs LLC.
Hi! I think your work is important)
I started reviewing it and want to suggest some changes to better code:
I think we should consider the case where the expression is not neither
an OpExpr and VarOpVar expression.
Have you tested this code with any benchmarks?
--
Regards,
Alena Rybakina
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
Attachments:
diff1.no-cfbottext/plain; charset=UTF-8; name=diff1.no-cfbotDownload
diff --git a/src/backend/statistics/extended_stats.c b/src/backend/statistics/extended_stats.c
index cb7d6d04ce5..07b3610d24e 100644
--- a/src/backend/statistics/extended_stats.c
+++ b/src/backend/statistics/extended_stats.c
@@ -1432,6 +1432,8 @@ statext_is_compatible_clause_internal(PlannerInfo *root, Node *clause,
return true;
}
+ else
+ return false;
}
/* Var/Expr IN Array */
@@ -2137,13 +2139,13 @@ examine_opclause_args(List *args, Node **exprp, Const **cstp,
* non-null pointers (exprp_left, exprp_right).
*/
bool
-is_opclause_var_op_var(List *args, Node **exprp_left, Node **exprp_right)
+is_opclause_var_op_var(List *args, Node **expr_left, Node **expr_right)
{
Node *leftop,
*rightop;
- Node *expr_left,
- *expr_right;
-
+
+ *expr_left = NULL;
+ *expr_right = NULL;
/* enforced by statext_is_compatible_clause_internal */
Assert(list_length(args) == 2);
@@ -2157,20 +2159,16 @@ is_opclause_var_op_var(List *args, Node **exprp_left, Node **exprp_right)
if (IsA(rightop, RelabelType))
rightop = (Node *) ((RelabelType *) rightop)->arg;
+
if (IsA(rightop, Var) && IsA(leftop, Var))
{
- expr_left = (Node *) leftop;
- expr_right = (Node *) rightop;
+ *expr_left = (Node *) leftop;
+ *expr_right = (Node *) rightop;
}
else
return false;
- /* return pointers to the extracted parts if requested */
- if (exprp_left && exprp_right)
- {
- *exprp_left = expr_left;
- *exprp_right = expr_right;
- }
+ Assert(expr_left && expr_right);
return true;
}
diff --git a/src/backend/statistics/mcv.c b/src/backend/statistics/mcv.c
index 2e2c028e0f0..dd1a1c0c829 100644
--- a/src/backend/statistics/mcv.c
+++ b/src/backend/statistics/mcv.c
@@ -1745,6 +1745,8 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
item->values[idx_right]));
}
}
+ else
+ elog(ERROR, "incompatible clause");
}
else if (IsA(clause, ScalarArrayOpExpr))
{
On 8/12/24 13:44, Alena Rybakina wrote:
Hi! I think your work is important)
I agree, and I'm grateful someone picked up the original patch. I'll try
to help to keep it moving forward. If the thread gets stuck, feel free
to ping me to take a look.
I started reviewing it and want to suggest some changes to better code:
I think we should consider the case where the expression is not neither
an OpExpr and VarOpVar expression.
Do you have some specific type of clauses in mind? Most of the extended
statistics only really handles this type of clauses, so I'm not sure
it's feasible to extend that - at least not in this patch.
Have you tested this code with any benchmarks?
FWIW I think we need to test two things - that it (a) improves the
estimates and (b) does not have significant overhead.
regards
--
Tomas Vondra
On 12.8.24 14:53, Tomas Vondra wrote:
I agree, and I'm grateful someone picked up the original patch. I'll try
to help to keep it moving forward. If the thread gets stuck, feel free
to ping me to take a look.
Good. Thank you!
I started reviewing it and want to suggest some changes to better code:
I think we should consider the case where the expression is not neither
an OpExpr and VarOpVar expression.Do you have some specific type of clauses in mind? Most of the extended
statistics only really handles this type of clauses, so I'm not sure
it's feasible to extend that - at least not in this patch.
I agree with Alena that we need to consider the following clauses: (Expr
op Var), (Var op Expr) and (Expr op Expr). And we need to return false
in these cases because we did it before my patch in
/* Check if the expression has the right shape */
if (!examine_opclause_args(expr->args, &clause_expr, NULL, NULL))
return false;
In is_opclause_var_op_var() function it is really useless local Node
*expr_left, *expr_right variables. However, we can't assign them NULL at
the begin because if I passed not-null pointers I have to return the
values. Otherwise remain them NULL.
Nevertheless, thank you for review, Alena.
Have you tested this code with any benchmarks?
FWIW I think we need to test two things - that it (a) improves the
estimates and (b) does not have significant overhead.
Yes, but only TPC-B. And the performance did not drop. In general, it'd
be better to do more tests and those listed by Tomas with new attached
patch.
Attachments:
v2-Add-support-for-Var-op-Var-clause-in-extended-MCV-st.patchtext/x-patch; charset=UTF-8; name=v2-Add-support-for-Var-op-Var-clause-in-extended-MCV-st.patchDownload
From fa67b0fa34408c0f1b0c9f079b84e7c71f3b5599 Mon Sep 17 00:00:00 2001
From: Ilia Evdokimov <ilya.evdokimov@tantorlabs.ru>
Date: Sat, 10 Aug 2024 14:35:25 +0300
Subject: [PATCH] Add support for (Var op Var) clause in extended MCV
statistics
Added a new leaf to the existing clauses tree, allowing the calculation
of selectivity specifically for (Var op Var) clauses. The new function
for this selectivity calculation has been integratedinto
the extended statistics mechanism, ensuring accurate application
during query planning.
---
src/backend/optimizer/path/clausesel.c | 25 +-
src/backend/statistics/README | 6 +-
src/backend/statistics/README.mcv | 6 +-
src/backend/statistics/extended_stats.c | 108 +++-
src/backend/statistics/mcv.c | 186 ++++--
.../statistics/extended_stats_internal.h | 6 +
src/include/statistics/statistics.h | 11 +-
src/test/regress/expected/stats_ext.out | 553 ++++++++++++++++++
src/test/regress/sql/stats_ext.sql | 166 ++++++
9 files changed, 983 insertions(+), 84 deletions(-)
diff --git a/src/backend/optimizer/path/clausesel.c b/src/backend/optimizer/path/clausesel.c
index 0ab021c1e8..cb888839bd 100644
--- a/src/backend/optimizer/path/clausesel.c
+++ b/src/backend/optimizer/path/clausesel.c
@@ -152,7 +152,7 @@ clauselist_selectivity_ext(PlannerInfo *root,
*/
s1 = statext_clauselist_selectivity(root, clauses, varRelid,
jointype, sjinfo, rel,
- &estimatedclauses, false);
+ &estimatedclauses, AND_CLAUSE);
}
/*
@@ -384,7 +384,7 @@ clauselist_selectivity_or(PlannerInfo *root,
*/
s1 = statext_clauselist_selectivity(root, clauses, varRelid,
jointype, sjinfo, rel,
- &estimatedclauses, true);
+ &estimatedclauses, OR_CLAUSE);
}
/*
@@ -691,6 +691,7 @@ clause_selectivity_ext(PlannerInfo *root,
Selectivity s1 = 0.5; /* default for any unhandled clause type */
RestrictInfo *rinfo = NULL;
bool cacheable = false;
+ Node *src = clause;
if (clause == NULL) /* can this still happen? */
return s1;
@@ -832,6 +833,7 @@ clause_selectivity_ext(PlannerInfo *root,
{
OpExpr *opclause = (OpExpr *) clause;
Oid opno = opclause->opno;
+ List *clauses = list_make1(src);
if (treat_as_join_clause(root, clause, rinfo, varRelid, sjinfo))
{
@@ -842,6 +844,25 @@ clause_selectivity_ext(PlannerInfo *root,
jointype,
sjinfo);
}
+ else if(use_extended_stats)
+ {
+ /* Check whether clauses are from one relation */
+ RelOptInfo *rel = find_single_rel_for_clauses(root, clauses);
+ Bitmapset *estimatedclauses = NULL;
+ if (rel && rel->rtekind == RTE_RELATION && rel->statlist != NIL)
+ s1 = statext_clauselist_selectivity(root, clauses, varRelid,
+ jointype, sjinfo, rel,
+ &estimatedclauses, VAR_OP_VAR_CLAUSE);
+
+ if (bms_num_members(estimatedclauses) != 1)
+ {
+ /* If there is no multi-column MCV statistics */
+ s1 = restriction_selectivity(root, opno,
+ opclause->args,
+ opclause->inputcollid,
+ varRelid);
+ }
+ }
else
{
/* Estimate selectivity for a restriction clause. */
diff --git a/src/backend/statistics/README b/src/backend/statistics/README
index 13a97a3566..d33b039aad 100644
--- a/src/backend/statistics/README
+++ b/src/backend/statistics/README
@@ -28,11 +28,7 @@ Each type of statistics may be used to estimate some subset of clause types.
(a) functional dependencies - equality clauses (AND), possibly IS NULL
- (b) MCV lists - equality and inequality clauses (AND, OR, NOT), IS [NOT] NULL
-
-Currently, only OpExprs in the form Var op Const, or Const op Var are
-supported, however it's feasible to expand the code later to also estimate the
-selectivities on clauses such as Var op Var.
+ (b) MCV lists - equality and inequality clauses (AND, OR, NOT), IS [NOT] NULL, Var op Var
Complex clauses
diff --git a/src/backend/statistics/README.mcv b/src/backend/statistics/README.mcv
index a918fb5634..1eaa4d3b17 100644
--- a/src/backend/statistics/README.mcv
+++ b/src/backend/statistics/README.mcv
@@ -39,12 +39,10 @@ Currently MCV lists support estimation of the following clause types:
(b) inequality clauses WHERE (a < 1) AND (b >= 2)
(c) NULL clauses WHERE (a IS NULL) AND (b IS NOT NULL)
(d) OR clauses WHERE (a < 1) OR (b >= 2)
-
-It's possible to add support for additional clauses, for example:
-
(e) multi-var clauses WHERE (a > b)
-and possibly others. These are tasks for the future, not yet implemented.
+It's possible to add support for additional clauses.
+These are tasks for the future, not yet implemented.
Hashed MCV (not yet implemented)
diff --git a/src/backend/statistics/extended_stats.c b/src/backend/statistics/extended_stats.c
index 99fdf208db..7a907dcb6f 100644
--- a/src/backend/statistics/extended_stats.c
+++ b/src/backend/statistics/extended_stats.c
@@ -1309,8 +1309,10 @@ choose_best_statistics(List *stats, char requiredkind, bool inh,
* (d) ScalarArrayOpExprs of the form (Var/Expr op ANY (Const)) or
* (Var/Expr op ALL (Const))
*
+ * (e) (Var op Var)
+ *
* In the future, the range of supported clauses may be expanded to more
- * complex cases, for example (Var op Var).
+ * complex cases.
*
* Arguments:
* clause: (sub)clause to be inspected (bare clause, not a RestrictInfo)
@@ -1359,21 +1361,19 @@ statext_is_compatible_clause_internal(PlannerInfo *root, Node *clause,
return true;
}
- /* (Var/Expr op Const) or (Const op Var/Expr) */
+ /* (Var/Expr op Const), (Const op Var/Expr) or (Var op Var) */
if (is_opclause(clause))
{
RangeTblEntry *rte = root->simple_rte_array[relid];
OpExpr *expr = (OpExpr *) clause;
Node *clause_expr;
+ Node *clause_expr_left = NULL;
+ Node *clause_expr_right = NULL;
/* Only expressions with two arguments are considered compatible. */
if (list_length(expr->args) != 2)
return false;
- /* Check if the expression has the right shape */
- if (!examine_opclause_args(expr->args, &clause_expr, NULL, NULL))
- return false;
-
/*
* If it's not one of the supported operators ("=", "<", ">", etc.),
* just ignore the clause, as it's not compatible with MCV lists.
@@ -1411,14 +1411,29 @@ statext_is_compatible_clause_internal(PlannerInfo *root, Node *clause,
!get_func_leakproof(get_opcode(expr->opno)))
return false;
- /* Check (Var op Const) or (Const op Var) clauses by recursing. */
- if (IsA(clause_expr, Var))
- return statext_is_compatible_clause_internal(root, clause_expr,
+ if (examine_opclause_args(expr->args, &clause_expr, NULL, NULL))
+ {
+ /* Check (Var op Const) or (Const op Var) clauses by recursing. */
+ if (IsA(clause_expr, Var))
+ return statext_is_compatible_clause_internal(root, clause_expr,
relid, attnums, exprs);
- /* Otherwise we have (Expr op Const) or (Const op Expr). */
- *exprs = lappend(*exprs, clause_expr);
- return true;
+ /* Otherwise we have (Expr op Const) or (Const op Expr). */
+ *exprs = lappend(*exprs, clause_expr);
+ return true;
+ }
+ else if (is_opclause_var_op_var(expr->args, &clause_expr_left, &clause_expr_right))
+ {
+ /* Check (Var op Var) clauses by recursing. */
+ if (!statext_is_compatible_clause_internal(root, clause_expr_left, relid, attnums, exprs))
+ return false;
+ if (!statext_is_compatible_clause_internal(root, clause_expr_right, relid, attnums, exprs))
+ return false;
+
+ return true;
+ }
+ else
+ return false;
}
/* Var/Expr IN Array */
@@ -1716,13 +1731,13 @@ static Selectivity
statext_mcv_clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid,
JoinType jointype, SpecialJoinInfo *sjinfo,
RelOptInfo *rel, Bitmapset **estimatedclauses,
- bool is_or)
+ enum ClauseType clause_type)
{
ListCell *l;
Bitmapset **list_attnums; /* attnums extracted from the clause */
List **list_exprs; /* expressions matched to any statistic */
int listidx;
- Selectivity sel = (is_or) ? 0.0 : 1.0;
+ Selectivity sel = (clause_type == OR_CLAUSE) ? 0.0 : 1.0;
RangeTblEntry *rte = planner_rt_fetch(rel->relid, root);
/* check if there's any stats that might be useful for us. */
@@ -1857,7 +1872,7 @@ statext_mcv_clauselist_selectivity(PlannerInfo *root, List *clauses, int varReli
list_exprs[listidx] = NULL;
}
- if (is_or)
+ if (clause_type == OR_CLAUSE)
{
bool *or_matches = NULL;
Selectivity simple_or_sel = 0.0,
@@ -1957,7 +1972,7 @@ statext_mcv_clauselist_selectivity(PlannerInfo *root, List *clauses, int varReli
*/
sel = sel + stat_sel - sel * stat_sel;
}
- else /* Implicitly-ANDed list of clauses */
+ else if (clause_type == AND_CLAUSE)
{
Selectivity simple_sel,
mcv_sel,
@@ -1991,6 +2006,16 @@ statext_mcv_clauselist_selectivity(PlannerInfo *root, List *clauses, int varReli
/* Factor this into the overall result */
sel *= stat_sel;
}
+ else if (clause_type == VAR_OP_VAR_CLAUSE)
+ {
+ /*
+ * Multi-column estimate using MCV statistics, along with base and
+ * total selectivities.
+ */
+ sel = mcv_clauselist_selectivity_var_op_var(root, stat, stat_clauses,
+ varRelid, jointype, sjinfo,
+ rel);
+ }
}
return sel;
@@ -2004,19 +2029,19 @@ Selectivity
statext_clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid,
JoinType jointype, SpecialJoinInfo *sjinfo,
RelOptInfo *rel, Bitmapset **estimatedclauses,
- bool is_or)
+ enum ClauseType clause_type)
{
Selectivity sel;
/* First, try estimating clauses using a multivariate MCV list. */
sel = statext_mcv_clauselist_selectivity(root, clauses, varRelid, jointype,
- sjinfo, rel, estimatedclauses, is_or);
+ sjinfo, rel, estimatedclauses, clause_type);
/*
* Functional dependencies only work for clauses connected by AND, so for
* OR clauses we're done.
*/
- if (is_or)
+ if (clause_type == OR_CLAUSE)
return sel;
/*
@@ -2102,6 +2127,51 @@ examine_opclause_args(List *args, Node **exprp, Const **cstp,
return true;
}
+/*
+ * is_opclause_var_op_var
+ * Split an operator expression's arguments into Var and Var parts.
+ *
+ * Attempts to match the arguments to (Var op Var), possibly with
+ * a RelabelType on top. When the expression matches this
+ * form, returns true, otherwise returns false.
+ *
+ * Optionally returns pointers to the extracted Var nodes, when passed
+ * non-null pointers (exprp_left, exprp_right).
+ */
+bool
+is_opclause_var_op_var(List *args, Node **expr_left, Node **expr_right)
+{
+ Node *leftop,
+ *rightop;
+
+
+ /* enforced by statext_is_compatible_clause_internal */
+ Assert(list_length(args) == 2);
+
+ leftop = linitial(args);
+ rightop = lsecond(args);
+
+ if (IsA(leftop, RelabelType))
+ leftop = (Node *) ((RelabelType *) leftop)->arg;
+
+ if (IsA(rightop, RelabelType))
+ rightop = (Node *) ((RelabelType *) rightop)->arg;
+
+ if (IsA(rightop, Var) && IsA(leftop, Var))
+ {
+ if(expr_left && expr_right)
+ {
+ *expr_left = (Node *) leftop;
+ *expr_right = (Node *) rightop;
+ }
+ }
+ else
+ return false;
+
+ Assert(expr_left && expr_right);
+
+ return true;
+}
/*
* Compute statistics about expressions of a relation.
diff --git a/src/backend/statistics/mcv.c b/src/backend/statistics/mcv.c
index b0e9aead84..dd1a1c0c82 100644
--- a/src/backend/statistics/mcv.c
+++ b/src/backend/statistics/mcv.c
@@ -1610,6 +1610,7 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
Assert(mcvlist->nitems <= STATS_MCVLIST_MAX_ITEMS);
matches = palloc(sizeof(bool) * mcvlist->nitems);
+
memset(matches, !is_or, sizeof(bool) * mcvlist->nitems);
/*
@@ -1639,73 +1640,113 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
bool expronleft;
int idx;
Oid collid;
+ Node *clause_expr_left,
+ *clause_expr_right;
fmgr_info(get_opcode(expr->opno), &opproc);
/* extract the var/expr and const from the expression */
- if (!examine_opclause_args(expr->args, &clause_expr, &cst, &expronleft))
- elog(ERROR, "incompatible clause");
+ if (examine_opclause_args(expr->args, &clause_expr, &cst, &expronleft))
+ {
+ /* match the attribute/expression to a dimension of the statistic */
+ idx = mcv_match_expression(clause_expr, keys, exprs, &collid);
- /* match the attribute/expression to a dimension of the statistic */
- idx = mcv_match_expression(clause_expr, keys, exprs, &collid);
+ /*
+ * Walk through the MCV items and evaluate the current clause. We
+ * can skip items that were already ruled out, and terminate if
+ * there are no remaining MCV items that might possibly match.
+ */
+ for (int i = 0; i < mcvlist->nitems; i++)
+ {
+ bool match = true;
+ MCVItem *item = &mcvlist->items[i];
- /*
- * Walk through the MCV items and evaluate the current clause. We
- * can skip items that were already ruled out, and terminate if
- * there are no remaining MCV items that might possibly match.
- */
- for (int i = 0; i < mcvlist->nitems; i++)
+ Assert(idx >= 0);
+
+ /*
+ * When the MCV item or the Const value is NULL we can treat
+ * this as a mismatch. We must not call the operator because
+ * of strictness.
+ */
+ if (item->isnull[idx] || cst->constisnull)
+ {
+ matches[i] = RESULT_MERGE(matches[i], is_or, false);
+ continue;
+ }
+
+ /*
+ * Skip MCV items that can't change result in the bitmap. Once
+ * the value gets false for AND-lists, or true for OR-lists,
+ * we don't need to look at more clauses.
+ */
+ if (RESULT_IS_FINAL(matches[i], is_or))
+ continue;
+
+ /*
+ * First check whether the constant is below the lower
+ * boundary (in that case we can skip the bucket, because
+ * there's no overlap).
+ *
+ * We don't store collations used to build the statistics, but
+ * we can use the collation for the attribute itself, as
+ * stored in varcollid. We do reset the statistics after a
+ * type change (including collation change), so this is OK.
+ * For expressions, we use the collation extracted from the
+ * expression itself.
+ */
+ if (expronleft)
+ match = DatumGetBool(FunctionCall2Coll(&opproc,
+ collid,
+ item->values[idx],
+ cst->constvalue));
+ else
+ match = DatumGetBool(FunctionCall2Coll(&opproc,
+ collid,
+ cst->constvalue,
+ item->values[idx]));
+
+ /* update the match bitmap with the result */
+ matches[i] = RESULT_MERGE(matches[i], is_or, match);
+ }
+ }
+ else if(is_opclause_var_op_var(expr->args, &clause_expr_left, &clause_expr_right))
{
- bool match = true;
- MCVItem *item = &mcvlist->items[i];
+ /* extract the var/expr and const from the expression */
+ int idx_left = mcv_match_expression(clause_expr_left, keys, exprs, &collid);
+ int idx_right = mcv_match_expression(clause_expr_right, keys, exprs, &collid);
- Assert(idx >= 0);
+ Assert((idx_left >= 0) && (idx_left < bms_num_members(keys) + list_length(exprs)));
+ Assert((idx_right >= 0) && (idx_right < bms_num_members(keys) + list_length(exprs)));
- /*
- * When the MCV item or the Const value is NULL we can treat
- * this as a mismatch. We must not call the operator because
- * of strictness.
- */
- if (item->isnull[idx] || cst->constisnull)
+ for (int i = 0; i < mcvlist->nitems; i++)
{
- matches[i] = RESULT_MERGE(matches[i], is_or, false);
- continue;
- }
+ MCVItem *item = &mcvlist->items[i];
- /*
- * Skip MCV items that can't change result in the bitmap. Once
- * the value gets false for AND-lists, or true for OR-lists,
- * we don't need to look at more clauses.
- */
- if (RESULT_IS_FINAL(matches[i], is_or))
- continue;
+ /*
+ * When either of the MCV items is NULL we can treat this
+ * as a mismatch. We must not call the operator because
+ * of strictness.
+ */
+ if (item->isnull[idx_left] || item->isnull[idx_right])
+ {
+ matches[i] = false;
+ continue;
+ }
- /*
- * First check whether the constant is below the lower
- * boundary (in that case we can skip the bucket, because
- * there's no overlap).
- *
- * We don't store collations used to build the statistics, but
- * we can use the collation for the attribute itself, as
- * stored in varcollid. We do reset the statistics after a
- * type change (including collation change), so this is OK.
- * For expressions, we use the collation extracted from the
- * expression itself.
- */
- if (expronleft)
- match = DatumGetBool(FunctionCall2Coll(&opproc,
- collid,
- item->values[idx],
- cst->constvalue));
- else
- match = DatumGetBool(FunctionCall2Coll(&opproc,
+ /*
+ * We don't store collations used to build the statistics,
+ * but we can use the collation for the attribute itself,
+ * as stored in varcollid. We do reset the statistics after
+ * a type change (including collation change), so this is OK.
+ */
+ matches[i] = DatumGetBool(FunctionCall2Coll(&opproc,
collid,
- cst->constvalue,
- item->values[idx]));
-
- /* update the match bitmap with the result */
- matches[i] = RESULT_MERGE(matches[i], is_or, match);
+ item->values[idx_left],
+ item->values[idx_right]));
+ }
}
+ else
+ elog(ERROR, "incompatible clause");
}
else if (IsA(clause, ScalarArrayOpExpr))
{
@@ -2083,6 +2124,45 @@ mcv_clauselist_selectivity(PlannerInfo *root, StatisticExtInfo *stat,
return s;
}
+/*
+ * mcv_clauselist_selectivity_var_op_var
+ * Use MCV statistics to estimate the selectivity of (Var op Var) clause.
+ *
+ * This determines which MCV items match clause and returns the sum of
+ * the frequencies of those items.
+ */
+Selectivity
+mcv_clauselist_selectivity_var_op_var(PlannerInfo *root, StatisticExtInfo *stat,
+ List *clauses, int varRelid,
+ JoinType jointype, SpecialJoinInfo *sjinfo,
+ RelOptInfo *rel)
+{
+ int i;
+ MCVList *mcv;
+ Selectivity s = 0.0;
+ RangeTblEntry *rte = root->simple_rte_array[rel->relid];
+
+ /* match/mismatch bitmap for each MCV item */
+ bool *matches = NULL;
+
+ /* load the MCV list stored in the statistics object */
+ mcv = statext_mcv_load(stat->statOid, rte->inh);
+
+ /* build a match bitmap for the clause */
+ matches = mcv_get_match_bitmap(root, clauses, stat->keys, stat->exprs,
+ mcv, false);
+
+ /* sum frequencies for all the matching MCV items */
+ for (i = 0; i < mcv->nitems; i++)
+ {
+ if (matches[i] != false)
+ {
+ s += mcv->items[i].frequency;
+ }
+ }
+
+ return s;
+}
/*
* mcv_clause_selectivity_or
diff --git a/src/include/statistics/extended_stats_internal.h b/src/include/statistics/extended_stats_internal.h
index 8eed9b338d..66b8b0d0b6 100644
--- a/src/include/statistics/extended_stats_internal.h
+++ b/src/include/statistics/extended_stats_internal.h
@@ -127,4 +127,10 @@ extern Selectivity mcv_clause_selectivity_or(PlannerInfo *root,
Selectivity *overlap_basesel,
Selectivity *totalsel);
+extern Selectivity mcv_clauselist_selectivity_var_op_var(PlannerInfo *root,
+ StatisticExtInfo *stat,
+ List *clauses, int varRelid,
+ JoinType jointype, SpecialJoinInfo *sjinfo,
+ RelOptInfo *rel);
+
#endif /* EXTENDED_STATS_INTERNAL_H */
diff --git a/src/include/statistics/statistics.h b/src/include/statistics/statistics.h
index 7f2bf18716..6bc4146af2 100644
--- a/src/include/statistics/statistics.h
+++ b/src/include/statistics/statistics.h
@@ -94,6 +94,14 @@ typedef struct MCVList
MCVItem items[FLEXIBLE_ARRAY_MEMBER]; /* array of MCV items */
} MCVList;
+/* Clause types of MCV lists */
+typedef enum ClauseType
+{
+ OR_CLAUSE, /* OR-clause */
+ AND_CLAUSE, /* AND-clause */
+ VAR_OP_VAR_CLAUSE, /* Var op Var */
+} ClauseType;
+
extern MVNDistinct *statext_ndistinct_load(Oid mvoid, bool inh);
extern MVDependencies *statext_dependencies_load(Oid mvoid, bool inh);
extern MCVList *statext_mcv_load(Oid mvoid, bool inh);
@@ -118,7 +126,7 @@ extern Selectivity statext_clauselist_selectivity(PlannerInfo *root,
SpecialJoinInfo *sjinfo,
RelOptInfo *rel,
Bitmapset **estimatedclauses,
- bool is_or);
+ enum ClauseType clause_type);
extern bool has_stats_of_kind(List *stats, char requiredkind);
extern StatisticExtInfo *choose_best_statistics(List *stats, char requiredkind,
bool inh,
@@ -126,5 +134,6 @@ extern StatisticExtInfo *choose_best_statistics(List *stats, char requiredkind,
List **clause_exprs,
int nclauses);
extern HeapTuple statext_expressions_load(Oid stxoid, bool inh, int idx);
+extern bool is_opclause_var_op_var(List *args, Node **exprp_left, Node **exprp_right);
#endif /* STATISTICS_H */
diff --git a/src/test/regress/expected/stats_ext.out b/src/test/regress/expected/stats_ext.out
index 8c4da95508..5a76ddbc72 100644
--- a/src/test/regress/expected/stats_ext.out
+++ b/src/test/regress/expected/stats_ext.out
@@ -2005,6 +2005,42 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = 1 OR b = '
343 | 200
(1 row)
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = c');
+ estimated | actual
+-----------+--------
+ 25 | 1250
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a != c');
+ estimated | actual
+-----------+--------
+ 4975 | 3750
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a > c');
+ estimated | actual
+-----------+--------
+ 1667 | 3750
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a >= c');
+ estimated | actual
+-----------+--------
+ 1667 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a < c');
+ estimated | actual
+-----------+--------
+ 1667 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a <= c');
+ estimated | actual
+-----------+--------
+ 1667 | 1250
+(1 row)
+
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a IN (1, 2, 51, 52) AND b IN ( ''1'', ''2'')');
estimated | actual
-----------+--------
@@ -2158,6 +2194,42 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = 1 OR b = '
200 | 200
(1 row)
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = c');
+ estimated | actual
+-----------+--------
+ 1250 | 1250
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a != c');
+ estimated | actual
+-----------+--------
+ 3750 | 3750
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a > c');
+ estimated | actual
+-----------+--------
+ 3750 | 3750
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a >= c');
+ estimated | actual
+-----------+--------
+ 5000 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a < c');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a <= c');
+ estimated | actual
+-----------+--------
+ 1250 | 1250
+(1 row)
+
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a IN (1, 2, 51, 52) AND b IN ( ''1'', ''2'')');
estimated | actual
-----------+--------
@@ -2573,6 +2645,109 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a IS NULL AND
3750 | 2500
(1 row)
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = c');
+ estimated | actual
+-----------+--------
+ 25 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a != c');
+ estimated | actual
+-----------+--------
+ 4975 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a > c');
+ estimated | actual
+-----------+--------
+ 1667 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a >= c');
+ estimated | actual
+-----------+--------
+ 1667 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a < c');
+ estimated | actual
+-----------+--------
+ 1667 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a <= c');
+ estimated | actual
+-----------+--------
+ 1667 | 0
+(1 row)
+
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b = d');
+ estimated | actual
+-----------+--------
+ 25 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b != d');
+ estimated | actual
+-----------+--------
+ 4975 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b < d');
+ estimated | actual
+-----------+--------
+ 1667 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b <= d');
+ estimated | actual
+-----------+--------
+ 1667 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b > d');
+ estimated | actual
+-----------+--------
+ 1667 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b >= d');
+ estimated | actual
+-----------+--------
+ 1667 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b != d');
+ estimated | actual
+-----------+--------
+ 4975 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b < d');
+ estimated | actual
+-----------+--------
+ 1667 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b <= d');
+ estimated | actual
+-----------+--------
+ 1667 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b > d');
+ estimated | actual
+-----------+--------
+ 1667 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b >= d');
+ estimated | actual
+-----------+--------
+ 1667 | 2500
+(1 row)
+
-- create statistics
CREATE STATISTICS mcv_lists_stats (mcv) ON a, b, d FROM mcv_lists;
ANALYZE mcv_lists;
@@ -2606,6 +2781,72 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a IS NULL AND
2500 | 2500
(1 row)
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b = d');
+ estimated | actual
+-----------+--------
+ 2500 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b != d');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b < d');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b <= d');
+ estimated | actual
+-----------+--------
+ 2500 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b > d');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b >= d');
+ estimated | actual
+-----------+--------
+ 2500 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b != d');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b < d');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b <= d');
+ estimated | actual
+-----------+--------
+ 2500 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b > d');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b >= d');
+ estimated | actual
+-----------+--------
+ 2500 | 2500
+(1 row)
+
-- mcv with pass-by-ref fixlen types, e.g. uuid
CREATE TABLE mcv_lists_uuid (
a UUID,
@@ -2700,6 +2941,78 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a AND
1094 | 0
(1 row)
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a = b');
+ estimated | actual
+-----------+--------
+ 9950 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a != b');
+ estimated | actual
+-----------+--------
+ 50 | 7500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a < b');
+ estimated | actual
+-----------+--------
+ 3333 | 10000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a <= b');
+ estimated | actual
+-----------+--------
+ 3333 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a > b');
+ estimated | actual
+-----------+--------
+ 3333 | 7500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a >= b');
+ estimated | actual
+-----------+--------
+ 3333 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a = b AND b = c');
+ estimated | actual
+-----------+--------
+ 50 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a != b AND b != c');
+ estimated | actual
+-----------+--------
+ 50 | 1250
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a < b AND b < c');
+ estimated | actual
+-----------+--------
+ 1111 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a <= b AND b <= c');
+ estimated | actual
+-----------+--------
+ 1111 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a > b AND b > c');
+ estimated | actual
+-----------+--------
+ 1111 | 1250
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a >= b AND b >= c');
+ estimated | actual
+-----------+--------
+ 1111 | 0
+(1 row)
+
CREATE STATISTICS mcv_lists_bool_stats (mcv) ON a, b, c
FROM mcv_lists_bool;
ANALYZE mcv_lists_bool;
@@ -2727,6 +3040,78 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a AND
1 | 0
(1 row)
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a = b');
+ estimated | actual
+-----------+--------
+ 2500 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a != b');
+ estimated | actual
+-----------+--------
+ 7500 | 7500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a < b');
+ estimated | actual
+-----------+--------
+ 10000 | 10000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a <= b');
+ estimated | actual
+-----------+--------
+ 2500 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a > b');
+ estimated | actual
+-----------+--------
+ 7500 | 7500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a >= b');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a = b AND b = c');
+ estimated | actual
+-----------+--------
+ 8750 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a != b AND b != c');
+ estimated | actual
+-----------+--------
+ 7500 | 1250
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a < b AND b < c');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a <= b AND b <= c');
+ estimated | actual
+-----------+--------
+ 8750 | 2500
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a > b AND b > c');
+ estimated | actual
+-----------+--------
+ 1250 | 1250
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a >= b AND b >= c');
+ estimated | actual
+-----------+--------
+ 10000 | 0
+(1 row)
+
-- mcv covering just a small fraction of data
CREATE TABLE mcv_lists_partial (
a INT,
@@ -2914,6 +3299,90 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = 0 OR
2649 | 1572
(1 row)
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = b AND c = d');
+ estimated | actual
+-----------+--------
+ 1 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a != b AND c != d');
+ estimated | actual
+-----------+--------
+ 4950 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a < b AND c > d');
+ estimated | actual
+-----------+--------
+ 556 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b AND c >= d');
+ estimated | actual
+-----------+--------
+ 556 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = b OR c = d');
+ estimated | actual
+-----------+--------
+ 50 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a != b OR c != d');
+ estimated | actual
+-----------+--------
+ 5000 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a < b OR c > d');
+ estimated | actual
+-----------+--------
+ 2778 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b OR c >= d');
+ estimated | actual
+-----------+--------
+ 2778 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b AND d >= c');
+ estimated | actual
+-----------+--------
+ 556 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b OR d >= c');
+ estimated | actual
+-----------+--------
+ 2778 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a < b');
+ estimated | actual
+-----------+--------
+ 1667 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a > b');
+ estimated | actual
+-----------+--------
+ 1667 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b');
+ estimated | actual
+-----------+--------
+ 1667 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a >= b');
+ estimated | actual
+-----------+--------
+ 1667 | 5000
+(1 row)
+
-- create separate MCV statistics
CREATE STATISTICS mcv_lists_multi_1 (mcv) ON a, b FROM mcv_lists_multi;
CREATE STATISTICS mcv_lists_multi_2 (mcv) ON c, d FROM mcv_lists_multi;
@@ -2960,6 +3429,90 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = 0 OR
1571 | 1572
(1 row)
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = b AND c = d');
+ estimated | actual
+-----------+--------
+ 5000 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a != b AND c != d');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a < b AND c > d');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b AND c >= d');
+ estimated | actual
+-----------+--------
+ 5000 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = b OR c = d');
+ estimated | actual
+-----------+--------
+ 5000 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a != b OR c != d');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a < b OR c > d');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b OR c >= d');
+ estimated | actual
+-----------+--------
+ 5000 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b AND d >= c');
+ estimated | actual
+-----------+--------
+ 5000 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b OR d >= c');
+ estimated | actual
+-----------+--------
+ 5000 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a < b');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a > b');
+ estimated | actual
+-----------+--------
+ 1 | 0
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b');
+ estimated | actual
+-----------+--------
+ 5000 | 5000
+(1 row)
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a >= b');
+ estimated | actual
+-----------+--------
+ 5000 | 5000
+(1 row)
+
DROP TABLE mcv_lists_multi;
-- statistics on integer expressions
CREATE TABLE expr_stats (a int, b int, c int);
diff --git a/src/test/regress/sql/stats_ext.sql b/src/test/regress/sql/stats_ext.sql
index 0c08a6cc42..34513224ed 100644
--- a/src/test/regress/sql/stats_ext.sql
+++ b/src/test/regress/sql/stats_ext.sql
@@ -999,6 +999,18 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = 1 OR b = '
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = 1 OR b = ''1'' OR c = 1 OR d IS NOT NULL');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a != c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a > c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a >= c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a < c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a <= c');
+
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a IN (1, 2, 51, 52) AND b IN ( ''1'', ''2'')');
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a IN (1, 2, 51, 52, NULL) AND b IN ( ''1'', ''2'', NULL)');
@@ -1054,6 +1066,18 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = 1 OR b = '
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = 1 OR b = ''1'' OR c = 1 OR d IS NOT NULL');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a != c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a > c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a >= c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a < c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a <= c');
+
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a IN (1, 2, 51, 52) AND b IN ( ''1'', ''2'')');
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a IN (1, 2, 51, 52, NULL) AND b IN ( ''1'', ''2'', NULL)');
@@ -1255,6 +1279,40 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = 1 OR b = '
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a IS NULL AND (b = ''x'' OR d = ''x'')');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a != c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a > c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a >= c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a < c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a <= c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b = d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b != d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b < d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b <= d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b > d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b >= d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b != d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b < d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b <= d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b > d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b >= d');
+
-- create statistics
CREATE STATISTICS mcv_lists_stats (mcv) ON a, b, d FROM mcv_lists;
@@ -1273,6 +1331,28 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a = 1 OR b = '
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE a IS NULL AND (b = ''x'' OR d = ''x'')');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b = d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b != d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b < d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b <= d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b > d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b >= d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b != d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b < d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b <= d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b > d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists WHERE b >= d');
+
-- mcv with pass-by-ref fixlen types, e.g. uuid
CREATE TABLE mcv_lists_uuid (
a UUID,
@@ -1348,6 +1428,30 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a AND
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a AND b AND NOT c');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a = b');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a != b');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a < b');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a <= b');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a > b');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a >= b');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a = b AND b = c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a != b AND b != c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a < b AND b < c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a <= b AND b <= c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a > b AND b > c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a >= b AND b >= c');
+
CREATE STATISTICS mcv_lists_bool_stats (mcv) ON a, b, c
FROM mcv_lists_bool;
@@ -1361,6 +1465,30 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a AND
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a AND b AND NOT c');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a = b');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a != b');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a < b');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a <= b');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a > b');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a >= b');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a = b AND b = c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a != b AND b != c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a < b AND b < c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a <= b AND b <= c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a > b AND b > c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_bool WHERE NOT a >= b AND b >= c');
+
-- mcv covering just a small fraction of data
CREATE TABLE mcv_lists_partial (
a INT,
@@ -1461,6 +1589,25 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = 0 AN
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE (a = 0 AND b = 0) OR (c = 0 AND d = 0)');
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = 0 OR b = 0 OR c = 0 OR d = 0');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = b AND c = d');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a != b AND c != d');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a < b AND c > d');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b AND c >= d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = b OR c = d');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a != b OR c != d');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a < b OR c > d');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b OR c >= d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b AND d >= c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b OR d >= c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a < b');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a > b');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a >= b');
+
-- create separate MCV statistics
CREATE STATISTICS mcv_lists_multi_1 (mcv) ON a, b FROM mcv_lists_multi;
CREATE STATISTICS mcv_lists_multi_2 (mcv) ON c, d FROM mcv_lists_multi;
@@ -1475,6 +1622,25 @@ SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = 0 AN
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE (a = 0 AND b = 0) OR (c = 0 AND d = 0)');
SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = 0 OR b = 0 OR c = 0 OR d = 0');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = b AND c = d');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a != b AND c != d');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a < b AND c > d');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b AND c >= d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a = b OR c = d');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a != b OR c != d');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a < b OR c > d');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b OR c >= d');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b AND d >= c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b OR d >= c');
+
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a < b');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a > b');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a <= b');
+SELECT * FROM check_estimated_rows('SELECT * FROM mcv_lists_multi WHERE a >= b');
+
DROP TABLE mcv_lists_multi;
--
2.34.1
On 8/12/24 17:57, Ilia Evdokimov wrote:
On 12.8.24 14:53, Tomas Vondra wrote:
I agree, and I'm grateful someone picked up the original patch. I'll try
to help to keep it moving forward. If the thread gets stuck, feel free
to ping me to take a look.Good. Thank you!
I started reviewing it and want to suggest some changes to better code:
I think we should consider the case where the expression is not neither
an OpExpr and VarOpVar expression.Do you have some specific type of clauses in mind? Most of the extended
statistics only really handles this type of clauses, so I'm not sure
it's feasible to extend that - at least not in this patch.I agree with Alena that we need to consider the following clauses: (Expr
op Var), (Var op Expr) and (Expr op Expr). And we need to return false
in these cases because we did it before my patch in/* Check if the expression has the right shape */
if (!examine_opclause_args(expr->args, &clause_expr, NULL, NULL))
return false;In is_opclause_var_op_var() function it is really useless local Node
*expr_left, *expr_right variables. However, we can't assign them NULL at
the begin because if I passed not-null pointers I have to return the
values. Otherwise remain them NULL.Nevertheless, thank you for review, Alena.
Ah, right. I agree we should handle clauses with expressions.
I don't recall why I wrote is_opclause_var_op_var() like this, but I
believe this was before we allowed extended statistics on expressions
(which was added in 2021, the patch is from 2020). I don't see why it
could not return expressions, but I haven't tried.
Have you tested this code with any benchmarks?
FWIW I think we need to test two things - that it (a) improves the
estimates and (b) does not have significant overhead.Yes, but only TPC-B. And the performance did not drop. In general, it'd
be better to do more tests and those listed by Tomas with new attached
patch.
Is TPC-B really interesting/useful for this patch? The queries are super
simple, with only a single clause (so it may not even get to the code
handling extended statistics). Did you create any extended stats?
I think you'll need to construct a custom test, with queries that have
multiple (var op var) clauses, extended stats created, etc. And
benchmark that.
FWIW I don't think it makes sense to benchmark the query execution - if
the estimate improves, it's possible to get arbitrary speedup, but
that's expected and mostly mostly irrelevant I think.
What I'd focus on is benchmarking just the query planning - we need the
overhead to be negligible (or at least small) so that it does not hurt
people with already good plans.
BTW can you elaborate why you are interested in this patch? Do you just
think it's interesting/useful, or do you have a workload where it would
actually help? I'm asking because me being uncertain how beneficial this
is in practice (not just being nice in theory) was one of the reasons
why I didn't do more work on this in 2021.
regards
--
Tomas Vondra
On 12.8.24 19:25, Tomas Vondra wrote:
Is TPC-B really interesting/useful for this patch? The queries are super
simple, with only a single clause (so it may not even get to the code
handling extended statistics). Did you create any extended stats?
No, it's not the case. I simply wanted to verify that other queries are
not slowed down after applying my patch.
I think you'll need to construct a custom test, with queries that have
multiple (var op var) clauses, extended stats created, etc. And
benchmark that.
I used the test generator from a previous thread [1]/messages/by-id/ecc0b08a-518d-7ad6-17ed-a5e962fc4f5f@enterprisedb.com and ran it with
|default_statistics_target = 1000| to achieve more accurate estimates
for 3000 rows. It would also be beneficial to run tests with 10,000 and
100,000 rows for a broader perspective. I've attached both the Python
test and the results, including the data. Here’s a breakdown of the issues:
1. (A op A) Clause: Before applying my patch, there were poor estimates
for expressions like |(A op A)|. Currently, we only have correct
estimates for the |(A = A)| clause, which transforms into |A IS NOT
NULL|. Should I address this in this thread? I believe we should
extend the same correction to clauses like |(A != A)|, |(A < A)|,
and similar conditions. However, this issue is not for current thread.
2. AND Clauses: The estimates for AND clauses were inaccurate before my
patch. I noticed code segments where I could add something specific
for the |(Var op Var)| clause, but I'm unsure if I'm missing
anything crucial. If my understanding is incorrect, I'd appreciate
any guidance or corrections.
FWIW I don't think it makes sense to benchmark the query execution - if
the estimate improves, it's possible to get arbitrary speedup, but
that's expected and mostly mostly irrelevant I think.What I'd focus on is benchmarking just the query planning - we need the
overhead to be negligible (or at least small) so that it does not hurt
people with already good plans.BTW can you elaborate why you are interested in this patch? Do you just
think it's interesting/useful, or do you have a workload where it would
actually help? I'm asking because me being uncertain how beneficial this
is in practice (not just being nice in theory) was one of the reasons
why I didn't do more work on this in 2021.
I have two reasons for pursuing this. Firstly, I've encountered some of
these queries in practice, although they are quite rare. While it might
be easy to dismiss these cases due to their infrequency, I believe that
we shouldn't overlook the opportunity to develop better handling for
them, regardless of how seldom they occur.
Secondly, I see that you're working on improving estimates for JOIN
clauses in thread [2]/messages/by-id/c8c0ff31-3a8a-7562-bbd3-78b2ec65f16c@enterprisedb.com. I believe that enhancing estimates for these rare
cases could also benefit future work on JOIN queries, particularly those
with multiple |ON (T1.column = T2.column)| conditions, which are
essentially |(Var op Var)| clauses. My idea is to start with non-JOIN
queries, and then apply the same approach to improve JOIN estimates. Of
course, I might be wrong, but I think this approach has potential.
[1]: /messages/by-id/ecc0b08a-518d-7ad6-17ed-a5e962fc4f5f@enterprisedb.com
/messages/by-id/ecc0b08a-518d-7ad6-17ed-a5e962fc4f5f@enterprisedb.com
[2]: /messages/by-id/c8c0ff31-3a8a-7562-bbd3-78b2ec65f16c@enterprisedb.com
/messages/by-id/c8c0ff31-3a8a-7562-bbd3-78b2ec65f16c@enterprisedb.com
--
Regards,
Ilia Evdokimov,
Tantor Labs LCC.
Attachments:
tests.zipapplication/zip; name=tests.zipDownload
PK 7�Y �
data.csvUT
KP�f�3�fKP�fux � � �}��e�����S��=��H����,��f$�x0�?T#)wU��#�s�����o��k�g��"eV�R�7n
��7�o�����?����?����o����o�����?��n|����/�����}��O��������?��?��o������_��_�O��?����O������������������_����?����_��_����ix��kh�U�b���r%�����������g���Z��t��E!Me���"x|����W��}6����������?�������o��[����+�-���G6>�C�j�J��s�� �A6�������b�_}��{��X�>�uR����y�V[����w?����?���7JT���TN}H1N����y3��#���7���Y ����9��j�� q��5{�R�����A�q���W���a�^k�Z���F-�*��{��a$�X���^��7���}���=�������9� ��U-�V������������7K��%�T��6s�qs�Tlv���cs ����]
�����j���65�Pc�)�-�q2�M�p�so��wn���S��s���2�� ���U��� <�[����T&/�Y�H�T� ���U����5�?Z���������O���l�2~/U����"���gyp��l���{
F�x�a�9��p���Jm�g*>����Y�2|�>������n�,St��:�c3�NP��m?:��[^{��(e�����TS��K�}:�H��J����_�����!z������o�4�;�j�D#�=[���Y�}2rvp�1�5CpB���3O�S�%�\�f�q7��)K���?{�^��7h��[�V�L
s����T�gw���Z�W�7��m��o�6����3MPR�m�z�[��=u�M
�7��������"��T�hr)����7�Le��f/-�@��dt�A�
�0s�xK�V��:��6CP7�5��������h=["�AMg<�BqIz�� ��Mo��������]L� 6�@�=������}Fv�_!����V�u�Z����I��3K���8�]�4�B����o<�=�Q���1�-S'�������{�
��������4!k�Cz�P���d}�{������O���dN���M��$���7��C���?9�g�*�vV�e�nP�,������� 9��w;��"l��s����T����J�?������@���
�_�\/"���D�8h��A]�H��U�b��<�%�'���VP���V��X� lc�:������1��K���pH�c%�����K��4Jmj ��|�2>�^�S��%��,�V=h��^�����z�I�����I)��7��u �Y�Y�`_�`AeN%�|��=�s��st����+��t�~y��`m�)fR�B�a�O�u3
�#d�A������[��o�s��|��IS��"r*�bU^����O����I���������;j��Z~����p�*���VK���fN�*�.!J��7>8�[X��#Y��
*q�Q��WM�$y{���~��������V`'l���R+T�
_-���@�Fw=������q�i�-�.��C�� L���>�o ��g��K(��X���z�<sq�����,*�U �`��z�0��pEy������������}�h���W�I��1���TY�;��K��07~��)����h/�����������}��@:��DJe����`�������5?u�3��4zgMt���t�7����<m���Re�sJ-6��;�f��%L%����l(���K-��U�����g��@�d�K��C,����/�a�x6c��g��@.]�c>=�F����zR�� ���0"[(��0jS}���=�����Q;8��a}�3Q� _�a`�Y�&���O1��0��������4�����:�fRSr(�u#�p�mj�j�gEB����C�d��#�di��Ph��$���up�S������FhlOX�g�L���^9�#�Sk���.be��V{v����Q��,oD��{
�I/Z�{)�XA����et�u�^�dz8�{��i������I`�\�����r-~�n�>����4����\h��!uU�6����T�&S��@��N�G�P�s���t�o���J�����E4�U��w}������A
������*-V�Q������'{��~Q^k+��rU�fb�>A��l
8)�'�\^]gz4l}��r���F�X3;�V��
h�v��O�j_�c�w���(�t&��7EF��
_b��5����%Qiix`��.LA.�1����Sz���d��6^OK�
�D���S�.�M��a���p�s����]FQ�����{1n&Z� ��DrP����._���� M�O$�}d_�
��k:S?�t�f ��������fK�}z5�\x:T�]V���Z�����`�v�����' �P��������.�Z������.� -Q�,�a�ZVH3��V�|�B�a������AiB���8�f) b�{�s>^��:����F+�$'Pp����!Z�w>�mEm�G�wk�:R��J�
��(,�sx�C6o!]���)2��"����Zi���r����t�p�S9�W���v��aX��V�:h��
��j#�H��AN�e?E�Q)
�y�>I�S)Y��^��%w��A�]�T�_M�G�:����K��N�hN��j6vs�TTK�HdW��NS�%�q�rv��z ���$�>RO�f��R�'�.%��P��L��^��V���%la����`��[v�������K�[ hn�{_u�����D��R�����`�oO�����e
L���39@\/`������m��>������������$��=�
����}��K�o�N]C�_���A����(@�dT�]���������x�z�2����
i9|]��
g�6��Z���^2�O/F�$M���� T��b[X�,@aLa�<�� D�QK�������(�]�+f�j~)<R�p�g����ZR*�6Y
k�q��xfN�����nC��<zVj|hU�8[qkm�Q��0va��Z>�����y6]L������`4��V2�� ]+�������G�p�G2R� ��R��m=�r��z�$]�,'��������Q��_8�)�/U�x���m%������w{�!��.C�Q�Xr������5��t��O��4��{kL\@@��XX���CU�t ���.�/dI�{��V�,���n��~�������i?<�MX�M�Z4��H�%��j�����{��O���$h��f���2z��<�Z�|����N��2HG��}@"T���J� �J���8�&�����������j��>%g��+T�}�sJ'^a+{�s����������' ��H��K���5��t����#�+{���x�|T9��]�eF@u�����&S�'V��<���O�g��H���0��h�g��p��_n��������m��hr��Z^�@`x�8��fm�J�8��[�p��.r�lk���p�������6�HS)lE4m����T���G7^}��4��`m�U [�:F� r��p|���o6��y�����C&��X�.i?=�Mx�h��!MLu5aL�U�������N����*Wq���i�;���sU�9g������x"���������I�
������2��QL5O���|r�66�y����O����H^��@�VI'Xim�6����}���d}I��U�Ji�Y�f�%��7e���X>�����j+4��
�2��%�bD�x�����2�_�o��=�Wk�Hi��XZ�;���i����'��m�� [$�P���<T�U������qx'����F�c�E@�{9���'To��>(��I�0�Z
���l=$t/6�������#�l`!����V�:�L�.���_)&|���>�r�l>��_��R�s���(��6�e�~���w7��z���f�_��H)������������q���k�����������/����|9�s��������ak�%/7^�C-4������n,��0�/u\���5�z��4�_&e�8h�P�&���Z�����l��������wn����9��X�:_E<?N�>����
�s�`����6 |3�ow_^���Tas�����\ue�p�3�$b5��\m�K���?���>��5���Z�/��\�GUPf�N7����D8tV��)K�m�LKG}SM�����M����.����eJ����>���p3�\�+��>�Cg��{��9�\k�T����&��zK
�O�y ]_���V����gP#���u�Ask@�����S���K?�����8�k��'W��j�}�$���/}�&��|���Y5���,R1���������Y~4�C�2���~�s@���l��$N�P���|?���^�C��+(l�������[Yzpb�n���i�x�;�|^�z�;S�R���6R�DKh]���E���6�^"T�x�^�����
GGj�����;�����G1�\)(1���.���N�f
kxM��&_�������lu!�����%�������Q����g����x���R�z�b�A&�I���O������������\k��VVZ�T^W��(�9���I���L���g�<k�T�0�s����h�r=����x^�����.zR���0�����ji{�j�O����}B0�Q�RzFiw8P�<�0�������X>l�N����Z���D��4vu~�=����U�c���v���N�D��q�n(�����S�p���������U�3g�ee���*u�������(g��>?I��uR���
!�����c�`�J���F"�!^�6F-�9�y��<1�38�]]��:�KR��������`eu�fH�M��1�Z�������q)����Wi��,���&�z��D(�8�Z�LC���������� ~���D
.
�X,V���K��DH���gU��*���w) zj���+Z�� ���xJ��k��-��s��k�����{���w%����\f��X�ck|�;�� � ����[�r.R�Hn|�0-$�]�;���y���5�����<�OR���d��1����5����@�4�����[������e������;����U���������<����N3�}����5n%K<Sd���:�������F�Nh4Y��|�1��0���<��{A����&7�2D���tK�����@�@��>I�x�����nN�`^:.��&N�jgfK���K;����� ���QI:i��;��O�qS6r�9p
�?������I���"1�,�Jx�ZZ �Y�}�3y��������m����TSo�}���5��CynI������N%���Yg�L��Zt�&O�r)G�8.D���#?%d'�5����C)P2���Z���V��co��-�x9���0l"��)�d�� 9'�L,�����8���LLbY�)��
�0fP�� ?�V�pi;��8�Q�5�M�5��vh��B2�*^q[Uy�B.{������
���6�4�
*������/0����>��?���S�e�u������ff�^�Q��������I����40W�A��$Dw��p���y���k��:����$�:�(����S�/��H$�f�����fy�A$�x��5�cfJ�K>f�'�����.o�tI(u��Usg�����f���G'U�w�+�)W���U���5����C��$���\���%��X���m��)��=\������12�
2�7l�C�G]��#��Tm9�y�u�0��x��9HP�#��!�H�h�k-��0�w� �@IV�����*�[�W�]��*�;�4u���K�"���W�8?��`n���`O(P�23#n\����*���,����S�>��$���V'����.��y <��??���Z���]��r#L/�0�m�3�9�eKD�s����`�Z�*
zd�T.y&��&
�"�����xr�����j���ofj`��f�i���\ �|4�o��95��t��5v��wf.�~��9����7�e��T��}�����k7�������O������������ ��C���z�2�_H�o��r���l$��U�Q��$_��k���~�����b�w���$�8x��k�P�rwI�����9�ou���"�mX����� r\aiM�S�B��$[��Z>n�z��{�Pj����t,�^o�d�W6���������������%9+��6�����2�(�g%�O�v�> ������~x�b�|jORg�x�k��Z��?G���CH>���e
���i��Z�
���y�X��f���P�������C(Z�J.��Y�;���\Eweq���e����{|����EPR����u+Z���k����u���F7f��.�*����KG�D��%y���ER���I]��r�'UO��#N�����Ut
���$�2��%=�������?p��:���VUJ��������C��2�wk�^2�D�%�������`GyN�9��w?;0x v����iR�E!o���5XB+�yr@����
���� R��L�u�G�- WJ�XS���A��L���=�w|�r��e���S��6�<y��\S��n�1_�@��0��
��3���9�;k����&�p��-"�5� �F<������U�`ql?�Fi��\b�����L��m�i^X2������Ut
��]*i���e���L�db�R�;�^��d�JF�Bc�[h��B{_6��V�g�j6����2����������R�[��jr�����e�KT'�,-�_��k��������R) �3��KP��� ,9|2`_��_�V�Y���X�7f|��Y��������3�}�����zco�X���{8�����k`�d9X���a.NI���(/���5��JV�������^�u��?�m�`���x���&W;�\[_�H�M(9�@����BW��B�������������7M51���4<�Y����;�Ka�G�Q�l�lDV��^�pj��z�������Z����m������I�J-�k�j��p�|�������r����� Ly������8��������}D4oo��0�Y.- ��
�Z�e�>,����ky�����->�����j�Y4�[T�;�?��x��Y��:.�9�mc7���?DC���yA/�R�������rb��K�
��+��4��a&�����r�`����2<��y���
�F
��j��k���:bq
��1�'C?�u������J/�{��7��)�~���MF]���9_� ^������6�����Z��l3-�
�6���i�8��P��Q�� w�HD���6��o�Tn���X�q4�Jm���fXyr
�������Kt~*���zY�M�����$�EJ6�A���t�����8�����J���m�:�c�a�aZ����6JJ�����N��6"���7��>��<�3�� �rw���\����$�N+���} $J����>�( {X$����[�����F�R���>;�����c��N�����D��f�$�K�LRRO��$��!=u�E������
��Fgu�a���$�TR��
���^����tu>�M %�0���%-�#�L|E9{� NcVO��e���W-��Q�:�S�I
1��sg,r��Sg#�^����$$��,-_bG@��<`���8�u1�w� ��R�eN'�Q�LNy��X#�����!��V�����s)6C`o:������wtw���`E���Z�����-an���|\���z�; �bS� rv�Qf`-��d�e*z?;��Q��/i�?\��PL�
[���9�;)�^�B�&e�%��E>.v��C=-��i�����y�#3��q(�����2� ��t��|/k+q���J�goz��{�|w�8,�q.���%\��O��f��Y�T��
�\�}��p.H�mVwt�<G��0M5nh[b�|W����;��������`�7���l����m�%B}�� ���*vO����_�p4�o<��o��l�AY������@�k���F���Kr����~l'�"��sL4��W2[�t�sY��)
������^���}����pz��u�O�}��J�+!n��.�z� #~o:{wI}�0�����l<j��i�}u�O\����K���>��g�j�qi������5����:Wb��jk�Ms8�G�O�@�V���M���2�-�a�
Aw���' ��� N.��J@�x�w�.������Q���W]�bu���r�A�dpYj�����J9;��������!pa(��8_|:[j����>�#{*O�a���{�<k��^gQ�$K���p�S��o�� ]o~�x!�W� \�b!����q��3[���ao���[x�B�ap��]w�)�3���q�H�<�����e,q�1hW�����sT���������\��m�������/���K�;� ��F���[��8����[iZ���\���J������3�r�{��F(w��#`\��Ag��6��l�}���uPtI�"Ue�r���Jp� }���;�����Z������THw�X�#�����F>�=��9��R�8�F���56S����z1o������u�dj��)�9(�JR�'���%_��}w��6���8�]j9qdB����������I�<�,i������YK��z��nt��f97^���$���2����nC�6krv�.�UZ��j�5�|���s�KM
�(c���
}���m���"T��ih�.� 4�k7���x<��J]w�)�
J�D�"�,���Y�F��
�w����[���\k
Ca�x����:��$�#��
������� u�5��M� �
��;��2��6���D�~��!��U���":���m�;��:X�=��yP �������o]�f_�~G/v�x���� �������y�/���0�����8q��]�����5��h)8��a�"������6�����t��#��'��Uo4fh����"��~�`��z-�����t�1g)X{�d�]K�����]��DZ%M�h��0���=���>�D7�/�����i���y�Kcx6I
trCR9P�����TW��5j��4_�-Z��tu����T�y\<����4?������b�JU5y@)a�����)�g��6o?��� �-,{�%�����f_R�}��Q�Wo��GMsI/4�B�4G��-�~���r���'���zX�A=�Ae�������v<�H���_���,~������L�h��Z�;�9S~� �M���xp��`TX
�t��������a���[�����^�.�HV \���P�{����v�r���7M^(��5)`��5�I�\�����0����+��F�a�fDn�NLu��g*k���vr��x���t{C���y�k�����8|1�4�� ��_������k����Z��Pc�u���K=���?���������?PK�=5B�% �
PK ��Y +�� results.csvUT
�P�f�P�f�P�fux � � ����$��$����w'v>���x�j����[��E����m UD�'*���u+3�i�TU�����_���x���?��8�M�6��������|x��;�����������������2�����i�����x���x�-���_�t�K�5���o����_t�No~z������:��_�����4{C������q�/�h:��#��m�{A\���
���+t��_���
��[����.�#�F_��z�����EwY�����������G�M�1h#|�����8�g3�/r�!�d����0�������>�V�y�v���Z��3���j(.�65����x�!����!}����h!�Z��u��l�!��B�r ��R�Qg�� �x�������z�e��aS?$(f7��D�}�����JP��l����}�e�a���t������@��{!��zq���?]�(�`�(��k���������I�p�Kh,��^� ���O���?�c���x��O��� ���/$��s��-�3C�pU-�R�r ����������>��&�����
5���
�N$���=W��:�6�z�����~}�����}}��f�'�ja���)��~}�����{vv���QW�`�^��O�������j�L����l���^W�aB��d�tx�� ���gz�i����dX�L�Nm�r;��<�uW�=LK7�x���z���y������~%KQ;�Sz�}"��g=���4k/����g'���2�$0/����a����D�C��aYR�b���-�`����P���n�Y:4@�h���3��Dm3�9�g����{��y�. �����j1����sq/�y����m�n��!�=�D�N�040?Og�����X����s��k���;�J�A�7p�_b�����`��.����_�/�[��W���3� �
7��s���������/{�<�g����C�g���eO^��'[9��[+j: ��;Z�RsN�����9��WP@�s��1����l�����!t�< ���:��0Y�h���M��`��� �
f���}<������cL�����C��p��* �x�4H�8caB��%��YJc���E�V�B?�m~������^�E�������8�f��|m[O�1���z���'` �U9_����f����V!��&*t0�j-
�8u�;��_���W�3�t��W#Q���Y�=��AA������0���n2�""o�c��g?J���K�?d�%h�b�l4����b��@cb��M:$&�G�����dBR���K�������b&���wX�\���h�% �~;��?u^����K�s����'{�%� o�z���8�LX`n�F�E��&����f�4��ge6�3�w������>lm�������3�;�8&���W�D���p/^���A&@r���,�U\j�sF@����J�����l{ [���-b�O��_~\qG7om��������7���
�4�_q ���PG,=%�]=��x,���KF��3y����s�8���t�q�m;]0��`��x�a�n0���FB ���k%{�)K��-���+N&�|u���|���/?�_�Lts3A����e�B[>b��|�*)H��|��F>��q%�
�{���v���QYM�z�!4�����e]��l&{��v���Xb���b��'�3?���0�rW�xC�["������a�Jy,w��6��K*��3W��q���c��i����@\>��8�� ��w4a�.Ke�{�����2�z����#�Z���}�?�j��>��KL�$=j]�v���;�����"T����K y�LY��j��t\����q�9�����Y�=��k��ok8�_K;�zI �vIA�-���)�[�Y�����[�����?��XhJX n�t�j%�p@:
Ls�R��528I�X`�k����t���� ���e�A����m�&��������\o2�'\�K����I�}��md0����a�A��c�p��z�6Ms����X�i�x�3�?A�|��u<�J�:<�A
����d)��D��{�AR����:��Ad'�F��S<�'�e`�k�4R�2����d|+�^��"_�
�\�����$ �Y��j9 ��m��>!�BU|��-�;f��_0��B�����/W�z{\uXs3M'��W&+G"