InnoDB fulltext search reads to the end of the index since MDEV-28730; phrase search is quadratic

CREATE TABLE t (id INT PRIMARY KEY, body TEXT, FULLTEXT(body)) ENGINE=InnoDB

  SELECT seq AS id, CONCAT('alpha beta gamma delta epsilon ', seq, ' zeta eta theta') AS body FROM seq_1_to_4000;

SELECT COUNT(*) FROM t WHERE MATCH(body) AGAINST('"gamma delta"' IN BOOLEAN MODE);

Debug builds, same machine (every row matches):

A RelWithDebInfo build of main with our MDEV-10267 changes (which do not touch this code) takes 5.4 s for 4000 rows and 21.1 s for 8000 rows.

fts_query_fetch_document() reads each document with QueryExecutor::read_by_index() on FTS_DOC_ID_INDEX (PAGE_CUR_GE, read_all=true), and doc_id_exact_match_comparator() returns STOP for the first record with another FTS_DOC_ID. row_search_mvcc() turns the resulting DB_SUCCESS_LOCKED_REC into DB_SUCCESS (row0sel.cc:5913), so the while (err == DB_SUCCESS) loop in read_by_index() (row0query.cc:551) continues to the end of the index, with a clustered index lookup for every record. For 300 (600) rows, gdb counts 300 (600) calls of fts_query_fetch_document() and 45150 (180300) calls of doc_id_exact_match_comparator() and Row_sel_get_clust_rec_for_mysql::operator(), i.e. N*(N+1)/2. Innodb_buffer_pool_read_requests grows by 16.0 million for the 4000-row query (32 thousand on 11.4).

So each matching document costs one lookup per row from it to the end of FTS_DOC_ID_INDEX. With 4000 rows of which 400 match, the query takes 30 s when the matching rows come first and 1.7 s when they come last (0.06 s for both on 11.4). Proximity search and query expansion use the same function: with 1000 rows, AGAINST('"gamma epsilon" @3' IN BOOLEAN MODE) takes 10.2 s (11.4: 0.19 s) and AGAINST('gamma' WITH QUERY EXPANSION) 10.5 s (0.43 s).

Word lookups in the on-disk index read to the end as well: FTSQueryExecutor::read_aux() also uses read_by_index() with read_all=true, and AuxRecordReader::compare_record() returns STOP after the matching word. After OPTIMIZE TABLE of a table with the words wrd1..wrd50000, AGAINST('wrd1' IN BOOLEAN MODE) calls compare_record() 50000 times ('wrd5': 5556 times, once for each word from it to the end of the auxiliary table); 20 such queries take 7.0 s instead of 0.014 s on 11.4.

The commit 81c3836bb2 (MDEV-28730 Remove internal parser usage from InnoDB FTS) is in main, 13.1 and 13.1.1, but not in 13.0, 12.3 or 11.4. This is not MDEV-37370 (the list walk in fts_phrase_or_proximity_search(), which 11.4 also has).