Bug #101855 SELECT DISTINCT returns wrong results if not_used_in_distinct and use JOIN CACHE
Submitted: 3 Dec 2020 11:43 Modified: 4 Dec 2020 15:33
Reporter: Hope Lee (OCA) Email Updates:
Status: Not a Bug Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S2 (Serious)
Version:8.0.13 OS:CentOS
Assigned to: CPU Architecture:Any

[3 Dec 2020 11:43] Hope Lee
Description:
In MySQL server newer than 5.6, there exists an optimization on SELECT DISTINCT queries. The prerequisite is that the select fields' list doesn't depend on some tables, represented by QEP_TAB::not_used_in_distinct. During the JOIN process, if we have found at least one record, we can abort finding more new records, which is called "shortcut join enumeration" by setting a smaller value to JOIN::return_tab. See the core codes in the sql_executor.cc(MySQL 8.0.13):

@@ 1876,10 @@ static enum_nested_loop_state evaluate_join_record(JOIN *join,

       /*
         Test if this was a SELECT DISTINCT query on a table that
         was not in the field list;  In this case we can abort if
         we found a row, as no new rows can be added to the result.
       */
       if (not_used_in_distinct && found_records != join->found_records)
         set_if_smaller(return_tab, qep_tab_idx - 1);

       set_if_smaller(join->return_tab, return_tab);

This is reasonable so far, but what if a JOIN_CACHE operation (for example, Block Nested Loop) is behind the current table? After this table, we keep putting records into the JOIN buffer. When the buffer is full we begin to evaluate the records inside and send out the results. 

During this process, we may find several matched results from the old records in the cache. After then, the program goes to the above codes and finds the join->found_records greater than found_records (actually, join->found_records could be more than 1 greater than found_records), then shortcut join enumeration. 

It's possible that the current record being joined doesn't get a full join results yet. The increasing join->found_records is because of the old records in the join buffer. So the shortcut join enumeration will miss the current row result output.

How to repeat:
Reproduce this issue depends on the records' sizes, the size of join_buffer_size, and specific data. Also, the data and table schema are complex to put here. But if appropriate, the issue will occur every time when running a specific query. Let's see the EXPLAIN output of a query which will trigger this issue:
root@localhost:test 8.0.13-rds-dev-debug> EXPLAIN SELECT DISTINCT res.id
    -> FROM (t_resource res, t_role_resource trr)
    ->     INNER JOIN (
    ->         SELECT tar.role_id
    ->         FROM t_account_role tar
    ->         WHERE tar.account_id = 'test'
    ->         UNION
    ->         SELECT a.account_id
    ->         FROM t_account_role a
    ->         WHERE a.account_id = 'test'
    ->     ) t
    ->     ON trr.role_id = t.role_id
    -> WHERE res.id = trr.resource_id
    ->     AND res.record_status = 1
    ->     AND trr.record_status = 1
    -> AND res.system_id IN ('0');
+----+--------------+------------+------------+------+--------------------------------+------------------------+---------+-------------------+------+----------+--------------------------------------------------------------+
| id | select_type  | table      | partitions | type | possible_keys                  | key                    | key_len | ref               | rows | filtered | Extra                                                        |
+----+--------------+------------+------------+------+--------------------------------+------------------------+---------+-------------------+------+----------+--------------------------------------------------------------+
|  1 | PRIMARY      | res        | NULL       | ref  | PRIMARY,idx_resource_system_id | idx_resource_system_id | 131     | const             |    1 |    10.00 | Using where; Using temporary                                 |
|  1 | PRIMARY      | trr        | NULL       | ref  | idx_trr_resource_id            | idx_trr_resource_id    | 133     | test.res.id,const |  140 |   100.00 | Distinct                                                     |
|  1 | PRIMARY      | <derived2> | NULL       | ALL  | NULL                           | NULL                   | NULL    | NULL              |    4 |    25.00 | Using where; Distinct; Using join buffer (Block Nested Loop) |
|  2 | DERIVED      | tar        | NULL       | ref  | idx_tar_account_id             | idx_tar_account_id     | 131     | const             |    1 |   100.00 | NULL                                                         |
|  3 | UNION        | a          | NULL       | ref  | idx_tar_account_id             | idx_tar_account_id     | 131     | const             |    1 |   100.00 | Using index                                                  |
| NULL | UNION RESULT | <union2,3> | NULL       | ALL  | NULL                           | NULL                   | NULL    | NULL              | NULL |     NULL | Using temporary                                              |
+----+--------------+------------+------------+------+--------------------------------+------------------------+---------+-------------------+------+----------+--------------------------------------------------------------+
6 rows in set, 1 warning (0.01 sec)

This fits the situations I have described above.
[3 Dec 2020 11:44] Hope Lee
SELECT DISTINCT returns wrong results when JOIN enumeration shortcut

(*) I confirm the code being submitted is offered under the terms of the OCA, and that I am authorized to contribute it.

Contribution: 0001-Bugfix-SELECT-DISTINCT-returns-wrong-results-when-JO.patch (application/octet-stream, text), 3.92 KiB.

[4 Dec 2020 2:47] Hope Lee
I have created the test case for this issue, try the following SQL(I'm testing on MySQL 8.0.13):
CREATE TABLE t1(id INT PRIMARY KEY);
CREATE TABLE t2(id INT, str_id VARCHAR(40));

delimiter //
CREATE PROCEDURE batch_insert(IN row_count int)
BEGIN
  SET @i = 1;
  REPEAT
    INSERT INTO t1 VALUES (@i);
    SET @j = 1;
    REPEAT
      SET @str = (SELECT SUBSTRING(MD5(RAND()), 1, 40));
      INSERT INTO t2 VALUES (@i, @str);
      SET @j = @j + 1;
    UNTIL @j > 100
    END REPEAT;
    INSERT INTO t2 VALUES (@i, "2d1a3ac2e3b6464c857d81554a94028b");
    SET @i = @i + 1;
  UNTIL @i > row_count
  END REPEAT;
END;
//
delimiter ;

CALL batch_insert(20);

CREATE TABLE t3(id INT, str_id VARCHAR(40));
INSERT INTO t3 VALUES (10, "2d1a3ac2e3b6464c857d81554a94028b");
CREATE TABLE t4 AS SELECT * FROM t3;

SET join_buffer_size=40112;

root@localhost:test 8.0.13-rds-dev-debug> EXPLAIN SELECT /*+ JOIN_PREFIX(t1, t2) NO_BNL(t2) */ DISTINCT t1.id FROM (t1, t2) INNER JOIN ( SELECT str_id FROM t3 WHERE id = 10 UNION SELECT str_id FROM t4 WHERE id = 10 ) t ON t2.str_id = t.str_id WHERE t1.id = t2.id;
+----+--------------+------------+------------+-------+---------------+---------+---------+------+------+----------+--------------------------------------------------------------+
| id | select_type  | table      | partitions | type  | possible_keys | key     | key_len | ref  | rows | filtered | Extra                                                        |
+----+--------------+------------+------------+-------+---------------+---------+---------+------+------+----------+--------------------------------------------------------------+
|  1 | PRIMARY      | t1         | NULL       | index | PRIMARY       | PRIMARY | 4       | NULL |   20 |   100.00 | Using index; Using temporary                                 |
|  1 | PRIMARY      | t2         | NULL       | ALL   | NULL          | NULL    | NULL    | NULL | 2020 |    10.00 | Using where; Distinct                                        |
|  1 | PRIMARY      | <derived2> | NULL       | ALL   | NULL          | NULL    | NULL    | NULL |    4 |    25.00 | Using where; Distinct; Using join buffer (Block Nested Loop) |
|  2 | DERIVED      | t3         | NULL       | ALL   | NULL          | NULL    | NULL    | NULL |    1 |   100.00 | Using where                                                  |
|  3 | UNION        | t4         | NULL       | ALL   | NULL          | NULL    | NULL    | NULL |    1 |   100.00 | Using where                                                  |
| NULL | UNION RESULT | <union2,3> | NULL       | ALL   | NULL          | NULL    | NULL    | NULL | NULL |     NULL | Using temporary                                              |
+----+--------------+------------+------------+-------+---------------+---------+---------+------+------+----------+--------------------------------------------------------------+
6 rows in set, 1 warning (0.01 sec)

Actual result:
root@localhost:test 8.0.13-rds-dev-debug> SELECT /*+ JOIN_PREFIX(t1, t2) NO_BNL(t2) */ DISTINCT t1.id FROM (t1, t2) INNER JOIN ( SELECT str_id FROM t3 WHERE id = 10 UNION SELECT str_id FROM t4 WHERE id = 10 ) t ON t2.str_id = t.str_id WHERE t1.id = t2.id;
+----+
| id |
+----+
|  1 |
|  2 |
|  3 |
|  4 |
|  5 |
|  6 |
|  7 |
|  9 |
| 10 |
| 11 |
| 12 |
| 13 |
| 14 |
| 15 |
| 17 |
| 18 |
| 19 |
| 20 |
+----+
18 rows in set (3.77 sec)

Expected result:
root@localhost:test 8.0.13-rds-dev-debug> SELECT DISTINCT t1.id FROM (t1, t2) INNER JOIN ( SELECT str_id FROM t3 WHERE id = 10 UNION SELECT str_id FROM t4 WHERE id = 10 ) t ON t2.str_id = t.str_id WHERE t1.id = t2.id;
+----+
| id |
+----+
|  1 |
|  2 |
|  3 |
|  4 |
|  5 |
|  6 |
|  7 |
|  8 |
|  9 |
| 10 |
| 11 |
| 12 |
| 13 |
| 14 |
| 15 |
| 16 |
| 17 |
| 18 |
| 19 |
| 20 |
+----+
20 rows in set (0.26 sec)

Please try several times with different join_buffer_size and keep the execution plan same with above.
[4 Dec 2020 13:42] MySQL Verification Team
Hi Mr. Lee,

Thank you for your bug report.

However, we need more data in order to proceed to process your report.

First of all, we do not test, nor do we fix bugs in old releases. Hence, can you please try whether you observe the same behaviour with 8.0.22.

Next, let us know in which situations do you get a result set with 8 and 16 in the ID column, when queries are identical. What are the join_buffer_size settings for 8.0.22 at which you get these wrong and correct results ??

Last, but not least, if we manage to repeat this behaviour, a fix can be very, very simple. The minimum value of join_buffer_size can be set to be, for example, 100 Kbytes, so when anyone enters a smaller  value, it gets set to 100 Kb.

We are waiting on your feedback.
[4 Dec 2020 14:24] Hope Lee
Firstly the same behavior has been observed with 8.0.22 with the above test data I have provided. Some rows are missing in the result.
root@localhost:test 8.0.22-rds-dev>  SELECT /*+ JOIN_PREFIX(t1, t2) NO_BNL(t2) */ DISTINCT t1.id FROM (t1, t2) INNER JOIN ( SELECT str_id FROM t3 WHERE id = 10 UNION SELECT str_id FROM t4 WHERE id = 10 ) t ON t2.str_id = t.str_id + 1 WHERE t1.id = t2.id;
+----+
| id |
+----+
| 17 |
| 16 |
| 15 |
| 14 |
| 13 |
| 12 |
| 11 |
| 10 |
|  8 |
|  7 |
|  6 |
|  5 |
|  4 |
|  2 |
|  1 |
| 19 |
+----+
16 rows in set, 2301 warnings (0.02 sec) 

root@localhost:test 8.0.22-rds-dev> EXPLAIN SELECT /*+ JOIN_PREFIX(t1, t2) NO_BNL(t2) */ DISTINCT t1.id FROM (t1, t2) INNER JOIN ( SELECT str_id FROM t3 WHERE id = 10 UNION SELEC
T str_id FROM t4 WHERE id = 10 ) t ON t2.str_id = t.str_id + 1 WHERE t1.id = t2.id;
+----+--------------+------------+------------+-------+---------------+---------+---------+------+------+----------+------------------------------------------------------+
| id | select_type  | table      | partitions | type  | possible_keys | key     | key_len | ref  | rows | filtered | Extra                                                |
+----+--------------+------------+------------+-------+---------------+---------+---------+------+------+----------+------------------------------------------------------+
|  1 | PRIMARY      | t1         | NULL       | index | PRIMARY       | PRIMARY | 4       | NULL |   20 |   100.00 | Using index; Using temporary                         |
|  1 | PRIMARY      | t2         | NULL       | ALL   | NULL          | NULL    | NULL    | NULL | 2020 |    10.00 | Using where; Distinct                                |
|  1 | PRIMARY      | <derived2> | NULL       | ALL   | NULL          | NULL    | NULL    | NULL |    4 |   100.00 | Using where; Distinct; Using join buffer (hash join) |
|  2 | DERIVED      | t3         | NULL       | ALL   | NULL          | NULL    | NULL    | NULL |    1 |   100.00 | Using where                                          |
|  3 | UNION        | t4         | NULL       | ALL   | NULL          | NULL    | NULL    | NULL |    1 |   100.00 | Using where                                          |
| NULL | UNION RESULT | <union2,3> | NULL       | ALL   | NULL          | NULL    | NULL    | NULL | NULL |     NULL | Using temporary                                      |
+----+--------------+------------+------------+-------+---------------+---------+---------+------+------+----------+------------------------------------------------------+
6 rows in set, 1 warning (0.00 sec)

root@localhost:test 8.0.22-rds-dev> SELECT @@join_buffer_size;
+--------------------+
| @@join_buffer_size |
+--------------------+
|             262144 |
+--------------------+
1 row in set (0.00 sec)

Second, how can you tell the queries are identical ?? The first query above with the wrong results are used with optimizer hints. The QEP of the two queries are different.

Last but not least, I have provided the fix patch above. What do you mean by "a fix can be very, very simple"? If you have found the fix is simple, can't you verify this issue does exist in all versions of MySQL?
[4 Dec 2020 14:36] MySQL Verification Team
HI,

Please, clear out some things for us.

If we understood you correctly, using optimiser hints alone leads to the bug, irrespective of the join buffer size ??? This is puzzling, since in the primary report you mentioned explicitly setting different sizes for this buffer. 

Is that correct ??? Can you please clarify ???

Also, what we wrote is that IF this is a bug due to the join buffer size, it can be fixed easily, by setting a minimum version for it.

Last, but not least, if this is found to be a bug, it yet has to be decided which version would get a fix.

We are looking forward to your precise answers.
[4 Dec 2020 14:48] Hope Lee
I'm talking about the 'not_used_in_distinc' optimization and JOIN CACHE use instead of join_buffer_size. 

Well, I think MySQL 8.0.22 has added some checks to avoid this issue.

But can't you verify this issue on 8.0.13? It's very easy to reproduce with the data and SQL with optimizer hints I have provided.
[4 Dec 2020 15:01] Hope Lee
Yes, using optimiser hints alone leads to the bug, irrespective of the join buffer size. 

With different join buffer size, the results will be different wrong. It depends on when join buffer will get full, and that record being processed will miss.
[4 Dec 2020 15:24] MySQL Verification Team
Hi,

Thank you for informing us that 8.0.22 does not have that problem. The fact that bug exists in 8.0.13 is irrelevant.

We never fix old releases of some version, like (in this case) 8.0. When a new release is published, it never gets changed, nor does it get any bugs fixed. All the bugs that are fixed go into the next release. For example, if a bug is verified for 8.0.22 , it will be fixed in 8.0.23 or 8.0.24.

Not a bug.
[4 Dec 2020 15:33] Hope Lee
Actually, I think you need to verify the issues in the old release. If it doesn't exist in lateset version, you can close it. Because there are so many users using the old versions. They may have encountered the same issue. And then when they come to bugs' home, they can learn about the verified issue.