[MDEV-8289] Semijoin inflates number of rows in query result Created: 2015-06-09  Updated: 2015-08-18  Resolved: 2015-08-18

Status: Closed
Project: MariaDB Server
Component/s: Optimizer
Affects Version/s: 5.3.12, 5.5, 10.0, 10.1
Fix Version/s: 10.0.22

Type: Bug Priority: Major
Reporter: Mateusz Michalowski Assignee: Sergei Petrunia
Resolution: Fixed Votes: 0
Labels: None
Environment:

mysql Ver 15.1 Distrib 10.0.18-MariaDB, for osx10.10 (x86_64) using readline 5.1
MariaDB installed with homebrew

Attachments: File semijoin.result     File semijoin.test    
Sprint: 5.5.45, 10.1.7-1

 Description   

Turning semijoin optimization on/off can affect number of rows returned by a query.

Enabling semojoin optimisation can cause a query like that:

SELECT * FROM manufacturers WHERE (...);

to return more rows than:

SELECT * FROM manufacturers;

Please, find a full test case setup attached.

Just to sum up the test case:
It executes the query below: (manufacturers table size: 2)

SELECT * FROM manufacturers WHERE manufacturers.id IN (             
  SELECT ships.manufacturers_id FROM owners JOIN ships ON owners.id = ships.owners_id WHERE owners.id = 1
 
);

Then the query returns:

  • 2 rows ( SET optimizer_switch='semijoin=off'; )
  • 3 rows ( SET optimizer_switch='semijoin=on'; )

 Comments   
Comment by Elena Stepanova [ 2015-06-10 ]

Thanks for the report and the test case.

Comment by Sergei Petrunia [ 2015-08-04 ]

EXPLAIN:

+------+-------------+---------------+--------+------------------------------+------------+---------+------------------------+------+----------------------------------+
 
| id   | select_type | table         | type   | possible_keys                | key        | key_len | ref                    | rows | Extra                            |
 
+------+-------------+---------------+--------+------------------------------+------------+---------+------------------------+------+----------------------------------+
 
|    1 | PRIMARY     | owners        | system | PRIMARY                      | NULL       | NULL    | NULL                   |    1 |                                  |
 
|    1 | PRIMARY     | ships         | range  | owners_idx,manufacturers_idx | owners_idx | 4       | NULL                   |    3 | Using index condition; LooseScan |
 
|    1 | PRIMARY     | manufacturers | eq_ref | PRIMARY                      | PRIMARY    | 4       | ships.manufacturers_id |    1 | Using index                      |
 
+------+-------------+---------------+--------+------------------------------+------------+---------+------------------------+------+----------------------------------+

if I use optimizer_switch='loosescan=off' , I get the correct result. It seems, Loose Scan strategy is the cause of the problem.

Comment by Sergei Petrunia [ 2015-08-04 ]

Indeed, why does it use range over owners_idx with LooseScan. The subquery is

manufacturers.id IN ( SELECT ships.manufacturers_id ...)

and the query doesn't have an equality between manufacturers_id and owners_idx.

The query plan seems to be incorrect.

Comment by Sergei Petrunia [ 2015-08-05 ]

Debugging, I see the following to happen:

1. Join optimization is run. It chooses to use LooseScan for manufacturers table, the index is manufacturers_idx. Correct.
None of the keyparts is bound, so we will be doing a full table scan. tab->type=JT_ALL, there is no quick select.

2. We end up here:

 
(gdb) wher
 
  #0  SQL_SELECT::test_quick_select (this=0x7fff68022d50, thd=0x59ff350, keys_to_use=..., prev_tables=13835058055282163714, limit=18446744073709551615, force_quick_range=false, ordered_output=false) at /home/psergey/dev-git/10.0/sql/opt_range.cc:2994
 
  #1  0x00000000006b6fd6 in make_join_select (join=0x7fff68009ed8, select=0x7fff6801f970, cond=0x7fff6800ba28) at /home/psergey/dev-git/10.0/sql/sql_select.cc:9707
 
  #2  0x00000000006a092d in JOIN::optimize_inner (this=0x7fff68009ed8) at /home/psergey/dev-git/10.0/sql/sql_select.cc:1533
 
  #3  0x000000000069ebbe in JOIN::optimize (this=0x7fff68009ed8) at /home/psergey/dev-git/10.0/sql/sql_select.cc:1022
 
  #4  0x00000000006a6a53 in mysql_select (thd=0x59ff350, rref_pointer_array=0x5a03610, tables=0x7fff68005570, wild_num=1, fields=..., conds=0x7fff680095a0, og_num=0, order=0x0, group=0x0, having=0x0, proc_param=0x0, select_options=2147748612, result=0x7fff68009818, unit=0x5a02ca8, select_lex=0x5a03398) at /home/psergey/dev-git/10.0/sql/sql_select.cc:3294
 
  #5  0x00000000006d9a38 in mysql_explain_union (thd=0x59ff350, unit=0x5a02ca8, result=0x7fff68009818) at /home/psergey/dev-git/10.0/sql/sql_select.cc:24052
 
  #6  0x000000000066fe35 in execute_sqlcom_select (thd=0x59ff350, all_tables=0x7fff68005570) at /home/psergey/dev-git/10.0/sql/sql_parse.cc:5237
 
  #7  0x0000000000668021 in mysql_execute_command (thd=0x59ff350) at /home/psergey/dev-git/10.0/sql/sql_parse.cc:2562
 
  #8  0x0000000000672d58 in mysql_parse (thd=0x59ff350, rawbuf=0x7fff68005228 "explain SELECT * FROM manufacturers WHERE manufacturers.id IN (", ' ' <repeats 16 times>, "SELECT ships.manufacturers_id FROM owners JOIN ships ON owners.id = ships.owners_id WHERE owners.id = 1 )", length=184, parser_state=0x7ffff7f39520) at /home/psergey/dev-git/10.0/sql/sql_parse.cc:6531

Here, the code choses to switch to a quick select. It totally ignores the fact that LooseScan doesn't work for the index that the quick select is using.

Comment by Sergei Petrunia [ 2015-08-05 ]

The first reaction is to make the code in make_join_select to not invoke SQL_SELECT::test_quick_select when the table in question is used for LooseScan.

It is a bit difficult to do: At this point in execution, information about whether Loose Scan is used is only stored in JOIN::best_positions. (It is moved into JOIN_TAB by setup_semijoin_dups_elimination which is called by make_join_readinfo which is called by JOIN::optimize_inner after the call to make_join_select.

Comment by Sergei Petrunia [ 2015-08-05 ]

Having fixed that, I get this (incorrect) plan (and a wrong query result): 

+------+-------------+---------------+--------+------------------------------+---------+---------+--------------------------------+------+------------------------+
 
| id   | select_type | table         | type   | possible_keys                | key     | key_len | ref                            | rows | Extra                  |
 
+------+-------------+---------------+--------+------------------------------+---------+---------+--------------------------------+------+------------------------+
 
|    1 | PRIMARY     | owners        | system | PRIMARY                      | NULL    | NULL    | NULL                           |    1 |                        |
 
|    1 | PRIMARY     | ships         | ALL    | owners_idx,manufacturers_idx | NULL    | NULL    | NULL                           |    4 | Using where; LooseScan |
 
|    1 | PRIMARY     | manufacturers | eq_ref | PRIMARY                      | PRIMARY | 4       | testing.ships.manufacturers_id |    1 | Using index            |
 
+------+-------------+---------------+--------+------------------------------+---------+---------+--------------------------------+------+------------------------+

Comment by Sergei Petrunia [ 2015-08-05 ]

http://lists.askmonty.org/pipermail/commits/2015-August/008227.html.

elenst, I would need testing for this commit. The test should check semi-join subqueries for wrong query results and crashes.

Comment by Elena Stepanova [ 2015-08-17 ]

psergey,

I have not got any regressions from 10.0 to 10.0 + your patch. Please push.
I used 10.0 because that's what the patch said in branch nick. If you want separate tests on 5.5, please let me know.

Generated at Thu Feb 08 07:26:01 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.