MDEV-16934 Query with very large IN clause lists runs slowly

This patch introduces support for the system variable eq_range_index_dive_limit
that existed in MySQL starting from 5.6. The variable sets a limit for
index dives into equality ranges. Index dives are performed by optimizer
to estimate the number of rows in range scans. Index dives usually provide
good estimate but they are pretty expensive. To estimate the number of rows
in equality ranges statistical data on indexes can be employed. Its usage gives
not so good estimates but it's cheap. So if the number of equality dives
required by an index scan exceeds the set limit no dives for equality
ranges are performed by the optimizer for this index.

As the new system variable is introduced in a stable version the default
value for it is set to a special value meaning there is no limit for the number
of index dives performed by the optimizer.

The patch partially uses the MySQL code for WL 5957
'Statistics-based Range optimization for many ranges'.

1 files changed, 37 insertions, 17 deletions

diff --git a/sql/opt_range_mrr.cc b/sql/opt_range_mrr.cc
index ace6208fd77..c7e4496f2c1 100644
--- a/sql/opt_range_mrr.cc
+++ b/sql/opt_range_mrr.cc
@@ -72,6 +72,7 @@ typedef struct st_sel_arg_range_seq
 range_seq_t sel_arg_range_seq_init(void *init_param, uint n_ranges, uint flags)
 {
   SEL_ARG_RANGE_SEQ *seq= (SEL_ARG_RANGE_SEQ*)init_param;
+  seq->param->range_count=0;
   seq->at_start= TRUE;
   seq->stack[0].key_tree= NULL;
   seq->stack[0].min_key= seq->param->min_key;
@@ -272,25 +273,44 @@ walk_up_n_right:
       key_info= NULL;
     else
       key_info= &seq->param->table->key_info[seq->real_keyno];
-    
+
     /*
-      Conditions below:
-       (1) - range analysis is used for estimating condition selectivity
-       (2) - This is a unique key, and we have conditions for all its 
-             user-defined key parts.
-       (3) - The table uses extended keys, this key covers all components,
-             and we have conditions for all key parts.
+      This is an equality range (keypart_0=X and ... and keypart_n=Z) if
+        (1) - There are no flags indicating open range (e.g.,
+              "keypart_x > y") or GIS.
+        (2) - The lower bound and the upper bound of the range has the
+              same value (min_key == max_key).
     */
-    if (!(cur->min_key_flag & ~NULL_RANGE) && !cur->max_key_flag &&
-        (!key_info ||   // (1)
-         ((uint)key_tree->part+1 == key_info->user_defined_key_parts && // (2)
-	  key_info->flags & HA_NOSAME) ||                               // (2)
-         ((key_info->flags & HA_EXT_NOSAME) &&                 // (3)
-          (uint)key_tree->part+1 == key_info->ext_key_parts)  // (3)
-        ) &&
-        range->start_key.length == range->end_key.length &&
-        !memcmp(seq->param->min_key,seq->param->max_key,range->start_key.length))
-      range->range_flag= UNIQUE_RANGE | (cur->min_key_flag & NULL_RANGE);
+    const uint is_open_range =
+        (NO_MIN_RANGE | NO_MAX_RANGE | NEAR_MIN | NEAR_MAX | GEOM_FLAG);
+    const bool is_eq_range_pred =
+        !(cur->min_key_flag & is_open_range) &&              // (1)
+        !(cur->max_key_flag & is_open_range) &&              // (1)
+        range->start_key.length == range->end_key.length &&  // (2)
+        !memcmp(seq->param->min_key, seq->param->max_key,    // (2)
+                range->start_key.length);
+
+    if (is_eq_range_pred)
+    {
+      range->range_flag = EQ_RANGE;
+
+      /*
+        Conditions below:
+          (1) - Range analysis is used for estimating condition selectivity
+          (2) - This is a unique key, and we have conditions for all its
+                user-defined key parts.
+          (3) - The table uses extended keys, this key covers all components,
+             and we have conditions for all key parts.
+      */
+      if (
+          !key_info ||                                                   // (1)
+          ((uint)key_tree->part+1 == key_info->user_defined_key_parts && // (2)
+	   key_info->flags & HA_NOSAME) ||                               // (2)
+          ((key_info->flags & HA_EXT_NOSAME) &&                          // (3)
+           (uint)key_tree->part+1 == key_info->ext_key_parts)            // (3)
+         )
+        range->range_flag |= UNIQUE_RANGE | (cur->min_key_flag & NULL_RANGE);
+    }
       
     if (seq->param->is_ror_scan)
     {