Accounting for metapages in genericcostestimate()

... sigh, this time with the patch actually attached.

regards, tom lane

On 2025-Apr-28, Tom Lane wrote:

@@ -135,6 +141,7 @@ typedef struct
double		numIndexTuples; /* number of leaf tuples visited */
double		spc_random_page_cost;	/* relevant random_page_cost value */
double		num_sa_scans;	/* # indexscans from ScalarArrayOpExprs */
+	BlockNumber numNonLeafPages;	/* # of index pages that are not leafs */
} GenericCosts;

The idea you described seems quite reasonable, though I didn't review
the patch in detail.

I find the use of "leafs" as plural for "leaf" a bit strange ...
We already have uses of that word, but I wonder if they don't mostly
or exclusively come from non-native English speakers.

--
Álvaro Herrera Breisgau, Deutschland — https://www.EnterpriseDB.com/

=?utf-8?Q?=C3=81lvaro?= Herrera <alvherre@kurilemu.de> writes:

On 2025-Apr-28, Tom Lane wrote:

+ BlockNumber numNonLeafPages; /* # of index pages that are not leafs */

I find the use of "leafs" as plural for "leaf" a bit strange ...
We already have uses of that word, but I wonder if they don't mostly
or exclusively come from non-native English speakers.

Yeah, "leaves" would be correct, but I wondered whether that'd confuse
non-native speakers more. Happy to change it though.

regards, tom lane

Hi Tom,

Per the discussion at [1], genericcostestimate() produces estimates

that are noticeably off for small indexes, because it fails to
discount the index metapage while computing numIndexPages.
Here's a first-draft attempt at improving that.

I reviewed this patch and it looks good to me overall. The approach
is clean: each AM declares its non-leaf page count, and
genericcostestimate() subtracts it from the total before the
pro-rata calculation. A few observations:

1. The guard condition change from "index->pages > 1" to
"index->pages > costs->numNonLeafPages" is consistent with the
new formula -- it now asks "are there any leaf pages?" rather than
"are there any pages beyond the first?". Arithmetic safety is
also preserved: the subtraction can't go negative or zero because
the guard prevents it, and divide-by-zero is still blocked by the
existing "index->tuples > 1" check.

2. All AMs that use genericcostestimate() are covered: btree,
hash, spgist, and bloom set numNonLeafPages = 1; GiST has no
metapage so it stays at 0, which is harmless since the result
doesn't change. GIN and BRIN do their own costing and are
unaffected. Note that bloom lives in contrib/bloom/blcost.c,
so external AMs that call genericcostestimate() may also want
to set this field.

3. I agree with the decision to ignore upper btree pages -- the
fanout makes them negligible, and estimating their count without
catalog data would add complexity for minimal benefit.

4. The test adjustments (join.sql, memoize.sql, select.sql) all
make sense as ways to preserve the original test intent despite
the cost shift. However, I noticed that all test changes are
defensive -- they keep existing plans from changing -- but there
is no positive test case showing that the patch actually produces
a better plan choice.

I'm attaching a positive test case based on the motivating
scenario from pgsql-performance: a tiny partial index vs a full
index on the same column. Without the patch the planner picks
the full index; with the patch, it correctly prefers the partial
one. All regression tests pass with both patches applied.

Overall, the benefit is modest but real for small indexes, and
there is no downside: when numNonLeafPages is left at zero the
behavior is identical to before, so existing external AM callers
are unaffected as long as they zero-initialize the struct.

Also, +1 for Alvaro's suggestion to change "leafs" to "leaves".

Best regards,
Henson

Henson Choi <assam258@gmail.com> writes:

Per the discussion at [1], genericcostestimate() produces estimates
that are noticeably off for small indexes, because it fails to
discount the index metapage while computing numIndexPages.
Here's a first-draft attempt at improving that.

I reviewed this patch and it looks good to me overall.

Thanks for reviewing!

4. The test adjustments (join.sql, memoize.sql, select.sql) all
make sense as ways to preserve the original test intent despite
the cost shift. However, I noticed that all test changes are
defensive -- they keep existing plans from changing -- but there
is no positive test case showing that the patch actually produces
a better plan choice.

I'm attaching a positive test case based on the motivating
scenario from pgsql-performance: a tiny partial index vs a full
index on the same column. Without the patch the planner picks
the full index; with the patch, it correctly prefers the partial
one. All regression tests pass with both patches applied.

Fair point. But I thought that it was kind of silly to build
a whole new moderately-large table when the adjacent tests are
exercising perfectly good small partial indexes on the existing
table onek2. All we need is a non-partial index to compete
against, so transiently making that should be cheaper. So
I did this:

-- onek2_u2_prtl should be preferred over this index, but we have to
-- discount the metapage to arrive at that answer
begin;
create index onek2_index_full on onek2 (stringu1, unique2);
explain (costs off)
select unique2 from onek2
where stringu1 < 'B'::name;
rollback;

(The begin/rollback is to ensure that no other tests can see this
index, in case it could mess up their results.)

Pushed with those changes.

regards, tom lane