Re: [Maria-developers] Performance of index intersection
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 ___ Mailing list: https://launchpad.net/~maria-developers Post to : maria-developers@lists.launchpad.net Unsubscribe : https://launchpad.net/~maria-developers More help : https://help.launchpad.net/ListHelp
Re: [Maria-developers] [Commits] cde9170709c: MDEV-18648: slave_parallel_mode= optimistic default in 10.5
sujatha writes:
Hi Sujutha,
> @sql/sql_class.h
> Moved 'wait_for_prior_commit(THD *thd)' method inside sql_class.cc
>
> @sql/sql_class.cc
> Added code to check for 'stop_on_error_sub_id' for event groups which get
> skipped
> and don't have any preceding group to wait for.
This looks like the wrong fix. The wait_for_commit mechanism is a low-level
API, it should not deal with things like stop_on_error_sub_id.
> 1,2,3 are scheduled in parallel.
> Since the above is true 'skip_event_group=true' is set. Simply call
> 'wait_for_prior_commit' to wakeup all waiters. Group '2' didn't had any
> waitee and its execution is skipped. Hence its wakeup_error=0.It sends a
> positive wakeup signal to '3'. Which commits. This results in a missed
> transaction. i.e 33 is missed.
I think this the the real problem. 2 is stopping because of error, it must
not call wakeup_subsequent_commits() without propagating the error, that
breaks the whole semantics of wait_for_commit.
Maybe it's enough just to also set rgi->worker_error here, when
skip_event_group is set due to error in an earlier group?
if (unlikely(entry->stop_on_error_sub_id <= rgi->wait_commit_sub_id))
skip_event_group= true;
Then wakeup_subsequent_commits() will correctly inform the following
transaction about the error so it doesn't try to commit on its own.
There is already similar code in the retry_event_group() function:
if (entry->stop_on_error_sub_id == (uint64) ULONGLONG_MAX ||
rgi->gtid_sub_id < entry->stop_on_error_sub_id)
...
else {
err= rgi->worker_error= 1;
Then all of the changes to sql_class.h and sql_class.cc can be omittet.
Also, this fix doesn't seem to belong with the other MDEV-18648 changes, it
is unrelated to what the default parallel replication mode is. So please do
it in a separate commit.
Hope this helps,
- Kristian.
> diff --git a/sql/sql_class.cc b/sql/sql_class.cc
> index 4eab241232b..5ba9c5fe456 100644
> --- a/sql/sql_class.cc
> +++ b/sql/sql_class.cc
> @@ -7365,6 +7365,33 @@
> wait_for_commit::register_wait_for_prior_commit(wait_for_commit *waitee)
> }
>
>
> +int wait_for_commit::wait_for_prior_commit(THD *thd)
> +{
> + /*
> + Quick inline check, to avoid function call and locking in the common
> case
> + where no wakeup is registered, or a registered wait was already
> signalled.
> + */
> + if (waitee)
> +return wait_for_prior_commit2(thd);
> + else
> + {
> +if (wakeup_error)
> + my_error(ER_PRIOR_COMMIT_FAILED, MYF(0));
> +else
> +{
> + rpl_group_info* rgi= thd->rgi_slave;
> + if (rgi && rgi->is_parallel_exec &&
> + rgi->parallel_entry->stop_on_error_sub_id < (uint64)ULONGLONG_MAX
> &&
> + rgi->gtid_sub_id >= rgi->parallel_entry->stop_on_error_sub_id)
> + {
> +my_error(ER_PRIOR_COMMIT_FAILED, MYF(0));
> +wakeup_error= ER_PRIOR_COMMIT_FAILED;
> + }
> +}
> +return wakeup_error;
> + }
> +}
> +
> /*
>Wait for commit of another transaction to complete, as already registered
>with register_wait_for_prior_commit(). If the commit already completed,
> @@ -7387,6 +7414,17 @@ wait_for_commit::wait_for_prior_commit2(THD *thd)
>{
> if (wakeup_error)
>my_error(ER_PRIOR_COMMIT_FAILED, MYF(0));
> +else
> +{
> + rpl_group_info* rgi= thd->rgi_slave;
> + if (rgi && rgi->is_parallel_exec &&
> + rgi->parallel_entry->stop_on_error_sub_id < (uint64)ULONGLONG_MAX
> &&
> + rgi->gtid_sub_id >= rgi->parallel_entry->stop_on_error_sub_id)
> + {
> +my_error(ER_PRIOR_COMMIT_FAILED, MYF(0));
> +wakeup_error= ER_PRIOR_COMMIT_FAILED;
> + }
> +}
> goto end;
>}
>/*
> diff --git a/sql/sql_class.h b/sql/sql_class.h
> index 72cb8148895..0a0a1aa9fa1 100644
> --- a/sql/sql_class.h
> +++ b/sql/sql_class.h
> @@ -2062,21 +2062,6 @@ struct wait_for_commit
>bool commit_started;
>
>void register_wait_for_prior_commit(wait_for_commit *waitee);
> - int wait_for_prior_commit(THD *thd)
> - {
> -/*
> - Quick inline check, to avoid function call and locking in the common
> case
> - where no wakeup is registered, or a registered wait was already
> signalled.
> -*/
> -if (waitee)
> - return wait_for_prior_commit2(thd);
> -else
> -{
> - if (wakeup_error)
> -my_error(ER_PRIOR_COMMIT_FAILED, MYF(0));
> - return wakeup_error;
> -}
> - }
>void wakeup_subsequent_commits(int wakeup_error_arg)
>{
> /*
> @@ -2123,6 +2108,7 @@ struct wait_for_commit
>
>void wakeup(int wakeup_error);
>
> + int wait_for_prior_commit(THD *thd);
>int wait_for_prior_commit2(THD *thd);
>void wakeup_subsequent_commits2(int wakeup_error);
>void unregister_wait_for_prior_commit2();
___
Mailing list: https://launchpad.net/~maria-developers
Post to : maria-developers@lists.launchpad.net
Unsubscribe :
