BUG #16846: "retrieved too many tuples in a bounded sort"

The following bug has been logged on the website:

Bug reference: 16846
Logged by: Yoran Heling
Email address: contact(at)yorhel(dot)nl
PostgreSQL version: 13.1
Operating system: Gentoo x86_64
Description:

I have a query that fails as follows:

> SELECT id FROM releases WHERE minage = 18 AND released <= 20210131 AND id
IN(SELECT id FROM releases_lang WHERE lang = 'ja') ORDER BY released DESC,
id LIMIT 50;
ERROR: XX000: retrieved too many tuples in a bounded sort
LOCATION: tuplesort_gettuple_common, tuplesort.c:2103

EXPLAIN output of the query is as follows:

QUERY PLAN

--------------------------------------------------------------------------------------------------------------------
Limit (cost=4.09..42.61 rows=50 width=8)
-> Incremental Sort (cost=4.09..25569.21 rows=33184 width=8)
Sort Key: releases.released DESC, releases.id
Presorted Key: releases.released
-> Nested Loop (cost=0.58..24272.33 rows=33184 width=8)
-> Index Scan Backward using releases_released on releases
(cost=0.29..9271.55 rows=45225 width=8)
Index Cond: (released <= 20210131)
Filter: (minage = 18)
-> Index Only Scan using releases_lang_pkey on releases_lang
(cost=0.29..0.33 rows=1 width=4)
Index Cond: ((id = releases.id) AND (lang =
'ja'::language))
(10 rows)

The problem is very data-dependent, changing any value in the query will
make it succeed. Here's an EXPLAIN ANALYZE that succeeds with a slightly
modified 'released' comparison. I don't know if this is relevant, but the
rows estimate is a little off. I did run a VACUUM ANALYZE.

QUERY PLAN

----------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=4.09..42.61 rows=50 width=8) (actual time=0.933..1.056 rows=50
loops=1)
-> Incremental Sort (cost=4.09..25569.21 rows=33184 width=8) (actual
time=0.933..1.050 rows=50 loops=1)
Sort Key: releases.released DESC, releases.id
Presorted Key: releases.released
Full-sort Groups: 1 Sort Method: quicksort Average Memory: 28kB
Peak Memory: 28kB
Pre-sorted Groups: 9 Sort Methods: top-N heapsort, quicksort
Average Memory: 25kB Peak Memory: 25kB
-> Nested Loop (cost=0.58..24272.33 rows=33184 width=8) (actual
time=0.149..0.991 rows=77 loops=1)
-> Index Scan Backward using releases_released on releases
(cost=0.29..9271.55 rows=45225 width=8) (actual time=0.029..0.481 rows=268
loops=1)
Index Cond: (released <= 20210128)
Filter: (minage = 18)
Rows Removed by Filter: 157
-> Index Only Scan using releases_lang_pkey on releases_lang
(cost=0.29..0.33 rows=1 width=4) (actual time=0.002..0.002 rows=0
loops=268)
Index Cond: ((id = releases.id) AND (lang =
'ja'::language))
Heap Fetches: 0
Planning Time: 0.647 ms
Execution Time: 1.120 ms
(16 rows)

Sadly I've not been able to create a minimum working example, but I have
been able to reproduce this on our public database dumps. I've made an
excerpt of the database with only the two referenced tables:
https://s.vndb.org/u/vndb-releases-test-20210131.sql.gz (~5.5MB compressed).
I can reproduce the error on that database with the above query.

(That data is part of the "near-complete database dump" documented at
https://vndb.org/d14#5 - the issue can also be reproduced on the full dump
after doing a "CREATE INDEX releases_released ON releases (released)")