Horton

Thread

Commits

  1. Discount the metapage when estimating number of index pages visited.

  1. Accounting for metapages in genericcostestimate()

    Tom Lane <tgl@sss.pgh.pa.us> — 2025-04-28T17:19:12Z

    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.

The basic issue is that the calculation of numIndexPages is (as the
comment says) meant to consider only leaf index pages, but we were
simply using the total index size (index->pages) in the formula.
Subtracting the metapage produces visibly saner results when the
index is only a couple pages in total.

I thought for a bit about trying to also discount index upper pages,
but decided it's not worth it, at least for now.  Given reasonable
index fanout, upper pages should amount to at most a percent or two
of the index, so accounting for them would only move the estimates by
a percent or two.  Moreover, it's hard to make a non-squishy estimate
of how many upper pages there are.  But we do know whether there's a
metapage or not, and failing to account for it produces 100% relative
error if the index has only one data-bearing page.  So that seems
worth dealing with.

Some notes:

* Adding a field to GenericCosts breaks ABI for external callers
of genericcostestimate(), but not API, if they followed the
recommendation to zero the whole struct.  If numNonLeafPages is
left at zero then the results don't change.  We wouldn't consider
back-patching a change like this anyway, so the ABI break is not
a problem.

* There are other uses of index->pages in selfuncs.c.  I looked
through them and didn't feel motivated to change any, but perhaps
someone else will have a different opinion.

* Unsurprisingly, this change causes several visible changes in the
core regression tests for index selection with small indexes.  In each
of them it seemed that the point of the test case was to test the plan
as-given.  So I hacked things up to keep the plans the same, either by
disabling an alternative plan choice or by increasing the size of the
table.

This is v19 material, so I'll park it in the next CF.

			regards, tom lane

[1] https://www.postgresql.org/message-id/flat/CACJPJu8oY9hb7LSsqHxbn24Gpa_tWBkcwPei%3DfottvgBeSc%2BPQ%40mail.gmail.com

#text/x-diff; name="v1-discount-metapage-in-genericcostestimate.patch" [v1-discount-metapage-in-genericcostestimate.patch] /home/tgl/pgsql/v1-discount-metapage-in-genericcostestimate.patch

  2. Re: Accounting for metapages in genericcostestimate()

    Tom Lane <tgl@sss.pgh.pa.us> — 2025-04-28T17:20:34Z

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

			regards, tom lane

  3. Re: Accounting for metapages in genericcostestimate()

    Álvaro Herrera <alvherre@kurilemu.de> — 2025-04-30T10:47:51Z

    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/

  4. Re: Accounting for metapages in genericcostestimate()

    Tom Lane <tgl@sss.pgh.pa.us> — 2025-04-30T13:46:07Z

    =?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

  5. Re: Accounting for metapages in genericcostestimate()

    Henson Choi <assam258@gmail.com> — 2026-03-09T05:41:12Z

    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

  6. Re: Accounting for metapages in genericcostestimate()

    Tom Lane <tgl@sss.pgh.pa.us> — 2026-03-20T18:56:28Z

    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