Hi Sergey!

Actually fetching min & max value for each keys (key1=1 and key2=2 in your case) should not cost much?
Then you can compute the overlap zone (Zone B in your graph) and directly perform a jump on the beginning of Zone B and stop at the end of Zone B instead of EOF, using the index with the less amount of matching rows.

BR,
  Jocelyn


> Le 1 oct. 2019 à 21:31, Sergey Petrunia <sergey@mariadb.com> a écrit :
>
> Hello,
>
> More thoughts on this:
>
> Let's consider a query
>
> select * from t1 where key1=1 and key2=2
>
> let's assume it uses index itnersection.
>
> Check the attached picture. It shows the table rowids at the center,
> key1 on the left, key2 on the right.
>
> There are three zones:
>
> - Zone A, where rowids matching 'key1=1' have no overlap with any rowids for 'key2=2'
>
> - Zone B, where rowids from two scans overlap.
>
> - Zone C, similar to zone A but at the end of the scan. Here, rowids matching
> key2=2 have no overlap.
>
> The current "merge-ordered-streams" algorithm takes care of "Zone C".
> the code will return EOF as soon as one of the merged streams has produced EOF.
>
> Now, let's look at Zone B.  Here, the code would scan both indexes forward
> and search for records with key=1 that have matches with key=2.
>
> The search forward is this loop in QUICK_ROR_INTERSECT_SELECT::get_next:
>
>    do
>    {
>      DBUG_EXECUTE_IF("innodb_quick_report_deadlock",
>                      DBUG_SET("+d,innodb_report_deadlock"););
>      if (unlikely((error= quick->get_next())))
>      {
>        /* On certain errors like deadlock, trx might be rolled back.*/
>        if (!thd->transaction_rollback_request)
>          quick_with_last_rowid->file->unlock_row();
>        DBUG_RETURN(error);
>      }
>      quick->file->position(quick->record);
>      cmp= head->file->cmp_ref(quick->file->ref, last_rowid);
>      if (cmp < 0)
>      {
>        /* This row is being skipped.  Release lock on it. */
>        quick->file->unlock_row();
>      }
>    } while (cmp < 0);
>
>
> the quick->get_next() call (after several levels of indirection) do this
> storage engine API call:
>
>  handler->index_next_same();
>
> And the question is whether it would be faster if this call was made instead:
>
>  handler->index_read_map(key_value, rowid_of_match_candidate);
>
> The answer is that it's faster to do a jump when we will jump over many
> records. When we jump over a few, it is actually slower than making several
> index_next_same() calls.  The first reason for this is that doing seeks will
> break InnoDB's prefetch buffer optimization. There might be other reasons.
>
> I don't have any idea how one could predict the jump size.
>
> As for Zone A, we could jump it over with one jump. If we first read the rowid
> from "key2=2", then we could already use it when making a lookup with key1=1.
>
> But what if we first did an index lookup on key1=1? Then we will miss the
> chance to jump to the first rowid for that one sees for key2=2...
>
> If we assume that the first jump is more important than others, we could just
> look at the first record in each of the merged indexes and then feed them all
> back the maximum rowid we saw as the starting point. This would let us jump
> over zone A.
>
> I think, implementing "jump over zone A" is easier than inventing a way to do
> jumps while in zone B. (And this is actually what your idea was).
>
>
> A different question - are there any example datasets or queries we
> could try this on? One can of course construct an artificial dataset and
> queries but it would be much nicer to try this on a real dataset and a real
> query.
>
> BR
> -- Sergei P.
>
> On Fri, Sep 20, 2019 at 12:31:10PM +0300, Sergey Petrunia wrote:
>> 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
>>
>>
>
> BR
> Sergei
> --
> Sergei Petrunia, Software Developer
> MariaDB Corporation | Skype: sergefp | Blog: http://s.petrunia.net/blog
>
>
> <index-merge1.jpg>