bug53761.patch

   1 # name       : bug53761.patch
   2 # maintainer : Alexey
   3 #
   4 # Backport of the fix for MySQL bug #53761 to 5.1
   5 #
   6 --- a/storage/innodb_plugin/btr/btr0cur.c
   7 +++ b/storage/innodb_plugin/btr/btr0cur.c
   8 @@ -3238,6 +3238,7 @@
   9  {
  10         btr_path_t*     slot;
  11         rec_t*          rec;
  12 +       page_t*         page;
  13
  14         ut_a(cursor->path_arr);
  15
  16 @@ -3260,8 +3261,155 @@
  17
  18         slot = cursor->path_arr + (root_height - height);
  19
  20 +       page = page_align(rec);
  21 +
  22         slot->nth_rec = page_rec_get_n_recs_before(rec);
  23 -       slot->n_recs = page_get_n_recs(page_align(rec));
  24 +       slot->n_recs = page_get_n_recs(page);
  25 +       slot->page_no = page_get_page_no(page);
  26 +       slot->page_level = btr_page_get_level_low(page);
  27 +}
  28 +
  29 +/*******************************************************************//**
  30 +Estimate the number of rows between slot1 and slot2 for any level on a
  31 +B-tree. This function starts from slot1->page and reads a few pages to
  32 +the right, counting their records. If we reach slot2->page quickly then
  33 +we know exactly how many records there are between slot1 and slot2 and
  34 +we set is_n_rows_exact to TRUE. If we cannot reach slot2->page quickly
  35 +then we calculate the average number of records in the pages scanned
  36 +so far and assume that all pages that we did not scan up to slot2->page
  37 +contain the same number of records, then we multiply that average to
  38 +the number of pages between slot1->page and slot2->page (which is
  39 +n_rows_on_prev_level). In this case we set is_n_rows_exact to FALSE.
  40 +@return        number of rows (exact or estimated) */
  41 +static
  42 +ib_int64_t
  43 +btr_estimate_n_rows_in_range_on_level(
  44 +/*==================================*/
  45 +       dict_index_t*   index,                  /*!< in: index */
  46 +       btr_path_t*     slot1,                  /*!< in: left border */
  47 +       btr_path_t*     slot2,                  /*!< in: right border */
  48 +       ib_int64_t      n_rows_on_prev_level,   /*!< in: number of rows
  49 +                                               on the previous level for the
  50 +                                               same descend paths; used to
  51 +                                               determine the numbe of pages
  52 +                                               on this level */
  53 +       ibool*          is_n_rows_exact)        /*!< out: TRUE if the returned
  54 +                                               value is exact i.e. not an
  55 +                                               estimation */
  56 +{
  57 +       ulint           space;
  58 +       ib_int64_t      n_rows;
  59 +       ulint           n_pages_read;
  60 +       ulint           page_no;
  61 +       ulint           zip_size;
  62 +       ulint           level;
  63 +
  64 +       space = dict_index_get_space(index);
  65 +
  66 +       n_rows = 0;
  67 +       n_pages_read = 0;
  68 +
  69 +       /* Assume by default that we will scan all pages between
  70 +       slot1->page_no and slot2->page_no */
  71 +       *is_n_rows_exact = TRUE;
  72 +
  73 +       /* add records from slot1->page_no which are to the right of
  74 +       the record which serves as a left border of the range, if any */
  75 +       if (slot1->nth_rec < slot1->n_recs) {
  76 +               n_rows += slot1->n_recs - slot1->nth_rec;
  77 +       }
  78 +
  79 +       /* add records from slot2->page_no which are to the left of
  80 +       the record which servers as a right border of the range, if any */
  81 +       if (slot2->nth_rec > 1) {
  82 +               n_rows += slot2->nth_rec - 1;
  83 +       }
  84 +
  85 +       /* count the records in the pages between slot1->page_no and
  86 +       slot2->page_no (non inclusive), if any */
  87 +
  88 +       zip_size = fil_space_get_zip_size(space);
  89 +
  90 +       /* Do not read more than this number of pages in order not to hurt
  91 +       performance with this code which is just an estimation. If we read
  92 +       this many pages before reaching slot2->page_no then we estimate the
  93 +       average from the pages scanned so far */
  94 +       #define N_PAGES_READ_LIMIT      10
  95 +
  96 +       page_no = slot1->page_no;
  97 +       level = slot1->page_level;
  98 +
  99 +       do {
 100 +               mtr_t           mtr;
 101 +               page_t*         page;
 102 +               buf_block_t*    block;
 103 +
 104 +               mtr_start(&mtr);
 105 +
 106 +               /* fetch the page */
 107 +               block = buf_page_get(space, zip_size, page_no, RW_S_LATCH,
 108 +                                    &mtr);
 109 +
 110 +               page = buf_block_get_frame(block);
 111 +
 112 +               /* It is possible that the tree has been reorganized in the
 113 +               meantime and this is a different page. If this happens the
 114 +               calculated estimate will be bogus, which is not fatal as
 115 +               this is only an estimate. We are sure that a page with
 116 +               page_no exists because InnoDB never frees pages, only
 117 +               reuses them. */
 118 +               if (fil_page_get_type(page) != FIL_PAGE_INDEX
 119 +                   || ut_dulint_cmp(btr_page_get_index_id(page), index->id)
 120 +                   || btr_page_get_level_low(page) != level) {
 121 +
 122 +                       /* The page got reused for something else */
 123 +                       goto inexact;
 124 +               }
 125 +
 126 +               n_pages_read++;
 127 +
 128 +               if (page_no != slot1->page_no) {
 129 +                       /* Do not count the records on slot1->page_no,
 130 +                       we already counted them before this loop. */
 131 +                       n_rows += page_get_n_recs(page);
 132 +               }
 133 +
 134 +               page_no = btr_page_get_next(page, &mtr);
 135 +
 136 +               mtr_commit(&mtr);
 137 +
 138 +               if (n_pages_read == N_PAGES_READ_LIMIT
 139 +                   || page_no == FIL_NULL) {
 140 +                       /* Either we read too many pages or
 141 +                       we reached the end of the level without passing
 142 +                       through slot2->page_no, the tree must have changed
 143 +                       in the meantime */
 144 +                       goto inexact;
 145 +               }
 146 +
 147 +       } while (page_no != slot2->page_no);
 148 +
 149 +       return(n_rows);
 150 +
 151 +inexact:
 152 +
 153 +       *is_n_rows_exact = FALSE;
 154 +
 155 +       /* We did interrupt before reaching slot2->page */
 156 +
 157 +       if (n_pages_read > 0) {
 158 +               /* The number of pages on this level is
 159 +               n_rows_on_prev_level, multiply it by the
 160 +               average number of recs per page so far */
 161 +               n_rows = n_rows_on_prev_level
 162 +                       * n_rows / n_pages_read;
 163 +       } else {
 164 +               /* The tree changed before we could even
 165 +               start with slot1->page_no */
 166 +               n_rows = 10;
 167 +       }
 168 +
 169 +       return(n_rows);
 170  }
 171
 172  /*******************************************************************//**
 173 @@ -3286,6 +3434,7 @@
 174         ibool           diverged_lot;
 175         ulint           divergence_level;
 176         ib_int64_t      n_rows;
 177 +       ibool           is_n_rows_exact;
 178         ulint           i;
 179         mtr_t           mtr;
 180
 181 @@ -3328,6 +3477,7 @@
 182         /* We have the path information for the range in path1 and path2 */
 183
 184         n_rows = 1;
 185 +       is_n_rows_exact = TRUE;
 186         diverged = FALSE;           /* This becomes true when the path is not
 187                                     the same any more */
 188         diverged_lot = FALSE;       /* This becomes true when the paths are
 189 @@ -3343,7 +3493,7 @@
 190                 if (slot1->nth_rec == ULINT_UNDEFINED
 191                     || slot2->nth_rec == ULINT_UNDEFINED) {
 192
 193 -                       if (i > divergence_level + 1) {
 194 +                       if (i > divergence_level + 1 && !is_n_rows_exact) {
 195                                 /* In trees whose height is > 1 our algorithm
 196                                 tends to underestimate: multiply the estimate
 197                                 by 2: */
 198 @@ -3355,7 +3505,9 @@
 199                         to over 1 / 2 of the estimated rows in the whole
 200                         table */
 201
 202 -                       if (n_rows > index->table->stat_n_rows / 2) {
 203 +                       if (n_rows > index->table->stat_n_rows / 2
 204 +                           && !is_n_rows_exact) {
 205 +
 206                                 n_rows = index->table->stat_n_rows / 2;
 207
 208                                 /* If there are just 0 or 1 rows in the table,
 209 @@ -3381,10 +3533,15 @@
 210                                         divergence_level = i;
 211                                 }
 212                         } else {
 213 -                               /* Maybe the tree has changed between
 214 -                               searches */
 215 -
 216 -                               return(10);
 217 +                               /* It is possible that
 218 +                               slot1->nth_rec >= slot2->nth_rec
 219 +                               if, for example, we have a single page
 220 +                               tree which contains (inf, 5, 6, supr)
 221 +                               and we select where x > 20 and x < 30;
 222 +                               in this case slot1->nth_rec will point
 223 +                               to the supr record and slot2->nth_rec
 224 +                               will point to 6 */
 225 +                               n_rows = 0;
 226                         }
 227
 228                 } else if (diverged && !diverged_lot) {
 229 @@ -3408,8 +3565,9 @@
 230                         }
 231                 } else if (diverged_lot) {
 232
 233 -                       n_rows = (n_rows * (slot1->n_recs + slot2->n_recs))
 234 -                               / 2;
 235 +                       n_rows = btr_estimate_n_rows_in_range_on_level(
 236 +                               index, slot1, slot2, n_rows,
 237 +                               &is_n_rows_exact);
 238                 }
 239         }
 240  }
 241 --- a/storage/innodb_plugin/include/btr0cur.h
 242 +++ b/storage/innodb_plugin/include/btr0cur.h
 243 @@ -670,6 +670,11 @@
 244                                 order); value ULINT_UNDEFINED
 245                                 denotes array end */
 246         ulint   n_recs;         /*!< number of records on the page */
 247 +       ulint   page_no;        /*!< no of the page containing the record */
 248 +       ulint   page_level;     /*!< level of the page, if later we fetch
 249 +                               the page under page_no and it is no different
 250 +                               level then we know that the tree has been
 251 +                               reorganized */
 252  };
 253
 254  #define BTR_PATH_ARRAY_N_SLOTS 250     /*!< size of path array (in slots) */
 255 --- a/mysql-test/suite/innodb_plugin/r/innodb_gis.result
 256 +++ b/mysql-test/suite/innodb_plugin/r/innodb_gis.result
 257 @@ -572,7 +572,7 @@
 258  EXPLAIN
 259  SELECT COUNT(*) FROM t2 WHERE p=POINTFROMTEXT('POINT(1 2)');
 260  id     select_type     table   type    possible_keys   key     key_len ref     rows    Extra
 261 -1      SIMPLE  t2      ref     p       p       28      const   1       Using where
 262 +1      SIMPLE  t2      ref     p       p       28      const   2       Using where
 263  SELECT COUNT(*) FROM t2 WHERE p=POINTFROMTEXT('POINT(1 2)');
 264  COUNT(*)
 265  2
 266 --- a/mysql-test/suite/innodb_plugin/r/innodb_mysql.result
 267 +++ b/mysql-test/suite/innodb_plugin/r/innodb_mysql.result
 268 @@ -889,13 +889,13 @@
 269  id     1
 270  select_type    SIMPLE
 271  table  t1
 272 -type   range
 273 +type   index
 274  possible_keys  bkey
 275 -key    bkey
 276 -key_len        5
 277 +key    PRIMARY
 278 +key_len        4
 279  ref    NULL
 280 -rows   16
 281 -Extra  Using where; Using index; Using filesort
 282 +rows   32
 283 +Extra  Using where
 284  SELECT * FROM t1 WHERE b BETWEEN 1 AND 2 ORDER BY a;
 285  a      b
 286  1      2
 287 @@ -934,12 +934,12 @@
 288  id     1
 289  select_type    SIMPLE
 290  table  t1
 291 -type   range
 292 +type   index
 293  possible_keys  bkey
 294  key    bkey
 295  key_len        5
 296  ref    NULL
 297 -rows   16
 298 +rows   32
 299  Extra  Using where; Using index
 300  SELECT * FROM t1 WHERE b BETWEEN 1 AND 2 ORDER BY b,a;
 301  a      b
 302 @@ -989,7 +989,7 @@
 303  key    bkey
 304  key_len        5
 305  ref    const
 306 -rows   8
 307 +rows   16
 308  Extra  Using where; Using index; Using filesort
 309  SELECT * FROM t2 WHERE b=1 ORDER BY a;
 310  a      b       c
 311 @@ -1018,7 +1018,7 @@
 312  key    bkey
 313  key_len        10
 314  ref    const,const
 315 -rows   8
 316 +rows   16
 317  Extra  Using where; Using index
 318  SELECT * FROM t2 WHERE b=1 AND c=1 ORDER BY a;
 319  a      b       c
 320 @@ -1047,7 +1047,7 @@
 321  key    bkey
 322  key_len        10
 323  ref    const,const
 324 -rows   8
 325 +rows   16
 326  Extra  Using where; Using index
 327  SELECT * FROM t2 WHERE b=1 AND c=1 ORDER BY b,c,a;
 328  a      b       c
 329 @@ -1076,7 +1076,7 @@
 330  key    bkey
 331  key_len        10
 332  ref    const,const
 333 -rows   8
 334 +rows   16
 335  Extra  Using where; Using index
 336  SELECT * FROM t2 WHERE b=1 AND c=1 ORDER BY c,a;
 337  a      b       c
 338 @@ -1211,7 +1211,7 @@
 339  key    b
 340  key_len        5
 341  ref    const
 342 -rows   1
 343 +rows   2
 344  Extra  Using where; Using index
 345  SELECT * FROM t1 WHERE b=2 ORDER BY a ASC;
 346  a      b
 347 @@ -1226,7 +1226,7 @@
 348  key    b
 349  key_len        5
 350  ref    const
 351 -rows   1
 352 +rows   2
 353  Extra  Using where; Using index
 354  SELECT * FROM t1 WHERE b=2 ORDER BY a DESC;
 355  a      b
 356 @@ -1370,7 +1370,7 @@
 357  INSERT INTO t1 (a,b,c) SELECT a+4,b,c FROM t1;
 358  EXPLAIN SELECT a, b, c FROM t1 WHERE b = 1 ORDER BY a DESC LIMIT 5;
 359  id     select_type     table   type    possible_keys   key     key_len ref     rows    Extra
 360 -1      SIMPLE  t1      index   t1_b    PRIMARY 4       NULL    8       Using where
 361 +1      SIMPLE  t1      range   t1_b    t1_b    5       NULL    8       Using where
 362  SELECT a, b, c FROM t1 WHERE b = 1 ORDER BY a DESC LIMIT 5;
 363  a      b       c
 364  8      1       1
 365 @@ -1729,7 +1729,7 @@
 366  FROM t1 WHERE c2 IN (1, 1) AND c3 = 2 GROUP BY c2) x;
 367  id     select_type     table   type    possible_keys   key     key_len ref     rows    Extra
 368  1      PRIMARY <derived2>      system  NULL    NULL    NULL    NULL    1
 369 -2      DERIVED t1      index   c3,c2   c2      10      NULL    5
 370 +2      DERIVED t1      ALL     c3,c2   c3      5               5       Using filesort
 371  DROP TABLE t1;
 372  CREATE TABLE t1 (c1 REAL, c2 REAL, c3 REAL, KEY (c3), KEY (c2, c3))
 373  ENGINE=InnoDB;
 374 @@ -1743,7 +1743,7 @@
 375  FROM t1 WHERE c2 IN (1, 1) AND c3 = 2 GROUP BY c2) x;
 376  id     select_type     table   type    possible_keys   key     key_len ref     rows    Extra
 377  1      PRIMARY <derived2>      system  NULL    NULL    NULL    NULL    1
 378 -2      DERIVED t1      index   c3,c2   c2      18      NULL    5
 379 +2      DERIVED t1      ALL     c3,c2   c3      9               5       Using filesort
 380  DROP TABLE t1;
 381  CREATE TABLE t1 (c1 DECIMAL(12,2), c2 DECIMAL(12,2), c3 DECIMAL(12,2),
 382  KEY (c3), KEY (c2, c3))
 383 @@ -1758,7 +1758,7 @@
 384  FROM t1 WHERE c2 IN (1, 1) AND c3 = 2 GROUP BY c2) x;
 385  id     select_type     table   type    possible_keys   key     key_len ref     rows    Extra
 386  1      PRIMARY <derived2>      system  NULL    NULL    NULL    NULL    1
 387 -2      DERIVED t1      index   c3,c2   c2      14      NULL    5
 388 +2      DERIVED t1      ALL     c3,c2   c3      7               5       Using filesort
 389  DROP TABLE t1;
 390  End of 5.1 tests
 391  drop table if exists t1, t2, t3;
 392 @@ -1834,7 +1834,7 @@
 393  key    b
 394  key_len        5
 395  ref    NULL
 396 -rows   3
 397 +rows   5
 398  Extra  Using where; Using index
 399  EXPLAIN SELECT c FROM bar WHERE c>2;;
 400  id     1
 401 @@ -2430,7 +2430,7 @@
 402  WHERE a BETWEEN 2 AND 7 OR pk=1000000) AS t;
 403  id     select_type     table   type    possible_keys   key     key_len ref     rows    Extra
 404  1      PRIMARY NULL    NULL    NULL    NULL    NULL    NULL    NULL    Select tables optimized away
 405 -2      DERIVED t1      index_merge     PRIMARY,idx     idx,PRIMARY     5,4     NULL    3537    Using sort_union(idx,PRIMARY); Using where
 406 +2      DERIVED t1      index_merge     PRIMARY,idx     idx,PRIMARY     5,4     NULL    1536    Using sort_union(idx,PRIMARY); Using where
 407  SELECT COUNT(*) FROM
 408  (SELECT * FROM t1 FORCE INDEX (idx,PRIMARY)
 409  WHERE a BETWEEN 2 AND 7 OR pk=1000000) AS t;
 410 --- a/mysql-test/r/index_merge_innodb.result
 411 +++ b/mysql-test/r/index_merge_innodb.result
 412 @@ -346,7 +346,7 @@
 413  FROM t1
 414  WHERE c = 1 AND b = 1 AND d = 1;
 415  id     select_type     table   type    possible_keys   key     key_len ref     rows    Extra
 416 -1      SIMPLE  t1      index_merge     c,bd    c,bd    5,10    NULL    1       Using intersect(c,bd); Using where; Using index
 417 +1      SIMPLE  t1      ref     c,bd    bd      10      const,const     2       Using where
 418  CREATE TABLE t2 ( a INT )
 419  SELECT a
 420  FROM t1
 421 --- a/mysql-test/r/rowid_order_innodb.result
 422 +++ b/mysql-test/r/rowid_order_innodb.result
 423 @@ -15,7 +15,7 @@
 424  (10, 1, 1);
 425  explain select * from t1 force index(key1, key2) where key1 < 3 or key2 < 3;
 426  id     select_type     table   type    possible_keys   key     key_len ref     rows    Extra
 427 -1      SIMPLE  t1      index_merge     key1,key2       key1,key2       5,5     NULL    4       Using sort_union(key1,key2); Using where
 428 +1      SIMPLE  t1      index_merge     key1,key2       key1,key2       5,5     NULL    5       Using sort_union(key1,key2); Using where
 429  select * from t1 force index(key1, key2) where key1 < 3 or key2 < 3;
 430  pk1    key1    key2
 431  -100   1       1
 432 --- a/mysql-test/r/type_bit_innodb.result
 433 +++ b/mysql-test/r/type_bit_innodb.result
 434 @@ -233,7 +233,7 @@
 435  127    403
 436  explain select a+0, b+0 from t1 where a > 40 and b > 200 order by 1;
 437  id     select_type     table   type    possible_keys   key     key_len ref     rows    Extra
 438 -1      SIMPLE  t1      range   a       a       2       NULL    19      Using where; Using index; Using filesort
 439 +1      SIMPLE  t1      range   a       a       2       NULL    27      Using where; Using index; Using filesort
 440  select a+0, b+0 from t1 where a > 40 and b > 200 order by 1;
 441  a+0    b+0
 442  44     307
 443 --- a/mysql-test/r/endspace.result
 444 +++ b/mysql-test/r/endspace.result
 445 @@ -201,12 +201,12 @@
 446  text1
 447  teststring
 448  teststring
 449 -select text1, length(text1) from t1 where text1='teststring' or text1 like 'teststring_%';
 450 +select text1, length(text1) from t1 where text1='teststring' or text1 like 'teststring_%' order by 1, 2;
 451  text1  length(text1)
 452  teststring             11
 453  teststring     10
 454  teststring     11
 455 -select text1, length(text1) from t1 where text1='teststring' or text1 >= 'teststring\t';
 456 +select text1, length(text1) from t1 where text1='teststring' or text1 >= 'teststring\t' order by 1, 2;
 457  text1  length(text1)
 458  teststring             11
 459  teststring     10
 460 --- a/mysql-test/t/endspace.test
 461 +++ b/mysql-test/t/endspace.test
 462 @@ -93,8 +93,8 @@
 463  select * from t1 where text1 like 'teststring_%';
 464
 465  # The following gives wrong result in InnoDB
 466 -select text1, length(text1) from t1 where text1='teststring' or text1 like 'teststring_%';
 467 -select text1, length(text1) from t1 where text1='teststring' or text1 >= 'teststring\t';
 468 +select text1, length(text1) from t1 where text1='teststring' or text1 like 'teststring_%' order by 1, 2;
 469 +select text1, length(text1) from t1 where text1='teststring' or text1 >= 'teststring\t' order by 1, 2;
 470  select concat('|', text1, '|') from t1 order by text1;
 471  drop table t1;
 472