Multi Range Read optimization
Contents
Multi Range Read is an optimization aimed at improving performance for IO-bound queries that need to scan lots of rows.
Multi Range Read is available in MariaDB since MariaDB 5.3, and MySQL has a subset of it in MySQL 5.6.
Multi Range Read can be used with
range
accessref
andeq_ref
access, when they are using Batched Key Access
as shown in this diagram:
The idea
Case 1: rowid sorting for range access
Consider a range query:
MariaDB [test]> explain select * from tbl where tbl.key1 between 1000 and 2000; +----+-------------+-------+-------+---------------+------+---------+------+------+-----------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+------+---------+------+------+-----------------------+ | 1 | SIMPLE | tbl | range | key1 | key1 | 5 | NULL | 960 | Using index condition | +----+-------------+-------+-------+---------------+------+---------+------+------+-----------------------+
When this query is executed, disk IO access pattern will follow the red line in this figure:
Execution will hit the table rows in random places, as marked with the blue line/numbers in the figure.
When the table is sufficiently big, each table record read will need to actually go to disk (and be served from buffer pool or OS cache), and query execution will be too slow to be practical. For example, a 10,000 RPM disk drive is able to make 167 seeks per second, so in the worst case, query execution will be capped at reading about 167 records per second.
SSD drives do not need to do disk seeks, so they will not be hurt as badly, however the performance will still be poor in many cases.
Multi-Range-Read optimization aims to make disk access faster by sorting record read requests and then doing one ordered disk sweep. If one enables Multi Range Read, EXPLAIN
will show Rowid-ordered scan
:
MariaDB [test]> set optimizer_switch='mrr=on'; Query OK, 0 rows affected (0.06 sec) MariaDB [test]> explain select * from tbl where tbl.key1 between 1000 and 2000; +----+-------------+-------+-------+---------------+------+---------+------+------+-------------------------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+-------+---------------+------+---------+------+------+-------------------------------------------+ | 1 | SIMPLE | tbl | range | key1 | key1 | 5 | NULL | 960 | Using index condition; Rowid-ordered scan | +----+-------------+-------+-------+---------------+------+---------+------+------+-------------------------------------------+ 1 row in set (0.03 sec)
and the execution will proceed as follows:
Reading disk data sequentially is generally faster, because
- Rotating drives do not have to move the head back and forth
- One can take advantage of IO-prefetching done at various levels
- Each disk page will be read exactly once, which means we won't rely on disk cache (or buffer pool) to save us from reading the same page multiple times.
The above can make a huge difference on performance. There is also a catch, though:
- If you're scanning small data ranges in a table that is sufficiently small so that it completely fits into the OS disk cache, then you may observe that the only effect of MRR is that extra buffering/sorting adds some CPU overhead.
LIMIT n
andORDER BY ... LIMIT n
queries with small values ofn
may become slower. The reason is that MRR reads data in disk order, whileORDER BY ... LIMIT n
wants firstn
records in index order.
Case 2: Rowid sorting for Batched Key Access
Batched Key Access can benefit from rowid sorting in the same way as range access does. If one has a join that uses index lookups:
MariaDB [test]> explain select * from t1,t2 where t2.key1=t1.col1; +----+-------------+-------+------+---------------+------+---------+--------------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+------+---------------+------+---------+--------------+------+-------------+ | 1 | SIMPLE | t1 | ALL | NULL | NULL | NULL | NULL | 1000 | Using where | | 1 | SIMPLE | t2 | ref | key1 | key1 | 5 | test.t1.col1 | 1 | | +----+-------------+-------+------+---------------+------+---------+--------------+------+-------------+ 2 rows in set (0.00 sec)
Execution of this query will cause table t2
to be hit in random locations by lookups made through t2.key1=t1.col
. If you enable Multi Range and and Batched Key Access, you will get table t2
to be accessed using a Rowid-ordered scan
:
MariaDB [test]> set optimizer_switch='mrr=on'; Query OK, 0 rows affected (0.06 sec) MariaDB [test]> set join_cache_level=6; Query OK, 0 rows affected (0.00 sec) MariaDB [test]> explain select * from t1,t2 where t2.key1=t1.col1; +----+-------------+-------+------+---------------+------+---------+--------------+------+--------------------------------------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+------+---------------+------+---------+--------------+------+--------------------------------------------------------+ | 1 | SIMPLE | t1 | ALL | NULL | NULL | NULL | NULL | 1000 | Using where | | 1 | SIMPLE | t2 | ref | key1 | key1 | 5 | test.t1.col1 | 1 | Using join buffer (flat, BKA join); Rowid-ordered scan | +----+-------------+-------+------+---------------+------+---------+--------------+------+--------------------------------------------------------+ 2 rows in set (0.00 sec)
The benefits will be similar to those listed for range
access.
An additional source of speedup is this property: if there are multiple records in t1
that have the same value of t1.col1
, then regular Nested-Loops join will make multiple index lookups for the same value of t2.key1=t1.col1
. The lookups may or may not hit the cache, depending on how big the join is. With Batched Key Access and Multi-Range Read, no duplicate index lookups will be made.
Case 3: Key sorting for Batched Key Access
Let us consider again example of neted loop join, with ref
access on the second table:
MariaDB [test]> explain select * from t1,t2 where t2.key1=t1.col1; +----+-------------+-------+------+---------------+------+---------+--------------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-------+------+---------------+------+---------+--------------+------+-------------+ | 1 | SIMPLE | t1 | ALL | NULL | NULL | NULL | NULL | 1000 | Using where | | 1 | SIMPLE | t2 | ref | key1 | key1 | 5 | test.t1.col1 | 1 | | +----+-------------+-------+------+---------------+------+---------+--------------+------+-------------+
Execution of this query plan will cause random hits to be made into the index t2.key1
, as shown in this picture:
In particular, on step #5 we'll read the same index page that we've read on step #2, and the page we've read on step #4 will be re-read on step#6. If all pages you're accessing are in the cache (in the buffer pool, if you're using InnoDB, and in the key cache, if you're using MyISAM), this is not a problem. However, if your hit ratio is poor and you're going to hit the disk, it makes sense to sort the lookup keys, like shown in this figure:
This is roughly what Key-ordered scan
optimization does. In EXPLAIN, it looks like follows:
MariaDB [test]> set optimizer_switch='mrr=on,mrr_sort_keys=on'; Query OK, 0 rows affected (0.00 sec) MariaDB [test]> set join_cache_level=6; Query OK, 0 rows affected (0.02 sec) MariaDB [test]> explain select * from t1,t2 where t2.key1=t1.col1\G *************************** 1. row *************************** id: 1 select_type: SIMPLE table: t1 type: ALL possible_keys: a key: NULL key_len: NULL ref: NULL rows: 1000 Extra: Using where *************************** 2. row *************************** id: 1 select_type: SIMPLE table: t2 type: ref possible_keys: key1 key: key1 key_len: 5 ref: test.t1.col1 rows: 1 Extra: Using join buffer (flat, BKA join); Key-ordered Rowid-ordered scan 2 rows in set (0.00 sec)
((TODO: a note about InnoDB's clustered primary index).
Buffer space management
.
Factsheet
- Multi Range Read is used by
range
access method for range scans.- Batched Key Access for joins
- Multi Range Read can cause slowdowns for small queries over small tables, so it is disabled by default.
- There are two strategies:
- Rowid-ordered scan
- Key-ordered scan
- : and you can tell if either of them is used by checking the
Extra
column inEXPLAIN
output. - There are three
@@optimizer_switch
flags you can switch ON:mrr=on
- enable MRR and rowid ordered scansmrr_sort_keys=on
- enable Key-ordered scans (you must also setmrr=on
for this to have any effect)mrr_cost_based=on
- enable cost-based choice whether to use MRR. Currently not recommended due to poor cost model. <</sql>>
Differences from MySQL
- MySQL supports only
Rowid ordered scan
, which it shows inEXPLAIN
asUsing MRR
. - EXPLAIN in MySQL shows "
Using MRR
", while in MariaDB it is either"Rowid-ordered scan"
, "Key-ordered scan
", orKey-ordered Rowid-ordered scan".
- for
range
access, the size of the buffer is controlled by the@mrr_buffer_size
variable (Original MySQL 6.0 and current MySQL 5.6 use@@read_rnd_buffer_size
, which is also used to control the buffer size for other algorithms) - [is this a difference?] When used with BKA, buffer space management is done by BKA code. It uses up to
@join_buffer_size
bytes per table, distributing it across its own buffers and buffers it provides to MRR.
See also
- What is MariaDB 5.3
- Multi-Range Read Optimization page in MySQL manual