InnoDB fulltext prefix search misses matching words with multi-level collations such as utf8mb4_uca1400_as_ci

With a collation that compares on more than one level, such as utf8mb4_uca1400_as_ci, a truncated word in a boolean mode search finds only some of the matching words:

SET NAMES utf8mb4;

CREATE TABLE t1 (id INT PRIMARY KEY, c TEXT, FULLTEXT(c))

  ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_uca1400_as_ci;

INSERT INTO t1 VALUES (1,'aab'), (2,'aabaa'), (3,'aábaa'), (4,'AABxx'),

  (5,'aabzz'), (6,'aábzz'), (7,'aacaa');

SELECT id FROM t1 WHERE MATCH(c) AGAINST('aab*' IN BOOLEAN MODE);

SELECT id FROM t1 WHERE MATCH(c) AGAINST('aáb*' IN BOOLEAN MODE);

Expected: 1, 2, 4, 5 for 'aab*' and 3, 6 for 'aáb*', the rows that c LIKE 'aab%' and c LIKE 'aáb%' return. Actual on 11.4, 13.1 and main: 1, 2 and 6.

Here the words are still in the FTS cache. If the index is built after the INSERT (CREATE TABLE t1 without FULLTEXT(c), then ALTER TABLE t1 ADD FULLTEXT(c)), the words are in the auxiliary tables. Then 11.4 returns 1, 2 and no rows, while 13.1 and main return the expected rows. utf8mb4_uca1400_as_cs gives the same results (InnoDB stores the words in lower case, so 'AABxx' matches 'aab*' there too).

The collation sorts by the primary weights first, so the words that match a prefix need not be next to each other. INNODB_FT_INDEX_CACHE and INNODB_FT_INDEX_TABLE list the words in this order: aab, aabaa, aábaa, aabxx, aabzz, aábzz, aacaa. 'aábaa' does not match 'aab*', but it is between two matches.

fts_cache_find_wildcard() (fts0que.cc) looks up one matching word in the cache and then moves to the previous and the next words only as long as they match, so it stops at 'aábaa'. In 11.4, the scan of the auxiliary table in fts_index_fetch_nodes() (WHERE word LIKE :word, an IB_LIKE_PREFIX end condition) stops at the first word that does not match in the same way. In 13.1 and main, the auxiliary table scan finds all matches only because it reads to the end of the index (MDEV-41754). The patch for MDEV-41754 makes that scan stop again, but keeps scanning for collations with more than one level (levels_for_order > 1), so the auxiliary table path stays correct in 13.1 and later. It does not change fts_cache_find_wildcard().

We noticed this while reviewing the patch for MDEV-41754.