Le vendredi 2 décembre 2022, 13:58:27 CET Ronan Dunklau a écrit :
> Le vendredi 2 décembre 2022, 12:33:33 CET Alexander Korotkov a écrit :
> > Hi, Ronan!
> > Thank you for your patch. Couple of quick questions.
> > 1) What magic number 50.0 stands for? I think we at least should make
> > it a macro.
>
> This is what is used in other tree-descending estimation functions, so I
> used that too. Maybe a DEFAULT_PAGE_CPU_COST macro would work for both ? If
> so I'll separate this into two patches, one introducing the macro for the
> other estimation functions, and this patch for gin.
The 0001 patch does this.
>
> > 2) "We only charge one data page for the startup cost" – should this
> > be dependent on number of search entries?
In fact there was another problem. The current code estimate two different
pathes for fetching data pages: in the case of a partial match, it takes into
account that all the data pages will have to be fetched. So this is is now
taken into account for the CPU cost as well.
For the regular search, we scale the number of data pages by the number of
search entries.
Best regards,
--
Ronan Dunklau
>From b3d03a96ecb3d03c4c212e3c434def6e0e77fcd4 Mon Sep 17 00:00:00 2001
From: Ronan Dunklau <ronan.dunk...@aiven.io>
Date: Tue, 6 Dec 2022 11:08:46 +0100
Subject: [PATCH v4 1/2] Extract the cpu page-process cost multiplier into a
macro.
Btree, GiST and SP-GiST all charge 50.0 * cpu_operator_cost for
processing an index page. Extract this to a macro to avoid repeated
magic numbers.
---
src/backend/utils/adt/selfuncs.c | 7 ++++---
1 file changed, 4 insertions(+), 3 deletions(-)
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index f116924d3c..5baf8cf631 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -140,6 +140,7 @@
#include "utils/timestamp.h"
#include "utils/typcache.h"
+#define DEFAULT_PAGE_CPU_MULTIPLIER 50.0
/* Hooks for plugins to get control when we ask for stats */
get_relation_stats_hook_type get_relation_stats_hook = NULL;
@@ -6858,7 +6859,7 @@ btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
* touched. The number of such pages is btree tree height plus one (ie,
* we charge for the leaf page too). As above, charge once per SA scan.
*/
- descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
+ descentCost = (index->tree_height + 1) * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;
costs.indexStartupCost += descentCost;
costs.indexTotalCost += costs.num_sa_scans * descentCost;
@@ -7053,7 +7054,7 @@ gistcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
/*
* Likewise add a per-page charge, calculated the same as for btrees.
*/
- descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
+ descentCost = (index->tree_height + 1) * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;
costs.indexStartupCost += descentCost;
costs.indexTotalCost += costs.num_sa_scans * descentCost;
@@ -7108,7 +7109,7 @@ spgcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
/*
* Likewise add a per-page charge, calculated the same as for btrees.
*/
- descentCost = (index->tree_height + 1) * 50.0 * cpu_operator_cost;
+ descentCost = (index->tree_height + 1) * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;
costs.indexStartupCost += descentCost;
costs.indexTotalCost += costs.num_sa_scans * descentCost;
--
2.38.1
>From 817f02fa5ace98b343e585568165cc2aef84328a 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 v4 2/2] 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 | 54 +++++++++++++++++++++++++++++---
1 file changed, 50 insertions(+), 4 deletions(-)
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index 5baf8cf631..0b78fe450b 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -7446,6 +7446,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;
@@ -7670,6 +7671,43 @@ 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 * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;
+ *indexTotalCost += entryPagesFetched * counts.arrayScans * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;
+
+ /*
+ * Add a cpu cost per data-page fetched. This is also not amortized over a loop.
+ * Since those are the data pages from the partial match algorithm, charge them as startup cost.
+ */
+ *indexStartupCost += DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost * dataPagesFetched;
+ /*
+ * Since we add the startup cost to the total cost later on, remove the initial arrayscan from the total.
+ */
+ *indexTotalCost += dataPagesFetched * (counts.arrayScans - 1) * DEFAULT_PAGE_CPU_MULTIPLIER * 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
@@ -7693,7 +7731,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.
@@ -7721,6 +7759,11 @@ gincostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
if (dataPagesFetchedBySel > dataPagesFetched)
dataPagesFetched = dataPagesFetchedBySel;
+ /* Add one page cpu-cost to the startup cost */
+ *indexStartupCost += DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost * counts.searchEntries;
+ /* Add once again a CPU-cost for those data pages, before amortizing for cache. */
+ *indexTotalCost += dataPagesFetched * counts.arrayScans * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;
+
/* Account for cache effects, the same as above */
if (outer_scans > 1 || counts.arrayScans > 1)
{
@@ -7732,11 +7775,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);
@@ -7744,7 +7787,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
