Diverging results in with mrr_sort_keys=ON|OFF and join_cache_level=5

[Philip Stoev]

The following query

SELECT table2.pk , table1.col_int_key
FROM t2 AS table1 JOIN
( t1 AS table2 JOIN t2 AS table3 ON table3.col_varchar_nokey = table2.col_varchar_key )
 ON table3.pk > table2.col_varchar_nokey
ORDER BY table1.pk ;

returns less rows with mrr_sort_keys=OFF in maria-5.3-mwl128-dsmrr-cpk and different rows in maria-5.3-dsmrr-cpk . engine_condition_pushdown can be OFF, so it is not a duplicate of bug #670417

[Philip Stoev (pstoev-askmonty)]

Test case:

--source include/have_innodb.inc

SET SESSION optimizer_switch='index_condition_pushdown=off';
SET SESSION join_cache_level=5;
SET SESSION join_buffer_size=1;
SET SESSION mrr_buffer_size=100000;

--disable_warnings
DROP TABLE /*! IF EXISTS */ t1;
DROP TABLE /*! IF EXISTS */ t2;
--enable_warnings

CREATE TABLE t1 (
  pk int(11) NOT NULL AUTO_INCREMENT,
  col_int_key int(11) NOT NULL,
  col_varchar_key varchar(1) NOT NULL,
  col_varchar_nokey varchar(1) NOT NULL,
  PRIMARY KEY (pk),
  KEY col_int_key (col_int_key),
  KEY col_varchar_key (col_varchar_key,col_int_key)
) ENGINE=InnoDB AUTO_INCREMENT=30 DEFAULT CHARSET=latin1;
INSERT INTO t1 VALUES (10,8,'v','v'),(11,8,'f','f'),(12,5,'v','v'),(13,8,'s','s'),(14,8,'a','a'),(15,6,'p','p'),(16,7,'z','z'),(17,2,'a','a'),(18,5,'h','h'),(19,7,'h','h'),(20,2,'v','v'),(21,9,'v','v'),(22,142,'b','b'),(23,3,'y','y'),(24,0,'v','v'),(25,3,'m','m'),(26,5,'z','z'),(27,9,'n','n'),(28,1,'d','d'),(29,107,'a','a');
CREATE TABLE t2 (
  pk int(11) NOT NULL AUTO_INCREMENT,
  col_int_key int(11) NOT NULL,
  col_varchar_key varchar(1) NOT NULL,
  col_varchar_nokey varchar(1) NOT NULL,
  PRIMARY KEY (pk),
  KEY col_int_key (col_int_key),
  KEY col_varchar_key (col_varchar_key,col_int_key)
) ENGINE=InnoDB AUTO_INCREMENT=21 DEFAULT CHARSET=latin1;
INSERT INTO t2 VALUES (1,9,'x','x'),(2,5,'g','g'),(3,1,'o','o'),(4,0,'g','g'),(5,1,'v','v'),(6,190,'m','m'),(7,6,'x','x'),(8,3,'c','c'),(9,4,'z','z'),(10,3,'i','i'),(11,186,'x','x'),(12,1,'g','g'),(13,8,'q','q'),(14,226,'m','m'),(15,133,'p','p'),(16,6,'e','e'),(17,3,'t','t'),(18,8,'j','j'),(19,5,'h','h'),(20,7,'w','w');

SET optimizer_switch='mrr_sort_keys=on';

EXPLAIN SELECT table2.pk , table1.col_int_key
FROM t2 AS table1 JOIN
( t1 AS table2 JOIN t2 AS table3 ON table3.col_varchar_nokey = table2.col_varchar_key )
 ON table3.pk > table2.col_varchar_nokey
ORDER BY table1.pk ;

CREATE TABLE p1 AS SELECT table2.pk , table1.col_int_key
FROM t2 AS table1 JOIN
( t1 AS table2 JOIN t2 AS table3 ON table3.col_varchar_nokey = table2.col_varchar_key )
 ON table3.pk > table2.col_varchar_nokey
ORDER BY table1.pk ;

SET optimizer_switch='mrr_sort_keys=off';

EXPLAIN SELECT table2.pk , table1.col_int_key
FROM t2 AS table1 JOIN
( t1 AS table2 JOIN t2 AS table3 ON table3.col_varchar_nokey = table2.col_varchar_key )
 ON table3.pk > table2.col_varchar_nokey
ORDER BY table1.pk ;

CREATE TABLE p2 AS SELECT table2.pk , table1.col_int_key
FROM t2 AS table1 JOIN
( t1 AS table2 JOIN t2 AS table3 ON table3.col_varchar_nokey = table2.col_varchar_key )
 ON table3.pk > table2.col_varchar_nokey
ORDER BY table1.pk ;

--let $diff_table_1 = test.p1
--let $diff_table_2 = test.p2
--source include/diff_tables.inc

[Sergey Petrunia (sergefp)]

The test query is a 3-way join, attempts to reduce it to two-way join by pre-joining two first tables from the join order were not successful - the result difference goes away for 2-way joins.

[Sergey Petrunia (sergefp)]

A testcase that's easier to work with:

MariaDB [f1]>SELECT count(*), sum(table1.col_int_key*table2.pk) FROM t2 AS table1, t1 AS table2, t2 AS table3 WHERE table3.col_varchar_nokey = table2.col_varchar_key AND table3.pk > table2.col_varchar_nokey ;
+----------+-----------------------------------+
| count(*) | sum(table1.col_int_key*table2.pk) |
+----------+-----------------------------------+
| 240 | 185955 |
+----------+-----------------------------------+
1 row in set (0.01 sec)

MariaDB [f1]> set join_cache_level=6;
Query OK, 0 rows affected (0.00 sec)

MariaDB [f1]> set join_buffer_size=1500;
Query OK, 0 rows affected (0.00 sec)

MariaDB [f1]> SELECT count(*), sum(table1.col_int_key*table2.pk) FROM t2 AS table1, t1 AS table2, t2 AS table3 WHERE table3.col_varchar_nokey = table2.col_varchar_key AND table3.pk > table2.col_varchar_nokey ;
+----------+-----------------------------------+
| count(*) | sum(table1.col_int_key*table2.pk) |
+----------+-----------------------------------+
| 240 | 187114 |
+----------+-----------------------------------+
1 row in set (0.18 sec)

The problem can't be repeated with bigger join_buffer_size. The problem can be repeated with smaller join_buffer_size

[Sergey Petrunia (sergefp)]

Figured out the problem. The problem shows up when
- DS-MRR implementation uses both ordered key reading and rndpos()-based full record retrieval,
- the table is an innodb table with user-visible primary key. This is needed so that handler->position() call gets the rowid value from the last record we've read.

When the above is satisfied, we can have the following scenario:
- Mrr_ordered_index_reader fills the buffer, sorts it, starts to return rows.
- At some point where Mrr_ordered_index_reader is in the middle of scanning the list of ranges with identical key, the rowid buffer gets full
- Mrr_ordered_index_reader's scan is interrupted, Mrr_ordered_rndpos_reader starts making rnd_pos() calls and returning records. This process causes table->record[0] to be rewritten.
- Mrr_ordered_rndpos_reader exhausts the supply of rowids and turns to Mrr_ordered_index_reader to get more.
- Mrr_ordered_index_reader, assuming that table->record[0] still has the index record it was scanning, returns the next range_id.

=> Mrr_ordered_rndpos_reader gets a range_id with rowid that does not match the range_id.

[Sergey Petrunia (sergefp)]

An apparent solution is to save/restore index tuple when we're interrupting/resuming the sequence of Mrr_ordered_index_reader::get_next() calls.