hi hackers,
When estimating the selectivity of an OR clause without extended
statistics, we assume that the conditions are independent. However, it
is quite common to see queries like (a = 1 OR a = 2). In such cases, the
assumption of independence can lead to a significant underestimation of
selectivity
Even when comparing OR conditions to IN, the results can differ
significantly. This issue is particularly noticeable when the number of
predicates in the OR clause is small, the table is large, and ndistinct
is low. Here’s an example of such a query on a large table with low
ndistinct:
CREATE TABLE test_table ( id SERIAL PRIMARY KEY, a INT );
INSERT INTO test_table (a) SELECT 1 FROM generate_series(1, 500000); --
500 000 rows with a = 1
INSERT INTO test_table (a) SELECT 2 FROM generate_series(1, 250000); --
250 000 rows with a = 2
INSERT INTO test_table (a) SELECT 3 FROM generate_series(1, 250000); --
250 000 rows with a = 3
ANALYZE test_table;
EXPLAIN ANALYZE SELECT * FROM test_table WHERE a IN (1, 2);
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
Seq Scan on test_table (cost=0.00..16925.00 rows=746800 width=8)
(actual time=0.055..50.064 rows=750000.00 loops=1)
Filter: (a = ANY ('{1,2}'::integer[]))
Rows Removed by Filter: 250000
Buffers: shared hit=32 read=4393
Planning:
Buffers: shared hit=33 read=15
Planning Time: 1.056 ms
Execution Time: 64.800 ms
(8 rows)
EXPLAIN ANALYZE SELECT * FROM test_table WHERE a = 1 OR a = 2;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
Seq Scan on test_table (cost=0.00..19425.00 rows=622674 width=8)
(actual time=0.029..40.451 rows=750000.00 loops=1)
Filter: ((a = 1) OR (a = 2))
Rows Removed by Filter: 250000
Buffers: shared hit=4425
Planning:
Buffers: shared hit=6
Planning Time: 0.222 ms
Execution Time: 54.214 ms
(8 rows)
Before applying my patch, the estimated row count is significantly lower
than the actual row count due to the independence assumption.
I propose a patch that improves selectivity estimation when the OR
clause contains only equality conditions on the same column. The patch
currently supports both simple equality expressions and IN. If all
predicates meet these criteria, the selectivity is computed as a sum
rather than using the default formula.
Here are the results of applying the patch to the same example:
EXPLAIN ANALYZE SELECT * FROM test_table WHERE a = 1 OR a = 2;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
Seq Scan on test_table (cost=0.00..19425.00 rows=746800 width=8)
(actual time=0.062..46.515 rows=750000.00 loops=1)
Filter: ((a = 1) OR (a = 2))
Rows Removed by Filter: 250000
Buffers: shared read=4425
Planning:
Buffers: shared hit=41 read=11
Planning Time: 1.019 ms
Execution Time: 61.013 ms
(8 rows)
This change improves cardinality estimation for such queries.
I am open to any suggestions, feedback, or improvements.
--
Best regards,
Ilia Evdokimov,
Tantor Labs LLC.
From 0a1f465b1be1c413a2db6c4f6be1a50db8fb105f Mon Sep 17 00:00:00 2001
From: Ilia Evdokimov <ilya.evdoki...@tantorlabs.ru>
Date: Mon, 3 Mar 2025 18:30:30 +0300
Subject: [PATCH v1] Improve selectivity estimation for OR clauseswith equality
conditions on the same column
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Previously, the selectivity estimation for OR clauses treated all conditions as independent,
applying the formula P(A ∪ B) = P(A) + P(B) - P(A)P(B). This led to incorrect estimates when
multiple equality conditions referred to the same column (e.g., "a = 1 OR a = 2").
This patch improves the selectivity calculation by detecting such cases and summing the individual
selectivities instead. This change improves cardinality estimation for queries with multiple equality
predicates on the same column, leading to better execution plan choices.
---
src/backend/optimizer/path/clausesel.c | 124 ++++++++++++++++++++++--
src/test/regress/expected/stats_ext.out | 12 +--
2 files changed, 120 insertions(+), 16 deletions(-)
diff --git a/src/backend/optimizer/path/clausesel.c b/src/backend/optimizer/path/clausesel.c
index 5d51f97f21..7f72695d96 100644
--- a/src/backend/optimizer/path/clausesel.c
+++ b/src/backend/optimizer/path/clausesel.c
@@ -20,6 +20,7 @@
#include "optimizer/pathnode.h"
#include "optimizer/plancat.h"
#include "statistics/statistics.h"
+#include "statistics/extended_stats_internal.h"
#include "utils/fmgroids.h"
#include "utils/lsyscache.h"
#include "utils/selfuncs.h"
@@ -341,6 +342,75 @@ clauselist_selectivity_ext(PlannerInfo *root,
return s1;
}
+static bool
+is_simple_equality_clause(Node *clause, Var **var)
+{
+ Node *clause_expr;
+
+ if (IsA(clause, RestrictInfo))
+ {
+ RestrictInfo *rinfo = (RestrictInfo *) clause;
+
+ /* Pseudoconstants are not interesting (they couldn't contain a Var) */
+ if (rinfo->pseudoconstant)
+ return false;
+
+ /* Clauses referencing multiple, or no, varnos are incompatible */
+ if (bms_membership(rinfo->clause_relids) != BMS_SINGLETON)
+ return false;
+
+ clause = (Node *) rinfo->clause;
+ }
+
+ if (is_opclause(clause))
+ {
+ OpExpr *expr = (OpExpr *) clause;
+
+ /* 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 an "=" operator, just ignore the clause */
+ if (get_oprrest(expr->opno) != F_EQSEL)
+ return false;
+
+ if (IsA(clause_expr, Var))
+ *var = (Var *) clause_expr;
+ }
+ else if (IsA(clause, ScalarArrayOpExpr))
+ {
+ ScalarArrayOpExpr *expr = (ScalarArrayOpExpr *) clause;
+ bool expronleft;
+
+ /* Only expressions with two arguments are considered compatible. */
+ if (list_length(expr->args) != 2)
+ return false;
+
+ /* Check if the expression has the right shape (one Var, one Const) */
+ if (!examine_opclause_args(expr->args, &clause_expr, NULL, &expronleft))
+ return false;
+
+ /* We only support Var on left, Const on right */
+ if (!expronleft)
+ return false;
+
+ /* If it's not an "=" operator, just ignore the clause */
+ if (get_oprrest(expr->opno) != F_EQSEL)
+ return false;
+
+ if (IsA(clause_expr, Var))
+ *var = (Var *) clause_expr;
+ }
+ else
+ return false;
+
+ return true;
+}
+
/*
* clauselist_selectivity_or -
* Compute the selectivity of an implicitly-ORed list of boolean
@@ -353,7 +423,6 @@ clauselist_selectivity_ext(PlannerInfo *root,
*
* The basic approach is to apply extended statistics first, on as many
* clauses as possible, in order to capture cross-column dependencies etc.
- * The remaining clauses are then estimated as if they were independent.
*/
static Selectivity
clauselist_selectivity_or(PlannerInfo *root,
@@ -368,6 +437,8 @@ clauselist_selectivity_or(PlannerInfo *root,
Bitmapset *estimatedclauses = NULL;
ListCell *lc;
int listidx;
+ bool all_eq_clauses = true;
+ Var *first_var = NULL;
/*
* Determine if these clauses reference a single relation. If so, and if
@@ -387,14 +458,38 @@ clauselist_selectivity_or(PlannerInfo *root,
&estimatedclauses, true);
}
- /*
- * Estimate the remaining clauses as if they were independent.
- *
- * Selectivities for an OR clause are computed as s1+s2 - s1*s2 to account
- * for the probable overlap of selected tuple sets.
- *
- * XXX is this too conservative?
- */
+ /* Check if all clauses use the same column and only equality conditions */
+ listidx = -1;
+ foreach (lc, clauses)
+ {
+ Node *clause = (Node *) lfirst(lc);
+ Var *var = NULL;
+
+ listidx++;
+
+ /*
+ * Skip this clause if it's already been estimated by some other
+ * statistics above.
+ */
+ if (bms_is_member(listidx, estimatedclauses))
+ continue;
+
+ if (!is_simple_equality_clause(clause, &var))
+ {
+ all_eq_clauses = false;
+ break;
+ }
+
+ if (first_var == NULL)
+ first_var = var;
+ else if (!equal(first_var, var))
+ {
+ all_eq_clauses = false;
+ break;
+ }
+ }
+
+ /* Estimate the remaining clauses. */
listidx = -1;
foreach(lc, clauses)
{
@@ -412,7 +507,16 @@ clauselist_selectivity_or(PlannerInfo *root,
s2 = clause_selectivity_ext(root, (Node *) lfirst(lc), varRelid,
jointype, sjinfo, use_extended_stats);
- s1 = s1 + s2 - s1 * s2;
+ if (all_eq_clauses)
+ {
+ /* If clauses are like 'a = 1 OR a = 2 OR ... ' */
+ s1 = s1 + s2;
+ }
+ else
+ {
+ /* If clauses are independent. */
+ s1 = s1 + s2 - s1 * s2;
+ }
}
return s1;
diff --git a/src/test/regress/expected/stats_ext.out b/src/test/regress/expected/stats_ext.out
index 904d3e623f..afd1dbfffc 100644
--- a/src/test/regress/expected/stats_ext.out
+++ b/src/test/regress/expected/stats_ext.out
@@ -1345,19 +1345,19 @@ SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE
SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE (a = 1 OR a = 51) AND b = ''1''');
estimated | actual
-----------+--------
- 99 | 100
+ 100 | 100
(1 row)
SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE (a = 1 OR a = 51) AND (b = ''1'' OR b = ''2'')');
estimated | actual
-----------+--------
- 99 | 100
+ 100 | 100
(1 row)
SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE (a = 1 OR a = 2 OR a = 51 OR a = 52) AND (b = ''1'' OR b = ''2'')');
estimated | actual
-----------+--------
- 197 | 200
+ 200 | 200
(1 row)
-- OR clauses referencing different attributes are incompatible
@@ -1687,19 +1687,19 @@ SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE
SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE ((a * 2) = 2 OR (a * 2) = 102) AND upper(b) = ''1''');
estimated | actual
-----------+--------
- 99 | 100
+ 100 | 100
(1 row)
SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE ((a * 2) = 2 OR (a * 2) = 102) AND (upper(b) = ''1'' OR upper(b) = ''2'')');
estimated | actual
-----------+--------
- 99 | 100
+ 100 | 100
(1 row)
SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE ((a * 2) = 2 OR (a * 2) = 4 OR (a * 2) = 102 OR (a * 2) = 104) AND (upper(b) = ''1'' OR upper(b) = ''2'')');
estimated | actual
-----------+--------
- 197 | 200
+ 200 | 200
(1 row)
-- OR clauses referencing different attributes
--
2.34.1
