Le mardi 25 octobre 2022, 16:18:57 CET Tom Lane a écrit :
> Alexander Korotkov <aekorot...@gmail.com> writes:
> > I think Tom's point was that it's wrong to add a separate entry-tree CPU
> > cost estimation to another estimation, which tries (very inadequately) to
> > estimate the whole scan cost. Instead, I propose writing better
> > estimations
> > for both entry-tree CPU cost and data-trees CPU cost and replacing
> > existing
> > CPU estimation altogether.
>
> Great idea, if someone is willing to do it ...
>
> regards, tom lane
Hello,
Sorry for the delay, but here is an updated patch which changes the costing in
the following way:
- add a descent cost similar to the btree one is charged for the initial
entry-tree
- additionally, a charge is applied per page in both the entry tree and
posting trees / lists
- instead of charging the quals to each tuple, charge them per entry only. We
still charge cpu_index_tuple_cost per tuple though.
With those changes, no need to tweak the magic number formula estimating the
number of pages. Maybe we can come up with something better for estimating
those later on ?
Best regards,
--
Ronan Dunklau
>From 49bc71f25967f9367196803be363509922aac8ab Mon Sep 17 00:00:00 2001
From: Ronan Dunklau <ronan.dunk...@aiven.io>
Date: Mon, 12 Sep 2022 15:40:18 +0200
Subject: [PATCH v3] Fix gin costing.
GIN index scans were not taking any descent CPU-based cost into account. That made
them look cheaper than other types of indexes when they shouldn't be.
We use the same heuristic as for btree indexes, but multiplying it by
the number of searched entries.
Additionnally, the cpu cost for the tree was based largely on
genericcostestimate. For a GIN index, we should not charge index quals
per tuple, but per entry. On top of this, charge cpu_index_tuple_cost
per actual tuple.
This should fix the cases where a GIN index is preferred over a btree,
and the ones where a memoize node is not added on top of the GIN index
scan because it seemed too cheap.
Per report of Hung Nguyen.
---
src/backend/utils/adt/selfuncs.c | 50 +++++++++++++++++++++++++++++---
1 file changed, 46 insertions(+), 4 deletions(-)
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index f116924d3c..1d07ae8e95 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -7445,6 +7445,7 @@ gincostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
qual_arg_cost,
spc_random_page_cost,
outer_scans;
+ Cost descentCost;
Relation indexRel;
GinStatsData ginStats;
ListCell *lc;
@@ -7669,6 +7670,41 @@ gincostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
*/
dataPagesFetched = ceil(numDataPages * partialScale);
+ *indexStartupCost = 0;
+ *indexTotalCost = 0;
+
+ /*
+ * Add a CPU-cost component to represent the costs of initial entry btree
+ * descent. We don't charge any I/O cost for touching upper btree levels,
+ * since they tend to stay in cache, but we still have to do about log2(N)
+ * comparisons to descend a btree of N leaf tuples. We charge one
+ * cpu_operator_cost per comparison.
+ *
+ * If there are ScalarArrayOpExprs, charge this once per SA scan. The
+ * ones after the first one are not startup cost so far as the overall
+ * plan is concerned, so add them only to "total" cost.
+ */
+ if (numEntries > 1) /* avoid computing log(0) */
+ {
+ descentCost = ceil(log(numEntries) / log(2.0)) * cpu_operator_cost;
+ *indexStartupCost += descentCost * counts.searchEntries;
+ *indexTotalCost += counts.arrayScans * descentCost * counts.searchEntries;
+ }
+
+ /*
+ * Add a cpu cost per entry-page fetched. This is not amortized over a loop.
+ */
+ *indexStartupCost += entryPagesFetched * 50.0 * cpu_operator_cost;
+ *indexTotalCost += entryPagesFetched * counts.arrayScans * 50.0 * cpu_operator_cost;
+
+ /*
+ * Add a cpu cost per data-page fetched. This is also not amortized over a loop.
+ * We only charge one data page for the startup cost, and everything else to
+ * the total cost.
+ */
+ *indexStartupCost += 50.0 * cpu_operator_cost;
+ *indexTotalCost += dataPagesFetched * counts.arrayScans * 50.0 * cpu_operator_cost;
+
/*
* Calculate cache effects if more than one scan due to nestloops or array
* quals. The result is pro-rated per nestloop scan, but the array qual
@@ -7692,7 +7728,7 @@ gincostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
* Here we use random page cost because logically-close pages could be far
* apart on disk.
*/
- *indexStartupCost = (entryPagesFetched + dataPagesFetched) * spc_random_page_cost;
+ *indexStartupCost += (entryPagesFetched + dataPagesFetched) * spc_random_page_cost;
/*
* Now compute the number of data pages fetched during the scan.
@@ -7720,6 +7756,9 @@ gincostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
if (dataPagesFetchedBySel > dataPagesFetched)
dataPagesFetched = dataPagesFetchedBySel;
+ /* Add once again a CPU-cost for those data pages, before amortizing for cache. */
+ *indexTotalCost += dataPagesFetched * counts.arrayScans * 50.0 * cpu_operator_cost;
+
/* Account for cache effects, the same as above */
if (outer_scans > 1 || counts.arrayScans > 1)
{
@@ -7731,11 +7770,11 @@ gincostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
}
/* And apply random_page_cost as the cost per page */
- *indexTotalCost = *indexStartupCost +
+ *indexTotalCost += *indexStartupCost +
dataPagesFetched * spc_random_page_cost;
/*
- * Add on index qual eval costs, much as in genericcostestimate. But we
+ * Add on index qual eval costs, much as in genericcostestimate. We charge cpu but we
* can disregard indexorderbys, since GIN doesn't support those.
*/
qual_arg_cost = index_other_operands_eval_cost(root, indexQuals);
@@ -7743,7 +7782,10 @@ gincostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
*indexStartupCost += qual_arg_cost;
*indexTotalCost += qual_arg_cost;
- *indexTotalCost += (numTuples * *indexSelectivity) * (cpu_index_tuple_cost + qual_op_cost);
+ /* Add a cpu cost per search entry, corresponding to the actual visited entries. */
+ *indexTotalCost += (counts.searchEntries * counts.arrayScans) * (qual_op_cost);
+ /* Now add a cpu cost per tuple in the posting lists / trees */
+ *indexTotalCost += (numTuples * *indexSelectivity) * (cpu_index_tuple_cost);
*indexPages = dataPagesFetched;
}
--
2.38.1
