MDEV-9764: MariaDB does not limit memory used for range optimization

A partial backport of 67f21fb3a077dedfd14b9ca720e926c55e682f93,
Bug#22283790: RANGE OPTIMIZER UTILIZES TOO MUCH MEMORY WITH MANY OR CONDITIONS

The backported part changes SEL_TREE::keys from being an array of
MAX_KEY elements (64*8=512 bytes) to a Mem_root_array<SEL_ARG*> (32 bytes +
alloc'ed array of as many elements as we need).

The patch doesn't fix the "not limiting memory" part, but the memory usage
is much lower with it.

1 files changed, 67 insertions, 0 deletions

diff --git a/sql/mem_root_array.h b/sql/mem_root_array.h
index 2dcc475cd7b..5daeedadcba 100644
--- a/sql/mem_root_array.h
+++ b/sql/mem_root_array.h
@@ -47,12 +47,21 @@ template<typename Element_type, bool has_trivial_destructor>
 class Mem_root_array
 {
 public:
+  /// Convenience typedef, same typedef name as std::vector
+  typedef Element_type value_type;
+
   Mem_root_array(MEM_ROOT *root)
     : m_root(root), m_array(NULL), m_size(0), m_capacity(0)
   {
     DBUG_ASSERT(m_root != NULL);
   }
 
+  Mem_root_array(MEM_ROOT *root, size_t n, const value_type &val= value_type())
+    : m_root(root), m_array(NULL), m_size(0), m_capacity(0)
+  {
+    resize(n, val);
+  }
+
   ~Mem_root_array()
   {
     clear();
@@ -70,6 +79,12 @@ public:
     return m_array[n];
   }
 
+  Element_type &operator[](size_t n) { return at(n); }
+  const Element_type &operator[](size_t n) const { return at(n); }
+
+  Element_type &back() { return at(size() - 1); }
+  const Element_type &back() const { return at(size() - 1); }
+
   // Returns a pointer to the first element in the array.
   Element_type *begin() { return &m_array[0]; }
 
@@ -155,6 +170,58 @@ public:
     return false;
   }
 
+  /**
+    Removes the last element in the array, effectively reducing the
+    container size by one. This destroys the removed element.
+   */
+  void pop_back()
+  {
+    DBUG_ASSERT(!empty());
+    if (!has_trivial_destructor)
+      back().~Element_type();
+    m_size-= 1;
+  }
+
+  /**
+    Resizes the container so that it contains n elements.
+
+    If n is smaller than the current container size, the content is
+    reduced to its first n elements, removing those beyond (and
+    destroying them).
+
+    If n is greater than the current container size, the content is
+    expanded by inserting at the end as many elements as needed to
+    reach a size of n. If val is specified, the new elements are
+    initialized as copies of val, otherwise, they are
+    value-initialized.
+
+    If n is also greater than the current container capacity, an automatic
+    reallocation of the allocated storage space takes place.
+
+    Notice that this function changes the actual content of the
+    container by inserting or erasing elements from it.
+   */
+  void resize(size_t n, const value_type &val= value_type())
+  {
+    if (n == m_size)
+      return;
+    if (n > m_size)
+    {
+      if (!reserve(n))
+      {
+        while (n != m_size)
+          push_back(val);
+      }
+      return;
+    }
+    if (!has_trivial_destructor)
+    {
+      while (n != m_size)
+        pop_back();
+    }
+    m_size= n;
+  }
+
   size_t capacity()     const { return m_capacity; }
   size_t element_size() const { return sizeof(Element_type); }
   bool   empty()        const { return size() == 0; }