MIME-Version: 1.0
References: <1203098.1743640224@sss.pgh.pa.us> <2BC8AB39-16D7-4423-BE0A-F0F4EA432E2E@gmail.com>
 <CAApHDvou3ZhHmQ6Qx9O9HbXigTu9oHdTFKibv96TyAbJ8WGYNw@mail.gmail.com> <1233327.1743656842@sss.pgh.pa.us>
In-Reply-To: <1233327.1743656842@sss.pgh.pa.us>
From: David Rowley <dgrowleyml@gmail.com>
Date: Thu, 3 Apr 2025 23:27:45 +1300
Message-ID: <CAApHDvp6nH+fV5g3D1ZMkwXNYQs=i8PYVb_4QsyS6z3NAgMqBg@mail.gmail.com>
Subject: Re: Postgres Query Plan using wrong index
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Manikandan Swaminathan <maniswami23@gmail.com>, pgsql-general@lists.postgresql.org
Content-Type: text/plain; charset="UTF-8"
Archived-At: <https://www.postgresql.org/message-id/CAApHDvp6nH%2BfV5g3D1ZMkwXNYQs%3Di8PYVb_4QsyS6z3NAgMqBg%40mail.gmail.com>
Precedence: bulk

On Thu, 3 Apr 2025 at 18:07, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> A simple-minded approach could be to just be pessimistic, and
> increase our estimate of how many rows would need to be scanned as a
> consequence of noticing that the columns have significant correlation.
> The shape of that penalty function would be mostly guesswork though,
> I fear.  (Even with a clear idea of what to do, making this happen
> seems a little complex --- just a SMOP, but I'm not very sure how to
> wire it up.)

The problem with being pessimistic is that if the distribution was
even or the col_a > 4996 were right at the start of an ordered scan of
the idx_col_b_a index, it would have been a good plan. There might be
just as many people getting good plans as there are bad and adding
pessimism here might just make one set of people happy and the others
sad.

I don't have a clear idea, but from a few minutes thinking about it,
maybe when we build the statistics on a table, once we're about done
with what happens today, if we then took the sample rows set and
sorted them according to the sort order of each amcanorder index then
go through the MCVs lists and histograms for each column and record a
min and max value for the percentage of the way through the sorted
sample rows that we find each MCV value and value within each
histogram bucket and store those in some new statistics kind against
the index (maybe indexes could opt into this).  This might sound like
it'd need lots of storage, but even 1 byte each for the min and max
would be better than today. 0 could mean near the start, 127 in the
middle and 255 at the end.

I imagine this could be done fairly efficiently by sorting the MCVs
lists by value and bsearching that array as we walk through the
indexed-ordered sample rows. The histograms should be sorted already.

When planning the query in question, to figure out the weighting of
how many rows we expect to have to read, we look at the stats against
the index to find the minimum position for values in the col_a
histogram where col_a > 4996. Instead of assuming an even
distribution, you use that minimum value to tell you what percentage
of the index must be read before a match is found.  The stored maximum
position value would do the same job for backward index scans.

David