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: Mon, 19 Sep 2022 09:15:25 +0200
Message-ID: <4768224.31r3eYUQgx@aivenronan>
Organization: aiven
In-Reply-To: <3871020.1663358699@sss.pgh.pa.us>
References: <3188617.44csPzL39Z@aivenronan> <4212593.ejJDZkT8p0@aivenronan>
 <3871020.1663358699@sss.pgh.pa.us>
MIME-Version: 1.0
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset="iso-8859-1"
Archived-At: 
 <https://www.postgresql.org/message-id/4768224.31r3eYUQgx%40aivenronan>
Precedence: bulk

Le vendredi 16 septembre 2022, 22:04:59 CEST Tom Lane a =E9crit :
> Ronan Dunklau <ronan.dunklau@aiven.io> writes:
> > The attached does that and is much simpler. I only took into account
> > entryPagesFetched, not sure if we should also charge something for data=
=20
pages.
>=20
> I think this is wrong, because there is already a CPU charge based on
> the number of tuples visited, down at the very end of the routine:
>=20
> 	*indexTotalCost +=3D (numTuples * *indexSelectivity) *=20
(cpu_index_tuple_cost + qual_op_cost);
>=20
> It's certainly possible to argue that that's incorrectly computed,
> but just adding another cost charge for the same topic can't be right.

I don't think it's the same thing. The entryPagesFetched is computed=20
independently of the selectivity and the number of tuples. As such, I think=
 it=20
makes sense to use it to compute the cost of descending the entry tree.

As mentioned earlier, I don't really understand the formula for computing=20
entryPagesFetched. If we were to estimate the tree height to compute the=20
descent cost as I first proposed, I feel like we would use two different me=
trics=20
for what is essentially the same cost: something proportional to the size o=
f=20
the entry tree.

>=20
> I do suspect that that calculation is bogus, because it looks like it's
> based on the concept of "apply the quals at each index entry", which we
> know is not how GIN operates.  So maybe we should drop that bit in favor
> of a per-page-ish cost like you have here.  Not sure.  In any case it
> seems orthogonal to the question of startup/descent costs.  Maybe we'd
> better tackle just one thing at a time.

Hum, good point. Maybe that should be revisited too.

>=20
> (BTW, given that that charge does exist and is not affected by
> repeated-scan amortization, why do we have a problem in the first place?
> Is it just too small?  I guess that when we're only expecting one tuple
> to be retrieved, it would only add about cpu_index_tuple_cost.)

Because with a very low selectivity, we end up under-charging for the cost =
of=20
walking the entry tree by a significant amount. As said above, I don't see =
how=20
those two things are the same: that charge estimates the cost of applying=20
index quals to the visited tuples, which is not the same as charging per en=
try=20
page visited.

>=20
> > Is the power(0.15) used an approximation for a log ? If so why ? Also
> > shouldn't we round that up ?
>=20
> No idea, but I'm pretty hesitant to just randomly fool with that equation
> when (a) neither of us know where it came from and (b) exactly no evidence
> has been provided that it's wrong.
>=20
> I note for instance that the existing logic switches from charging 1 page
> per search to 2 pages per search at numEntryPages =3D 15 (1.5 ^ (1/0.15)).
> Your version would switch at 2 pages, as soon as the pow() result is even
> fractionally above 1.0.  Maybe the existing logic is too optimistic there,
> but ceil() makes it too pessimistic I think.  I'd sooner tweak the power
> constant than change from rint() to ceil().

You're right, I was too eager to try to raise the CPU cost proportionnally =
to=20
the number of array scans (scalararrayop). I'd really like to understand wh=
ere=20
this equation comes from though...=20

Best regards,

=2D-=20
Ronan Dunklau