From: Ronan Dunklau <ronan.dunklau@aiven.io>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: pgsql-hackers@lists.postgresql.org
Subject: Re: Fix gin index cost estimation
Date: Thu, 15 Sep 2022 12:25:06 +0200
Message-ID: <4212593.ejJDZkT8p0@aivenronan>
Organization: aiven
In-Reply-To: <1924159.usQuhbGJ8B@aivenronan>
References: <3188617.44csPzL39Z@aivenronan> <4157141.1662676376@sss.pgh.pa.us>
 <1924159.usQuhbGJ8B@aivenronan>
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="nextPart2123342.Mh6RI2rZIc"
Content-Transfer-Encoding: 7Bit
Archived-At: 
 <https://www.postgresql.org/message-id/4212593.ejJDZkT8p0%40aivenronan>
Precedence: bulk

This is a multi-part message in MIME format.

--nextPart2123342.Mh6RI2rZIc
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset="iso-8859-1"

Le lundi 12 septembre 2022, 16:41:16 CEST Ronan Dunklau a =E9crit :
> But I realised that another approach might be better suited: since we wan=
t=20
to
> charge a cpu cost for every page visited, actually basing that on the=20
already
> estimated entryPagesFetched and dataPagesFetched would be better, instead=
 of
> copying what is done for other indexes type and estimating the tree heigh=
t.=20
It
> would be simpler, as we don't need to estimate the tree height anymore.
>=20
> I will submit a patch doing that.

The attached does that and is much simpler. I only took into account=20
entryPagesFetched, not sure if we should also charge something for data pag=
es.

Instead of trying to estimate the height of the tree, we rely on the=20
(imperfect) estimation of the number of entry pages fetched, and charge 50=
=20
times cpu_operator_cost to that, in addition to the cpu_operator_cost charg=
ed=20
per entry visited.

I also adapted to take into accounts multiple scans induced by scalar array=
=20
operations.=20

As it is, I don't understand the following calculation:

/*
* Estimate number of entry pages read.  We need to do
* counts.searchEntries searches.  Use a power function as it should be,
 * but tuples on leaf pages usually is much greater. Here we include all
 * searches in entry tree, including search of first entry in partial
 * match algorithm
 */
entryPagesFetched +=3D ceil(counts.searchEntries * rint(pow(numEntryPages,=
=20
0.15)));

Is the power(0.15) used an approximation for a log ? If so why ? Also=20
shouldn't we round that up ?
It seems to me it's unlikely to affect the total too much in normal cases=20
(adding at worst random_page_cost) but if we start to charge cpu operator=20
costs as proposed here it makes a big difference and it is probably
safer to overestimate a bit than the opposite.

With those changes, the gin cost (purely cpu-wise) stays above the btree on=
e=20
as I think it should be.=20

=2D-=20
Ronan Dunklau
--nextPart2123342.Mh6RI2rZIc
Content-Disposition: attachment; filename="v2-0001-Fix-gin-costing.patch"
Content-Transfer-Encoding: 7Bit
Content-Type: text/x-patch; charset="UTF-8";
 name="v2-0001-Fix-gin-costing.patch"

From 8635a22ee5f90297756f072199c69a318bd17ea2 Mon Sep 17 00:00:00 2001
From: Ronan Dunklau <ronan.dunklau@aiven.io>
Date: Mon, 12 Sep 2022 15:40:18 +0200
Subject: [PATCH v2] 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.

Per report of Hung Nguyen.
---
 src/backend/utils/adt/selfuncs.c | 34 +++++++++++++++++++++++++++++---
 1 file changed, 31 insertions(+), 3 deletions(-)

diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index c746759eef..881e470a07 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -7419,6 +7419,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;
@@ -7622,7 +7623,7 @@ gincostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
 	 * searches in entry tree, including search of first entry in partial
 	 * match algorithm
 	 */
-	entryPagesFetched += ceil(counts.searchEntries * rint(pow(numEntryPages, 0.15)));
+	entryPagesFetched += ceil(counts.searchEntries * ceil(pow(numEntryPages, 0.15)));
 
 	/*
 	 * Add an estimate of entry pages read by partial match algorithm. It's a
@@ -7643,6 +7644,33 @@ 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 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;
+
 	/*
 	 * 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
@@ -7666,7 +7694,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.
@@ -7705,7 +7733,7 @@ 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;
 
 	/*
-- 
2.37.3


--nextPart2123342.Mh6RI2rZIc--