Hello David, On Mon, Sep 16, 2019 at 09:07:09PM +1200, David Sickmiller wrote:
I've been using MySQL/MariaDB for two decades but have more recently been working with Elasticsearch. I knew to expect an inverted index to speed up querying full text fields, but I've been surprised (and a bit annoyed) at how fast ES can query structured data. (In my case, I'm largely looking for intersections of a number of varchar fields with lowish cardinality, e.g. WHERE country = 'US' AND client = 'Microsoft' AND status = 'Completed'.)
Elasticsearch seems to have several things going on, but I think a core aspect, to use RDMS terminology, is that each column is indexed, and index unions/intersections are used if the WHERE clause references multiple columns.
I've heard that MySQL/MariaDB has the ability to merge indexes, but I've rarely observed it in person. Googling for it yields a bunch of StackOverflow posts complaining how slow it is, with responses agreeing and explaining how to disable it.
If I'm reading the MySQL/MariaDB code correctly, it looks like MariaDB will intersect indexes by looping through each index, reading the rowids of all matching keys and then, at the end (or once the buffer is full), checking whether each rowid is present in each index.
There are two algorithms: 1. index_merge/intersection This is implemented in QUICK_ROR_INTERSECT_SELECT. It is applicable when rowids from each source we are merging come ordered by the rowid value. This requirement is met when the scan over a single-point range. If the table has an index defined as INDEX i1(col1, ..., colN) then index tuples that compare as equal are ordered by their rowid. That is, if one does an index scan over (col1, ... colN)=(const1, ..., constN) they will get the records i`n rowid order. QUICK_ROR_INTERSECT select will run the scans on all merged streams simultaneously and do ordered-stream-merge on them. 2. index_merge/sort-interesect ( https://mariadb.com/kb/en/library/index_merge-sort_intersection/) This is implemented in QUICK_INDEX_INTERSECT_SELECT. The algorithm doesn't assume that the input streams are ordered. It scans all inputs and puts the rowids into a "Unique" object (think RB tree which overflows to disk). After the scans are finished, it can check which rowids were produced in all of the inputs, and those are in the intersection.
I wonder if there's an opportunity to speed this up. If we first read in the rowids from one index (ideally the one with the fewest matches), we could tell the storage engine that, when reading the next index, it should skip over rowids lower than the next candidate intersection.
This is a good idea, neither QUICK_ROR_INTERSECT_SELECT, nor QUICK_INDEX_INTERSECT_SELECT do this.
In the best case scenario, I think this could enable InnoDB to use its page directory to skip past some of the keys, improving the performance from O(n) to O(log n).
Agree. If the scans being merged produce data with non-overlapping rowid ranges, then things could be sped up. I'm just wondering how often this is the case in practice. Do you have any thoughts this?
That said, this is all new to me. Maybe there's an obvious reason this wouldn't make much of an improvement, or maybe I've overlooked that it's already been done. However, if it looks promising to you folk, and it's something you'd consider merging, I'd be willing to attempt writing a PR for it.
BR Sergei -- Sergei Petrunia, Software Developer MariaDB Corporation | Skype: sergefp | Blog: http://s.petrunia.net/blog