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

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.