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.

1 files changed, 90 insertions, 0 deletions

diff --git a/mysys/my_bitmap.c b/mysys/my_bitmap.c
index 0e5421ec484..260289cf041 100644
--- a/mysys/my_bitmap.c
+++ b/mysys/my_bitmap.c
@@ -100,6 +100,44 @@ void create_last_word_mask(MY_BITMAP *map)
 }
 
 
+static inline my_bitmap_map last_word_mask(uint bit)
+{
+  my_bitmap_map last_word_mask;
+  uint n_bits= bit + 1;
+  unsigned char const mask= invers_last_byte_mask(n_bits);
+
+  /*
+    The first bytes are to be set to zero since they represent real  bits
+    in the bitvector. The last bytes are set to 0xFF since they  represent
+    bytes not used by the bitvector. Finally the last byte contains  bits
+    as set by the mask above.
+  */
+  unsigned char *ptr= (unsigned char*)&last_word_mask;
+
+  switch ((n_bits + 7)/8 & 3) {
+  case 1:
+    last_word_mask= ~0U;
+    ptr[0]= mask;
+    break;
+  case 2:
+    last_word_mask= ~0U;
+    ptr[0]= 0;
+    ptr[1]= mask;
+    break;
+  case 3:
+    last_word_mask= 0U;
+    ptr[2]= mask;
+    ptr[3]= 0xFFU;
+    break;
+  case 0:
+    last_word_mask= 0U;
+    ptr[3]= mask;
+    break;
+  }
+  return last_word_mask;
+}
+
+
 static inline void bitmap_lock(MY_BITMAP *map __attribute__((unused)))
 {
 #ifdef THREAD
@@ -410,6 +448,58 @@ void bitmap_intersect(MY_BITMAP *map, const MY_BITMAP *map2)
   }
 }
 
+
+/*
+  Check if there is some bit index between start_bit and end_bit, such that
+  this is bit is set for all bitmaps in bitmap_list.
+
+  SYNOPSIS
+    bitmap_exists_intersection()
+    bitmpap_array [in]  a set of MY_BITMAPs
+    bitmap_count  [in]  number of elements in bitmpap_array
+    start_bit     [in]  beginning (inclusive) of the range of bits to search
+    end_bit       [in]  end (inclusive) of the range of bits to search, must be
+                        no bigger than the bits of the shortest bitmap.
+
+  NOTES
+  This function assumes that for at least one of the bitmaps in bitmap_array all
+  bits outside the range [start_bit, end_bit] are 0. As a result is not
+  necessary to take care of the bits outside the range [start_bit, end_bit].
+
+  RETURN
+    TRUE  if an intersecion exists
+    FALSE no intersection
+*/
+
+my_bool bitmap_exists_intersection(const MY_BITMAP **bitmap_array,
+                                   uint bitmap_count,
+                                   uint start_bit, uint end_bit)
+{
+  uint i, j, start_idx, end_idx;
+  my_bitmap_map cur_res;
+
+  DBUG_ASSERT(bitmap_count && end_bit >= start_bit);
+  for (j= 0; j < bitmap_count; j++)
+    DBUG_ASSERT(end_bit < bitmap_array[j]->n_bits);
+
+  start_idx= start_bit/8/sizeof(my_bitmap_map);
+  end_idx= end_bit/8/sizeof(my_bitmap_map);
+
+  for (i= start_idx; i < end_idx; i++)
+  {
+    cur_res= ~0;
+    for (j= 0; cur_res && j < bitmap_count; j++)
+      cur_res &= bitmap_array[j]->bitmap[i];
+    if (cur_res)
+      return TRUE;
+  }
+  cur_res= ~last_word_mask(end_bit);
+  for (j= 0; cur_res && j < bitmap_count; j++)
+    cur_res &= bitmap_array[j]->bitmap[end_idx];
+  return cur_res != 0;
+}
+
+
 /* True if union of bitmaps have all bits set */
 
 my_bool bitmap_union_is_set_all(const MY_BITMAP *map1, const MY_BITMAP *map2)