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@yorhel.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)")