[Commits] f5a5ac4: MDEV-9531: GROUP_CONCAT with ORDER BY inside takes a lot of memory while it's executed

Oleksandr Byelkin sanja at mariadb.com
Mon Sep 26 17:21:18 EEST 2016


revision-id: f5a5ac49b5ff7b04aa816d33ca44d9fe88a94498 (mariadb-10.1.17-23-gf5a5ac4)
parent(s): d30809a3cde823ad696304a941afe5a562bfa3ed
committer: Oleksandr Byelkin
timestamp: 2016-09-26 16:21:18 +0200
message:

MDEV-9531: GROUP_CONCAT with ORDER BY inside takes a lot of memory while it's executed

Limitation added to Red-Black tree.

---
 include/my_tree.h                    |  14 ++-
 mysql-test/r/group_concat_big.result |   6 ++
 mysql-test/t/group_concat_big.test   |   6 ++
 mysys/tree.c                         | 164 +++++++++++++++++++++++++----------
 sql/item_sum.cc                      |  43 +++++++--
 5 files changed, 178 insertions(+), 55 deletions(-)

diff --git a/include/my_tree.h b/include/my_tree.h
index 02cab02..c255653 100644
--- a/include/my_tree.h
+++ b/include/my_tree.h
@@ -57,11 +57,14 @@ typedef struct st_tree_element {
 } TREE_ELEMENT;
 
 #define ELEMENT_CHILD(element, offs) (*(TREE_ELEMENT**)((char*)element + offs))
+#define ELEMENT_CHILD_PTR(element, offs) ((TREE_ELEMENT**)((char*)element + offs))
 
 typedef struct st_tree {
   TREE_ELEMENT *root,null_element;
   TREE_ELEMENT **parents[MAX_TREE_HEIGHT];
+  TREE_ELEMENT *free_element;
   uint offset_to_key,elements_in_tree,size_of_element;
+  uint elements_limit, del_direction;
   size_t memory_limit, allocated;
   qsort_cmp2 compare;
   void *custom_arg;
@@ -73,10 +76,13 @@ typedef struct st_tree {
 } TREE;
 
 	/* Functions on whole tree */
-void init_tree(TREE *tree, size_t default_alloc_size, size_t memory_limit,
-               int size, qsort_cmp2 compare,
-	       tree_element_free free_element, void *custom_arg,
-               myf my_flags);
+void
+init_tree2(TREE *tree, size_t default_alloc_size, size_t memory_limit,
+           int elements_limit, int size, qsort_cmp2 compare,
+           tree_element_free free_element, void *custom_arg, myf my_flags);
+#define init_tree(A, B, C, D, E, F, G, H) \
+  init_tree2(A, B, C, 0, D, E, F, G, H)
+
 void delete_tree(TREE*);
 void reset_tree(TREE*);
 
diff --git a/mysql-test/r/group_concat_big.result b/mysql-test/r/group_concat_big.result
new file mode 100644
index 0000000..4de0ebb
--- /dev/null
+++ b/mysql-test/r/group_concat_big.result
@@ -0,0 +1,6 @@
+SELECT GROUP_CONCAT( seq, seq, seq, seq, seq, seq, seq, seq ORDER BY
+2,1,3,4,6,5,8,7 ) AS cfield1 FROM seq_1_to_50000000;
+cfield1
+11111111,22222222,33333333,44444444,55555555,66666666,77777777,88888888,99999999,1010101010101010,1111111111111111,1212121212121212,1313131313131313,1414141414141414,1515151515151515,1616161616161616,1717171717171717,1818181818181818,1919191919191919,2020202020202020,2121212121212121,2222222222222222,2323232323232323,2424242424242424,2525252525252525,2626262626262626,2727272727272727,2828282828282828,2929292929292929,3030303030303030,3131313131313131,3232323232323232,3333333333333333,3434343434343434,3535353535353535,3636363636363636,3737373737373737,3838383838383838,3939393939393939,4040404040404040,4141414141414141,4242424242424242,4343434343434343,4444444444444444,4545454545454545,4646464646464646,4747474747474747,4848484848484848,4949494949494949,5050505050505050,5151515151515151,5252525252525252,5353535353535353,5454545454545454,5555555555555555,5656565656565656,5757575757575757,5858585858585858,5959595959595959,6060606060606060,6161616161616161,6262626262626262,6363636
 363636363,6464646464646464,65656565
+Warnings:
+Warning	1260	Row 65 was cut by GROUP_CONCAT()
diff --git a/mysql-test/t/group_concat_big.test b/mysql-test/t/group_concat_big.test
new file mode 100644
index 0000000..c3bd2dc
--- /dev/null
+++ b/mysql-test/t/group_concat_big.test
@@ -0,0 +1,6 @@
+
+--source include/big_test.inc
+--source include/have_sequence.inc
+
+SELECT GROUP_CONCAT( seq, seq, seq, seq, seq, seq, seq, seq ORDER BY
+2,1,3,4,6,5,8,7 ) AS cfield1 FROM seq_1_to_50000000;
diff --git a/mysys/tree.c b/mysys/tree.c
index ab810c6..1ab32a2 100644
--- a/mysys/tree.c
+++ b/mysys/tree.c
@@ -84,10 +84,10 @@ static void rb_delete_fixup(TREE *tree,TREE_ELEMENT ***parent);
 static int test_rb_tree(TREE_ELEMENT *element);
 #endif
 
-void init_tree(TREE *tree, size_t default_alloc_size, size_t memory_limit,
-               int size, qsort_cmp2 compare,
-	       tree_element_free free_element, void *custom_arg,
-               myf my_flags)
+void init_tree2(TREE *tree, size_t default_alloc_size,
+                size_t memory_limit, int el_limit,
+                int size, qsort_cmp2 compare, tree_element_free free_element,
+                void *custom_arg, myf my_flags)
 {
   DBUG_ENTER("init_tree");
   DBUG_PRINT("enter",("tree: 0x%lx  size: %d", (long) tree, size));
@@ -96,6 +96,7 @@ void init_tree(TREE *tree, size_t default_alloc_size, size_t memory_limit,
     default_alloc_size= DEFAULT_ALLOC_SIZE;
   default_alloc_size= MY_ALIGN(default_alloc_size, DEFAULT_ALIGN_SIZE);
   bzero((uchar*) &tree->null_element,sizeof(tree->null_element));
+  tree->free_element= 0;
   tree->root= &tree->null_element;
   tree->compare=compare;
   tree->size_of_element= size > 0 ? (uint) size : 0;
@@ -107,6 +108,20 @@ void init_tree(TREE *tree, size_t default_alloc_size, size_t memory_limit,
   tree->null_element.colour=BLACK;
   tree->null_element.left=tree->null_element.right=0;
   tree->my_flags= my_flags;
+  if (el_limit < 0)
+  {
+    //free first
+    tree->del_direction= ((char*)&tree->null_element.left) -
+      ((char*)&tree->null_element);
+    tree->elements_limit= -el_limit;
+  }
+  else
+  {
+    //free last
+    tree->del_direction= ((char*)&tree->null_element.right) -
+      ((char*)&tree->null_element);
+    tree->elements_limit= el_limit;
+  }
   tree->flag= 0;
   if (!free_element && size >= 0 &&
       ((uint) size <= sizeof(void*) || ((uint) size & (sizeof(void*)-1))))
@@ -158,6 +173,10 @@ static void free_tree(TREE *tree, myf free_flags)
       free_root(&tree->mem_root, free_flags);
     }
   }
+  if (tree->free_element && tree->free)
+      (*tree->free)(tree->free_element, free_free,
+                    tree->custom_arg);
+  tree->free_element= 0;
   tree->root= &tree->null_element;
   tree->elements_in_tree=0;
   tree->allocated=0;
@@ -190,6 +209,48 @@ static void delete_tree_element(TREE *tree, TREE_ELEMENT *element)
   }
 }
 
+/**
+  exclude leaf node from the tree
+
+  @param tree            Tree where we deleting
+  @param parent          Pointer from parent to the element we are excluding
+*/
+
+void tree_exclude(TREE *tree, TREE_ELEMENT ***parent)
+{
+  int remove_colour;
+  TREE_ELEMENT ***org_parent, *nod;
+  TREE_ELEMENT *element= **parent;
+  if (element->left == &tree->null_element)
+  {
+    (**parent)=element->right;
+    remove_colour= element->colour;
+  }
+  else if (element->right == &tree->null_element)
+  {
+    (**parent)=element->left;
+    remove_colour= element->colour;
+  }
+  else
+  {
+    org_parent= parent;
+    *++parent= &element->right; nod= element->right;
+    while (nod->left != &tree->null_element)
+    {
+      *++parent= &nod->left; nod= nod->left;
+    }
+    (**parent)=nod->right;		/* unlink nod from tree */
+    remove_colour= nod->colour;
+    org_parent[0][0]=nod;		/* put y in place of element */
+    org_parent[1]= &nod->right;
+    nod->left=element->left;
+    nod->right=element->right;
+    nod->colour=element->colour;
+  }
+  if (remove_colour == BLACK)
+    rb_delete_fixup(tree,parent);
+}
+
 
 /*
   insert, search and delete of elements
@@ -203,7 +264,34 @@ TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size,
                           void* custom_arg)
 {
   int cmp;
-  TREE_ELEMENT *element,***parent;
+  TREE_ELEMENT *element, ***parent;
+
+  if (tree->elements_limit &&
+      tree->elements_in_tree >= tree->elements_limit)
+  {
+    /*
+      The limit reached so we should remove one.
+      It is done on the very beginning because:
+      1) "parents" will be used
+      2) removing make incorrect search pass
+      If we will not insert now, we leave freed element for future use
+    */
+    // It is not checked with keys stored in the tree. That who need should,
+    // check it
+    DBUG_ASSERT(key_size == 0);
+
+    parent= tree->parents;
+    *parent = &tree->root; element= tree->root;
+    while (element != &tree->null_element)
+    {
+      *++parent= ELEMENT_CHILD_PTR(element, tree->del_direction);
+      element= ELEMENT_CHILD(element, tree->del_direction);
+    }
+    parent--;
+    tree->free_element= **parent;
+    tree_exclude(tree, parent);
+    tree->elements_in_tree--;
+  }
 
   parent= tree->parents;
   *parent = &tree->root; element= tree->root;
@@ -228,21 +316,31 @@ TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size,
     if (tree->flag & TREE_ONLY_DUPS)
       return((TREE_ELEMENT *) 1);
     alloc_size=sizeof(TREE_ELEMENT)+key_size+tree->size_of_element;
-    tree->allocated+=alloc_size;
-
-    if (tree->memory_limit && tree->elements_in_tree
-                           && tree->allocated > tree->memory_limit)
+    if (tree->free_element)
     {
-      reset_tree(tree);
-      return tree_insert(tree, key, key_size, custom_arg);
+      DBUG_ASSERT(key_size == 0);
+      element= tree->free_element;
+      tree->free_element= NULL;
     }
+    else
+    {
+      tree->allocated+=alloc_size;
 
+      if (tree->memory_limit && tree->elements_in_tree
+          && tree->allocated > tree->memory_limit)
+      {
+        reset_tree(tree);
+        return tree_insert(tree, key, key_size, custom_arg);
+      }
+
+      if (tree->with_delete)
+        element=(TREE_ELEMENT *) my_malloc(alloc_size,
+                                           MYF(tree->my_flags | MY_WME));
+      else
+        element=(TREE_ELEMENT *) alloc_root(&tree->mem_root,alloc_size);
+    }
     key_size+=tree->size_of_element;
-    if (tree->with_delete)
-      element=(TREE_ELEMENT *) my_malloc(alloc_size,
-                                         MYF(tree->my_flags | MY_WME));
-    else
-      element=(TREE_ELEMENT *) alloc_root(&tree->mem_root,alloc_size);
+
     if (!element)
       return(NULL);
     **parent=element;
@@ -277,10 +375,11 @@ TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size,
   return element;
 }
 
+
 int tree_delete(TREE *tree, void *key, uint key_size, void *custom_arg)
 {
-  int cmp,remove_colour;
-  TREE_ELEMENT *element,***parent, ***org_parent, *nod;
+  int cmp;
+  TREE_ELEMENT *element,***parent;
   if (!tree->with_delete)
     return 1;					/* not allowed */
 
@@ -302,34 +401,7 @@ int tree_delete(TREE *tree, void *key, uint key_size, void *custom_arg)
       *++parent = &element->left; element= element->left;
     }
   }
-  if (element->left == &tree->null_element)
-  {
-    (**parent)=element->right;
-    remove_colour= element->colour;
-  }
-  else if (element->right == &tree->null_element)
-  {
-    (**parent)=element->left;
-    remove_colour= element->colour;
-  }
-  else
-  {
-    org_parent= parent;
-    *++parent= &element->right; nod= element->right;
-    while (nod->left != &tree->null_element)
-    {
-      *++parent= &nod->left; nod= nod->left;
-    }
-    (**parent)=nod->right;		/* unlink nod from tree */
-    remove_colour= nod->colour;
-    org_parent[0][0]=nod;		/* put y in place of element */
-    org_parent[1]= &nod->right;
-    nod->left=element->left;
-    nod->right=element->right;
-    nod->colour=element->colour;
-  }
-  if (remove_colour == BLACK)
-    rb_delete_fixup(tree,parent);
+  tree_exclude(tree, parent);
   if (tree->free)
     (*tree->free)(ELEMENT_KEY(tree,element), free_free, tree->custom_arg);
   tree->allocated-= sizeof(TREE_ELEMENT) + tree->size_of_element + key_size;
diff --git a/sql/item_sum.cc b/sql/item_sum.cc
index 540eefc..97b2b94 100644
--- a/sql/item_sum.cc
+++ b/sql/item_sum.cc
@@ -3511,17 +3511,50 @@ bool Item_func_group_concat::setup(THD *thd)
 
   if (arg_count_order)
   {
+    uint min_rec_length= 1; //at least 1 byte per rec (coma)
+    {
+      List_iterator_fast<Item> li(all_fields);
+      Item *item;
+      while ((item= li++))
+      {
+        switch (item->result_type())
+        {
+          case STRING_RESULT:
+            break;  // could be empty string
+          case DECIMAL_RESULT:
+          case REAL_RESULT:
+            min_rec_length+=2;
+            break;
+          case INT_RESULT:
+            min_rec_length++;
+            break;
+          case TIME_RESULT:
+            min_rec_length+=6;
+            break;
+          default:
+          case ROW_RESULT:
+            DBUG_ASSERT(0);
+            break;
+        }
+      }
+    }
     tree= &tree_base;
+    long long elements_limit=
+      (thd->variables.group_concat_max_len + 0.5)/min_rec_length;
+    if (elements_limit > INT_MAX)
+      elements_limit= INT_MAX;
+    DBUG_PRINT("info", ("tree limit is %lld", elements_limit));
     /*
       Create a tree for sorting. The tree is used to sort (according to the
       syntax of this function). If there is no ORDER BY clause, we don't
       create this tree.
     */
-    init_tree(tree, (uint) MY_MIN(thd->variables.max_heap_table_size,
-                               thd->variables.sortbuff_size/16), 0,
-              tree_key_length, 
-              group_concat_key_cmp_with_order, NULL, (void*) this,
-              MYF(MY_THREAD_SPECIFIC));
+    init_tree2(tree, (uint) MY_MIN(thd->variables.max_heap_table_size,
+                                   thd->variables.sortbuff_size/16),
+               0, (int)elements_limit,
+               tree_key_length,
+               group_concat_key_cmp_with_order, NULL, (void*) this,
+               MYF(MY_THREAD_SPECIFIC));
   }
 
   if (distinct)


More information about the commits mailing list