diff options
author | unknown <timour@askmonty.org> | 2011-11-17 01:25:10 +0200 |
---|---|---|
committer | unknown <timour@askmonty.org> | 2011-11-17 01:25:10 +0200 |
commit | 42221abaed700f6dc5d280b462755851780e8487 (patch) | |
tree | de3407cdfbd18cfe5d5c77a2ae2fa44cb6f02e19 /sql | |
parent | c05e5b9c65f76ba2d3a6844add88c03076b2cb5d (diff) | |
download | mariadb-git-42221abaed700f6dc5d280b462755851780e8487.tar.gz |
Fix bug lp:869036
Apart from the fix, the patch also adds few more unrelated test
cases for partial matching, and fixes few typos.
Analysis:
This bug uncovered that partial matching via rowid intersection
didn't handle the case when:
- the left IN argument has some NULLs,
- there are no non-null value matches, and there is no non-null
column,
- the subquery columns that are not covered with the NULLs in
the left IN argument contain at least one row, such that it
has NULL values in all columns where the left IN operand has
no NULLs.
In this case there is a partial match.
In addition the analysis of the related code uncovered incorrect
handling of few other related cases.
Solution:
The solution for the bug is to check if there exists a row with
NULLs in all columns other than the ones having NULL in the
let IN operand.
The check is implemented via checking whether the bitmaps that
store NULL information in class Ordered_key have a non-empty
intersection for the relevant columns.
The intersection itself is implemented via the function
bitmap_exists_intersection() in my_bitmap.c.
Diffstat (limited to 'sql')
-rw-r--r-- | sql/item_subselect.cc | 110 | ||||
-rw-r--r-- | sql/item_subselect.h | 13 |
2 files changed, 103 insertions, 20 deletions
diff --git a/sql/item_subselect.cc b/sql/item_subselect.cc index 71408528903..18374000dff 100644 --- a/sql/item_subselect.cc +++ b/sql/item_subselect.cc @@ -4849,14 +4849,14 @@ bool Ordered_key::init(MY_BITMAP *columns_to_index) Item_func_lt *fn_less_than; key_column_count= bitmap_bits_set(columns_to_index); - - // TIMOUR: check for mem allocation err, revert to scan - key_columns= (Item_field**) thd->alloc(key_column_count * sizeof(Item_field*)); compare_pred= (Item_func_lt**) thd->alloc(key_column_count * sizeof(Item_func_lt*)); + if (!key_columns || !compare_pred) + return TRUE; /* Revert to table scan partial match. */ + for (uint i= 0; i < columns_to_index->n_bits; i++) { if (!bitmap_is_set(columns_to_index, i)) @@ -5316,10 +5316,13 @@ subselect_rowid_merge_engine::init(MY_BITMAP *non_null_key_parts, merge_keys_count == 1 && non_null_key_parts)); /* Allocate buffers to hold the merged keys and the mapping between rowids and - row numbers. + row numbers. All small buffers are allocated in the runtime memroot. Big + buffers are allocated from the OS via malloc. */ if (!(merge_keys= (Ordered_key**) thd->alloc(merge_keys_count * sizeof(Ordered_key*))) || + !(null_bitmaps= (MY_BITMAP**) thd->alloc(merge_keys_count * + sizeof(MY_BITMAP*))) || !(row_num_to_rowid= (uchar*) my_malloc((size_t)(row_count * rowid_length), MYF(MY_WME)))) return TRUE; @@ -5537,6 +5540,56 @@ bool subselect_rowid_merge_engine::test_null_row(rownum_t row_num) } +/** + Test if a subset of NULL-able columns contains a row of NULLs. +*/ + +bool subselect_rowid_merge_engine:: +exists_complementing_null_row(MY_BITMAP *keys_to_complement) +{ + rownum_t highest_min_row= 0; + rownum_t lowest_max_row= UINT_MAX; + uint count_null_keys, i, j; + Ordered_key *cur_key; + + count_null_keys= keys_to_complement->n_bits - + bitmap_bits_set(keys_to_complement); + if (count_null_keys == 1) + { + /* + The caller guarantees that the complement to keys_to_complement + contains only columns with NULLs. Therefore if there is only one column, + it is guaranteed to contain NULLs. + */ + return TRUE; + } + + for (i= (non_null_key ? 1 : 0), j= 0; i < merge_keys_count; i++) + { + cur_key= merge_keys[i]; + if (bitmap_is_set(keys_to_complement, cur_key->get_keyid())) + continue; + DBUG_ASSERT(cur_key->get_null_count()); + if (cur_key->get_min_null_row() > highest_min_row) + highest_min_row= cur_key->get_min_null_row(); + if (cur_key->get_max_null_row() < lowest_max_row) + lowest_max_row= cur_key->get_max_null_row(); + null_bitmaps[j++]= cur_key->get_null_key(); + } + DBUG_ASSERT(count_null_keys == j); + + if (lowest_max_row < highest_min_row) + { + /* The intersection of NULL rows is empty. */ + return FALSE; + } + + return bitmap_exists_intersection((const MY_BITMAP**) null_bitmaps, + count_null_keys, + highest_min_row, lowest_max_row); +} + + /* @retval TRUE there is a partial match (UNKNOWN) @retval FALSE there is no match at all (FALSE) @@ -5549,7 +5602,7 @@ bool subselect_rowid_merge_engine::partial_match() Ordered_key *cur_key; rownum_t cur_row_num; uint count_nulls_in_search_key= 0; - uint max_covering_null_row_len= + uint max_null_in_any_row= ((select_materialize_with_stats *) result)->get_max_nulls_in_row(); bool res= FALSE; @@ -5602,29 +5655,52 @@ bool subselect_rowid_merge_engine::partial_match() /* If the outer reference consists of only NULLs, or if it has NULLs in all - nullable columns, the result is UNKNOWN. + nullable columns (above we guarantee there is a match for the non-null + coumns), the result is UNKNOWN. */ - if (count_nulls_in_search_key == - ((Item_in_subselect *) item)->left_expr->cols() - - (non_null_key ? non_null_key->get_column_count() : 0)) + if (count_nulls_in_search_key == merge_keys_count - test(non_null_key)) { res= TRUE; goto end; } /* + If the outer row has NULLs in some columns, and + there is no match for any of the remaining columns, and + there is a subquery row with NULLs in all unmatched columns, + then there is a partial match, otherwise the result is FALSE. + */ + if (count_nulls_in_search_key && !pq.elements) + { + DBUG_ASSERT(!non_null_key); + /* + Check if the intersection of all NULL bitmaps of all keys that + are not in matching_outer_cols is non-empty. + */ + res= exists_complementing_null_row(&matching_outer_cols); + goto end; + } + + /* If there is no NULL (sub)row that covers all NULL columns, and there is no - single match for any of the NULL columns, the result is FALSE. + match for any of the NULL columns, the result is FALSE. Notice that if there + is a non-null key, and there is only one matching key, the non-null key is + the matching key. This is so, because this method returns FALSE if the + non-null key doesn't have a match. */ - if ((pq.elements == 1 && non_null_key && - max_covering_null_row_len < merge_keys_count - 1) || - pq.elements == 0) + if (!count_nulls_in_search_key && + (!pq.elements || + (pq.elements == 1 && non_null_key && + max_null_in_any_row < merge_keys_count-1))) { - if (pq.elements == 0) + if (!pq.elements) { - DBUG_ASSERT(!non_null_key); /* Must follow from the logic of this method */ - /* This case must be handled by subselect_partial_match_engine::exec() */ - DBUG_ASSERT(max_covering_null_row_len != tmp_table->s->fields); + DBUG_ASSERT(!non_null_key); + /* + The case of a covering null row is handled by + subselect_partial_match_engine::exec() + */ + DBUG_ASSERT(max_null_in_any_row != tmp_table->s->fields); } res= FALSE; goto end; diff --git a/sql/item_subselect.h b/sql/item_subselect.h index 2012306c0f7..28ce0061729 100644 --- a/sql/item_subselect.h +++ b/sql/item_subselect.h @@ -999,7 +999,7 @@ protected: /* - Distinguish the type od (0-based) row numbers from the type of the index into + Distinguish the type of (0-based) row numbers from the type of the index into an array of row numbers. */ typedef ha_rows rownum_t; @@ -1075,9 +1075,9 @@ protected: /* Count of NULLs per column. */ ha_rows null_count; /* The row number that contains the first NULL in a column. */ - ha_rows min_null_row; + rownum_t min_null_row; /* The row number that contains the last NULL in a column. */ - ha_rows max_null_row; + rownum_t max_null_row; protected: bool alloc_keys_buffers(); @@ -1110,6 +1110,10 @@ public: DBUG_ASSERT(i < key_column_count); return key_columns[i]->field->field_index; } + rownum_t get_min_null_row() { return min_null_row; } + rownum_t get_max_null_row() { return max_null_row; } + MY_BITMAP * get_null_key() { return &null_key; } + ha_rows get_null_count() { return null_count; } /* Get the search key element that corresponds to the i-th key part of this index. @@ -1280,6 +1284,8 @@ protected: Ordered_key **merge_keys; /* The number of elements in merge_keys. */ uint merge_keys_count; + /* The NULL bitmaps of merge keys.*/ + MY_BITMAP **null_bitmaps; /* An index on all non-NULL columns of 'tmp_table'. The index has the logical form: <[v_i1 | ... | v_ik], rownum>. It allows to find the row @@ -1305,6 +1311,7 @@ protected: static int cmp_keys_by_cur_rownum(void *arg, uchar *k1, uchar *k2); bool test_null_row(rownum_t row_num); + bool exists_complementing_null_row(MY_BITMAP *keys_to_complement); bool partial_match(); public: subselect_rowid_merge_engine(THD *thd_arg, |