Merge lp:~akopytov/percona-server/bug832528 into lp:percona-server/5.1

[Alexey Kopytov]

Backport of the fix for MySQL bug #53761 to 5.1. There is no test case, because:

1. The bug can only be triggered on a fairly large dataset (verified the fix manually on customer's data dump).
2. The original fix did not contain a test case.

[Alexey Kopytov (akopytov)]

http://jenkins.percona.com/view/Percona%20Server%205.1/job/percona-server-5.1-param/126/

[Yasufumi Kinoshita (yasufumi-kinoshita)]

I think no conflict with other XtraDB patches.

review: Approve

=== added file 'patches/bug53761.patch'
--- patches/bug53761.patch	1970-01-01 00:00:00 +0000
+++ patches/bug53761.patch	2011-08-25 09:13:51 +0000
@@ -0,0 +1,409 @@
+# name       : bug53761.patch
+# maintainer : Alexey
+#
+# Backport of the fix for MySQL bug #53761 to 5.1
+#
+--- a/storage/innodb_plugin/btr/btr0cur.c
++++ b/storage/innodb_plugin/btr/btr0cur.c
+@@ -3117,6 +3117,7 @@
+ {
+ 	btr_path_t*	slot;
+ 	rec_t*		rec;
++	page_t*		page;
+ 
+ 	ut_a(cursor->path_arr);
+ 
+@@ -3139,8 +3140,155 @@
+ 
+ 	slot = cursor->path_arr + (root_height - height);
+ 
++	page = page_align(rec);
++
+ 	slot->nth_rec = page_rec_get_n_recs_before(rec);
+-	slot->n_recs = page_get_n_recs(page_align(rec));
++	slot->n_recs = page_get_n_recs(page);
++	slot->page_no = page_get_page_no(page);
++	slot->page_level = btr_page_get_level_low(page);
++}
++
++/*******************************************************************//**
++Estimate the number of rows between slot1 and slot2 for any level on a
++B-tree. This function starts from slot1->page and reads a few pages to
++the right, counting their records. If we reach slot2->page quickly then
++we know exactly how many records there are between slot1 and slot2 and
++we set is_n_rows_exact to TRUE. If we cannot reach slot2->page quickly
++then we calculate the average number of records in the pages scanned
++so far and assume that all pages that we did not scan up to slot2->page
++contain the same number of records, then we multiply that average to
++the number of pages between slot1->page and slot2->page (which is
++n_rows_on_prev_level). In this case we set is_n_rows_exact to FALSE.
++@return	number of rows (exact or estimated) */
++static
++ib_int64_t
++btr_estimate_n_rows_in_range_on_level(
++/*==================================*/
++	dict_index_t*	index,			/*!< in: index */
++	btr_path_t*	slot1,			/*!< in: left border */
++	btr_path_t*	slot2,			/*!< in: right border */
++	ib_int64_t	n_rows_on_prev_level,	/*!< in: number of rows
++						on the previous level for the
++						same descend paths; used to
++						determine the numbe of pages
++						on this level */
++	ibool*		is_n_rows_exact)	/*!< out: TRUE if the returned
++						value is exact i.e. not an
++						estimation */
++{
++	ulint		space;
++	ib_int64_t	n_rows;
++	ulint		n_pages_read;
++	ulint		page_no;
++	ulint		zip_size;
++	ulint		level;
++
++	space = dict_index_get_space(index);
++
++	n_rows = 0;
++	n_pages_read = 0;
++
++	/* Assume by default that we will scan all pages between
++	slot1->page_no and slot2->page_no */
++	*is_n_rows_exact = TRUE;
++
++	/* add records from slot1->page_no which are to the right of
++	the record which serves as a left border of the range, if any */
++	if (slot1->nth_rec < slot1->n_recs) {
++		n_rows += slot1->n_recs - slot1->nth_rec;
++	}
++
++	/* add records from slot2->page_no which are to the left of
++	the record which servers as a right border of the range, if any */
++	if (slot2->nth_rec > 1) {
++		n_rows += slot2->nth_rec - 1;
++	}
++
++	/* count the records in the pages between slot1->page_no and
++	slot2->page_no (non inclusive), if any */
++
++	zip_size = fil_space_get_zip_size(space);
++
++	/* Do not read more than this number of pages in order not to hurt
++	performance with this code which is just an estimation. If we read
++	this many pages before reaching slot2->page_no then we estimate the
++	average from the pages scanned so far */
++	#define N_PAGES_READ_LIMIT	10
++
++	page_no = slot1->page_no;
++	level = slot1->page_level;
++
++	do {
++		mtr_t		mtr;
++		page_t*		page;
++		buf_block_t*	block;
++
++		mtr_start(&mtr);
++
++		/* fetch the page */
++		block = buf_page_get(space, zip_size, page_no, RW_S_LATCH,
++				     &mtr);
++
++		page = buf_block_get_frame(block);
++
++		/* It is possible that the tree has been reorganized in the
++		meantime and this is a different page. If this happens the
++		calculated estimate will be bogus, which is not fatal as
++		this is only an estimate. We are sure that a page with
++		page_no exists because InnoDB never frees pages, only
++		reuses them. */
++		if (fil_page_get_type(page) != FIL_PAGE_INDEX
++		    || ut_dulint_cmp(btr_page_get_index_id(page), index->id)
++		    || btr_page_get_level_low(page) != level) {
++
++			/* The page got reused for something else */
++			goto inexact;
++		}
++
++		n_pages_read++;
++
++		if (page_no != slot1->page_no) {
++			/* Do not count the records on slot1->page_no,
++			we already counted them before this loop. */
++			n_rows += page_get_n_recs(page);
++		}
++
++		page_no = btr_page_get_next(page, &mtr);
++
++		mtr_commit(&mtr);
++
++		if (n_pages_read == N_PAGES_READ_LIMIT
++		    || page_no == FIL_NULL) {
++			/* Either we read too many pages or
++			we reached the end of the level without passing
++			through slot2->page_no, the tree must have changed
++			in the meantime */
++			goto inexact;
++		}
++
++	} while (page_no != slot2->page_no);
++
++	return(n_rows);
++
++inexact:
++
++	*is_n_rows_exact = FALSE;
++
++	/* We did interrupt before reaching slot2->page */
++
++	if (n_pages_read > 0) {
++		/* The number of pages on this level is
++		n_rows_on_prev_level, multiply it by the
++		average number of recs per page so far */
++		n_rows = n_rows_on_prev_level
++			* n_rows / n_pages_read;
++	} else {
++		/* The tree changed before we could even
++		start with slot1->page_no */
++		n_rows = 10;
++	}
++
++	return(n_rows);
+ }
+ 
+ /*******************************************************************//**
+@@ -3165,6 +3313,7 @@
+ 	ibool		diverged_lot;
+ 	ulint		divergence_level;
+ 	ib_int64_t	n_rows;
++	ibool		is_n_rows_exact;
+ 	ulint		i;
+ 	mtr_t		mtr;
+ 
+@@ -3207,6 +3356,7 @@
+ 	/* We have the path information for the range in path1 and path2 */
+ 
+ 	n_rows = 1;
++	is_n_rows_exact = TRUE;
+ 	diverged = FALSE;	    /* This becomes true when the path is not
+ 				    the same any more */
+ 	diverged_lot = FALSE;	    /* This becomes true when the paths are
+@@ -3222,7 +3372,7 @@
+ 		if (slot1->nth_rec == ULINT_UNDEFINED
+ 		    || slot2->nth_rec == ULINT_UNDEFINED) {
+ 
+-			if (i > divergence_level + 1) {
++			if (i > divergence_level + 1 && !is_n_rows_exact) {
+ 				/* In trees whose height is > 1 our algorithm
+ 				tends to underestimate: multiply the estimate
+ 				by 2: */
+@@ -3234,7 +3384,9 @@
+ 			to over 1 / 2 of the estimated rows in the whole
+ 			table */
+ 
+-			if (n_rows > index->table->stat_n_rows / 2) {
++			if (n_rows > index->table->stat_n_rows / 2
++			    && !is_n_rows_exact) {
++
+ 				n_rows = index->table->stat_n_rows / 2;
+ 
+ 				/* If there are just 0 or 1 rows in the table,
+@@ -3260,10 +3412,15 @@
+ 					divergence_level = i;
+ 				}
+ 			} else {
+-				/* Maybe the tree has changed between
+-				searches */
+-
+-				return(10);
++				/* It is possible that
++				slot1->nth_rec >= slot2->nth_rec
++				if, for example, we have a single page
++				tree which contains (inf, 5, 6, supr)
++				and we select where x > 20 and x < 30;
++				in this case slot1->nth_rec will point
++				to the supr record and slot2->nth_rec
++				will point to 6 */
++				n_rows = 0;
+ 			}
+ 
+ 		} else if (diverged && !diverged_lot) {
+@@ -3287,8 +3444,9 @@
+ 			}
+ 		} else if (diverged_lot) {
+ 
+-			n_rows = (n_rows * (slot1->n_recs + slot2->n_recs))
+-				/ 2;
++			n_rows = btr_estimate_n_rows_in_range_on_level(
++				index, slot1, slot2, n_rows,
++				&is_n_rows_exact);
+ 		}
+ 	}
+ }
+--- a/storage/innodb_plugin/include/btr0cur.h
++++ b/storage/innodb_plugin/include/btr0cur.h
+@@ -652,6 +652,11 @@
+ 				order); value ULINT_UNDEFINED
+ 				denotes array end */
+ 	ulint	n_recs;		/*!< number of records on the page */
++	ulint	page_no;	/*!< no of the page containing the record */
++	ulint	page_level;	/*!< level of the page, if later we fetch
++				the page under page_no and it is no different
++				level then we know that the tree has been
++				reorganized */
+ };
+ 
+ #define BTR_PATH_ARRAY_N_SLOTS	250	/*!< size of path array (in slots) */
+--- a/mysql-test/suite/innodb_plugin/r/innodb_gis.result
++++ b/mysql-test/suite/innodb_plugin/r/innodb_gis.result
+@@ -572,7 +572,7 @@
+ EXPLAIN 
+ SELECT COUNT(*) FROM t2 WHERE p=POINTFROMTEXT('POINT(1 2)');
+ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+-1	SIMPLE	t2	ref	p	p	28	const	1	Using where
++1	SIMPLE	t2	ref	p	p	28	const	2	Using where
+ SELECT COUNT(*) FROM t2 WHERE p=POINTFROMTEXT('POINT(1 2)');
+ COUNT(*)
+ 2
+--- a/mysql-test/suite/innodb_plugin/r/innodb_mysql.result
++++ b/mysql-test/suite/innodb_plugin/r/innodb_mysql.result
+@@ -889,13 +889,13 @@
+ id	1
+ select_type	SIMPLE
+ table	t1
+-type	range
++type	index
+ possible_keys	bkey
+-key	bkey
+-key_len	5
++key	PRIMARY
++key_len	4
+ ref	NULL
+-rows	16
+-Extra	Using where; Using index; Using filesort
++rows	32
++Extra	Using where
+ SELECT * FROM t1 WHERE b BETWEEN 1 AND 2 ORDER BY a;
+ a	b
+ 1	2
+@@ -934,12 +934,12 @@
+ id	1
+ select_type	SIMPLE
+ table	t1
+-type	range
++type	index
+ possible_keys	bkey
+ key	bkey
+ key_len	5
+ ref	NULL
+-rows	16
++rows	32
+ Extra	Using where; Using index
+ SELECT * FROM t1 WHERE b BETWEEN 1 AND 2 ORDER BY b,a;
+ a	b
+@@ -989,7 +989,7 @@
+ key	bkey
+ key_len	5
+ ref	const
+-rows	8
++rows	16
+ Extra	Using where; Using index; Using filesort
+ SELECT * FROM t2 WHERE b=1 ORDER BY a;
+ a	b	c
+@@ -1018,7 +1018,7 @@
+ key	bkey
+ key_len	10
+ ref	const,const
+-rows	8
++rows	16
+ Extra	Using where; Using index
+ SELECT * FROM t2 WHERE b=1 AND c=1 ORDER BY a;
+ a	b	c
+@@ -1047,7 +1047,7 @@
+ key	bkey
+ key_len	10
+ ref	const,const
+-rows	8
++rows	16
+ Extra	Using where; Using index
+ SELECT * FROM t2 WHERE b=1 AND c=1 ORDER BY b,c,a;
+ a	b	c
+@@ -1076,7 +1076,7 @@
+ key	bkey
+ key_len	10
+ ref	const,const
+-rows	8
++rows	16
+ Extra	Using where; Using index
+ SELECT * FROM t2 WHERE b=1 AND c=1 ORDER BY c,a;
+ a	b	c
+@@ -1211,7 +1211,7 @@
+ key	b
+ key_len	5
+ ref	const
+-rows	1
++rows	2
+ Extra	Using where; Using index
+ SELECT * FROM t1 WHERE b=2 ORDER BY a ASC;
+ a	b
+@@ -1226,7 +1226,7 @@
+ key	b
+ key_len	5
+ ref	const
+-rows	1
++rows	2
+ Extra	Using where; Using index
+ SELECT * FROM t1 WHERE b=2 ORDER BY a DESC;
+ a	b
+@@ -1370,7 +1370,7 @@
+ INSERT INTO t1 (a,b,c) SELECT a+4,b,c FROM t1;
+ EXPLAIN SELECT a, b, c FROM t1 WHERE b = 1 ORDER BY a DESC LIMIT 5;
+ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+-1	SIMPLE	t1	index	t1_b	PRIMARY	4	NULL	8	Using where
++1	SIMPLE	t1	range	t1_b	t1_b	5	NULL	8	Using where
+ SELECT a, b, c FROM t1 WHERE b = 1 ORDER BY a DESC LIMIT 5;
+ a	b	c
+ 8	1	1
+@@ -1729,7 +1729,7 @@
+ FROM t1 WHERE c2 IN (1, 1) AND c3 = 2 GROUP BY c2) x;
+ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+ 1	PRIMARY	<derived2>	system	NULL	NULL	NULL	NULL	1	
+-2	DERIVED	t1	index	c3,c2	c2	10	NULL	5	
++2	DERIVED	t1	ALL	c3,c2	c3	5		5	Using filesort
+ DROP TABLE t1;
+ CREATE TABLE t1 (c1 REAL, c2 REAL, c3 REAL, KEY (c3), KEY (c2, c3))
+ ENGINE=InnoDB;
+@@ -1743,7 +1743,7 @@
+ FROM t1 WHERE c2 IN (1, 1) AND c3 = 2 GROUP BY c2) x;
+ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+ 1	PRIMARY	<derived2>	system	NULL	NULL	NULL	NULL	1	
+-2	DERIVED	t1	index	c3,c2	c2	18	NULL	5	
++2	DERIVED	t1	ALL	c3,c2	c3	9		5	Using filesort
+ DROP TABLE t1;
+ CREATE TABLE t1 (c1 DECIMAL(12,2), c2 DECIMAL(12,2), c3 DECIMAL(12,2), 
+ KEY (c3), KEY (c2, c3))
+@@ -1758,7 +1758,7 @@
+ FROM t1 WHERE c2 IN (1, 1) AND c3 = 2 GROUP BY c2) x;
+ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+ 1	PRIMARY	<derived2>	system	NULL	NULL	NULL	NULL	1	
+-2	DERIVED	t1	index	c3,c2	c2	14	NULL	5	
++2	DERIVED	t1	ALL	c3,c2	c3	7		5	Using filesort
+ DROP TABLE t1;
+ End of 5.1 tests
+ drop table if exists t1, t2, t3;
+@@ -1834,7 +1834,7 @@
+ key	b
+ key_len	5
+ ref	NULL
+-rows	3
++rows	5
+ Extra	Using where; Using index
+ EXPLAIN SELECT c FROM bar WHERE c>2;;
+ id	1
+@@ -2430,7 +2430,7 @@
+ WHERE a BETWEEN 2 AND 7 OR pk=1000000) AS t;
+ id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+ 1	PRIMARY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Select tables optimized away
+-2	DERIVED	t1	index_merge	PRIMARY,idx	idx,PRIMARY	5,4	NULL	3537	Using sort_union(idx,PRIMARY); Using where
++2	DERIVED	t1	index_merge	PRIMARY,idx	idx,PRIMARY	5,4	NULL	1536	Using sort_union(idx,PRIMARY); Using where
+ SELECT COUNT(*) FROM
+ (SELECT * FROM t1 FORCE INDEX (idx,PRIMARY)
+ WHERE a BETWEEN 2 AND 7 OR pk=1000000) AS t;

=== modified file 'patches/series'
--- patches/series	2011-08-01 21:45:17 +0000
+++ patches/series	2011-08-25 09:13:51 +0000
@@ -60,3 +60,4 @@
 bug813587.patch
 innodb_bug47167_test_fix.patch
 disable_query_cache_28249_test_sporadic_failure.patch
+bug53761.patch