MIME-Version: 1.0
From: Merlin Moncure <mmoncure@gmail.com>
Date: Tue, 17 Mar 2026 15:01:09 -0600
Message-ID: 
 <CAHyXU0xkTBW4p2N9QNLwye3O5SgzSGSMiPjFb7P8MyXCrEhhwg@mail.gmail.com>
Subject: postgres chooses objectively wrong index
To: pgsql-performance@lists.postgresql.org
Content-Type: multipart/alternative; boundary="00000000000011bee0064d3ea32e"
Archived-At: 
 <https://www.postgresql.org/message-id/CAHyXU0xkTBW4p2N9QNLwye3O5SgzSGSMiPjFb7P8MyXCrEhhwg%40mail.gmail.com>
Precedence: bulk

--00000000000011bee0064d3ea32e
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

I've been maintaining an airflow style orchestrator in pl/pgsql, and it's
revealed a performance issue I just can't solve.  There is a table, task,
which may normally contain billions of rows, but only a tiny portion is
interesting for specific reasons=E2=80=94a common pattern in task-type syst=
ems.

CREATE TABLE async.task
(
  task_id BIGSERIAL PRIMARY KEY,
  target TEXT REFERENCES async.target ON UPDATE CASCADE ON DELETE CASCADE,
  priority INT DEFAULT 0,
  entered TIMESTAMPTZ DEFAULT clock_timestamp(),
  consumed TIMESTAMPTZ,
  processed TIMESTAMPTZ,
  yielded TIMESTAMPTZ,
  times_up TIMESTAMPTZ,
  concurrency_pool TEXT
);

CREATE OR REPLACE FUNCTION async.task_execution_state(t async.task)
  RETURNS async.task_execution_state_t AS
$$
  SELECT
    CASE
      WHEN t.processed IS NOT NULL THEN 'FINISHED'
      WHEN t.consumed IS NULL AND t.yielded IS NULL THEN 'READY'
      WHEN t.yielded IS NOT NULL THEN 'YIELDED'
      WHEN t.consumed IS NOT NULL AND t.yielded IS NULL THEN 'RUNNING'
    END::async.task_execution_state_t;
$$ LANGUAGE SQL IMMUTABLE;

"processed NOT NULL" defines the 'needle', let's say typically <0.01%.   Of
those cases, a few patterns need defense from a performance standpoint.
Naturally, partial indexes are used because we don't want to index the
entire table.

/* supports fetching eligible tasks */
CREATE INDEX ON async.task(concurrency_pool, priority, entered)
WHERE async.task_execution_state(task) =3D 'READY';

/* look up expired tasks.  Times up qual is to prevent index being used for
 * any other purpose.
 */
CREATE INDEX ON async.task(times_up)
  WHERE
    async.task_execution_state(task) IN('READY', 'RUNNING', 'YIELDED')
    AND times_up IS NOT NULL;

/* supports cleaning up dead tasks on startup and other needs for
 * processing unfinished tasks.
 */
CREATE INDEX ON async.task(task_id)
  WHERE async.task_execution_state(task) IN('READY', 'RUNNING', 'YIELDED');

These indexes support queries called in a tight loop, for example:

SELECT *
FRROM async.task
WHERE
  async.task_execution_state(task.*) =3D
'READY'::async.task_execution_state_t
  AND concurrency_pool =3D 'xyz'
ORDER BY priority, entered
LIMIT 10;

Usually, we get a plan that looks like this:

 Limit  (cost=3D0.38..39.74 rows=3D10 width=3D563) (actual time=3D0.054..0.=
054
rows=3D0 loops=3D1)
   ->  Index Scan using task_concurrency_pool_priority_entered_idx on task
 (cost=3D0.38..705.08 rows=3D179 width=3D563) (actual time=3D0.053..0.053 r=
ows=3D0
loops=3D1)
         Index Cond: (concurrency_pool =3D 'xyz'::text)
 Planning Time: 0.234 ms
 Execution Time: 0.072 ms

Let's note that the partial index predicate exactly matches the where
clause, and that the index from left to right matches in terms of equality
and ordering.  No sorting is required, and the results are excellent.  The
final costing here is IMNSHO very high: 39.74, and I believe that is the
fundamental issue.

Sometimes, based on a certain data distribution, we get results like this:

Limit  (cost=3D25.75..25.78 rows=3D10 width=3D563) (actual time=3D8.909..8.=
911
rows=3D0 loops=3D1)
  ->  Sort  (cost=3D25.75..26.20 rows=3D179 width=3D563) (actual
time=3D8.908..8.909 rows=3D0 loops=3D1)
        Sort Key: priority, entered
        Sort Method: quicksort  Memory: 25kB
        ->  Bitmap Heap Scan on task  (cost=3D9.10..21.89 rows=3D179 width=
=3D563)
(actual time=3D8.902..8.903 rows=3D0 loops=3D1)
              Recheck Cond: ((async.task_execution_state(task.*) =3D ANY
('{READY,RUNNING,YIELDED}'::async.task_execution_state_t[])) AND
(concurrency_pool =3D 'xyz'::text) AND (async.task_execution_state(task.*) =
=3D
'READY'::async.task_execution_state_t))
              ->  BitmapAnd  (cost=3D9.10..9.10 rows=3D3 width=3D0) (actual
time=3D8.883..8.883 rows=3D0 loops=3D1)
                    ->  Bitmap Index Scan on task_task_id_idx
 (cost=3D0.00..4.38 rows=3D575191 width=3D0) (actual time=3D8.828..8.828 ro=
ws=3D16
loops=3D1)
                    ->  Bitmap Index Scan on
task_concurrency_pool_priority_entered_idx  (cost=3D0.00..4.38 rows=3D179
width=3D0) (actual time=3D0.053..0.053 rows=3D0 loops=3D1)
                          Index Cond: (concurrency_pool =3D 'xyz'::text)
Planning Time: 0.262 ms
Execution Time: 8.946 ms

In this case, we get an explicit sort and other unnecessary work for a 100x
degradation in runtime.  My basic issue is that I do not believe any data
distribution that allows plan #2 to beat plan #1, given the more specific
predicate and index order matching result order.  I suspect this is a very
long standing issue concerning insufficient weight given to partial
indexes, predicate matching, and possibly index-supported sorting.  I've
dealt with some variant of this problem for many years.

Sometimes, there can be even worse plans, running into 10-20 seconds, for a
~ 10 order of magnitude miss.  I can manage this at the query level by:
* turning off various planner directives, heap scan, etc
* adding faux columns to the table to support forcing index selection in
particular cases (CREATE INDEX ON foo WHERE this_case IS NULL....SELECT *
FROM foo WHERE this_case IS NULL...)

I'm wondering if there are other tricks that might apply here, for example,
multi column index statistics...curious if anyone has thoughts on that.

Any suggestions?

merlin

--00000000000011bee0064d3ea32e
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div dir=3D"ltr"><div>I&#39;ve been maintaining an airflow=
 style orchestrator in pl/pgsql, and it&#39;s revealed a performance issue =
I just can&#39;t solve.=C2=A0 There is a table, task, which may normally=C2=
=A0contain billions of rows, but only a tiny portion is interesting for spe=
cific reasons=E2=80=94a common pattern in task-type systems.</div><div><br>=
</div><div>CREATE TABLE async.task<br>(<br>=C2=A0 task_id BIGSERIAL PRIMARY=
 KEY,<br>=C2=A0 target TEXT REFERENCES async.target ON UPDATE CASCADE ON DE=
LETE CASCADE,<br>=C2=A0 priority INT DEFAULT 0,<br>=C2=A0 entered TIMESTAMP=
TZ DEFAULT clock_timestamp(), <br>=C2=A0 consumed TIMESTAMPTZ, <br>=C2=A0 p=
rocessed TIMESTAMPTZ, <br>=C2=A0 yielded TIMESTAMPTZ,</div><div>=C2=A0 time=
s_up TIMESTAMPTZ,</div><div>=C2=A0 concurrency_pool TEXT<br>);</div><div><b=
r></div><div>CREATE OR REPLACE FUNCTION async.task_execution_state(t async.=
task) <br>=C2=A0 RETURNS async.task_execution_state_t AS<br>$$<br>=C2=A0 SE=
LECT <br>=C2=A0 =C2=A0 CASE <br>=C2=A0 =C2=A0 =C2=A0 WHEN t.processed IS NO=
T NULL THEN &#39;FINISHED&#39;<br>=C2=A0 =C2=A0 =C2=A0 WHEN t.consumed IS N=
ULL AND t.yielded IS NULL THEN &#39;READY&#39;<br>=C2=A0 =C2=A0 =C2=A0 WHEN=
 t.yielded IS NOT NULL THEN &#39;YIELDED&#39;<br>=C2=A0 =C2=A0 =C2=A0 WHEN =
t.consumed IS NOT NULL AND t.yielded IS NULL THEN &#39;RUNNING&#39;<br>=C2=
=A0 =C2=A0 END::async.task_execution_state_t;<br>$$ LANGUAGE SQL IMMUTABLE;=
<br></div><div><br></div><div>&quot;processed NOT NULL&quot; defines the &#=
39;needle&#39;, let&#39;s say typically &lt;0.01%.=C2=A0 =C2=A0Of those cas=
es, a few patterns need defense from a performance standpoint. Naturally, p=
artial indexes are used because we don&#39;t want to index the entire table=
.</div><div><br></div><div>/* supports fetching eligible tasks */</div><div=
>CREATE INDEX ON async.task(concurrency_pool, priority, entered) <br>WHERE =
async.task_execution_state(task) =3D &#39;READY&#39;;<br><br>/* look up exp=
ired tasks.=C2=A0 Times up qual is to prevent index being used for<br>=C2=
=A0* any other purpose.<br>=C2=A0*/<br>CREATE INDEX ON async.task(times_up)=
<br>=C2=A0 WHERE <br>=C2=A0 =C2=A0 async.task_execution_state(task) IN(&#39=
;READY&#39;, &#39;RUNNING&#39;, &#39;YIELDED&#39;)<br>=C2=A0 =C2=A0 AND tim=
es_up IS NOT NULL;<br><br>/* supports cleaning up dead tasks on startup and=
 other needs for <br>=C2=A0* processing unfinished tasks.<br>=C2=A0*/<br>CR=
EATE INDEX ON async.task(task_id)<br>=C2=A0 WHERE async.task_execution_stat=
e(task) IN(&#39;READY&#39;, &#39;RUNNING&#39;, &#39;YIELDED&#39;);</div><di=
v><br></div><div>These indexes support queries called in a tight loop, for =
example:</div><div><br></div><div>SELECT *</div><div>FRROM async.task=C2=A0=
</div><div>WHERE=C2=A0</div><div>=C2=A0 async.task_execution_state(task.*) =
=3D &#39;READY&#39;::async.task_execution_state_t =C2=A0</div><div>=C2=A0 A=
ND concurrency_pool =3D &#39;xyz&#39;=C2=A0</div><div>ORDER BY priority, en=
tered=C2=A0</div><div>LIMIT 10;</div><div><br></div><div>Usually, we get a =
plan that looks like this:=C2=A0</div><div><br></div><div>=C2=A0Limit =C2=
=A0(cost=3D0.38..39.74 rows=3D10 width=3D563) (actual time=3D0.054..0.054 r=
ows=3D0 loops=3D1)<br>=C2=A0 =C2=A0-&gt; =C2=A0Index Scan using task_concur=
rency_pool_priority_entered_idx on task =C2=A0(cost=3D0.38..705.08 rows=3D1=
79 width=3D563) (actual time=3D0.053..0.053 rows=3D0 loops=3D1)<br>=C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0Index Cond: (concurrency_pool =3D &#39;xyz&#39;:=
:text)<br>=C2=A0Planning Time: 0.234 ms<br>=C2=A0Execution Time: 0.072 ms</=
div><div><br></div><div>Let&#39;s note that the partial=C2=A0index predicat=
e exactly matches the where clause, and that the index from left to right m=
atches in terms of equality and ordering.=C2=A0 No sorting is required, and=
 the results are excellent.=C2=A0 The final costing here is IMNSHO very hig=
h: 39.74, and I believe that is the fundamental issue.</div><div><br></div>=
<div>Sometimes, based on a certain data distribution, we get results like t=
his:</div><div><br></div><div>Limit =C2=A0(cost=3D25.75..25.78 rows=3D10 wi=
dth=3D563) (actual time=3D8.909..8.911 rows=3D0 loops=3D1)<br>=C2=A0 -&gt; =
=C2=A0Sort =C2=A0(cost=3D25.75..26.20 rows=3D179 width=3D563) (actual time=
=3D8.908..8.909 rows=3D0 loops=3D1)<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 Sort Key=
: priority, entered<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 Sort Method: quicksort =
=C2=A0Memory: 25kB<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 -&gt; =C2=A0Bitmap Heap S=
can on task =C2=A0(cost=3D9.10..21.89 rows=3D179 width=3D563) (actual time=
=3D8.902..8.903 rows=3D0 loops=3D1)<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 Recheck Cond: ((async.task_execution_state(task.*) =3D ANY (&=
#39;{READY,RUNNING,YIELDED}&#39;::async.task_execution_state_t[])) AND (con=
currency_pool =3D &#39;xyz&#39;::text) AND (async.task_execution_state(task=
.*) =3D &#39;READY&#39;::async.task_execution_state_t))<br>=C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 -&gt; =C2=A0BitmapAnd =C2=A0(cost=3D9.10=
..9.10 rows=3D3 width=3D0) (actual time=3D8.883..8.883 rows=3D0 loops=3D1)<=
br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 -&=
gt; =C2=A0Bitmap Index Scan on task_task_id_idx =C2=A0(cost=3D0.00..4.38 ro=
ws=3D575191 width=3D0) (actual time=3D8.828..8.828 rows=3D16 loops=3D1)<br>=
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 -&gt;=
 =C2=A0Bitmap Index Scan on task_concurrency_pool_priority_entered_idx =C2=
=A0(cost=3D0.00..4.38 rows=3D179 width=3D0) (actual time=3D0.053..0.053 row=
s=3D0 loops=3D1)<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=
 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 Index Cond: (concurrency_pool =3D &#39;=
xyz&#39;::text)<br>Planning Time: 0.262 ms<br>Execution Time: 8.946 ms</div=
><div><br></div><div><div>In this case, we get an explicit sort and other u=
nnecessary work for a 100x degradation in runtime.=C2=A0 My basic issue is =
that I do not believe any data distribution that allows plan #2 to beat pla=
n #1, given the more specific predicate and index order matching result ord=
er.=C2=A0 I suspect this is a very long standing issue concerning insuffici=
ent weight given to partial indexes, predicate matching, and possibly index=
-supported sorting.=C2=A0 I&#39;ve dealt with some variant of this problem =
for many years.</div><div></div></div><div><br></div><div>Sometimes, there =
can be even worse plans, running into 10-20 seconds, for a ~ 10 order of ma=
gnitude miss.=C2=A0 I can manage this at the query level by:</div><div>* tu=
rning off various planner directives, heap scan, etc</div><div>* adding fau=
x columns to the table to support forcing index selection in particular cas=
es (CREATE INDEX ON foo WHERE this_case IS NULL....SELECT * FROM foo WHERE =
this_case IS NULL...)</div><div><br></div><div>I&#39;m wondering if there a=
re other tricks that might apply here, for example, multi column index stat=
istics...curious if anyone has thoughts on that.</div><div><br></div><div>A=
ny suggestions?</div><div><br></div><div>merlin</div><div><br></div><div><b=
r></div><div><br></div><div><br></div><div><br></div></div>
</div>

--00000000000011bee0064d3ea32e--