Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
From: Manikandan Swaminathan <maniswami23@gmail.com>
Mime-Version: 1.0 (1.0)
Subject: Re: Postgres Query Plan using wrong index
Date: Wed, 2 Apr 2025 20:24:08 -0700
Message-Id: <2BC8AB39-16D7-4423-BE0A-F0F4EA432E2E@gmail.com>
References: <1203098.1743640224@sss.pgh.pa.us>
Cc: pgsql-general@lists.postgresql.org
In-Reply-To: <1203098.1743640224@sss.pgh.pa.us>
To: Tom Lane <tgl@sss.pgh.pa.us>
Archived-At: <https://www.postgresql.org/message-id/2BC8AB39-16D7-4423-BE0A-F0F4EA432E2E%40gmail.com>
Precedence: bulk

Thanks Tom.

Since you mentioned the planner not knowing about the correlation between th=
e columns, I=E2=80=99m curious, why doesn=E2=80=99t making a multivariate st=
atistic make a difference?

CREATE STATISTICS col_a_col_b_stats (dependencies) ON col_a, col_b FROM test=
_table;
ANALYZE test_table;

And the resulting query plan which uses just the index on col_b:

postgres=3D# explain analyze select min(col_b) from test_table  where col_a >=
 4996;
                                                                   =20
 Result  (cost=3D62.13..62.14 rows=3D1 width=3D4) (actual time=3D536.648..53=
6.649 rows=3D1 loops=3D1)
   InitPlan 1
     ->  Limit  (cost=3D0.43..62.13 rows=3D1 width=3D4) (actual time=3D536.6=
41..536.641 rows=3D1 loops=3D1)
           ->  Index Scan using idx_col_a_btree on test_table  (cost=3D0.43.=
.254987.43 rows=3D4133 width=3D4) (actual time=3D536.640..536.640 rows=3D1 l=
oops=3D1)
                 Filter: (col_a > 4996)
                 Rows Removed by Filter: 9992000
 Planning Time: 0.285 ms
 Execution Time: 536.681 ms

>=20
> On Apr 2, 2025, at 5:30 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>=20
> =EF=BB=BFManikandan Swaminathan <maniswami23@gmail.com> writes:
>> 1) Why is the query currently picking the poorly performing index?
>=20
> Because the planner thinks that one will be cheaper, as you can see by
> comparing the cost estimates in EXPLAIN.  It's wrong, but this is a
> hard problem to estimate well.  Especially when the behavior depends
> on a correlation between columns that the planner knows nothing about.
>=20
>> 2) Why would the index you suggested, (col_b, col_a), perform better than=
 (col_a, col_b)? I would=E2=80=99ve expected the filter on col_a to come fir=
st, followed by the aggregate on col_b. In my mind, it needs to find rows ma=
tching the col_a condition before calculating the MIN(col_b), and I assumed i=
t would traverse the B-tree accordingly.
>=20
> The idea the planner is using is "scan the index in order (that is,
> in col_b order) until you find the first row satisfying the other
> constraints (that is, the col_a condition).  Then that row's col_b
> value is the correct MIN(), and you can stop."  Since it knows nothing
> of the cross-column correlation, its estimate of how many rows it'll
> have to scan through is overly optimistic.  But it knows that the
> other way involves scanning a whole lot of the index --- there's no
> chance of stopping early --- so that's estimated as higher-cost.
>=20
> The index I suggested on (col_b, col_a) is amenable to this same
> plan shape, since col_b is still the major sort column.  The
> reason it wins is that the col_a condition can be checked in the
> index without having to visit the heap, thus eliminating a lot of
> random access to the heap.
>=20
>> 3) Why does the planner choose the better-performing (col_a, col_b) index=
 when the filter is col_a > 5000, but switch to the slower (col_b) index whe=
n the filter is not at the edge of the range, like col_a > 4996?
>=20
> At some point, as less and less of the col_a-major index would need to
> be scanned, there's a crossover in the cost estimates for the two ways
> of doing this.  I would not have cared to predict where the crossover
> is, but you evidently found it empirically.
>=20
>> For reference, here=E2=80=99s the query plan when filtering for col_a > 5=
000. It uses the correct index on (col_a, col_b).
>=20
> You would do a lot better to approach this without rigid notions of
> which is the "correct" index.  All of the ones we've discussed are
> potentially usable for this query, and they all have different cost
> curves depending on how selective the col_a condition is.  Even the
> index on col_b alone could potentially be the best, because it'll be
> smaller than the two-column indexes.  So if the col_a condition is
> very unselective then it's (at least in theory) possible that that
> would be the best choice.
>=20
>            regards, tom lane