MDEV-21829: Use packed sort keys in Unique objects10.5-varun2

The task deals with packing the values stored in the Unique tree for each record.

The changes brought by this feature is:

  1) Unique tree can have dynamic length keys
  2) Format of keys looks like
     <key_length> <packed_value1> <packed_value2> ....... <packed_valueN>

Unique class is currently used in

1) agg_func(DISTINCT col)
   Here most aggregate functions like SUM, AVG accept only fixed size arguments
   so it is not beneficial to use packing for these. Packing is done for
   COUNT and GROUP_CONCAT (or JSON_ARRAYAGG) aggregate function as these are meaningful

2) index-merge stores row-ids
   index merge stores row-ids which are of fixed size, so packing is not required

3) Engine Independent Table statistics
   Packing is done here for variable length data types

This task is an extension to MDEV-21580.

1 files changed, 93 insertions, 21 deletions

diff --git a/sql/sql_statistics.cc b/sql/sql_statistics.cc
index 879955af723..bf6cebbf7e8 100644
--- a/sql/sql_statistics.cc
+++ b/sql/sql_statistics.cc
@@ -1570,7 +1570,16 @@ public:
       return 0;
     if (count > bucket_capacity * (curr_bucket + 1))
     {
-      column->store_field_value((uchar *) elem, col_length);
+      uchar *to= (uchar* )elem;
+      if (column->is_packable())
+      {
+        column->unpack(column->ptr,
+                       to + Unique::size_of_length_field,
+                       to + Unique::read_packed_length(to), 0);
+      }
+      else
+        column->store_field_value(to, col_length);
+
       histogram->set_value(curr_bucket,
                            column->pos_in_interval(min_value, max_value)); 
       curr_bucket++;
@@ -1646,13 +1655,11 @@ public:
     of the parameters to be passed to the constructor of the Unique object. 
   */  
 
-  Count_distinct_field(Field *field, size_t max_heap_table_size)
+  Count_distinct_field(Field *field)
   {
     table_field= field;
-    tree_key_length= field->pack_length();
-
-    tree= new Unique((qsort_cmp2) simple_str_key_cmp, (void*) field,
-                     tree_key_length, max_heap_table_size, 1);
+    tree_key_length= 0;
+    tree= NULL;
   }
 
   virtual ~Count_distinct_field()
@@ -1670,6 +1677,48 @@ public:
     return (tree != NULL);
   }
 
+
+  /*
+    @brief
+      Create and setup the Unique object for the column
+
+    @param
+      thd                    Thread structure
+      max_heap_table_size    max allowed size of the unique tree
+  */
+  bool setup(THD *thd, size_t max_heap_table_size)
+  {
+    if (table_field->is_packable())
+    {
+      tree_key_length= table_field->max_packed_col_length(table_field->pack_length());
+
+      tree_key_length+= Unique::size_of_length_field;
+      tree= new Unique((qsort_cmp2) simple_packed_str_key_cmp, (void*) this,
+                       tree_key_length, max_heap_table_size, 1, TRUE);
+    }
+    else
+    {
+      if (table_field->type() == MYSQL_TYPE_BIT)
+      {
+        tree_key_length= sizeof(ulonglong);
+        tree= new Unique((qsort_cmp2) simple_ulonglong_key_cmp,
+                         (void*) &tree_key_length,
+                         tree_key_length, max_heap_table_size, 1, FALSE);
+      }
+      else
+      {
+        tree_key_length= table_field->pack_length();
+        tree= new Unique((qsort_cmp2) simple_str_key_cmp, (void*) table_field,
+                         tree_key_length, max_heap_table_size, 1, FALSE);
+      }
+    }
+    if (!tree)
+      return true;  // OOM
+
+    return tree->setup(thd, table_field);
+  }
+
+
   /*
     @brief
     Add the value of 'field' to the container of the Unique object 'tree'
@@ -1677,7 +1726,20 @@ public:
   virtual bool add()
   {
     table_field->mark_unused_memory_as_defined();
-    return tree->unique_add(table_field->ptr);
+    uchar *orig_to= table_field->ptr;
+    DBUG_ASSERT(tree);
+
+    uint length= tree->get_size();
+    if (tree->is_packed())
+    {
+      uchar *to;
+      orig_to= to= tree->get_packed_rec_ptr();
+      to+= Unique::size_of_length_field;
+      to+= table_field->make_packed_record_field(to);
+      length= static_cast<uint>(to - orig_to);
+      Unique::store_packed_length(orig_to, length);
+    }
+    return tree->unique_add(orig_to, length);
   }
 
   /*
@@ -1733,16 +1795,31 @@ public:
     return table_field->collected_stats->histogram.get_values();
   }
 
+  static int simple_packed_str_key_cmp(void* arg, uchar* key1, uchar* key2);
+  static int simple_ulonglong_key_cmp(void* arg, uchar* key1, uchar* key2);
+
 };
 
 
-static
-int simple_ulonglong_key_cmp(void* arg, uchar* key1, uchar* key2)
+int Count_distinct_field::simple_ulonglong_key_cmp(void* arg,
+                                                   uchar* key1, uchar* key2)
 {
   ulonglong *val1= (ulonglong *) key1;
   ulonglong *val2= (ulonglong *) key2;
   return *val1 > *val2 ? 1 : *val1 == *val2 ? 0 : -1; 
 }
+
+
+/*
+  @brief
+    Compare function for packed keys
+*/
+int Count_distinct_field::simple_packed_str_key_cmp(void* arg,
+                                                    uchar* key1, uchar* key2)
+{
+  Count_distinct_field *compare_arg= (Count_distinct_field*)arg;
+  return compare_arg->tree->compare_packed_keys(key1, key2);
+}
   
 
 /* 
@@ -1755,20 +1832,12 @@ class Count_distinct_field_bit: public Count_distinct_field
 {
 public:
 
-  Count_distinct_field_bit(Field *field, size_t max_heap_table_size)
-  {
-    table_field= field;
-    tree_key_length= sizeof(ulonglong);
-
-    tree= new Unique((qsort_cmp2) simple_ulonglong_key_cmp,
-                     (void*) &tree_key_length,
-                     tree_key_length, max_heap_table_size, 1);
-  }
+  Count_distinct_field_bit(Field *field): Count_distinct_field(field){}
 
   bool add()
   {
     longlong val= table_field->val_int();   
-    return tree->unique_add(&val);
+    return tree->unique_add(&val, tree->get_size());
   }
 };
 
@@ -2344,8 +2413,11 @@ void Column_statistics_collected::init(THD *thd, Field *table_field)
   {
     count_distinct=
       table_field->type() == MYSQL_TYPE_BIT ?
-      new Count_distinct_field_bit(table_field, max_heap_table_size) :
-      new Count_distinct_field(table_field, max_heap_table_size);
+      new Count_distinct_field_bit(table_field) :
+      new Count_distinct_field(table_field);
+
+    if (count_distinct && count_distinct->setup(thd, max_heap_table_size))
+      count_distinct= NULL;
   }
   if (count_distinct && !count_distinct->exists())
     count_distinct= NULL;