MDEV-21580: Allow packed sort keys in sort buffer

This task deals with packing the sort key inside the sort buffer, which  would
lead to efficient usage of the memory allocated for the sort buffer.

The changes brought by this feature are
  1) Sort buffers would have sort keys of variable length
  2) The format for sort keys inside the sort buffer would look like
     |<sort_length><null_byte><key_part1><null_byte><key_part2>.......|
      sort_length is the extra bytes that are required to store the variable
      length of a sort key.
  3) When packing of sort key is done we store the ORIGINAL VALUES inside
     the sort buffer and not the STRXFRM form (mem-comparable sort keys).
  4) Special comparison function packed_keys_comparison() is introduced
     to compare 2 sort keys.

This patch also contains contributions from Sergei Petrunia.

1 files changed, 93 insertions, 39 deletions

diff --git a/sql/sql_type.h b/sql/sql_type.h
index ce87c8e9d93..ee56e7146da 100644
--- a/sql/sql_type.h
+++ b/sql/sql_type.h
@@ -86,6 +86,7 @@ class handler;
 struct Schema_specification_st;
 struct TABLE;
 struct SORT_FIELD_ATTR;
+struct SORT_FIELD;
 class Vers_history_point;
 class Virtual_column_info;
 class Conv_source;
@@ -3332,6 +3333,14 @@ protected:
                               bool maybe_null, bool null_value,
                               bool unsigned_flag,
                               longlong value) const;
+  void store_sort_key_longlong(uchar *to, bool unsigned_flag,
+                               longlong value) const;
+
+  uint make_packed_sort_key_longlong(uchar *to, bool maybe_null,
+                                     bool null_value, bool unsigned_flag,
+                                     longlong value,
+                                     const SORT_FIELD_ATTR *sort_field) const;
+
   bool Item_func_or_sum_illegal_param(const char *name) const;
   bool Item_func_or_sum_illegal_param(const Item_func_or_sum *) const;
   bool check_null(const Item *item, st_value *value) const;
@@ -3752,12 +3761,25 @@ public:
                                           const uchar *buffer,
                                           LEX_CUSTRING *gis_options) const;
 
-  virtual void make_sort_key(uchar *to, Item *item,
-                             const SORT_FIELD_ATTR *sort_field,
-                             Sort_param *param) const= 0;
-  virtual void sortlength(THD *thd,
+  /*
+    Create a fixed size key part for a sort key
+  */
+  virtual void make_sort_key_part(uchar *to, Item *item,
+                                  const SORT_FIELD_ATTR *sort_field,
+                                  Sort_param *param) const= 0;
+
+  /*
+    create a compact size key part for a sort key
+  */
+  virtual uint make_packed_sort_key_part(uchar *to, Item *item,
+                                         const SORT_FIELD_ATTR *sort_field,
+                                         Sort_param *param) const=0;
+
+  virtual void sort_length(THD *thd,
                           const Type_std_attributes *item,
                           SORT_FIELD_ATTR *attr) const= 0;
+  virtual bool is_packable() const { return false; }
+
 
   virtual uint32 max_display_length(const Item *item) const= 0;
   virtual uint32 Item_decimal_notation_int_digits(const Item *item) const { return 0; }
@@ -4149,14 +4171,21 @@ public:
                                    const Bit_addr &bit,
                                    const Column_definition_attributes *attr,
                                    uint32 flags) const override;
-  void make_sort_key(uchar *to, Item *item,
-                     const SORT_FIELD_ATTR *sort_field,
-                     Sort_param *param) const override
+  void make_sort_key_part(uchar *to, Item *item,
+                          const SORT_FIELD_ATTR *sort_field,
+                          Sort_param *param) const override
+  {
+    DBUG_ASSERT(0);
+  }
+  uint make_packed_sort_key_part(uchar *to, Item *item,
+                                 const SORT_FIELD_ATTR *sort_field,
+                                 Sort_param *param) const override
   {
     DBUG_ASSERT(0);
+    return 0;
   }
-  void sortlength(THD *thd, const Type_std_attributes *item,
-                            SORT_FIELD_ATTR *attr) const override
+  void sort_length(THD *thd, const Type_std_attributes *item,
+                   SORT_FIELD_ATTR *attr) const override
   {
     DBUG_ASSERT(0);
   }
@@ -4481,11 +4510,15 @@ public:
   bool subquery_type_allows_materialization(const Item *inner,
                                             const Item *outer)
                                             const override;
-  void make_sort_key(uchar *to, Item *item, const SORT_FIELD_ATTR *sort_field,
-                     Sort_param *param) const override;
-  void sortlength(THD *thd,
-                  const Type_std_attributes *item,
-                  SORT_FIELD_ATTR *attr) const override;
+  void make_sort_key_part(uchar *to, Item *item,
+                          const SORT_FIELD_ATTR *sort_field,
+                          Sort_param *param) const override;
+  uint make_packed_sort_key_part(uchar *to, Item *item,
+                                 const SORT_FIELD_ATTR *sort_field,
+                                 Sort_param *param) const override;
+  void sort_length(THD *thd,
+                   const Type_std_attributes *item,
+                   SORT_FIELD_ATTR *attr) const override;
   bool Item_const_eq(const Item_const *a, const Item_const *b,
                      bool binary_cmp) const override;
   bool Item_eq_value(THD *thd, const Type_cmp_attributes *attr,
@@ -4588,8 +4621,12 @@ public:
                            bool show_field) const override;
   Field *make_num_distinct_aggregator_field(MEM_ROOT *, const Item *)
     const override;
-  void make_sort_key(uchar *to, Item *item, const SORT_FIELD_ATTR *sort_field,
-                     Sort_param *param) const override;
+  void make_sort_key_part(uchar *to, Item *item,
+                          const SORT_FIELD_ATTR *sort_field,
+                          Sort_param *param) const override;
+  uint make_packed_sort_key_part(uchar *to, Item *item,
+                                 const SORT_FIELD_ATTR *sort_field,
+                                 Sort_param *param) const override;
   void
   Column_definition_attributes_frm_pack(const Column_definition_attributes *at,
                                         uchar *buff) const override;
@@ -4599,9 +4636,9 @@ public:
                                           const uchar *buffer,
                                           LEX_CUSTRING *gis_options)
                                           const override;
-  void sortlength(THD *thd,
-                  const Type_std_attributes *item,
-                  SORT_FIELD_ATTR *attr) const override;
+  void sort_length(THD *thd,
+                   const Type_std_attributes *item,
+                   SORT_FIELD_ATTR *attr) const override;
   uint32 max_display_length(const Item *item) const override;
   uint32 Item_decimal_notation_int_digits(const Item *item) const override;
   Item *create_typecast_item(THD *thd, Item *item,
@@ -4838,14 +4875,18 @@ public:
                           const Record_addr &addr,
                           const Type_all_attributes &attr,
                           TABLE_SHARE *share) const override;
-  void make_sort_key(uchar *to, Item *item, const SORT_FIELD_ATTR *sort_field,
-                     Sort_param *param) const override;
+  void make_sort_key_part(uchar *to, Item *item,
+                          const SORT_FIELD_ATTR *sort_field,
+                          Sort_param *param) const override;
+  uint make_packed_sort_key_part(uchar *to, Item *item,
+                                 const SORT_FIELD_ATTR *sort_field,
+                                 Sort_param *param) const override;
   void
   Column_definition_attributes_frm_pack(const Column_definition_attributes *at,
                                         uchar *buff) const override;
-  void sortlength(THD *thd,
-                  const Type_std_attributes *item,
-                  SORT_FIELD_ATTR *attr) const override;
+  void sort_length(THD *thd,
+                   const Type_std_attributes *item,
+                   SORT_FIELD_ATTR *attr) const override;
   bool Item_const_eq(const Item_const *a, const Item_const *b,
                      bool binary_cmp) const override;
   bool Item_eq_value(THD *thd, const Type_cmp_attributes *attr,
@@ -4945,11 +4986,15 @@ public:
   void
   Column_definition_attributes_frm_pack(const Column_definition_attributes *at,
                                         uchar *buff) const override;
-  void make_sort_key(uchar *to, Item *item,  const SORT_FIELD_ATTR *sort_field,
-                     Sort_param *param) const override;
-  void sortlength(THD *thd,
-                  const Type_std_attributes *item,
-                  SORT_FIELD_ATTR *attr) const override;
+  void make_sort_key_part(uchar *to, Item *item,
+                          const SORT_FIELD_ATTR *sort_field,
+                          Sort_param *param) const override;
+  uint make_packed_sort_key_part(uchar *to, Item *item,
+                                 const SORT_FIELD_ATTR *sort_field,
+                                 Sort_param *param) const override;
+  void sort_length(THD *thd,
+                   const Type_std_attributes *item,
+                   SORT_FIELD_ATTR *attr) const override;
   bool Item_const_eq(const Item_const *a, const Item_const *b,
                      bool binary_cmp) const override;
   bool Item_param_set_from_value(THD *thd,
@@ -5034,11 +5079,16 @@ public:
   const Type_handler *
   type_handler_adjusted_to_max_octet_length(uint max_octet_length,
                                             CHARSET_INFO *cs) const override;
-  void make_sort_key(uchar *to, Item *item, const SORT_FIELD_ATTR *sort_field,
-                     Sort_param *param) const override;
-  void sortlength(THD *thd,
-                  const Type_std_attributes *item,
-                  SORT_FIELD_ATTR *attr) const override;
+  void make_sort_key_part(uchar *to, Item *item,
+                          const SORT_FIELD_ATTR *sort_field,
+                          Sort_param *param) const override;
+  uint make_packed_sort_key_part(uchar *to, Item *item,
+                                 const SORT_FIELD_ATTR *sort_field,
+                                 Sort_param *param) const override;
+  void sort_length(THD *thd,
+                   const Type_std_attributes *item,
+                   SORT_FIELD_ATTR *attr) const override;
+  bool is_packable()const override { return true; }
   bool union_element_finalize(const Item * item) const override;
   uint calc_key_length(const Column_definition &def) const override;
   bool Column_definition_prepare_stage1(THD *thd,
@@ -6230,11 +6280,15 @@ public:
   cmp_item *make_cmp_item(THD *thd, CHARSET_INFO *cs) const override;
   in_vector *make_in_vector(THD *thd, const Item_func_in *f, uint nargs)
                             const override;
-  void make_sort_key(uchar *to, Item *item, const SORT_FIELD_ATTR *sort_field,
-                     Sort_param *param) const override;
-  void sortlength(THD *thd,
-                  const Type_std_attributes *item,
-                  SORT_FIELD_ATTR *attr) const override;
+  void make_sort_key_part(uchar *to, Item *item,
+                          const SORT_FIELD_ATTR *sort_field,
+                          Sort_param *param) const override;
+  uint make_packed_sort_key_part(uchar *to, Item *item,
+                                 const SORT_FIELD_ATTR *sort_field,
+                                 Sort_param *param) const override;
+  void sort_length(THD *thd,
+                   const Type_std_attributes *item,
+                   SORT_FIELD_ATTR *attr) const override;
   bool Column_definition_fix_attributes(Column_definition *c) const override;
   uint Item_decimal_scale(const Item *item) const override
   {