> With such a large number of key items, it would be much > faster to sort the key items, and do a "merge join" of the key items and > the item on the page.
Here is a patch set along those lines, v2 attached. The locking is unchanged.
0001 sorts the query entries once. For each pending list row, it then looks up the row's keys in them with a binary search. That is faster than a plain merge, because a row usually has far fewer keys than the query. In Kirill's case, a 1s statement_timeout fires after 202s on master and after 1s with 0001. With a default size pending list, 1000 entry queries are 22x faster. Queries with fewer than 64 entries take the old path.
0002 calls the consistent functions after the pending list lock is released. It helps when many rows match. 0001 can go in without it.
0003 adds tests.
Large arrays are still slow in startScanKey(), but it holds no lock.
