Improve rowcount estimate for UNNEST(column)
Hello,
Here is a patch to improve rowcount estimates for
`UNNEST(some_array_column)`. Today we hard code this to 10, but we
have statistics about array size, so it's easy to use them.
I've seen plans where this would make a difference. If the array has
only 1 or 2 elements, then overestimating the rowcount by 10 leads to
unnecessary seqscans downstream. I can see how an underestimate would
cause issues too.
This patch builds on a391ff3c3d41 which allowed set-returning
functions like UNNEST to include a support function to estimate their
result count. (There is a nice writeup at
https://www.cybertec-postgresql.com/en/optimizer-support-functions/)
But that patch only changes UNNEST if it has a Const or ArrayExpr
argument.
The statistic I'm using is the last value in the DECHIST array, which
is the average number of distinct elements in the array. Using the
plain (non-distinct) element count would be more accurate, but we
don't have that, and using distinct elements is still better than a
hardcoded 10.
The real change is in estimate_array_length, which has several callers
besides array_unnest_support, but I think this change should give more
accurate estimates for all of them.
There is a comment that estimate_array_length must agree with
scalararraysel. I don't think this commit introduces any
discrepancies. The most relevant case there is `scalar = ANY/ALL
(array)`, which also consults DECHIST (and/or MCELEM).
I wasn't sure where to put a test. I finally settled on arrays.sql
since (1) that has other UNNEST tests (2) array_unnest_support is in
util/adt/arrayfuncs.c (3) I couldn't find a place devoted to
rowcount/selectivity estimates. I'm happy to move it if someone has a
better idea!
Based on 712dc2338b23.
Yours,
--
Paul ~{:-)
pj@illuminatedcomputing.com
Attachments:
v1-0001-Use-statitics-for-estimating-UNNEST-column-rows.patchapplication/octet-stream; name=v1-0001-Use-statitics-for-estimating-UNNEST-column-rows.patchDownload
From 682a1fa6f591fd687cb80c78a0968631e4e0987b Mon Sep 17 00:00:00 2001
From: "Paul A. Jungwirth" <pj@illuminatedcomputing.com>
Date: Sat, 25 Nov 2023 09:12:52 -0800
Subject: [PATCH v1] Use statitics for estimating UNNEST(column) rows
Extends estimate_array_length to consult DECHIST statistics when called
with a Var. This improves planning with array_unnest_support (added in
a391ff3c3d41) and should give more accurate results for other callers
too. DECHIST has the average *distinct* element count which isn't
exactly what we want, but it should still be an improvement over a fixed
10.
---
src/backend/optimizer/path/costsize.c | 8 ++---
src/backend/utils/adt/array_typanalyze.c | 1 +
src/backend/utils/adt/arrayfuncs.c | 2 +-
src/backend/utils/adt/selfuncs.c | 39 +++++++++++++++++++-----
src/include/utils/selfuncs.h | 2 +-
src/test/regress/expected/arrays.out | 10 ++++++
src/test/regress/sql/arrays.sql | 4 +++
7 files changed, 53 insertions(+), 13 deletions(-)
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index d6ceafd51c5..8bcdcc7fd84 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -1254,7 +1254,7 @@ cost_tidscan(Path *path, PlannerInfo *root,
ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) qual;
Node *arraynode = (Node *) lsecond(saop->args);
- ntuples += estimate_array_length(arraynode);
+ ntuples += estimate_array_length(root, arraynode);
}
else if (IsA(qual, CurrentOfExpr))
{
@@ -4741,7 +4741,7 @@ cost_qual_eval_walker(Node *node, cost_qual_eval_context *context)
Node *arraynode = (Node *) lsecond(saop->args);
QualCost sacosts;
QualCost hcosts;
- int estarraylen = estimate_array_length(arraynode);
+ int estarraylen = estimate_array_length(context->root, arraynode);
set_sa_opfuncid(saop);
sacosts.startup = sacosts.per_tuple = 0;
@@ -4779,7 +4779,7 @@ cost_qual_eval_walker(Node *node, cost_qual_eval_context *context)
*/
context->total.startup += sacosts.startup;
context->total.per_tuple += sacosts.per_tuple *
- estimate_array_length(arraynode) * 0.5;
+ estimate_array_length(context->root, arraynode) * 0.5;
}
}
else if (IsA(node, Aggref) ||
@@ -4830,7 +4830,7 @@ cost_qual_eval_walker(Node *node, cost_qual_eval_context *context)
context->total.startup += perelemcost.startup;
if (perelemcost.per_tuple > 0)
context->total.per_tuple += perelemcost.per_tuple *
- estimate_array_length((Node *) acoerce->arg);
+ estimate_array_length(context->root, (Node *) acoerce->arg);
}
else if (IsA(node, RowCompareExpr))
{
diff --git a/src/backend/utils/adt/array_typanalyze.c b/src/backend/utils/adt/array_typanalyze.c
index 04b3764b686..a60d5fb5d24 100644
--- a/src/backend/utils/adt/array_typanalyze.c
+++ b/src/backend/utils/adt/array_typanalyze.c
@@ -604,6 +604,7 @@ compute_array_stats(VacAttrStats *stats, AnalyzeAttrFetchFunc fetchfunc,
/*
* Prepare to fill stanumbers with the histogram, followed by the
* average count. This array must be stored in anl_context.
+ * We use the average count in estimate_array_length.
*/
hist = (float4 *)
MemoryContextAlloc(stats->anl_context,
diff --git a/src/backend/utils/adt/arrayfuncs.c b/src/backend/utils/adt/arrayfuncs.c
index 631012a0f28..f902deff025 100644
--- a/src/backend/utils/adt/arrayfuncs.c
+++ b/src/backend/utils/adt/arrayfuncs.c
@@ -6337,7 +6337,7 @@ array_unnest_support(PG_FUNCTION_ARGS)
/* We can use estimated argument values here */
arg1 = estimate_expression_value(req->root, linitial(args));
- req->rows = estimate_array_length(arg1);
+ req->rows = estimate_array_length(req->root, arg1);
ret = (Node *) req;
}
}
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index 35c9e3c86fe..807c4e5ba80 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -2131,7 +2131,7 @@ scalararraysel(PlannerInfo *root,
* It's important that this agree with scalararraysel.
*/
int
-estimate_array_length(Node *arrayexpr)
+estimate_array_length(PlannerInfo *root, Node *arrayexpr)
{
/* look through any binary-compatible relabeling of arrayexpr */
arrayexpr = strip_array_coercion(arrayexpr);
@@ -2152,11 +2152,36 @@ estimate_array_length(Node *arrayexpr)
{
return list_length(((ArrayExpr *) arrayexpr)->elements);
}
- else
+ else if (arrayexpr && IsA(arrayexpr, Var))
{
- /* default guess --- see also scalararraysel */
- return 10;
+ /*
+ * It's a column, so use its average elem count.
+ * This is stored in the last stanumbers element of the DECHIST statistics.
+ * Actually that is the count of *distinct* elements,
+ * but this is still better than 10.
+ */
+ VariableStatData vardata;
+ AttStatsSlot sslot;
+ int nelem = -1;
+
+ examine_variable(root, arrayexpr, 0, &vardata);
+
+ if (HeapTupleIsValid(vardata.statsTuple))
+ {
+ if (get_attstatsslot(&sslot, vardata.statsTuple, STATISTIC_KIND_DECHIST, InvalidOid, ATTSTATSSLOT_NUMBERS))
+ {
+ nelem = sslot.numbers[sslot.nnumbers - 1];
+ free_attstatsslot(&sslot);
+ }
+ }
+ ReleaseVariableStats(vardata);
+
+ if (nelem >= 0)
+ return nelem;
}
+
+ /* default guess --- see also scalararraysel */
+ return 10;
}
/*
@@ -6538,7 +6563,7 @@ genericcostestimate(PlannerInfo *root,
if (IsA(rinfo->clause, ScalarArrayOpExpr))
{
ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) rinfo->clause;
- int alength = estimate_array_length(lsecond(saop->args));
+ int alength = estimate_array_length(root, lsecond(saop->args));
if (alength > 1)
num_sa_scans *= alength;
@@ -6818,7 +6843,7 @@ btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
{
ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
Node *other_operand = (Node *) lsecond(saop->args);
- int alength = estimate_array_length(other_operand);
+ int alength = estimate_array_length(root, other_operand);
clause_op = saop->opno;
found_saop = true;
@@ -7412,7 +7437,7 @@ gincost_scalararrayopexpr(PlannerInfo *root,
{
counts->exactEntries++;
counts->searchEntries++;
- counts->arrayScans *= estimate_array_length(rightop);
+ counts->arrayScans *= estimate_array_length(root, rightop);
return true;
}
diff --git a/src/include/utils/selfuncs.h b/src/include/utils/selfuncs.h
index 2f76c473db4..bf9678157f7 100644
--- a/src/include/utils/selfuncs.h
+++ b/src/include/utils/selfuncs.h
@@ -200,7 +200,7 @@ extern Selectivity scalararraysel(PlannerInfo *root,
ScalarArrayOpExpr *clause,
bool is_join_clause,
int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo);
-extern int estimate_array_length(Node *arrayexpr);
+extern int estimate_array_length(PlannerInfo *root, Node *arrayexpr);
extern Selectivity rowcomparesel(PlannerInfo *root,
RowCompareExpr *clause,
int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo);
diff --git a/src/test/regress/expected/arrays.out b/src/test/regress/expected/arrays.out
index 23404982f71..96a0c4a1e34 100644
--- a/src/test/regress/expected/arrays.out
+++ b/src/test/regress/expected/arrays.out
@@ -2699,3 +2699,13 @@ SELECT array_sample('{1,2,3,4,5,6}'::int[], -1); -- fail
ERROR: sample size must be between 0 and 6
SELECT array_sample('{1,2,3,4,5,6}'::int[], 7); --fail
ERROR: sample size must be between 0 and 6
+-- test rowcount estimate of unnest(column)
+analyze arrtest;
+explain select elem from arrtest, unnest(a) x(elem);
+ QUERY PLAN
+-------------------------------------------------------------------
+ Nested Loop (cost=0.00..1.15 rows=6 width=2)
+ -> Seq Scan on arrtest (cost=0.00..1.03 rows=3 width=29)
+ -> Function Scan on unnest x (cost=0.00..0.02 rows=2 width=2)
+(3 rows)
+
diff --git a/src/test/regress/sql/arrays.sql b/src/test/regress/sql/arrays.sql
index 50aa539fdc1..21507cf8129 100644
--- a/src/test/regress/sql/arrays.sql
+++ b/src/test/regress/sql/arrays.sql
@@ -825,3 +825,7 @@ SELECT array_dims(array_sample('[-1:2][2:3]={{1,2},{3,NULL},{5,6},{7,8}}'::int[]
SELECT array_dims(array_sample('{{{1,2},{3,NULL}},{{5,6},{7,8}},{{9,10},{11,12}}}'::int[], 2));
SELECT array_sample('{1,2,3,4,5,6}'::int[], -1); -- fail
SELECT array_sample('{1,2,3,4,5,6}'::int[], 7); --fail
+
+-- test rowcount estimate of unnest(column)
+analyze arrtest;
+explain select elem from arrtest, unnest(a) x(elem);
--
2.32.0 (Apple Git-132)
On Sat, 2023-11-25 at 09:19 -0800, Paul A Jungwirth wrote:
Here is a patch to improve rowcount estimates for
`UNNEST(some_array_column)`. Today we hard code this to 10, but we
have statistics about array size, so it's easy to use them.I've seen plans where this would make a difference. If the array has
only 1 or 2 elements, then overestimating the rowcount by 10 leads to
unnecessary seqscans downstream. I can see how an underestimate would
cause issues too.
The idea sounds good to me.
I didn't test or scrutinize the code, but I noticed that you use
EXPLAIN in the regression tests. I think that makes the tests vulnerable
to changes in the parameters or in the block size.
Perhaps you can write a function that runs EXPLAIN and extracts just the
row count. That should be stable enough.
Yours,
Laurenz Albe
Laurenz Albe <laurenz.albe@cybertec.at> writes:
On Sat, 2023-11-25 at 09:19 -0800, Paul A Jungwirth wrote:
Here is a patch to improve rowcount estimates for
`UNNEST(some_array_column)`. Today we hard code this to 10, but we
have statistics about array size, so it's easy to use them.
The idea sounds good to me.
I didn't read the patch either yet, but it seems like a reasonable idea.
I didn't test or scrutinize the code, but I noticed that you use
EXPLAIN in the regression tests. I think that makes the tests vulnerable
to changes in the parameters or in the block size.
Yes, this regression test is entirely unacceptable; the numbers will
not be stable enough. Even aside from the different-settings issue,
you can't rely on ANALYZE deriving exactly the same stats every time.
Usually what we try to do is devise a query where the plan shape
changes because of the better estimate. That typically will provide
some insulation against small changes in the numerical estimates.
regards, tom lane
Hi.
Since both array_op_test, arrest both are not dropped at the end of
src/test/regress/sql/arrays.sql.
I found using table array_op_test test more convincing.
select
reltuples * 10 as original,
reltuples * (select
floor(elem_count_histogram[array_length(elem_count_histogram,1)])
from pg_stats
where tablename = 'array_op_test' and attname = 'i')
as with_patch
,(select (elem_count_histogram[array_length(elem_count_histogram,1)])
from pg_stats
where tablename = 'array_op_test' and attname = 'i')
as elem_count_histogram_last_element
from pg_class where relname = 'array_op_test';
original | with_patch | elem_count_histogram_last_element
----------+------------+-----------------------------------
1030 | 412 | 4.7843137
(1 row)
without patch:
explain select unnest(i) from array_op_test;
QUERY PLAN
----------------------------------------------------------------------
ProjectSet (cost=0.00..9.95 rows=1030 width=4)
-> Seq Scan on array_op_test (cost=0.00..4.03 rows=103 width=40)
(2 rows)
with patch:
explain select unnest(i) from array_op_test;
QUERY PLAN
----------------------------------------------------------------------
ProjectSet (cost=0.00..6.86 rows=412 width=4)
-> Seq Scan on array_op_test (cost=0.00..4.03 rows=103 width=40)
(2 rows)
--------
because, in the estimate_array_length function, `nelem =
sslot.numbers[sslot.nnumbers - 1];` will round 4.7843137 to 4.
so with patch estimated row 412 = 103 *4. without patch estimated rows
= 103 * 10.
On Mon, Nov 27, 2023 at 3:05 PM jian he <jian.universality@gmail.com> wrote:
Hi.
Since both array_op_test, arrest both are not dropped at the end of
src/test/regress/sql/arrays.sql.
I found using table array_op_test test more convincing.select
reltuples * 10 as original,
reltuples * (select
floor(elem_count_histogram[array_length(elem_count_histogram,1)])
from pg_stats
where tablename = 'array_op_test' and attname = 'i')
as with_patch
,(select (elem_count_histogram[array_length(elem_count_histogram,1)])
from pg_stats
where tablename = 'array_op_test' and attname = 'i')
as elem_count_histogram_last_element
from pg_class where relname = 'array_op_test';
original | with_patch | elem_count_histogram_last_element
----------+------------+-----------------------------------
1030 | 412 | 4.7843137
(1 row)without patch:
explain select unnest(i) from array_op_test;
QUERY PLAN
----------------------------------------------------------------------
ProjectSet (cost=0.00..9.95 rows=1030 width=4)
-> Seq Scan on array_op_test (cost=0.00..4.03 rows=103 width=40)
(2 rows)with patch:
explain select unnest(i) from array_op_test;
QUERY PLAN
----------------------------------------------------------------------
ProjectSet (cost=0.00..6.86 rows=412 width=4)
-> Seq Scan on array_op_test (cost=0.00..4.03 rows=103 width=40)
(2 rows)
--------
Hi.
I did a minor change. change estimate_array_length return type to
double, cost_tidscan function inside `int ntuples` to `double
ntuples`.
`clamp_row_est(get_function_rows(root, expr->funcid, clause));` will
round 4.7843137 to 5.
so with your patch and my refactor, the rows will be 103 * 5 = 515.
explain select unnest(i) from array_op_test;
QUERY PLAN
----------------------------------------------------------------------
ProjectSet (cost=0.00..7.38 rows=515 width=4)
-> Seq Scan on array_op_test (cost=0.00..4.03 rows=103 width=40)
(2 rows)
Attachments:
v1-0001-minor-refactor.patchtext/x-patch; charset=US-ASCII; name=v1-0001-minor-refactor.patchDownload
From 448e0149d0dd1cfc0ab629a6fc164c6071169926 Mon Sep 17 00:00:00 2001
From: pgaddict <jian.universality@gmail.com>
Date: Thu, 30 Nov 2023 12:15:01 +0800
Subject: [PATCH v1 1/1] minor refactor.
make estimate_array_length return double instead of int.
similarily change estimate_array_length's caller fucntion cost_tidscan's variable ntuple
from type int to double.
because in estimate_array_length, we may need "average count of distinct element values"
info, and that is a float4 data type.
---
src/backend/optimizer/path/costsize.c | 6 +++---
src/backend/utils/adt/selfuncs.c | 18 +++++++++---------
src/include/utils/selfuncs.h | 2 +-
3 files changed, 13 insertions(+), 13 deletions(-)
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 8bcdcc7f..65854fbe 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -1227,7 +1227,7 @@ cost_tidscan(Path *path, PlannerInfo *root,
QualCost qpqual_cost;
Cost cpu_per_tuple;
QualCost tid_qual_cost;
- int ntuples;
+ double ntuples;
ListCell *l;
double spc_random_page_cost;
@@ -1242,7 +1242,7 @@ cost_tidscan(Path *path, PlannerInfo *root,
path->rows = baserel->rows;
/* Count how many tuples we expect to retrieve */
- ntuples = 0;
+ ntuples = 0.0;
foreach(l, tidquals)
{
RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
@@ -4741,7 +4741,7 @@ cost_qual_eval_walker(Node *node, cost_qual_eval_context *context)
Node *arraynode = (Node *) lsecond(saop->args);
QualCost sacosts;
QualCost hcosts;
- int estarraylen = estimate_array_length(context->root, arraynode);
+ double estarraylen = estimate_array_length(context->root, arraynode);
set_sa_opfuncid(saop);
sacosts.startup = sacosts.per_tuple = 0;
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index 6346b41d..f6519c7f 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -2130,7 +2130,7 @@ scalararraysel(PlannerInfo *root,
*
* It's important that this agree with scalararraysel.
*/
-int
+double
estimate_array_length(PlannerInfo *root, Node *arrayexpr)
{
/* look through any binary-compatible relabeling of arrayexpr */
@@ -2145,12 +2145,12 @@ estimate_array_length(PlannerInfo *root, Node *arrayexpr)
if (arrayisnull)
return 0;
arrayval = DatumGetArrayTypeP(arraydatum);
- return ArrayGetNItems(ARR_NDIM(arrayval), ARR_DIMS(arrayval));
+ return (double) ArrayGetNItems(ARR_NDIM(arrayval), ARR_DIMS(arrayval));
}
else if (arrayexpr && IsA(arrayexpr, ArrayExpr) &&
!((ArrayExpr *) arrayexpr)->multidims)
{
- return list_length(((ArrayExpr *) arrayexpr)->elements);
+ return (double) list_length(((ArrayExpr *) arrayexpr)->elements);
}
else if (arrayexpr && IsA(arrayexpr, Var))
{
@@ -2162,7 +2162,7 @@ estimate_array_length(PlannerInfo *root, Node *arrayexpr)
*/
VariableStatData vardata;
AttStatsSlot sslot;
- int nelem = -1;
+ double nelem = -1;
examine_variable(root, arrayexpr, 0, &vardata);
@@ -2170,18 +2170,18 @@ estimate_array_length(PlannerInfo *root, Node *arrayexpr)
{
if (get_attstatsslot(&sslot, vardata.statsTuple, STATISTIC_KIND_DECHIST, InvalidOid, ATTSTATSSLOT_NUMBERS))
{
- nelem = sslot.numbers[sslot.nnumbers - 1];
+ nelem = (double) sslot.numbers[sslot.nnumbers - 1];
free_attstatsslot(&sslot);
}
}
ReleaseVariableStats(vardata);
if (nelem >= 0)
- return nelem;
+ return (double) nelem;
}
/* default guess --- see also scalararraysel */
- return 10;
+ return 10.0;
}
/*
@@ -6565,7 +6565,7 @@ genericcostestimate(PlannerInfo *root,
if (IsA(rinfo->clause, ScalarArrayOpExpr))
{
ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) rinfo->clause;
- int alength = estimate_array_length(root, lsecond(saop->args));
+ double alength = estimate_array_length(root, lsecond(saop->args));
if (alength > 1)
num_sa_scans *= alength;
@@ -6845,7 +6845,7 @@ btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
{
ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
Node *other_operand = (Node *) lsecond(saop->args);
- int alength = estimate_array_length(root, other_operand);
+ double alength = estimate_array_length(root, other_operand);
clause_op = saop->opno;
found_saop = true;
diff --git a/src/include/utils/selfuncs.h b/src/include/utils/selfuncs.h
index bf967815..02a6224b 100644
--- a/src/include/utils/selfuncs.h
+++ b/src/include/utils/selfuncs.h
@@ -200,7 +200,7 @@ extern Selectivity scalararraysel(PlannerInfo *root,
ScalarArrayOpExpr *clause,
bool is_join_clause,
int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo);
-extern int estimate_array_length(PlannerInfo *root, Node *arrayexpr);
+extern double estimate_array_length(PlannerInfo *root, Node *arrayexpr);
extern Selectivity rowcomparesel(PlannerInfo *root,
RowCompareExpr *clause,
int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo);
--
2.34.1
Hello,
On 11/26/23 12:22, Tom Lane wrote:
Yes, this regression test is entirely unacceptable; the numbers will
not be stable enough. Even aside from the different-settings issue,
you can't rely on ANALYZE deriving exactly the same stats every time.
Usually what we try to do is devise a query where the plan shape
changes because of the better estimate.
Here is a patch with an improved test. With the old "10" estimate we get a Merge Join, but now that
the planner can see there are only ~4 elements per array, we get a Nested Loop.
It was actually hard to get a new plan, since all our regress tables' arrays have around 5 elements
average, which isn't so far from 10. Adding a table with 1- or 2- element arrays would be more
dramatic. So I resorted to tuning the query with `WHERE seqno <= 50`. Hopefully that's not cheating
too much.
I thought about also adding a test where the old code *underestimates*, but then I'd have to add a
new table with big arrays. If it's worth it let me know.
On 11/26/23 23:05, jian he wrote:
I found using table array_op_test test more convincing.
True, arrtest is pretty small. The new test uses array_op_test instead.
On 11/29/23 20:35, jian he wrote:
I did a minor change. change estimate_array_length return type to double
I'm not sure I want to change estimate_array_length from returning ints to returning doubles, since
it's called in many places. I can see how that might give plans that are more accurate yet, so maybe
it's worth it? It feels like it ought to be a separate patch to me, but if others want me to include
it here please let me know.
I did add clamp_row_est since it's essentially free and maybe gives some safety.
Rebased onto d43bd090a8.
Yours,
--
Paul ~{:-)
pj@illuminatedcomputing.com
Attachments:
v2-0001-Use-statitics-for-estimating-UNNEST-column-rows.patchtext/x-patch; charset=UTF-8; name=v2-0001-Use-statitics-for-estimating-UNNEST-column-rows.patchDownload
From f8246ff806f4b3ec1441e515ada97662a8fe8967 Mon Sep 17 00:00:00 2001
From: "Paul A. Jungwirth" <pj@illuminatedcomputing.com>
Date: Sat, 25 Nov 2023 09:12:52 -0800
Subject: [PATCH v2] Use statitics for estimating UNNEST(column) rows
Extends estimate_array_length to consult DECHIST statistics when called
with a Var. This improves planning with array_unnest_support (added in
a391ff3c3d41) and should give more accurate results for other callers
too. DECHIST has the average *distinct* element count which isn't
exactly what we want, but it should still be an improvement over a fixed
10.
---
src/backend/optimizer/path/costsize.c | 8 ++---
src/backend/utils/adt/array_typanalyze.c | 1 +
src/backend/utils/adt/arrayfuncs.c | 2 +-
src/backend/utils/adt/selfuncs.c | 39 +++++++++++++++++++-----
src/include/utils/selfuncs.h | 2 +-
src/test/regress/expected/arrays.out | 20 ++++++++++++
src/test/regress/sql/arrays.sql | 11 +++++++
7 files changed, 70 insertions(+), 13 deletions(-)
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index d6ceafd51c..8bcdcc7fd8 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -1254,7 +1254,7 @@ cost_tidscan(Path *path, PlannerInfo *root,
ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) qual;
Node *arraynode = (Node *) lsecond(saop->args);
- ntuples += estimate_array_length(arraynode);
+ ntuples += estimate_array_length(root, arraynode);
}
else if (IsA(qual, CurrentOfExpr))
{
@@ -4741,7 +4741,7 @@ cost_qual_eval_walker(Node *node, cost_qual_eval_context *context)
Node *arraynode = (Node *) lsecond(saop->args);
QualCost sacosts;
QualCost hcosts;
- int estarraylen = estimate_array_length(arraynode);
+ int estarraylen = estimate_array_length(context->root, arraynode);
set_sa_opfuncid(saop);
sacosts.startup = sacosts.per_tuple = 0;
@@ -4779,7 +4779,7 @@ cost_qual_eval_walker(Node *node, cost_qual_eval_context *context)
*/
context->total.startup += sacosts.startup;
context->total.per_tuple += sacosts.per_tuple *
- estimate_array_length(arraynode) * 0.5;
+ estimate_array_length(context->root, arraynode) * 0.5;
}
}
else if (IsA(node, Aggref) ||
@@ -4830,7 +4830,7 @@ cost_qual_eval_walker(Node *node, cost_qual_eval_context *context)
context->total.startup += perelemcost.startup;
if (perelemcost.per_tuple > 0)
context->total.per_tuple += perelemcost.per_tuple *
- estimate_array_length((Node *) acoerce->arg);
+ estimate_array_length(context->root, (Node *) acoerce->arg);
}
else if (IsA(node, RowCompareExpr))
{
diff --git a/src/backend/utils/adt/array_typanalyze.c b/src/backend/utils/adt/array_typanalyze.c
index 04b3764b68..a60d5fb5d2 100644
--- a/src/backend/utils/adt/array_typanalyze.c
+++ b/src/backend/utils/adt/array_typanalyze.c
@@ -604,6 +604,7 @@ compute_array_stats(VacAttrStats *stats, AnalyzeAttrFetchFunc fetchfunc,
/*
* Prepare to fill stanumbers with the histogram, followed by the
* average count. This array must be stored in anl_context.
+ * We use the average count in estimate_array_length.
*/
hist = (float4 *)
MemoryContextAlloc(stats->anl_context,
diff --git a/src/backend/utils/adt/arrayfuncs.c b/src/backend/utils/adt/arrayfuncs.c
index 631012a0f2..f902deff02 100644
--- a/src/backend/utils/adt/arrayfuncs.c
+++ b/src/backend/utils/adt/arrayfuncs.c
@@ -6337,7 +6337,7 @@ array_unnest_support(PG_FUNCTION_ARGS)
/* We can use estimated argument values here */
arg1 = estimate_expression_value(req->root, linitial(args));
- req->rows = estimate_array_length(arg1);
+ req->rows = estimate_array_length(req->root, arg1);
ret = (Node *) req;
}
}
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index e11d022827..be21a8c125 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -2131,7 +2131,7 @@ scalararraysel(PlannerInfo *root,
* It's important that this agree with scalararraysel.
*/
int
-estimate_array_length(Node *arrayexpr)
+estimate_array_length(PlannerInfo *root, Node *arrayexpr)
{
/* look through any binary-compatible relabeling of arrayexpr */
arrayexpr = strip_array_coercion(arrayexpr);
@@ -2152,11 +2152,36 @@ estimate_array_length(Node *arrayexpr)
{
return list_length(((ArrayExpr *) arrayexpr)->elements);
}
- else
+ else if (arrayexpr && IsA(arrayexpr, Var))
{
- /* default guess --- see also scalararraysel */
- return 10;
+ /*
+ * It's a column, so use its average elem count.
+ * This is stored in the last stanumbers element of the DECHIST statistics.
+ * Actually that is the count of *distinct* elements,
+ * but this is still better than 10.
+ */
+ VariableStatData vardata;
+ AttStatsSlot sslot;
+ int nelem = -1;
+
+ examine_variable(root, arrayexpr, 0, &vardata);
+
+ if (HeapTupleIsValid(vardata.statsTuple))
+ {
+ if (get_attstatsslot(&sslot, vardata.statsTuple, STATISTIC_KIND_DECHIST, InvalidOid, ATTSTATSSLOT_NUMBERS))
+ {
+ nelem = clamp_row_est(sslot.numbers[sslot.nnumbers - 1]);
+ free_attstatsslot(&sslot);
+ }
+ }
+ ReleaseVariableStats(vardata);
+
+ if (nelem >= 0)
+ return nelem;
}
+
+ /* default guess --- see also scalararraysel */
+ return 10;
}
/*
@@ -6540,7 +6565,7 @@ genericcostestimate(PlannerInfo *root,
if (IsA(rinfo->clause, ScalarArrayOpExpr))
{
ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) rinfo->clause;
- int alength = estimate_array_length(lsecond(saop->args));
+ int alength = estimate_array_length(root, lsecond(saop->args));
if (alength > 1)
num_sa_scans *= alength;
@@ -6820,7 +6845,7 @@ btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
{
ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
Node *other_operand = (Node *) lsecond(saop->args);
- int alength = estimate_array_length(other_operand);
+ int alength = estimate_array_length(root, other_operand);
clause_op = saop->opno;
found_saop = true;
@@ -7414,7 +7439,7 @@ gincost_scalararrayopexpr(PlannerInfo *root,
{
counts->exactEntries++;
counts->searchEntries++;
- counts->arrayScans *= estimate_array_length(rightop);
+ counts->arrayScans *= estimate_array_length(root, rightop);
return true;
}
diff --git a/src/include/utils/selfuncs.h b/src/include/utils/selfuncs.h
index 2f76c473db..bf9678157f 100644
--- a/src/include/utils/selfuncs.h
+++ b/src/include/utils/selfuncs.h
@@ -200,7 +200,7 @@ extern Selectivity scalararraysel(PlannerInfo *root,
ScalarArrayOpExpr *clause,
bool is_join_clause,
int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo);
-extern int estimate_array_length(Node *arrayexpr);
+extern int estimate_array_length(PlannerInfo *root, Node *arrayexpr);
extern Selectivity rowcomparesel(PlannerInfo *root,
RowCompareExpr *clause,
int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo);
diff --git a/src/test/regress/expected/arrays.out b/src/test/regress/expected/arrays.out
index 23404982f7..c154e5a9cc 100644
--- a/src/test/regress/expected/arrays.out
+++ b/src/test/regress/expected/arrays.out
@@ -2699,3 +2699,23 @@ SELECT array_sample('{1,2,3,4,5,6}'::int[], -1); -- fail
ERROR: sample size must be between 0 and 6
SELECT array_sample('{1,2,3,4,5,6}'::int[], 7); --fail
ERROR: sample size must be between 0 and 6
+-- test rowcount estimate of unnest(column)
+EXPLAIN (COSTS OFF)
+WITH flat AS (
+ SELECT UNNEST(i) AS elem
+ FROM array_op_test
+ WHERE seqno <= 50
+)
+SELECT flat.*
+FROM flat
+JOIN tenk1 ON thousand = elem;
+ QUERY PLAN
+------------------------------------------------------------
+ Nested Loop
+ -> ProjectSet
+ -> Seq Scan on array_op_test
+ Filter: (seqno <= 50)
+ -> Index Only Scan using tenk1_thous_tenthous on tenk1
+ Index Cond: (thousand = (unnest(array_op_test.i)))
+(6 rows)
+
diff --git a/src/test/regress/sql/arrays.sql b/src/test/regress/sql/arrays.sql
index 50aa539fdc..a0e3258b92 100644
--- a/src/test/regress/sql/arrays.sql
+++ b/src/test/regress/sql/arrays.sql
@@ -825,3 +825,14 @@ SELECT array_dims(array_sample('[-1:2][2:3]={{1,2},{3,NULL},{5,6},{7,8}}'::int[]
SELECT array_dims(array_sample('{{{1,2},{3,NULL}},{{5,6},{7,8}},{{9,10},{11,12}}}'::int[], 2));
SELECT array_sample('{1,2,3,4,5,6}'::int[], -1); -- fail
SELECT array_sample('{1,2,3,4,5,6}'::int[], 7); --fail
+
+-- test rowcount estimate of unnest(column)
+EXPLAIN (COSTS OFF)
+WITH flat AS (
+ SELECT UNNEST(i) AS elem
+ FROM array_op_test
+ WHERE seqno <= 50
+)
+SELECT flat.*
+FROM flat
+JOIN tenk1 ON thousand = elem;
--
2.42.0
Paul Jungwirth <pj@illuminatedcomputing.com> writes:
Here is a patch with an improved test. With the old "10" estimate we get a Merge Join, but now that
the planner can see there are only ~4 elements per array, we get a Nested Loop.
Pushed with minor editorialization. I ended up not using the test
case, because I was afraid it wouldn't be all that stable, and
code coverage shows that we are exercising the added code path
even without a bespoke test case.
On 11/29/23 20:35, jian he wrote:
I did a minor change. change estimate_array_length return type to double
I'm not sure I want to change estimate_array_length from returning
ints to returning doubles, since it's called in many places.
But your patch forces every one of those places to be touched anyway,
as a consequence of adding the "root" argument. I looked at the
callers and saw that every single one of them (in core anyway) ends up
using the result in a "double" rowcount calculation, so we're really
not buying anything by converting to integer and back again. There's
also a question of whether the number from DECHIST could be big enough
to overflow an int. Perhaps not given the current calculation method,
but since it's a float4 there's at least a theoretical risk. Hence,
I adopted Jian's suggestion.
One other point is that examine_variable is capable of succeeding
on things that aren't Vars, so I thought the restriction to Vars
was inappropriate.
regards, tom lane