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, 345 insertions, 28 deletions

diff --git a/sql/item_sum.cc b/sql/item_sum.cc
index e79344507b2..96b17e74019 100644
--- a/sql/item_sum.cc
+++ b/sql/item_sum.cc
@@ -701,6 +701,32 @@ int Aggregator_distinct::composite_key_cmp(void* arg, uchar* key1, uchar* key2)
 }
 
 
+/**
+  Correctly compare composite keys.
+
+  Used by the Unique class to compare packed keys. Will do correct comparisons
+  for composite keys with various field types.
+
+  @param arg     Pointer to the relevant Aggregator_distinct instance
+  @param key1    left key image
+  @param key2    right key image
+
+  @return        comparison result
+    @retval <0       if key1 < key2
+    @retval =0       if key1 = key2
+    @retval >0       if key1 > key2
+*/
+
+int
+Aggregator_distinct::composite_packed_key_cmp(void* arg,
+                                              uchar* key1, uchar* key2)
+{
+  Aggregator_distinct *aggr= (Aggregator_distinct *) arg;
+  DBUG_ASSERT(aggr->tree);
+  return aggr->tree->compare_packed_keys(key1, key2);
+}
+
+
 /***************************************************************************/
 
 C_MODE_START
@@ -766,13 +792,19 @@ bool Aggregator_distinct::setup(THD *thd)
       return TRUE;
 
     /* Create a table with an unique key over all parameters */
+    uint non_const_items= 0;
     for (uint i=0; i < item_sum->get_arg_count() ; i++)
     {
       Item *item=item_sum->get_arg(i);
       if (list.push_back(item, thd->mem_root))
         return TRUE;                              // End of memory
-      if (item->const_item() && item->is_null())
-        always_null= true;
+      if (item->const_item())
+      {
+        if (item->is_null())
+          always_null= true;
+      }
+      else
+        non_const_items++;
     }
     if (always_null)
       return FALSE;
@@ -861,16 +893,27 @@ bool Aggregator_distinct::setup(THD *thd)
           }
         }
       }
+
+      bool allow_packing= item_sum->is_packing_allowed(table, &tree_key_length);
+
+      if (allow_packing)
+      {
+        compare_key= (qsort_cmp2) composite_packed_key_cmp;
+        cmp_arg= (void*)this;
+      }
+
       DBUG_ASSERT(tree == 0);
       tree= new Unique(compare_key, cmp_arg, tree_key_length,
-                       item_sum->ram_limitation(thd));
+                       item_sum->ram_limitation(thd), 0, allow_packing);
       /*
         The only time tree_key_length could be 0 is if someone does
         count(distinct) on a char(0) field - stupid thing to do,
         but this has to be handled - otherwise someone can crash
         the server with a DoS attack
       */
-      if (! tree)
+      if (!tree || tree->setup(thd, item_sum,
+                               non_const_items, item_sum->get_arg_count(),
+                               TRUE))
         return TRUE;
     }
     return FALSE;
@@ -987,9 +1030,23 @@ bool Aggregator_distinct::add()
     if (copy_funcs(tmp_table_param->items_to_copy, table->in_use))
       return TRUE;
 
-    for (Field **field=table->field ; *field ; field++)
-      if ((*field)->is_real_null(0))
-        return 0;					// Don't count NULL
+    uchar *to= NULL, *orig_to= table->record[0] + table->s->null_bytes;
+    uint packed_length= 0;
+
+    if (is_distinct_packed())
+    {
+      orig_to= to= tree->get_packed_rec_ptr();
+      if ((to= make_packed_record(to)) == NULL)
+        return false;
+      packed_length= static_cast<uint>(to - orig_to);
+      Unique::store_packed_length(orig_to, packed_length);
+    }
+    else
+    {
+      for (Field **field=table->field ; *field ; field++)
+        if ((*field)->is_real_null(0))
+          return 0;         // Don't count NULL
+    }
 
     if (tree)
     {
@@ -999,7 +1056,8 @@ bool Aggregator_distinct::add()
         bloat the tree without providing any valuable info. Besides,
         key_length used to initialize the tree didn't include space for them.
       */
-      return tree->unique_add(table->record[0] + table->s->null_bytes);
+      return tree->unique_add(orig_to, tree->is_packed() ?
+                                       packed_length : tree->get_size());
     }
     if (unlikely((error= table->file->ha_write_tmp_row(table->record[0]))) &&
         table->file->is_fatal_error(error, HA_CHECK_DUP))
@@ -1017,7 +1075,7 @@ bool Aggregator_distinct::add()
       '0' values are also stored in the tree. This doesn't matter
       for SUM(DISTINCT), but is important for AVG(DISTINCT)
     */
-    return tree->unique_add(table->field[0]->ptr);
+    return tree->unique_add(table->field[0]->ptr, tree->get_size());
   }
 }
 
@@ -1778,6 +1836,48 @@ bool Aggregator_distinct::unique_walk_function_for_count(void *element)
 }
 
 
+/*
+  @brief
+    Checks whether the unique tree is packed or not
+
+  @retval
+    TRUE    tree stored packed values
+    FALSE   otherwise
+*/
+
+bool Aggregator_distinct::is_distinct_packed()
+{
+  return tree && tree->is_packed();
+
+}
+
+
+/*
+  @brief
+    Make a record with packed values
+
+  @param
+    to                     buffer to store the packed value
+*/
+uchar *Aggregator_distinct::make_packed_record(uchar *to)
+{
+  to+= Unique::size_of_length_field;
+
+  for (Field **field=table->field ; *field ; field++)
+  {
+    Field *fld= (*field);
+    if (fld->is_real_null(0))
+      return NULL;         // Don't count NULL
+
+    /*
+      Storing the packed values for the non-const fields of the record
+    */
+    to+= fld->make_packed_record_field(to);
+  }
+  return to;
+}
+
+
 Aggregator_distinct::~Aggregator_distinct()
 {
   if (tree)
@@ -3612,6 +3712,33 @@ int group_concat_key_cmp_with_distinct_with_nulls(void* arg,
 
 
 /**
+  Compares the packed values for fields in expr list of GROUP_CONCAT.
+  @note
+
+     GROUP_CONCAT([DISTINCT] expr [,expr ...]
+              [ORDER BY {unsigned_integer | col_name | expr}
+                  [ASC | DESC] [,col_name ...]]
+              [SEPARATOR str_val])
+
+  @return
+  @retval -1 : key1 < key2
+  @retval  0 : key1 = key2
+  @retval  1 : key1 > key2
+*/
+int group_concat_packed_key_cmp_with_distinct(void *arg,
+                                              const void *a_ptr,
+                                              const void *b_ptr)
+{
+  Item_func_group_concat *item_func= (Item_func_group_concat*)arg;
+
+  DBUG_ASSERT(item_func->unique_filter);
+  uchar *a= (uchar*)a_ptr;
+  uchar *b= (uchar*)b_ptr;
+  return item_func->unique_filter->compare_packed_keys(a, b);
+}
+
+
+/**
   function of sort for syntax: GROUP_CONCAT(expr,... ORDER BY col,... )
 */
 
@@ -3778,10 +3905,21 @@ int dump_leaf_key(void* key_arg, element_count count __attribute__((unused)),
   String tmp((char *)table->record[1], table->s->reclength,
              default_charset_info);
   String tmp2;
-  uchar *key= (uchar *) key_arg;
+  const uchar *key= (const uchar *) key_arg;
+  const uchar *key_end= NULL;
   String *result= &item->result;
   Item **arg= item->args, **arg_end= item->args + item->arg_count_field;
   uint old_length= result->length();
+  SORT_FIELD *pos;
+
+  const bool packed= item->is_distinct_packed();
+
+  if (packed)
+  {
+    pos= item->unique_filter->get_sortorder();
+    key_end= key + item->unique_filter->get_full_size();
+    key+= Unique::size_of_length_field;
+  }
 
   ulonglong *offset_limit= &item->copy_offset_limit;
   ulonglong *row_limit = &item->copy_row_limit;
@@ -3822,11 +3960,43 @@ int dump_leaf_key(void* key_arg, element_count count __attribute__((unused)),
       Field *field= (*arg)->get_tmp_table_field();
       if (field)
       {
-        uint offset= (field->offset(field->table->record[0]) -
-                      table->s->null_bytes);
-        DBUG_ASSERT(offset < table->s->reclength);
-        res= item->get_str_from_field(*arg, field, &tmp, key,
-                                      offset + item->get_null_bytes());
+        if (packed)
+        {
+          DBUG_ASSERT(pos->field == field);
+          if (!item->skip_nulls() && field->maybe_null())
+          {
+            if (*key == 0)
+            {
+              // Case with NULL value
+              field->set_null();
+              res= item->get_str_from_field(*arg, field, &tmp);
+              key++;
+            }
+            else
+            {
+              // Case with NOT NULL value
+              field->set_notnull();
+              const uchar *end= field->unpack(field->ptr, key+1, key_end, 0);
+              res= item->get_str_from_field(*arg, field, &tmp);
+              key= end;
+            }
+          }
+          else
+          {
+            const uchar *end= field->unpack(field->ptr, key, key_end, 0);
+            res= item->get_str_from_field(*arg, field, &tmp);
+            key= end;
+          }
+          pos++;
+        }
+        else
+        {
+          uint offset= (field->offset(field->table->record[0]) -
+                        table->s->null_bytes);
+          DBUG_ASSERT(offset < table->s->reclength);
+          res= item->get_str_from_field(*arg, field, &tmp, key,
+                                        offset + item->get_null_bytes());
+        }
       }
       else
         res= item->get_str_from_item(*arg, &tmp);
@@ -4137,6 +4307,14 @@ bool Item_func_group_concat::add(bool exclude_nulls)
   size_t row_str_len= 0;
   StringBuffer<MAX_FIELD_WIDTH> buf;
   String *res;
+  uchar *to= NULL, *orig_to= get_record_pointer();
+
+  if (is_distinct_packed())
+  {
+    orig_to= to= unique_filter->get_packed_rec_ptr();
+    to+= Unique::size_of_length_field;
+  }
+
   for (uint i= 0; i < arg_count_field; i++)
   {
     Item *show_item= args[i];
@@ -4151,6 +4329,24 @@ bool Item_func_group_concat::add(bool exclude_nulls)
         return 0;                    // Skip row if it contains null
       if (tree && (res= field->val_str(&buf)))
         row_str_len+= res->length();
+
+      /*
+        Storing the packed values for the non-const fields of the record
+      */
+      if (is_distinct_packed())
+      {
+        if (!exclude_nulls && field->maybe_null())
+        {
+          if (field->is_null_in_record((const uchar*) table->record[0]))
+          {
+            *to++=0;
+            continue;
+          }
+          *to++=1;
+        }
+        uchar* end= field->pack(to, field->ptr);
+        to+=  static_cast<uint>(end - to);
+      }
     }
     else
     {
@@ -4167,9 +4363,17 @@ bool Item_func_group_concat::add(bool exclude_nulls)
 
   if (distinct) 
   {
+    DBUG_ASSERT(unique_filter);
+    uint packed_length= unique_filter->get_size();
+
+    if (unique_filter->is_packed())
+    {
+      packed_length= static_cast<uint>(to - orig_to);
+      Unique::store_packed_length(orig_to, packed_length);
+    }
     /* Filter out duplicate rows. */
     uint count= unique_filter->elements_in_tree();
-    unique_filter->unique_add(get_record_pointer());
+    unique_filter->unique_add(get_record_pointer(), packed_length);
     if (count == unique_filter->elements_in_tree())
       row_eligible= FALSE;
   }
@@ -4285,16 +4489,22 @@ bool Item_func_group_concat::setup(THD *thd)
 
   /* Push all not constant fields to the list and create a temp table */
   always_null= 0;
+  uint non_const_items= 0;
   for (uint i= 0; i < arg_count_field; i++)
   {
     Item *item= args[i];
     if (list.push_back(item, thd->mem_root))
       DBUG_RETURN(TRUE);
-    if (item->const_item() && item->is_null() && skip_nulls())
+    if (item->const_item())
     {
-      always_null= 1;
-      DBUG_RETURN(FALSE);
+      if (item->is_null() && skip_nulls())
+      {
+        always_null= 1;
+        DBUG_RETURN(FALSE);
+      }
     }
+    else
+      non_const_items++;
   }
 
   List<Item> all_fields(list);
@@ -4377,6 +4587,7 @@ bool Item_func_group_concat::setup(THD *thd)
      the row is not added to the result.
   */
   uint tree_key_length= table->s->reclength - table->s->null_bytes;
+  bool allow_packing= is_packing_allowed(&tree_key_length);
 
   if (arg_count_order)
   {
@@ -4395,10 +4606,16 @@ bool Item_func_group_concat::setup(THD *thd)
   }
 
   if (distinct)
-    unique_filter= new Unique(get_comparator_function_for_distinct(),
+  {
+    unique_filter= new Unique(get_comparator_function_for_distinct(allow_packing),
                               (void*)this,
                               tree_key_length + get_null_bytes(),
-                              ram_limitation(thd));
+                              ram_limitation(thd), 0, allow_packing);
+
+    if (!unique_filter || unique_filter->setup(thd, this, non_const_items,
+                                               arg_count_field, skip_nulls()))
+      DBUG_RETURN(TRUE);
+  }
   if ((row_limit && row_limit->cmp_type() != INT_RESULT) ||
       (offset_limit && offset_limit->cmp_type() != INT_RESULT))
   {
@@ -4456,11 +4673,13 @@ String* Item_func_group_concat::val_str(String* str)
     Get the comparator function for DISTINT clause
 */
 
-qsort_cmp2 Item_func_group_concat::get_comparator_function_for_distinct()
+qsort_cmp2 Item_func_group_concat::get_comparator_function_for_distinct(bool packed)
 {
-  return skip_nulls() ?
-         group_concat_key_cmp_with_distinct :
-         group_concat_key_cmp_with_distinct_with_nulls;
+  return packed ?
+         group_concat_packed_key_cmp_with_distinct :
+         (skip_nulls() ?
+          group_concat_key_cmp_with_distinct :
+          group_concat_key_cmp_with_distinct_with_nulls);
 }
 
 
@@ -4488,9 +4707,11 @@ qsort_cmp2 Item_func_group_concat::get_comparator_function_for_order_by()
 
 uchar* Item_func_group_concat::get_record_pointer()
 {
-  return skip_nulls() ?
-         table->record[0] + table->s->null_bytes :
-         table->record[0];
+  return is_distinct_packed() ?
+         unique_filter->get_packed_rec_ptr() :
+         (skip_nulls() ?
+          table->record[0] + table->s->null_bytes :
+          table->record[0]);
 }
 
 
@@ -4511,6 +4732,102 @@ uint Item_func_group_concat::get_null_bytes()
 }
 
 
+/*
+  @brief
+    Checks whether the unique tree is packed or not
+
+  @retval
+    TRUE    tree stored packed values
+    FALSE   otherwise
+*/
+
+bool Item_func_group_concat::is_distinct_packed()
+{
+  return unique_filter && unique_filter->is_packed();
+}
+
+
+/*
+  @brief
+    Checks if one can store packed values in the Unique tree
+
+  @param
+    total_length   [OUT] length of the key in the tree
+
+  @retval
+    TRUE     packing allowed
+    FALSE    packing not allowed
+*/
+
+bool Item_func_group_concat::is_packing_allowed(uint* total_length)
+{
+  /*
+    TODO varun:
+    Currently Unique is not packed if ORDER BY clause is used
+    This needs to be implemented when MDEV-22089 is fixed
+  */
+  if (!distinct || arg_count_order)
+    return false;
+
+  return Item_sum::is_packing_allowed(table, total_length);
+}
+
+
+/*
+  @brief
+    Check if storing packed values inside the Unique tree is allowed
+
+  @param table           Table structure
+  @total_length     [OUT] max length of the packed key(takes into account
+                          the length bytes also)
+*/
+
+
+bool Item_sum::is_packing_allowed(TABLE *table, uint* total_length)
+{
+  uint size_of_packable_fields= 0;
+  uint tot_length= 0;
+  for (uint i= 0; i < get_arg_count(); i++)
+  {
+    Item *item= args[i];
+    if (item->const_item())
+      continue;
+    Field *field= item->get_tmp_table_field();
+    if (field)
+    {
+      /*
+        For blob columns packing is not allowed
+      */
+      if (field->flags & BLOB_FLAG)
+        return false;
+
+      tot_length+= field->sort_length_without_suffix();
+      if (field->is_packable())
+      {
+        size_of_packable_fields+=
+              number_storage_requirement(field->sort_length_without_suffix());
+      }
+    }
+  }
+
+  // All fields are of fixed size
+  if (size_of_packable_fields == 0)
+    return false;
+
+  /*
+    TODO varun: we can introduce a heuristic here, no need to do packing if we
+    have small VARCHAR or CHAR
+  */
+  *total_length= tot_length;
+  /*
+    Unique::size_of_lengt_field is the length bytes to store the packed length
+    for each record inserted in the Unique tree
+  */
+  (*total_length)+= Unique::size_of_length_field + size_of_packable_fields;
+  return true;
+}
+
+
 void Item_func_group_concat::print(String *str, enum_query_type query_type)
 {
   str->append(func_name());