Horton

Thread

Commits

  1. Simplify loop logic in nodeIncrementalSort.c.

  2. Fix YA incremental sort bug.

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

    The Post Office <noreply@postgresql.org> — 2021-01-31T09:09:49Z

    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)")

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

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-01-31T16:16:08Z

    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

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

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-01-31T16:35:28Z

    ... 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

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

    Neil Chen <carpenter.nail.cz@gmail.com> — 2021-02-04T03:42:06Z

    Greetings,

I did a debug trace on this problem and found the trigger condition of the
problem. As Tom said, this is a problem only when 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 the
last tuple and judging that it does not belong to the previous group, the
program breaks from the for loop. However, because the lastTuple has been
set to true, the subsequent process will mistakenly think that the tuple
has been put into prefixsort_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 query plan 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 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.

-- 
There is no royal road to learning.
HighGo Software Co.

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

    Mahendra Singh Thalor <mahi6run@gmail.com> — 2021-02-04T16:42:58Z

    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 only when 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 the last tuple and judging that it does not belong to the previous group, the program breaks from the for loop. However, because the lastTuple has been set to true, the subsequent process will mistakenly think that the tuple has been put into prefixsort_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 query plan 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 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,
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

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

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-02-05T00:17:12Z

    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

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

    Neil Chen <carpenter.nail.cz@gmail.com> — 2021-02-05T03:02:52Z

    On Fri, Feb 5, 2021 at 12:43 AM Mahendra Singh Thalor <mahi6run@gmail.com>
wrote:

> h 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,
> 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.
>
>
Oh, sorry I didn't describe it clearly, yes. It's a good idea to add test
cases to the patch. But Tom mentioned that he's already doing it, so I
don't want to do it again. Thank you for your reply.

-- 
There is no royal road to learning.
HighGo Software Co.

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

    Neil Chen <carpenter.nail.cz@gmail.com> — 2021-02-05T03:07:12Z

    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.

-- 
There is no royal road to learning.
HighGo Software Co.

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

    James Coleman <jtc331@gmail.com> — 2021-02-10T22:38:17Z

    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

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

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-02-11T17:05:58Z

    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

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

    James Coleman <jtc331@gmail.com> — 2021-02-15T13:55:40Z

    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

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

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-02-15T15:18:46Z

    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