| Bug #98770 | Non-covering full index scan is always preferred over table scan for GROUP BY | ||
|---|---|---|---|
| Submitted: | 28 Feb 2020 4:02 | Modified: | 3 Mar 2020 13:14 |
| Reporter: | Øystein Grøvlen | Email Updates: | |
| Status: | Verified | Impact on me: | |
| Category: | MySQL Server: Optimizer | Severity: | S5 (Performance) |
| Version: | 8.0.19 | OS: | Any |
| Assigned to: | CPU Architecture: | Any | |
[28 Feb 2020 13:27]
MySQL Verification Team
Hi Øystein, Thank you for yet another useful report. There are only couple of requests from me. We do not use DBT3, so, could you upload for us a test case with a smaller size then that huge database ??? Testing a bug on 50 Gb is a bit too much. May be you could upload a dump only of that table ??? We use mostly sysbench and our internal "World" database, without any additional requests. Next, EXPLAINs do not show "Using index", which means that data pages are read. That column is actually empty, so this looks like second bug report. There is no "Using where" nor "Using index", so may be there should be some third category. Do you concur ??? Next, you have shown that MEMORY engine is faster then TempTable engine. That would be a third bug report. Do you concur with this as well ??? Hence , we have three bugs in a single report. Would you agree that this should lead to three bug reports, all of which quite useful ??? Many thanks in advance.
[28 Feb 2020 18:41]
Øystein Grøvlen
Hi Sinisa! 1. Here is the results from running a similar query against the world database: mysql> SELECT sql_text, timer_wait/1000000000.0 "Time (ms)" FROM performance_schema.events_statements_history order by timer_start; +--------------------------------------------------------------------+-----------+ | sql_text | Time (ms) | +--------------------------------------------------------------------+-----------+ | truncate performance_schema.events_statements_history | 3.1604 | | select avg(population) from city group by countrycode | 7.2727 | | select avg(population) from city group by countrycode | 7.0528 | | select avg(population) from city group by countrycode | 6.9788 | | select avg(population) from city group by countrycode | 7.1160 | | select avg(population) from city group by countrycode | 6.9783 | | select avg(population) from city group by countrycode | 7.0807 | | select avg(population) from city group by countrycode | 6.9727 | | select avg(population) from city group by countrycode | 6.9246 | | select avg(population) from city group by countrycode | 6.9634 | | select avg(population) from city group by countrycode | 6.9464 | | select avg(population) from city use index () group by countrycode | 3.1152 | | select avg(population) from city use index () group by countrycode | 2.9697 | | select avg(population) from city use index () group by countrycode | 3.0242 | | select avg(population) from city use index () group by countrycode | 3.1219 | | select avg(population) from city use index () group by countrycode | 3.1007 | | select avg(population) from city use index () group by countrycode | 3.0109 | | select avg(population) from city use index () group by countrycode | 2.9983 | | select avg(population) from city use index () group by countrycode | 2.9582 | | select avg(population) from city use index () group by countrycode | 3.3237 | | select avg(population) from city use index () group by countrycode | 3.1143 | +--------------------------------------------------------------------+-----------+ 21 rows in set (0.01 sec) As you can see, the default plan takes around 7 ms, while a table scan uses around 3 ms. 2. I see no problem with the EXPLAIN output. There is no "Using index" because the index scan is not covering, and there is no "Using where" because there is no WHERE clause. I do think it is a good idea to add information about everything that is not used. That will be a long list! 3. Yes, it looks like the query is 10% faster when using the MEMORY engine for temporary tables. I can file a separate bug for that.
[28 Feb 2020 19:10]
Øystein Grøvlen
If the query is disk-bound, the use of a non-covering index scan is a total disaster. This is the result of running the query on a DBT3 SF10 database with a 1 GB buffer pool (O_DIRECT is used to make this really disk-bound): -------------- select max(total) from ( select l_partkey, l_suppkey, sum(l_quantity) total from lineitem group by l_partkey, l_suppkey) dt -------------- +------------+ | max(total) | +------------+ | 780.00 | +------------+ 1 row in set (1 hour 42 min 50.52 sec) -------------- select max(total) from ( select l_partkey, l_suppkey, sum(l_quantity) total from lineitem use index () group by l_partkey, l_suppkey) dt -------------- +------------+ | max(total) | +------------+ | 780.00 | +------------+ 1 row in set (1 min 46.85 sec) -------------- set internal_tmp_mem_storage_engine=MEMORY -------------- Query OK, 0 rows affected (0.00 sec) -------------- select max(total) from ( select l_partkey, l_suppkey, sum(l_quantity) total from lineitem group by l_partkey, l_suppkey) dt -------------- +------------+ | max(total) | +------------+ | 780.00 | +------------+ 1 row in set (1 hour 42 min 14.12 sec) -------------- select max(total) from ( select l_partkey, l_suppkey, sum(l_quantity) total from lineitem use index () group by l_partkey, l_suppkey) dt -------------- +------------+ | max(total) | +------------+ | 780.00 | +------------+ 1 row in set (7 min 37.11 sec) Using index scans is 60 times slower with index scan, and in this case, table scan is much faster even when the temporary tables overflows to InnoDB.
[3 Mar 2020 13:14]
MySQL Verification Team
Hi Øystein Grøvlen, Thank you for the results. I have repeated your test case results. I think that this report actually covers three bugs, but will wait for other reports from Øystein. Verified as reported.
Description: If query contains GROUP BY on and indexed column , optimizer will always choose full index scan over table scan even when the index is non-covering. It is hard to find examples where this actually is a good idea. Some examples with DBT3 database, scale factor 10 (32 GB buffer pool, so all data in memory): mysql> explain select c_nationkey, sum(c_acctbal) from customer group by c_nationkey; +----+-------------+----------+------------+-------+---------------+---------------+---------+------+---------+----------+-------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+----------+------------+-------+---------------+---------------+---------+------+---------+----------+-------+ | 1 | SIMPLE | customer | NULL | index | i_c_nationkey | i_c_nationkey | 9 | NULL | 1442773 | 100.00 | NULL | +----+-------------+----------+------------+-------+---------------+---------------+---------+------+---------+----------+-------+ 1 row in set, 1 warning (0.00 sec) mysql> select c_nationkey, sum(c_acctbal) from customer group by c_nationkey; +-------------+----------------+ | c_nationkey | sum(c_acctbal) | +-------------+----------------+ | 0 | 268727967.93 | | 1 | 268445901.51 | | 2 | 269844850.34 | | 3 | 269347303.31 | | 4 | 269207115.03 | | 5 | 272855132.39 | | 6 | 270441588.36 | | 7 | 269991779.89 | | 8 | 271302483.04 | | 9 | 271434191.92 | | 10 | 271189253.04 | | 11 | 271271131.15 | | 12 | 269345607.23 | | 13 | 269863231.63 | | 14 | 267281180.97 | | 15 | 269517523.48 | | 16 | 269989036.21 | | 17 | 268070719.04 | | 18 | 269149987.41 | | 19 | 269191526.59 | | 20 | 269676520.58 | | 21 | 269774378.34 | | 22 | 270770602.42 | | 23 | 270680883.97 | | 24 | 270994214.69 | +-------------+----------------+ 25 rows in set (3.99 sec) mysql> explain select c_nationkey, sum(c_acctbal) from customer use index () group by c_nationkey; +----+-------------+----------+------------+------+---------------+------+---------+------+---------+----------+-----------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+----------+------------+------+---------------+------+---------+------+---------+----------+-----------------+ | 1 | SIMPLE | customer | NULL | ALL | i_c_nationkey | NULL | NULL | NULL | 1442773 | 100.00 | Using temporary | +----+-------------+----------+------------+------+---------------+------+---------+------+---------+----------+-----------------+ 1 row in set, 1 warning (0.00 sec) mysql> select c_nationkey, sum(c_acctbal) from customer use index () group by c_nationkey; +-------------+----------------+ | c_nationkey | sum(c_acctbal) | +-------------+----------------+ | 15 | 269517523.48 | | 13 | 269863231.63 | | 1 | 268445901.51 | | 4 | 269207115.03 | | 3 | 269347303.31 | | 20 | 269676520.58 | | 18 | 269149987.41 | | 17 | 268070719.04 | | 8 | 271302483.04 | | 5 | 272855132.39 | | 23 | 270680883.97 | | 10 | 271189253.04 | | 2 | 269844850.34 | | 6 | 270441588.36 | | 22 | 270770602.42 | | 12 | 269345607.23 | | 0 | 268727967.93 | | 21 | 269774378.34 | | 19 | 269191526.59 | | 16 | 269989036.21 | | 9 | 271434191.92 | | 11 | 271271131.15 | | 7 | 269991779.89 | | 14 | 267281180.97 | | 24 | 270994214.69 | +-------------+----------------+ 25 rows in set (1.13 sec) We see that query takes more than 3 times as long with index scan. Another example with a query that has very many groups: mysql> select max(total) from ( select l_partkey, l_suppkey, sum(l_quantity) total from lineitem group by l_partkey, l_suppkey) dt; +------------+ | max(total) | +------------+ | 780.00 | +------------+ 1 row in set (4 min 38.28 sec) mysql> select max(total) from ( select l_partkey, l_suppkey, sum(l_quantity) total from lineitem use index () group by l_partkey, l_suppkey) dt; +------------+ | max(total) | +------------+ | 780.00 | +------------+ 1 row in set (1 min 52.44 sec) Table scan is still much faster. Note, however, that if we use the pre-8.0 temporary table scheme so that the temporary table will overflow to InnoDB for queries with many groups, index scan will be faster: mysql> set internal_tmp_mem_storage_engine=MEMORY; Query OK, 0 rows affected (0.00 sec) mysql> select max(total) from ( select l_partkey, l_suppkey, sum(l_quantity) total from lineitem use index () group by l_partkey, l_suppkey) dt; +------------+ | max(total) | +------------+ | 780.00 | +------------+ 1 row in set (7 min 43.10 sec) mysql> select max(total) from ( select l_partkey, l_suppkey, sum(l_quantity) total from lineitem group by l_partkey, l_suppkey) dt; +------------+ | max(total) | +------------+ | 780.00 | +------------+ 1 row in set (4 min 40.03 sec) Note that for queries with few groups, table scan is still much faster: mysql> set internal_tmp_mem_storage_engine=MEMORY; Query OK, 0 rows affected (0.00 sec) mysql> select c_nationkey, sum(c_acctbal) from customer group by c_nationkey; +-------------+----------------+ | c_nationkey | sum(c_acctbal) | +-------------+----------------+ | 0 | 268727967.93 | | 1 | 268445901.51 | | 2 | 269844850.34 | | 3 | 269347303.31 | | 4 | 269207115.03 | | 5 | 272855132.39 | | 6 | 270441588.36 | | 7 | 269991779.89 | | 8 | 271302483.04 | | 9 | 271434191.92 | | 10 | 271189253.04 | | 11 | 271271131.15 | | 12 | 269345607.23 | | 13 | 269863231.63 | | 14 | 267281180.97 | | 15 | 269517523.48 | | 16 | 269989036.21 | | 17 | 268070719.04 | | 18 | 269149987.41 | | 19 | 269191526.59 | | 20 | 269676520.58 | | 21 | 269774378.34 | | 22 | 270770602.42 | | 23 | 270680883.97 | | 24 | 270994214.69 | +-------------+----------------+ 25 rows in set (4.20 sec) mysql> select c_nationkey, sum(c_acctbal) from customer use index () group by c_nationkey; +-------------+----------------+ | c_nationkey | sum(c_acctbal) | +-------------+----------------+ | 15 | 269517523.48 | | 13 | 269863231.63 | | 1 | 268445901.51 | | 4 | 269207115.03 | | 3 | 269347303.31 | | 20 | 269676520.58 | | 18 | 269149987.41 | | 17 | 268070719.04 | | 8 | 271302483.04 | | 5 | 272855132.39 | | 23 | 270680883.97 | | 10 | 271189253.04 | | 2 | 269844850.34 | | 6 | 270441588.36 | | 22 | 270770602.42 | | 12 | 269345607.23 | | 0 | 268727967.93 | | 21 | 269774378.34 | | 19 | 269191526.59 | | 16 | 269989036.21 | | 9 | 271434191.92 | | 11 | 271271131.15 | | 7 | 269991779.89 | | 14 | 267281180.97 | | 24 | 270994214.69 | +-------------+----------------+ 25 rows in set (1.03 sec) How to repeat: Run the following queries against a DBT3 database: select c_nationkey, sum(c_acctbal) from customer group by c_nationkey; select c_nationkey, sum(c_acctbal) from customer use index () group by c_nationkey; select c_nationkey, sum(c_acctbal) from customer group by c_nationkey; select c_nationkey, sum(c_acctbal) from customer use index () group by c_nationkey; Suggested fix: Change test_if_cheaper_ordering so that it does not switch from table scan to index scan if index is not covering: diff --git a/sql/sql_select.cc b/sql/sql_select.cc index 01d2fdfb92b..e1bedbdef8e 100644 --- a/sql/sql_select.cc +++ b/sql/sql_select.cc @@ -5248,7 +5248,7 @@ bool test_if_cheaper_ordering(const JOIN_TAB *tab, ORDER_with_src *order, */ if (((cur_access_method == JT_ALL || cur_access_method == JT_INDEX_SCAN) && - (is_covering || group || table->force_index)) || + (is_covering || table->force_index)) || index_scan_time < read_time) { ha_rows quick_records = table_records; const ha_rows refkey_select_limit = Alternatively, only switch if the estimated number of groups is very high.