MDEV-16188 Use in-memory PK filters built from range index scans

This patch contains a full implementation of the optimization
that allows to use in-memory rowid / primary filters built for range  
conditions over indexes. In many cases usage of such filters reduce  
the number of disk seeks spent for fetching table rows.

In this implementation the choice of what possible filter to be applied  
(if any) is made purely on cost-based considerations.

This implementation re-achitectured the partial implementation of
the feature pushed by Galina Shalygina in the commit
8d5a11122c32f4d9eb87536886c6e893377bdd07.

Besides this patch contains a better implementation of the generic  
handler function handler::multi_range_read_info_const() that
takes into account gaps between ranges when calculating the cost of
range index scans. It also contains some corrections of the
implementation of the handler function records_in_range() for MyISAM.

This patch supports the feature for InnoDB and MyISAM.

10 files changed, 114 insertions, 26 deletions

diff --git a/storage/myisam/ha_myisam.cc b/storage/myisam/ha_myisam.cc
index 9ab7d156251..012691ef2da 100644
--- a/storage/myisam/ha_myisam.cc
+++ b/storage/myisam/ha_myisam.cc
@@ -769,7 +769,8 @@ ulong ha_myisam::index_flags(uint inx, uint part, bool all_parts) const
   else 
   {
     flags= HA_READ_NEXT | HA_READ_PREV | HA_READ_RANGE |
-          HA_READ_ORDER | HA_KEYREAD_ONLY | HA_DO_INDEX_COND_PUSHDOWN;
+           HA_READ_ORDER | HA_KEYREAD_ONLY | HA_DO_INDEX_COND_PUSHDOWN |
+           HA_DO_RANGE_FILTER_PUSHDOWN;
   }
   return flags;
 }
@@ -1880,6 +1881,9 @@ int ha_myisam::index_init(uint idx, bool sorted)
   active_index=idx;
   if (pushed_idx_cond_keyno == idx)
     mi_set_index_cond_func(file, handler_index_cond_check, this);
+  if (pushed_rowid_filter)
+    mi_set_rowid_filter_func(file, handler_rowid_filter_check,
+                             handler_rowid_filter_is_active, this);
   return 0; 
 }
 
@@ -1891,6 +1895,7 @@ int ha_myisam::index_end()
   //pushed_idx_cond_keyno= MAX_KEY;
   mi_set_index_cond_func(file, NULL, 0);
   in_range_check_pushed_down= FALSE;
+  mi_set_rowid_filter_func(file, NULL, NULL, 0);
   ds_mrr.dsmrr_close();
 #if !defined(DBUG_OFF) && defined(SQL_SELECT_FIXED_FOR_UPDATE)
   file->update&= ~HA_STATE_AKTIV;               // Forget active row
@@ -1926,6 +1931,9 @@ int ha_myisam::index_read_idx_map(uchar *buf, uint index, const uchar *key,
   end_range= NULL;
   if (index == pushed_idx_cond_keyno)
     mi_set_index_cond_func(file, handler_index_cond_check, this);
+  if (pushed_rowid_filter)
+    mi_set_rowid_filter_func(file, handler_rowid_filter_check,
+                             handler_rowid_filter_is_active, this);
   res= mi_rkey(file, buf, index, key, keypart_map, find_flag);
   mi_set_index_cond_func(file, NULL, 0);
   return res;
@@ -2591,6 +2599,14 @@ Item *ha_myisam::idx_cond_push(uint keyno_arg, Item* idx_cond_arg)
   return NULL;
 }
 
+bool ha_myisam::rowid_filter_push(Rowid_filter* rowid_filter)
+{
+  pushed_rowid_filter= rowid_filter;
+  mi_set_rowid_filter_func(file, handler_rowid_filter_check,
+			   handler_rowid_filter_is_active, this);
+  return false;
+}
+
 struct st_mysql_storage_engine myisam_storage_engine=
 { MYSQL_HANDLERTON_INTERFACE_VERSION };
 
@@ -2681,7 +2697,7 @@ my_bool ha_myisam::register_query_cache_table(THD *thd, const char *table_name,
 
       If the table size is unknown the SELECT statement can't be cached.
 
-      When concurrent inserts are disabled at table open, mi_open()
+      When concurrent inserts are disabled at table open, mi_ondopen()
       does not assign a get_status() function. In this case the local
       ("current") status is never updated. We would wrongly think that
       we cannot cache the statement.
diff --git a/storage/myisam/ha_myisam.h b/storage/myisam/ha_myisam.h
index 804963f5efc..f9f11b6f480 100644
--- a/storage/myisam/ha_myisam.h
+++ b/storage/myisam/ha_myisam.h
@@ -172,6 +172,8 @@ public:
 
   /* Index condition pushdown implementation */
   Item *idx_cond_push(uint keyno, Item* idx_cond);
+  bool rowid_filter_push(Rowid_filter* rowid_filter);
+
 private:
   DsMrr_impl ds_mrr;
   friend ICP_RESULT index_cond_func_myisam(void *arg);
diff --git a/storage/myisam/mi_extra.c b/storage/myisam/mi_extra.c
index c10bf61a477..e28b9be501e 100644
--- a/storage/myisam/mi_extra.c
+++ b/storage/myisam/mi_extra.c
@@ -418,6 +418,16 @@ void mi_set_index_cond_func(MI_INFO *info, index_cond_func_t func,
   info->index_cond_func_arg= func_arg;
 }
 
+void mi_set_rowid_filter_func(MI_INFO *info,
+                              rowid_filter_func_t check_func,
+                              rowid_filter_func_t is_active_func,
+                              void *func_arg)
+{
+  info->rowid_filter_func= check_func;
+  info->rowid_filter_is_active_func= is_active_func;
+  info->rowid_filter_func_arg= func_arg;
+}
+
 /*
     Start/Stop Inserting Duplicates Into a Table, WL#1648.
  */
diff --git a/storage/myisam/mi_key.c b/storage/myisam/mi_key.c
index 4bd01dcbfa0..8bf63af8f5f 100644
--- a/storage/myisam/mi_key.c
+++ b/storage/myisam/mi_key.c
@@ -529,6 +529,19 @@ ICP_RESULT mi_check_index_cond(register MI_INFO *info, uint keynr,
   return res;
 }
 
+
+int mi_check_rowid_filter(MI_INFO *info)
+{
+  return info->rowid_filter_func(info->rowid_filter_func_arg);
+}
+
+int mi_check_rowid_filter_is_active(MI_INFO *info)
+{
+  if (info->rowid_filter_is_active_func == NULL)
+    return 0;
+  return info->rowid_filter_is_active_func(info->rowid_filter_func_arg);
+}
+
 /*
   Retrieve auto_increment info
 
diff --git a/storage/myisam/mi_range.c b/storage/myisam/mi_range.c
index 2074c873979..185f2ca61fa 100644
--- a/storage/myisam/mi_range.c
+++ b/storage/myisam/mi_range.c
@@ -22,9 +22,10 @@
 #include "myisamdef.h"
 #include "rt_index.h"
 
-static ha_rows _mi_record_pos(MI_INFO *, const uchar *, key_part_map,
-                              enum ha_rkey_function);
-static double _mi_search_pos(MI_INFO *,MI_KEYDEF *,uchar *, uint,uint,my_off_t);
+static double _mi_record_pos(MI_INFO *, const uchar *, key_part_map,
+                             enum ha_rkey_function);
+static double _mi_search_pos(MI_INFO *,MI_KEYDEF *,uchar *, uint,uint,
+                             my_off_t,my_bool);
 static uint _mi_keynr(MI_INFO *info,MI_KEYDEF *,uchar *, uchar *,uint *);
 
 /*
@@ -48,7 +49,8 @@ static uint _mi_keynr(MI_INFO *info,MI_KEYDEF *,uchar *, uchar *,uint *);
 ha_rows mi_records_in_range(MI_INFO *info, int inx,
                             key_range *min_key, key_range *max_key)
 {
-  ha_rows start_pos,end_pos,res;
+  ha_rows res;
+  double start_pos,end_pos,diff;
   DBUG_ENTER("mi_records_in_range");
 
   if ((inx = _mi_check_index(info,inx)) < 0)
@@ -94,16 +96,27 @@ ha_rows mi_records_in_range(MI_INFO *info, int inx,
 #endif
   case HA_KEY_ALG_BTREE:
   default:
-    start_pos= (min_key ?  _mi_record_pos(info, min_key->key,
-                                          min_key->keypart_map, min_key->flag)
-                        : (ha_rows) 0);
+    start_pos= (min_key ?_mi_record_pos(info, min_key->key,
+                                        min_key->keypart_map, min_key->flag)
+                        : (double) 0);
     end_pos=   (max_key ?  _mi_record_pos(info, max_key->key,
                                           max_key->keypart_map, max_key->flag)
-                        : info->state->records + (ha_rows) 1);
+		        : (double) info->state->records);
     res= (end_pos < start_pos ? (ha_rows) 0 :
           (end_pos == start_pos ? (ha_rows) 1 : end_pos-start_pos));
     if (start_pos == HA_POS_ERROR || end_pos == HA_POS_ERROR)
       res=HA_POS_ERROR;
+    else
+    {
+      diff= end_pos - start_pos;
+      if (diff >= 0)
+      {
+        if (!(res= (diff + 0.5)))
+	  res= 1;
+      }
+      else
+        res= 0;
+    }
   }
 
   if (info->s->concurrent_insert)
@@ -115,11 +128,25 @@ ha_rows mi_records_in_range(MI_INFO *info, int inx,
 }
 
 
-	/* Find relative position (in records) for key in index-tree */
+/*
+  To find an approximate relative position of a key tuple among all index
+  key tuples would not be hard if we considered B-trees where all key
+  tuples were contained only in leaf nodes. If we consider a B-tree where
+  key tuples are stored also in non-leaf nodes we have to convert such
+  tree into the tree of the first type. The transformation procedure is
+  simple: the key tuple k goes alter the last key tuple in the most right
+  sub-tree pointer to which is coupled with k. As a result of this
+  transformation each leaf node except the most right one in the tree will
+  contain one extra key tuple following those originally belonging to
+  the leaf.
+*/
+
+
+/* Find relative position (in records) for key in index-tree */
 
-static ha_rows _mi_record_pos(MI_INFO *info, const uchar *key,
-                              key_part_map keypart_map,
-			      enum ha_rkey_function search_flag)
+static double _mi_record_pos(MI_INFO *info, const uchar *key,
+                             key_part_map keypart_map,
+                             enum ha_rkey_function search_flag)
 {
   uint inx=(uint) info->lastinx, nextflag, key_len;
   MI_KEYDEF *keyinfo=info->s->keyinfo+inx;
@@ -175,11 +202,11 @@ static ha_rows _mi_record_pos(MI_INFO *info, const uchar *key,
   */
   pos=_mi_search_pos(info,keyinfo,key_buff,key_len,
 		     nextflag | SEARCH_SAVE_BUFF | SEARCH_UPDATE,
-		     info->s->state.key_root[inx]);
+		     info->s->state.key_root[inx], TRUE);
   if (pos >= 0.0)
   {
-    DBUG_PRINT("exit",("pos: %ld",(ulong) (pos*info->state->records)));
-    DBUG_RETURN((ulong) (pos*info->state->records+0.5));
+    DBUG_PRINT("exit",("pos: %g",(pos*info->state->records)));
+    DBUG_RETURN(pos*info->state->records);
   }
   DBUG_RETURN(HA_POS_ERROR);
 }
@@ -191,7 +218,7 @@ static ha_rows _mi_record_pos(MI_INFO *info, const uchar *key,
 static double _mi_search_pos(register MI_INFO *info,
 			     register MI_KEYDEF *keyinfo,
 			     uchar *key, uint key_len, uint nextflag,
-			     register my_off_t pos)
+			     register my_off_t pos, my_bool last_in_level)
 {
   int flag;
   uint nod_flag,keynr,UNINIT_VAR(max_keynr);
@@ -222,7 +249,8 @@ static double _mi_search_pos(register MI_INFO *info,
     if (flag > 0 && ! nod_flag)
       offset= 1.0;
     else if ((offset=_mi_search_pos(info,keyinfo,key,key_len,nextflag,
-				    _mi_kpos(nod_flag,keypos))) < 0)
+				    _mi_kpos(nod_flag,keypos),
+                                    last_in_level && after_key)) < 0)
       DBUG_RETURN(offset);
   }
   else
@@ -241,13 +269,15 @@ static double _mi_search_pos(register MI_INFO *info,
         Matches keynr + [0-1]
       */
       if ((offset=_mi_search_pos(info,keyinfo,key,key_len,SEARCH_FIND,
-				 _mi_kpos(nod_flag,keypos))) < 0)
+				 _mi_kpos(nod_flag,keypos),
+                                 last_in_level && after_key)) < 0)
 	DBUG_RETURN(offset);			/* Read error */
     }
   }
   DBUG_PRINT("info",("keynr: %d  offset: %g  max_keynr: %d  nod: %d  flag: %d",
 		     keynr,offset,max_keynr,nod_flag,flag));
-  DBUG_RETURN((keynr+offset)/(max_keynr+1));
+  DBUG_RETURN((keynr+offset-MY_TEST(!nod_flag))/
+              (max_keynr+MY_TEST(nod_flag || !last_in_level)));
 err:
   DBUG_PRINT("exit",("Error: %d",my_errno));
   DBUG_RETURN (-1.0);
diff --git a/storage/myisam/mi_rkey.c b/storage/myisam/mi_rkey.c
index 1dddb8b49ad..c0f9b2046fc 100644
--- a/storage/myisam/mi_rkey.c
+++ b/storage/myisam/mi_rkey.c
@@ -120,7 +120,9 @@ int mi_rkey(MI_INFO *info, uchar *buf, int inx, const uchar *key,
               (search_flag != HA_READ_KEY_EXACT ||
               last_used_keyseg != keyinfo->seg + keyinfo->keysegs)) ||
              (info->index_cond_func && 
-              (res= mi_check_index_cond(info, inx, buf)) == ICP_NO_MATCH))
+              (res= mi_check_index_cond(info, inx, buf)) == ICP_NO_MATCH) ||
+	     (mi_check_rowid_filter_is_active(info) &&
+	      !mi_check_rowid_filter(info)))
       {
         uint not_used[2];
         /*
diff --git a/storage/myisam/mi_rnext.c b/storage/myisam/mi_rnext.c
index 6e3701abe6b..c3af209fd71 100644
--- a/storage/myisam/mi_rnext.c
+++ b/storage/myisam/mi_rnext.c
@@ -102,7 +102,9 @@ int mi_rnext(MI_INFO *info, uchar *buf, int inx)
     while ((info->s->concurrent_insert &&
             info->lastpos >= info->state->data_file_length) ||
            (info->index_cond_func &&
-           (icp_res= mi_check_index_cond(info, inx, buf)) == ICP_NO_MATCH))
+            (icp_res= mi_check_index_cond(info, inx, buf)) == ICP_NO_MATCH) ||
+           (mi_check_rowid_filter_is_active(info) &&
+	    !mi_check_rowid_filter(info)))
     {
       /*
         If we are at the last key on the key page, allow writers to
diff --git a/storage/myisam/mi_rnext_same.c b/storage/myisam/mi_rnext_same.c
index d6856459ae7..ac818bfa2da 100644
--- a/storage/myisam/mi_rnext_same.c
+++ b/storage/myisam/mi_rnext_same.c
@@ -95,7 +95,9 @@ int mi_rnext_same(MI_INFO *info, uchar *buf)
         */
         if (info->lastpos < info->state->data_file_length && 
             (!info->index_cond_func || 
-             (icp_res= mi_check_index_cond(info, inx, buf)) != ICP_NO_MATCH))
+             (icp_res= mi_check_index_cond(info, inx, buf)) != ICP_NO_MATCH) &&
+            (!mi_check_rowid_filter_is_active(info) ||
+	     mi_check_rowid_filter(info)))
           break;
       }
   }
diff --git a/storage/myisam/mi_rprev.c b/storage/myisam/mi_rprev.c
index 27fbda95574..a78bab6a040 100644
--- a/storage/myisam/mi_rprev.c
+++ b/storage/myisam/mi_rprev.c
@@ -59,7 +59,9 @@ int mi_rprev(MI_INFO *info, uchar *buf, int inx)
     while ((share->concurrent_insert && 
             info->lastpos >= info->state->data_file_length) ||
            (info->index_cond_func &&
-            (icp_res= mi_check_index_cond(info, inx, buf)) == ICP_NO_MATCH))
+            (icp_res= mi_check_index_cond(info, inx, buf)) == ICP_NO_MATCH) ||
+	   (mi_check_rowid_filter_is_active(info) &&
+	    !mi_check_rowid_filter(info)))
     {
       /*
         If we are at the last (i.e. first?) key on the key page, 
diff --git a/storage/myisam/myisamdef.h b/storage/myisam/myisamdef.h
index e350626f192..d51e0f9f9e1 100644
--- a/storage/myisam/myisamdef.h
+++ b/storage/myisam/myisamdef.h
@@ -305,6 +305,9 @@ struct st_myisam_info
   my_bool create_unique_index_by_sort;
   index_cond_func_t index_cond_func;   /* Index condition function */
   void *index_cond_func_arg;           /* parameter for the func */
+  rowid_filter_func_t rowid_filter_func;   /* rowid filter check function */
+  rowid_filter_func_t rowid_filter_is_active_func;  /* is activefunction */
+  void *rowid_filter_func_arg;             /* parameter for the func */
   THR_LOCK_DATA lock;
   uchar *rtree_recursion_state;         /* For RTREE */
   int rtree_recursion_depth;
@@ -724,14 +727,20 @@ int mi_munmap_file(MI_INFO *info);
 void mi_remap_file(MI_INFO *info, my_off_t size);
 
 ICP_RESULT mi_check_index_cond(MI_INFO *info, uint keynr, uchar *record);
+int mi_check_rowid_filter(MI_INFO *info);
+int mi_check_rowid_filter_is_active(MI_INFO *info);
     /* Functions needed by mi_check */
 int killed_ptr(HA_CHECK *param);
 void mi_check_print_error(HA_CHECK *param, const char *fmt, ...);
 void mi_check_print_warning(HA_CHECK *param, const char *fmt, ...);
 void mi_check_print_info(HA_CHECK *param, const char *fmt, ...);
 pthread_handler_t thr_find_all_keys(void *arg);
-extern void mi_set_index_cond_func(MI_INFO *info, index_cond_func_t func,
+extern void mi_set_index_cond_func(MI_INFO *info, index_cond_func_t check_func,
                                    void *func_arg);
+extern void mi_set_rowid_filter_func(MI_INFO *info,
+                                     rowid_filter_func_t check_func,
+                                     rowid_filter_func_t is_active_func,
+                                     void *func_arg);
 int flush_blocks(HA_CHECK *param, KEY_CACHE *key_cache, File file,
                  ulonglong *dirty_part_map);