memory.reArrangeFallback uses 50% of the time for SELECT with 8k partitions

[mjonss]

Bug Report

Profiling a simple SELECT * FROM t for a partitioned table with maximum number of partitions spends around half the time in the memory.reArrangeFallback tracking function.

1. Minimal reproduce step (Required)

create table tp (a int primary key, b varchar(255)) partition by hash (a) partitions 8192;
insert into tp values (1, 'row with id 1, partition p1 filler data'), (2, 'partition p2, filler data for row with id 2'), (9, 'filler data for row with id 9, partition p9');
-- start profiling and run this over and over again for profiling:
select * from tp;

2. What did you expect to see? (Required)

The result to be given within milliseconds at least (MySQL does it in 0.1 second)

mysql> create table tp (a int primary key, b varchar(255)) partition by hash (a) partitions 8192;
Query OK, 0 rows affected (1 min 10,58 sec)

mysql> insert into tp values (1, 'row with id 1, partition p1 filler data'), (2, 'partition p2, filler data for row with id 2'), (9, 'filler data for row with id 9, partition p9');
Query OK, 3 rows affected (0,57 sec)
Records: 3  Duplicates: 0  Warnings: 0

mysql> select * from tp;
+---+---------------------------------------------+
| a | b                                           |
+---+---------------------------------------------+
| 1 | row with id 1, partition p1 filler data     |
| 2 | partition p2, filler data for row with id 2 |
| 9 | filler data for row with id 9, partition p9 |
+---+---------------------------------------------+
3 rows in set (0,11 sec)

3. What did you see instead (Required)

The SELECT query took 1 second

tidb> create table tp (a int primary key, b varchar(255)) partition by hash (a) partitions 8192;
Query OK, 0 rows affected (0,16 sec)

tidb> insert into tp values (1, 'row with id 1, partition p1 filler data'), (2, 'partition p2, filler data for row with id 2'), (9, 'filler data for row with id 9, partition p9');
Query OK, 3 rows affected (0,00 sec)
Records: 3  Duplicates: 0  Warnings: 0

tidb> select * from tp;
+---+---------------------------------------------+
| a | b                                           |
+---+---------------------------------------------+
| 1 | row with id 1, partition p1 filler data     |
| 2 | partition p2, filler data for row with id 2 |
| 9 | filler data for row with id 9, partition p9 |
+---+---------------------------------------------+
3 rows in set (1,01 sec)

4. What is your TiDB version? (Required)

Release Version: v5.4.0-alpha-289-g92c7c075d5
Edition: Community
Git Commit Hash: 92c7c075d502f81af2298582f66533bc23cb3d53
Git Branch: master
UTC Build Time: 2021-12-01 12:29:27
GoVersion: go1.17
Race Enabled: false
TiKV Min Version: v3.0.0-60965b006877ca7234adaced7890d7b029ed1306
Check Table Before Drop: false 

Profiles: