Обсуждение: 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)")

PG Bug reporting form <noreply@postgresql.org> writes:
> 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

> 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 confirm this is reproducible on HEAD with the referenced test data.
(Load it into a utf8-encoding database, ANALYZE, and boom.)

I presume that the incremental-sort patch is at fault, though I've
not tried to run it to ground since I have no idea how that works.

            regards, tom lane

... btw, I did confirm that

set enable_incremental_sort = 0;

makes the error go away.  So that might do as a temporary workaround
until we fix it.

            regards, tom lane

On Thu, 4 Feb 2021 at 09:12, Neil Chen <carpenter.nail.cz@gmail.com> wrote:
>
>
> Greetings,
>
> I did a debug trace on this problem and found the trigger condition of the problem. As Tom said, this is a problem
onlywhen incremental sorting is triggered. Specifically, the number of times the value of index column appears exceeds
DEFAULT_MAX_FULL_SORT_GROUP_SIZE(64), call the switchToPresortedPrefixMode function. In this function, after reading
thelast tuple and judging that it does not belong to the previous group, the program breaks from the for loop. However,
becausethe lastTuple has been set to true, the subsequent process will mistakenly think that the tuple has been put
intoprefixsort_state. 
>
> I've given the following example to reproduce the bug:
> bugdb=# \d test
>                 Table "public.test"
>  Column |  Type   | Collation | Nullable | Default
> --------+---------+-----------+----------+---------
>  a      | integer |           |          |
>  b      | integer |           |          |
>  c      | text    |           |          |
>  d      | text    |           |          |
> Indexes:
>     "test_btree" btree (a)
>
> insert into test values(1,1,'cccccc','dddddd');
> insert into test select 2,generate_series(2,70),'cccccccc','dddddddd';    /* The number of tuples exceeds 64 */
> insert into test select 3,generate_series(71,70000),'cccccccc','dddddddd';   /* More data is used to ensure that the
queryplan uses incremental sorting */ 
>
> bugdb=# explain select b from test order by a,b limit 2;
>                                         QUERY PLAN
> ------------------------------------------------------------------------------------------
>  Limit  (cost=950.29..950.37 rows=2 width=8)
>    ->  Incremental Sort  (cost=950.29..3812.85 rows=70000 width=8)
>          Sort Key: a, b
>          Presorted Key: a
>          ->  Index Scan using test_btree on test  (cost=0.29..1800.29 rows=70000 width=8)
> (5 rows)
>
> Through the following two queries, it is found that the first query returned an error result. It should return 1 and
2.The error reason is the same as the reported bug. 
> bugdb=# select b from test order by a,b limit 2;
>  b
> ----
>   1
>  66
> (2 rows)
>
> bugdb=# select * from test limit 5;
>  a | b |    c     |    d
> ---+---+----------+----------
>  1 | 1 | cccccc   | dddddd
>  2 | 2 | cccccccc | dddddddd
>  2 | 3 | cccccccc | dddddddd
>  2 | 4 | cccccccc | dddddddd
>  2 | 5 | cccccccc | dddddddd
> (5 rows)
>
> Bugs can be fixed with this additional patch, and I have also done tests and regression tests. I hope hackers can
helpme to see if I think wrong or miss anything, and I'm sorry that English is not my first language. I hope you can
tellme if you have any better opinions on the expression of notes, thanks. 
>
Hi Neil,
Please can you give exact steps to reproduce this bug on
head.(smallest test case)

If it is possible to add a test case for this bug, then please add it in patch.

--
Thanks and Regards
Mahendra Singh Thalor
EnterpriseDB: http://www.enterprisedb.com

Neil Chen <carpenter.nail.cz@gmail.com> writes:
> Bugs can be fixed with this additional patch, and I have also done tests
> and regression tests. I hope hackers can help me to see if I think wrong or
> miss anything, and I'm sorry that English is not my first language. I hope
> you can tell me if you have any better opinions on the expression of notes,
> thanks.

Hi Neil,

I poked at this until I found a small modification of the existing
regression tests that would reach the problematic path with lastTuple
true.  That confirmed that there's a problem, because it gave a flat-out
wrong answer.  I'm not really familiar enough with this code to be sure
if this is a complete fix, but it fixes the cases we have and it doesn't
break anything else in our regression tests.  So, in view of the fact
that we have 13.2 release deadline on Monday, I went ahead and pushed it.
(I did rewrite your comment.)

Thanks for the patch!

            regards, tom lane

On Thu, Feb 4, 2021 at 10:07 PM Neil Chen <carpenter.nail.cz@gmail.com> wrote:
>
>
>
> On Fri, Feb 5, 2021 at 8:17 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>>
>>
>> I poked at this until I found a small modification of the existing
>> regression tests that would reach the problematic path with lastTuple
>> true.  That confirmed that there's a problem, because it gave a flat-out
>> wrong answer.  I'm not really familiar enough with this code to be sure
>> if this is a complete fix, but it fixes the cases we have and it doesn't
>> break anything else in our regression tests.  So, in view of the fact
>> that we have 13.2 release deadline on Monday, I went ahead and pushed it.
>> (I did rewrite your comment.)
>>
>
> That's great, I will also continue to try to check if it is a complete fix.
> Thank you.

I didn't see this thread until now (unfortunately I'm not able to
consistently keep up with mailing list traffic, though I'm happy to be
tagged on any incremental sort issue so I see that discussion). I
reviewed the patch, and I believe it's correct.

I did have to stare a bit at nodeIncrementalSort.c for a while though
to realize that the test case works because the full sort state was
bounded (so 5 tuples is enough to trigger the case even though a
cursory reading of the code and the bug description would imply that
64 tuples are needed to trigger it). So I have a mild preference for
noting that in the test case comment, and I also lean towards having
an EXPLAIN on the test case query to make sure it remains a valid test
case in the future (i.e., making sure other changes don't change plan
such that this case no longer has regression coverage.)

We can simplify the code a bit so that lastTuple is only set to true
when necessary, rather than setting it only to unset it in this case.

Attached is a patch to do all of the above, though I'm hardly
interested in making this a hill to die on.

James

James Coleman <jtc331@gmail.com> writes:
> I didn't see this thread until now (unfortunately I'm not able to
> consistently keep up with mailing list traffic, though I'm happy to be
> tagged on any incremental sort issue so I see that discussion). I
> reviewed the patch, and I believe it's correct.

Thanks for looking.

> I did have to stare a bit at nodeIncrementalSort.c for a while though
> to realize that the test case works because the full sort state was
> bounded (so 5 tuples is enough to trigger the case even though a
> cursory reading of the code and the bug description would imply that
> 64 tuples are needed to trigger it). So I have a mild preference for
> noting that in the test case comment, and I also lean towards having
> an EXPLAIN on the test case query to make sure it remains a valid test
> case in the future (i.e., making sure other changes don't change plan
> such that this case no longer has regression coverage.)

No objection to doing that, however ...

> We can simplify the code a bit so that lastTuple is only set to true
> when necessary, rather than setting it only to unset it in this case.

I stared at this for awhile and eventually convinced myself that it
implemented the same logic, but it still seems overly complex.  We
do not need either the firstTuple or lastTuple flags, and we could
convert the nTuple adjustments into a normal for-loop with (IMO)
much greater intelligibility.  What do you think of the attached?

            regards, tom lane

diff --git a/src/backend/executor/nodeIncrementalSort.c b/src/backend/executor/nodeIncrementalSort.c
index 82fa800cb1..459c879f0b 100644
--- a/src/backend/executor/nodeIncrementalSort.c
+++ b/src/backend/executor/nodeIncrementalSort.c
@@ -288,9 +288,7 @@ switchToPresortedPrefixMode(PlanState *pstate)
 {
     IncrementalSortState *node = castNode(IncrementalSortState, pstate);
     ScanDirection dir;
-    int64        nTuples = 0;
-    bool        lastTuple = false;
-    bool        firstTuple = true;
+    int64        nTuples;
     TupleDesc    tupDesc;
     PlanState  *outerNode;
     IncrementalSort *plannode = castNode(IncrementalSort, node->ss.ps.plan);
@@ -343,20 +341,16 @@ switchToPresortedPrefixMode(PlanState *pstate)
      * Copy as many tuples as we can (i.e., in the same prefix key group) from
      * the full sort state to the prefix sort state.
      */
-    for (;;)
+    for (nTuples = 0; nTuples < node->n_fullsort_remaining; nTuples++)
     {
-        lastTuple = node->n_fullsort_remaining - nTuples == 1;
-
         /*
          * When we encounter multiple prefix key groups inside the full sort
          * tuplesort we have to carry over the last read tuple into the next
          * batch.
          */
-        if (firstTuple && !TupIsNull(node->transfer_tuple))
+        if (nTuples == 0 && !TupIsNull(node->transfer_tuple))
         {
             tuplesort_puttupleslot(node->prefixsort_state, node->transfer_tuple);
-            nTuples++;
-
             /* The carried over tuple is our new group pivot tuple. */
             ExecCopySlot(node->group_pivot, node->transfer_tuple);
         }
@@ -376,7 +370,6 @@ switchToPresortedPrefixMode(PlanState *pstate)
             if (isCurrentGroup(node, node->group_pivot, node->transfer_tuple))
             {
                 tuplesort_puttupleslot(node->prefixsort_state, node->transfer_tuple);
-                nTuples++;
             }
             else
             {
@@ -395,27 +388,10 @@ switchToPresortedPrefixMode(PlanState *pstate)
                  */
                 ExecClearTuple(node->group_pivot);

-                /*
-                 * Also make sure we take the didn't-consume-all-the-tuples
-                 * path below, even if this happened to be the last tuple of
-                 * the batch.
-                 */
-                lastTuple = false;
+                /* Break out of for-loop early */
                 break;
             }
         }
-
-        firstTuple = false;
-
-        /*
-         * If we've copied all of the tuples from the full sort state into the
-         * prefix sort state, then we don't actually know that we've yet found
-         * the last tuple in that prefix key group until we check the next
-         * tuple from the outer plan node, so we retain the current group
-         * pivot tuple prefix key group comparison.
-         */
-        if (lastTuple)
-            break;
     }

     /*
@@ -428,14 +404,15 @@ switchToPresortedPrefixMode(PlanState *pstate)
     node->n_fullsort_remaining -= nTuples;
     SO1_printf("Setting n_fullsort_remaining to " INT64_FORMAT "\n", node->n_fullsort_remaining);

-    if (lastTuple)
+    if (node->n_fullsort_remaining == 0)
     {
         /*
-         * We've confirmed that all tuples remaining in the full sort batch is
-         * in the same prefix key group and moved all of those tuples into the
-         * presorted prefix tuplesort. Now we can save our pivot comparison
-         * tuple and continue fetching tuples from the outer execution node to
-         * load into the presorted prefix tuplesort.
+         * We've found that all tuples remaining in the full sort batch are in
+         * the same prefix key group and moved all of those tuples into the
+         * presorted prefix tuplesort.  We don't know that we've yet found the
+         * last tuple in the current prefix key group, so save our pivot
+         * comparison tuple and continue fetching tuples from the outer
+         * execution node to load into the presorted prefix tuplesort.
          */
         ExecCopySlot(node->group_pivot, node->transfer_tuple);
         SO_printf("Setting execution_status to INCSORT_LOADPREFIXSORT (switchToPresortedPrefixMode)\n");
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index d574583844..68ca321163 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -676,6 +676,21 @@ select * from (select * from t order by a) s order by a, b limit 70;
 (70 rows)

 -- Checks case where we hit a group boundary at the last tuple of a batch.
+-- Because the full sort state is bounded, we scan 64 tuples (the mode
+-- transition point) but only retain 5. Thus when we transition modes, all
+-- tuples in the full sort state have different prefix keys.
+explain (costs off) select * from (select * from t order by a) s order by a, b limit 5;
+           QUERY PLAN
+---------------------------------
+ Limit
+   ->  Incremental Sort
+         Sort Key: t.a, t.b
+         Presorted Key: t.a
+         ->  Sort
+               Sort Key: t.a
+               ->  Seq Scan on t
+(7 rows)
+
 select * from (select * from t order by a) s order by a, b limit 5;
  a | b
 ---+---
diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql
index 9965fcd777..81429164d4 100644
--- a/src/test/regress/sql/incremental_sort.sql
+++ b/src/test/regress/sql/incremental_sort.sql
@@ -150,6 +150,10 @@ analyze t;
 explain (costs off) select * from (select * from t order by a) s order by a, b limit 70;
 select * from (select * from t order by a) s order by a, b limit 70;
 -- Checks case where we hit a group boundary at the last tuple of a batch.
+-- Because the full sort state is bounded, we scan 64 tuples (the mode
+-- transition point) but only retain 5. Thus when we transition modes, all
+-- tuples in the full sort state have different prefix keys.
+explain (costs off) select * from (select * from t order by a) s order by a, b limit 5;
 select * from (select * from t order by a) s order by a, b limit 5;

 -- Test rescan.

On Thu, Feb 11, 2021 at 12:06 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> James Coleman <jtc331@gmail.com> writes:
> > I didn't see this thread until now (unfortunately I'm not able to
> > consistently keep up with mailing list traffic, though I'm happy to be
> > tagged on any incremental sort issue so I see that discussion). I
> > reviewed the patch, and I believe it's correct.
>
> Thanks for looking.
>
> > I did have to stare a bit at nodeIncrementalSort.c for a while though
> > to realize that the test case works because the full sort state was
> > bounded (so 5 tuples is enough to trigger the case even though a
> > cursory reading of the code and the bug description would imply that
> > 64 tuples are needed to trigger it). So I have a mild preference for
> > noting that in the test case comment, and I also lean towards having
> > an EXPLAIN on the test case query to make sure it remains a valid test
> > case in the future (i.e., making sure other changes don't change plan
> > such that this case no longer has regression coverage.)
>
> No objection to doing that, however ...
>
> > We can simplify the code a bit so that lastTuple is only set to true
> > when necessary, rather than setting it only to unset it in this case.
>
> I stared at this for awhile and eventually convinced myself that it
> implemented the same logic, but it still seems overly complex.  We
> do not need either the firstTuple or lastTuple flags, and we could
> convert the nTuple adjustments into a normal for-loop with (IMO)
> much greater intelligibility.  What do you think of the attached?

Yes, that looks even better. Not sure how I missed that I'd just
reimplemented a normal for-loop with firstTuple/lastTuple conditions,
but I guess that's the benefit of coming at it with fresh eyes and
without the history of how it got the way it was.

+1 on committing v2.

James

James Coleman <jtc331@gmail.com> writes:
> On Thu, Feb 11, 2021 at 12:06 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> I stared at this for awhile and eventually convinced myself that it
>> implemented the same logic, but it still seems overly complex.  We
>> do not need either the firstTuple or lastTuple flags, and we could
>> convert the nTuple adjustments into a normal for-loop with (IMO)
>> much greater intelligibility.  What do you think of the attached?

> Yes, that looks even better. Not sure how I missed that I'd just
> reimplemented a normal for-loop with firstTuple/lastTuple conditions,
> but I guess that's the benefit of coming at it with fresh eyes and
> without the history of how it got the way it was.

> +1 on committing v2.

Sounds good, pushed.

            regards, tom lane