[MDEV-8603] Wrong result (missing rows) with InnoDB, index_merge, AND and OR conditions - Jira

Details

Type: Bug
Status: Closed (View Workflow)
Priority: Major
Resolution: Fixed
Affects Version/s: 5.5(EOL), 10.0(EOL), 10.1(EOL)
Fix Version/s: 5.5.55
Component/s: Optimizer
Labels:
None

Sprint:
10.1.21

Description

Test case
--source include/have_innodb.inc

CREATE TABLE t1 (
id INT NOT NULL,
state VARCHAR(64),
capital VARCHAR(64),
UNIQUE KEY (id),
KEY (state),
KEY (capital)
) ENGINE=InnoDB;

INSERT INTO t1 VALUES
(1,'Arizona','Phoenix'),
(2,'Hawaii','Honolulu'),
(3,'Georgia','Atlanta'),
(4,'Florida','Tallahassee'),
(5,'Alaska','Juneau'),
(6,'Michigan','Lansing'),
(7,'Pennsylvania','Harrisburg'),
(8,'Virginia','Richmond')
;

SELECT * FROM t1 FORCE KEY (state,capital)
WHERE ( state = 'Alabama' OR state >= 'Colorado' ) AND id IS NOT NULL AND id != 9
OR ( capital >= 'Topeka' OR state = 'Kansas' ) AND state != 'Texas'
;

Actual result
MariaDB [test]> SELECT * FROM t1 FORCE KEY (state,capital)
-> WHERE ( state = 'Alabama' OR state >= 'Colorado' ) AND id IS NOT NULL AND id != 9
-> OR ( capital >= 'Topeka' OR state = 'Kansas' ) AND state != 'Texas'
-> ;
+----+----------+----------+
\| id \| state \| capital \|
+----+----------+----------+
\| 8 \| Virginia \| Richmond \|
+----+----------+----------+
1 row in set (0.00 sec)

Expected result
+----+--------------+-------------+
\| id \| state \| capital \|
+----+--------------+-------------+
\| 4 \| Florida \| Tallahassee \|
\| 3 \| Georgia \| Atlanta \|
\| 2 \| Hawaii \| Honolulu \|
\| 6 \| Michigan \| Lansing \|
\| 7 \| Pennsylvania \| Harrisburg \|
\| 8 \| Virginia \| Richmond \|
+----+--------------+-------------+
6 rows in set (0.00 sec)

Note: Apparently it started happening on 10.0 some time between 10.0.4 and 10.0.5; my search pointed at the merge 67e2e14627731082ea9c31392f34fc920aef86df, but it's not 100% certain.
Could not reproduce (with this test case) on 5.5.

Attachments

Activity

Ascending order - Click to sort in descending order

Sergei Petrunia added a comment - 2017-01-03 14:55

this looks a bit similar to ~~MDEV-10927~~. Varun, can you check if the patch is fixed by the fix for ~~MDEV-10927~~ (that is, repeatable before it and not repeatable after?)

Sergei Petrunia added a comment - 2017-01-03 14:55 this looks a bit similar to MDEV-10927 . Varun , can you check if the patch is fixed by the fix for MDEV-10927 (that is, repeatable before it and not repeatable after?)

Varun Gupta (Inactive) added a comment - 2017-01-05 00:42

#0 Unique::get (this=0x10c2dd2a0, table=0x10c2a6070) at /Users/varun/MariaDB/10.1/10.1/sql/uniques.cc:753
#1 0x00000001001c1a16 in read_keys_and_merge_scans (thd=0x10be529b0, head=0x10c2a6070, quick_selects=..., pk_quick_select=0x0, read_record=0x10c226b28,
intersection=false, filtered_scans=0x0, unique_ptr=0x10c226ac0) at /Users/varun/MariaDB/10.1/10.1/sql/opt_range.cc:10778
#2 0x00000001001c1cd7 in QUICK_INDEX_MERGE_SELECT::read_keys_and_merge (this=0x10c226a80) at /Users/varun/MariaDB/10.1/10.1/sql/opt_range.cc:10800
#3 0x00000001001aee33 in QUICK_INDEX_SORT_SELECT::reset (this=0x10c226a80) at /Users/varun/MariaDB/10.1/10.1/sql/opt_range.cc:1365
#4 0x0000000100358451 in join_init_read_record (tab=0x10c238560) at /Users/varun/MariaDB/10.1/10.1/sql/sql_select.cc:19209
#5 0x0000000100363717 in sub_select (join=0x10c235688, join_tab=0x10c238560, end_of_records=false)
at /Users/varun/MariaDB/10.1/10.1/sql/sql_select.cc:18301
#6 0x000000010034ce8e in do_select (join=0x10c235688, fields=0x10be56c10, table=0x0, procedure=0x0)
at /Users/varun/MariaDB/10.1/10.1/sql/sql_select.cc:17959
#7 0x000000010034beb8 in JOIN::exec_inner (this=0x10c235688) at /Users/varun/MariaDB/10.1/10.1/sql/sql_select.cc:3215
#8 0x0000000100349292 in JOIN::exec (this=0x10c235688) at /Users/varun/MariaDB/10.1/10.1/sql/sql_select.cc:2505
#9 0x0000000100330dc4 in mysql_select (thd=0x10be529b0, rref_pointer_array=0x10be56d70, tables=0x10c2336b0, wild_num=1, fields=..., conds=0x10c2354a8,
og_num=0, order=0x0, group=0x0, having=0x0, proc_param=0x0, select_options=2147748608, result=0x10c235668, unit=0x10be563f8, select_lex=0x10be56af8)
at /Users/varun/MariaDB/10.1/10.1/sql/sql_select.cc:3439
#10 0x000000010033071f in handle_select (thd=0x10be529b0, lex=0x10be56330, result=0x10c235668, setup_tables_done_option=0)
at /Users/varun/MariaDB/10.1/10.1/sql/sql_select.cc:372
#11 0x00000001002e87c5 in execute_sqlcom_select (thd=0x10be529b0, all_tables=0x10c2336b0) at /Users/varun/MariaDB/10.1/10.1/sql/sql_parse.cc:5899
#12 0x00000001002dcb71 in mysql_execute_command (thd=0x10be529b0) at /Users/varun/MariaDB/10.1/10.1/sql/sql_parse.cc:2971
#13 0x00000001002d9403 in mysql_parse (thd=0x10be529b0,
rawbuf=0x10c233308 "SELECT * FROM t1 FORCE KEY (state,capital) \nWHERE ( state = 'Alabama' OR state >= 'Colorado' ) AND id IS NOT NULL AND id != 9 OR ( capital >= 'Topeka' OR state = 'Kansas' ) AND state != 'Texas'", length=193, parser_state=0x700000abae70)
at /Users/varun/MariaDB/10.1/10.1/sql/sql_parse.cc:7322
#14 0x00000001002d4d25 in dispatch_command (command=COM_QUERY, thd=0x10be529b0, packet=0x109b5edf1 "", packet_length=194)
at /Users/varun/MariaDB/10.1/10.1/sql/sql_parse.cc:1488
#15 0x00000001002d7cc3 in do_command (thd=0x10be529b0) at /Users/varun/MariaDB/10.1/10.1/sql/sql_parse.cc:1109
#16 0x00000001004531b8 in do_handle_one_connection (thd_arg=0x10be529b0) at /Users/varun/MariaDB/10.1/10.1/sql/sql_connect.cc:1350
#17 0x0000000100452f3d in handle_one_connection (arg=0x10be529b0) at /Users/varun/MariaDB/10.1/10.1/sql/sql_connect.cc:1262
#18 0x00000001006d3975 in pfs_spawn_thread (arg=0x109bb7470) at /Users/varun/MariaDB/10.1/10.1/storage/perfschema/pfs.cc:1860
#19 0x00007fff94ca199d in _pthread_body () from /usr/lib/system/libsystem_pthread.dylib
#20 0x00007fff94ca191a in _pthread_start () from /usr/lib/system/libsystem_pthread.dylib
#21 0x00007fff94c9f351 in thread_start () from /usr/lib/system/libsystem_pthread.dylib
#22 0x0000000000000000 in ?? ()

Varun Gupta (Inactive) added a comment - 2017-01-05 00:42 #0 Unique::get (this=0x10c2dd2a0, table=0x10c2a6070) at /Users/varun/MariaDB/10.1/10.1/sql/uniques.cc:753 #1 0x00000001001c1a16 in read_keys_and_merge_scans (thd=0x10be529b0, head=0x10c2a6070, quick_selects=..., pk_quick_select=0x0, read_record=0x10c226b28, intersection=false, filtered_scans=0x0, unique_ptr=0x10c226ac0) at /Users/varun/MariaDB/10.1/10.1/sql/opt_range.cc:10778 #2 0x00000001001c1cd7 in QUICK_INDEX_MERGE_SELECT::read_keys_and_merge (this=0x10c226a80) at /Users/varun/MariaDB/10.1/10.1/sql/opt_range.cc:10800 #3 0x00000001001aee33 in QUICK_INDEX_SORT_SELECT::reset (this=0x10c226a80) at /Users/varun/MariaDB/10.1/10.1/sql/opt_range.cc:1365 #4 0x0000000100358451 in join_init_read_record (tab=0x10c238560) at /Users/varun/MariaDB/10.1/10.1/sql/sql_select.cc:19209 #5 0x0000000100363717 in sub_select (join=0x10c235688, join_tab=0x10c238560, end_of_records=false) at /Users/varun/MariaDB/10.1/10.1/sql/sql_select.cc:18301 #6 0x000000010034ce8e in do_select (join=0x10c235688, fields=0x10be56c10, table=0x0, procedure=0x0) at /Users/varun/MariaDB/10.1/10.1/sql/sql_select.cc:17959 #7 0x000000010034beb8 in JOIN::exec_inner (this=0x10c235688) at /Users/varun/MariaDB/10.1/10.1/sql/sql_select.cc:3215 #8 0x0000000100349292 in JOIN::exec (this=0x10c235688) at /Users/varun/MariaDB/10.1/10.1/sql/sql_select.cc:2505 #9 0x0000000100330dc4 in mysql_select (thd=0x10be529b0, rref_pointer_array=0x10be56d70, tables=0x10c2336b0, wild_num=1, fields=..., conds=0x10c2354a8, og_num=0, order=0x0, group=0x0, having=0x0, proc_param=0x0, select_options=2147748608, result=0x10c235668, unit=0x10be563f8, select_lex=0x10be56af8) at /Users/varun/MariaDB/10.1/10.1/sql/sql_select.cc:3439 #10 0x000000010033071f in handle_select (thd=0x10be529b0, lex=0x10be56330, result=0x10c235668, setup_tables_done_option=0) at /Users/varun/MariaDB/10.1/10.1/sql/sql_select.cc:372 #11 0x00000001002e87c5 in execute_sqlcom_select (thd=0x10be529b0, all_tables=0x10c2336b0) at /Users/varun/MariaDB/10.1/10.1/sql/sql_parse.cc:5899 #12 0x00000001002dcb71 in mysql_execute_command (thd=0x10be529b0) at /Users/varun/MariaDB/10.1/10.1/sql/sql_parse.cc:2971 #13 0x00000001002d9403 in mysql_parse (thd=0x10be529b0, rawbuf=0x10c233308 "SELECT * FROM t1 FORCE KEY (state,capital) \nWHERE ( state = 'Alabama' OR state >= 'Colorado' ) AND id IS NOT NULL AND id != 9 OR ( capital >= 'Topeka' OR state = 'Kansas' ) AND state != 'Texas'", length=193, parser_state=0x700000abae70) at /Users/varun/MariaDB/10.1/10.1/sql/sql_parse.cc:7322 #14 0x00000001002d4d25 in dispatch_command (command=COM_QUERY, thd=0x10be529b0, packet=0x109b5edf1 "", packet_length=194) at /Users/varun/MariaDB/10.1/10.1/sql/sql_parse.cc:1488 #15 0x00000001002d7cc3 in do_command (thd=0x10be529b0) at /Users/varun/MariaDB/10.1/10.1/sql/sql_parse.cc:1109 #16 0x00000001004531b8 in do_handle_one_connection (thd_arg=0x10be529b0) at /Users/varun/MariaDB/10.1/10.1/sql/sql_connect.cc:1350 #17 0x0000000100452f3d in handle_one_connection (arg=0x10be529b0) at /Users/varun/MariaDB/10.1/10.1/sql/sql_connect.cc:1262 #18 0x00000001006d3975 in pfs_spawn_thread (arg=0x109bb7470) at /Users/varun/MariaDB/10.1/10.1/storage/perfschema/pfs.cc:1860 #19 0x00007fff94ca199d in _pthread_body () from /usr/lib/system/libsystem_pthread.dylib #20 0x00007fff94ca191a in _pthread_start () from /usr/lib/system/libsystem_pthread.dylib #21 0x00007fff94c9f351 in thread_start () from /usr/lib/system/libsystem_pthread.dylib #22 0x0000000000000000 in ?? ()

Varun Gupta (Inactive) added a comment - 2017-01-06 17:12 - edited

The issue is that all the row ids are not getting added to the tree. The size of the tree is showing 1 instead of 8.
/*
Ok all rowids are in the Unique now. The next call will initialize
head->sort structure so it can be used to iterate through the rowids
sequence.
*/
result= unique->get(head);
(gdb)
11398 result= unique->get(head);
(gdb) p unique->tree.elements_in_tree
$1 = 1

Varun Gupta (Inactive) added a comment - 2017-01-06 17:12 - edited The issue is that all the row ids are not getting added to the tree. The size of the tree is showing 1 instead of 8. /* Ok all rowids are in the Unique now. The next call will initialize head->sort structure so it can be used to iterate through the rowids sequence. */ result= unique->get(head); (gdb) 11398 result= unique->get(head); (gdb) p unique->tree.elements_in_tree $1 = 1

Varun Gupta (Inactive) added a comment - 2017-01-10 13:02 - edited

{panel:title=My title}

mysqld.trace

T@7    : | | | | | | | | | | >print_quick

quick index_merge select

merged scans {

  quick range select, key capital, length: 67

    Topeka <= X

  quick range select, key state, length: 71

    Alabama <= X < Alabama/9

    Alabama/9 < X <= Alabama

    Kansas <= X <= Kansas

    Texas <= X

other_keys: 0x0:

T@7    : | | | | | | | | | | <print_quick

{panel}

Varun Gupta (Inactive) added a comment - 2017-01-10 13:02 - edited {panel:title=My title} mysqld.trace T @7 : | | | | | | | | | | >print_quick quick index_merge select merged scans { quick range select, key capital, length: 67 Topeka <= X quick range select, key state, length: 71 Alabama <= X < Alabama/ 9 Alabama/ 9 < X <= Alabama Kansas <= X <= Kansas Texas <= X } other_keys: 0x0 : T @7 : | | | | | | | | | | <print_quick {panel}

Varun Gupta (Inactive) added a comment - 2017-01-10 13:49 - edited

Lets take a row from the above query:
(id, state, capital)= ( 7 , Pennsylvania , Harrisburg)

The WHERE clause is:

 WHERE

( state = 'Alabama' OR state >= 'Colorado' ) AND id IS NOT NULL AND id != 9

OR

( capital >= 'Topeka' OR state = 'Kansas' ) AND state != 'Texas';

( state = 'Alabama' OR state >= 'Colorado' ) AND id IS NOT NULL AND id != 9`=TRUE

( capital >= 'Topeka' OR state = 'Kansas' ) AND state != 'Texas'` = TRUE

(but it doesn't matter because the first line evaluated to TRUE already)

—

 T@7    : | | | | | | | | | | >print_quick

quick index_merge select

merged scans {

  quick range select, key capital, length: 67

    Topeka <= X

  quick range select, key state, length: 71

    Alabama <= X < Alabama/9

    Alabama/9 < X <= Alabama

    Kansas <= X <= Kansas

    Texas <= X

other_keys: 0x0:

T@7    : | | | | | | | | | | <print_quick

(id, state, capital)= ( 7 , Pennsylvania , Harrisburg)

quick range select, key capital, length: 67
Topeka <= X

^ this scan will not read the row with city="Harrisburg"

looking at the second scan

Kansas <= X <= Kansas
// Pennsylvania should be here
Texas <= X

^ this scan will also not read the row with state=Pennsylvania

Varun Gupta (Inactive) added a comment - 2017-01-10 13:49 - edited Lets take a row from the above query: (id, state, capital)= ( 7 , Pennsylvania , Harrisburg) The WHERE clause is: WHERE ( state = 'Alabama' OR state >= 'Colorado' ) AND id IS NOT NULL AND id != 9 OR ( capital >= 'Topeka' OR state = 'Kansas' ) AND state != 'Texas' ; ( state = 'Alabama' OR state >= 'Colorado' ) AND id IS NOT NULL AND id != 9`=TRUE ( capital >= 'Topeka' OR state = 'Kansas' ) AND state != 'Texas'` = TRUE (but it doesn't matter because the first line evaluated to TRUE already) — T @7 : | | | | | | | | | | >print_quick quick index_merge select merged scans { quick range select, key capital, length: 67 Topeka <= X quick range select, key state, length: 71 Alabama <= X < Alabama/ 9 Alabama/ 9 < X <= Alabama Kansas <= X <= Kansas Texas <= X } other_keys: 0x0 : T @7 : | | | | | | | | | | <print_quick (id, state, capital)= ( 7 , Pennsylvania , Harrisburg) quick range select, key capital, length: 67 Topeka <= X ^ this scan will not read the row with city="Harrisburg" looking at the second scan Kansas <= X <= Kansas // Pennsylvania should be here Texas <= X ^ this scan will also not read the row with state=Pennsylvania

Igor Babaev (Inactive) added a comment - 2017-01-17 18:09

Sergey,
I've taken the bug because I investigated it and found a fix.

Igor Babaev (Inactive) added a comment - 2017-01-17 18:09 Sergey, I've taken the bug because I investigated it and found a fix.

Igor Babaev (Inactive) added a comment - 2017-01-17 19:24 - edited

This is a 5.5 bug (actually a 5.3 bug). It can be reproduced in 5.5 with the following test case:

CREATE TABLE t1 (

  id INT NOT NULL,

  state VARCHAR(64),

  capital VARCHAR(64),

  UNIQUE KEY (id),

  KEY state (state,id),

  KEY capital (capital, id)

) ENGINE=MyISAM;

INSERT INTO t1 VALUES

  (1,'Arizona','Phoenix'),

  (2,'Hawaii','Honolulu'),

  (3,'Georgia','Atlanta'),

  (4,'Florida','Tallahassee'),

  (5,'Alaska','Juneau'),

  (6,'Michigan','Lansing'),

  (7,'Pennsylvania','Harrisburg'),

  (8,'Virginia','Richmond')

SELECT * FROM t1 FORCE KEY (state,capital)

WHERE ( state = 'Alabama' OR state >= 'Colorado' ) AND id != 9

   OR ( capital >= 'Topeka' OR state = 'Kansas' ) AND state != 'Texas';

For this test case we have:

MariaDB [test]> SELECT * FROM t1 FORCE KEY (state,capital)

    -> WHERE ( state = 'Alabama' OR state >= 'Colorado' ) AND id != 9

    ->    OR ( capital >= 'Topeka' OR state = 'Kansas' ) AND state != 'Texas';

+----+----------+----------+

| id | state    | capital  |

+----+----------+----------+

|  8 | Virginia | Richmond |

+----+----------+----------+

The problem is that the range optimizer builds here an invalid index merge: the scan for the index 'state' contains wrong ranges.
As the cost of this invalid index merge is the cheapest the optimizer chooses it . Following it the server returns wrong result set.

Igor Babaev (Inactive) added a comment - 2017-01-17 19:24 - edited This is a 5.5 bug (actually a 5.3 bug). It can be reproduced in 5.5 with the following test case: CREATE TABLE t1 ( id INT NOT NULL, state VARCHAR(64), capital VARCHAR(64), UNIQUE KEY (id), KEY state (state,id), KEY capital (capital, id) ) ENGINE=MyISAM; INSERT INTO t1 VALUES (1,'Arizona','Phoenix'), (2,'Hawaii','Honolulu'), (3,'Georgia','Atlanta'), (4,'Florida','Tallahassee'), (5,'Alaska','Juneau'), (6,'Michigan','Lansing'), (7,'Pennsylvania','Harrisburg'), (8,'Virginia','Richmond') ; SELECT * FROM t1 FORCE KEY (state,capital) WHERE ( state = 'Alabama' OR state >= 'Colorado' ) AND id != 9 OR ( capital >= 'Topeka' OR state = 'Kansas' ) AND state != 'Texas'; For this test case we have: MariaDB [test]> SELECT * FROM t1 FORCE KEY (state,capital) -> WHERE ( state = 'Alabama' OR state >= 'Colorado' ) AND id != 9 -> OR ( capital >= 'Topeka' OR state = 'Kansas' ) AND state != 'Texas'; +----+----------+----------+ | id | state | capital | +----+----------+----------+ | 8 | Virginia | Richmond | +----+----------+----------+ The problem is that the range optimizer builds here an invalid index merge: the scan for the index 'state' contains wrong ranges. As the cost of this invalid index merge is the cheapest the optimizer chooses it . Following it the server returns wrong result set.

Igor Babaev (Inactive) added a comment - 2017-01-19 05:10

The fix for this bug was pushed into the 5.5 tree.
The fix should be applied upstream as it is (to 10.0, 10.1, 10.2)

Igor Babaev (Inactive) added a comment - 2017-01-19 05:10 The fix for this bug was pushed into the 5.5 tree. The fix should be applied upstream as it is (to 10.0, 10.1, 10.2)

People

Assignee:: Igor Babaev (Inactive)

Reporter:: Elena Stepanova

Votes:: 0 Vote for this issue

Watchers:: 5 Start watching this issue

Dates

Created:: 2015-08-12 13:34

Updated:: 2017-01-19 05:10

Resolved:: 2017-01-19 05:10

Git Integration

Error rendering 'com.xiplink.jira.git.jira_git_plugin:git-issue-webpanel'. Please contact your Jira administrators.

MariaDB Server