Assertion `0' failed in QUICK_INDEX_SORT_SELECT::need_sorted_output() with index_merge+index_merge_sort_union+loosescan+semijoin, IN subquery, InnoDB

[Elena Stepanova]

Query:
SELECT * FROM t1 WHERE b IN (
  SELECT d FROM t2, t1
  WHERE a = d AND ( pk < 2 OR d = 'z' )
);

mysqld: opt_range.h:584: virtual void QUICK_INDEX_SORT_SELECT::need_sorted_output(): Assertion `0' failed.
120323 3:32:15 [ERROR] mysqld got signal 6 ;

#8 0xb748e014 in __assert_fail () from /lib/libc.so.6
#9 0x0841bb69 in QUICK_INDEX_SORT_SELECT::need_sorted_output (this=0x9ee6f38) at opt_range.h:584
#10 0x084261f4 in setup_semijoin_dups_elimination (join=0x9eebfc8, options=0, no_jbuf_after=3)
    at opt_subselect.cc:4110
#11 0x0836856a in make_join_readinfo (join=0x9eebfc8, options=0, no_jbuf_after=3)
    at sql_select.cc:9494
#12 0x0835487a in JOIN::optimize (this=0x9eebfc8) at sql_select.cc:1536
#13 0x083591c8 in mysql_select (thd=0x9e687f0, rref_pointer_array=0x9e6a38c, tables=0x9ed6e48,
    wild_num=1, fields=..., conds=0x9ed8380, og_num=0, order=0x0, group=0x0, having=0x0,
    proc_param=0x0, select_options=2147764736, result=0x9ed8528, unit=0x9e69f70,
    select_lex=0x9e6a250) at sql_select.cc:2938
#14 0x08350ecb in handle_select (thd=0x9e687f0, lex=0x9e69f14, result=0x9ed8528,
    setup_tables_done_option=0) at sql_select.cc:285
#15 0x082ebf4d in execute_sqlcom_select (thd=0x9e687f0, all_tables=0x9ed6e48) at sql_parse.cc:5151
#16 0x082e3329 in mysql_execute_command (thd=0x9e687f0) at sql_parse.cc:2284
#17 0x082ee588 in mysql_parse (thd=0x9e687f0,
    rawbuf=0x9ed6c70 "SELECT * FROM t1 WHERE b IN ( \nSELECT d FROM t2, t1 \nWHERE a = d AND ( pk < 2 OR d = 'z' )\n)", length=92, found_semicolon=0x9d744234) at sql_parse.cc:6152
#18 0x082e0f69 in dispatch_command (command=COM_QUERY, thd=0x9e687f0,
    packet=0x9f06131 "SELECT * FROM t1 WHERE b IN ( \nSELECT d FROM t2, t1 \nWHERE a = d AND ( pk < 2 OR d = 'z' )\n)", packet_length=92) at sql_parse.cc:1228
#19 0x082e0413 in do_command (thd=0x9e687f0) at sql_parse.cc:923
#20 0x082dd399 in handle_one_connection (arg=0x9e687f0) at sql_connect.cc:1193
#21 0xb771cb25 in start_thread () from /lib/libpthread.so.0

bzr version-info
revision-id: <email address hidden>
date: 2012-03-22 13:23:55 +0100
build-date: 2012-03-23 03:35:16 +0400
revno: 3466

This particular test case passes on MariaDB 5.5 (revno 3345), but I have a bigger one which fails with the same assertion.

Minimal optimizer_switch: index_merge=on,index_merge_sort_union=on,loosescan=on,semijoin=on
Full optimizer_switch (default): index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_merge_sort_intersection=off,index_condition_pushdown=on,derived_merge=on,derived_with_keys=on,firstmatch=on,loosescan=on,materialization=on,in_to_exists=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,mrr=off,mrr_cost_based=off,mrr_sort_keys=off,outer_join_with_cache=on,semijoin_with_cache=on,join_cache_incremental=on,join_cache_hashed=on,join_cache_bka=on,optimize_join_buffer_size=off,table_elimination=on

EXPLAIN also fails.

Test case:

--source include/have_innodb.inc
SET optimizer_switch = 'index_merge=on,index_merge_sort_union=on,loosescan=on,semijoin=on';

CREATE TABLE t1 (
  a INT, b VARCHAR(1), c INT,
  KEY(a), KEY(b)
) ENGINE=InnoDB;

INSERT INTO t1 VALUES
(1,'v',9),(2,'v',8),(3,'c',7),(4,'m',6),(5,'x',5),
(6,'i',4),(7,'e',3),(8,'p',2),(9,'s',1),(10,'j',9),
(11,'z',8),(12,'c',7),(13,'a',6),(14,'q',5),(15,'y',4),
(16,'n',3),(17,'r',2),(18,'v',1),(19,'p',0);

CREATE TABLE t2 (
  pk INT, d VARCHAR(1), e INT,
  PRIMARY KEY(pk), KEY(d,e)
) ENGINE=InnoDB;

INSERT INTO t2 VALUES
(1,'x',1),(2,'d',2),(3,'r',3),(4,'f',4),(5,'y',5),
(6,'u',6),(7,'m',7),(8,'k',8),(9,'o',9),(10,'w',1),
(11,'m',2),(12,'q',3),(13,'m',4),(14,'d',5),
(15,'g',6),(16,'x',7),(17,'f',8);

SELECT * FROM t1 WHERE b IN (
  SELECT d FROM t2, t1
  WHERE a = d AND ( pk < 2 OR d = 'z' )
);

# End of test case

[Sergey Petrunia (sergefp)]

The failure scenario is as follows:

> best_access_path(idx=0, table=t2)

 > considers ref access
  - start considering ref access and LooseScan
  - ref access is not possible (cost=DBL_MAX)
  - LooseScan (as full index scan) is possible (cost=1.025)

 > then consider full scan/range accesses
  - find that quick access is possible
  - however it's not applicable for loose scan.
  - still, quick select is chosen.
< best_access_path
...

> advance_sj_state
  (choses the above loose scan over full index scan)
<

The problem is that subsequent code assumes that tab->type==JT_ALL &&
tab->quick!=NULL => use quick select for retrieval.

And eventually we crash with an assert because QUICK_SORT_INTERSECT_SELECT is
unable to produce records in order (that's true).

[Sergey Petrunia (sergefp)]

Have a patch, need review.