MDEV-21580: Allow packed sort keys in sort bufferbb-10.5-mdev6915-ext

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.

1 files changed, 54 insertions, 4 deletions

diff --git a/sql/field.h b/sql/field.h
index 4a8eec35b05..71e9b3a2128 100644
--- a/sql/field.h
+++ b/sql/field.h
@@ -51,6 +51,8 @@ class Table_ident;
 class SEL_ARG;
 class RANGE_OPT_PARAM;
 struct KEY_PART;
+struct SORT_FIELD;
+struct SORT_FIELD_ATTR;
 
 enum enum_check_fields
 {
@@ -1075,6 +1077,12 @@ public:
   virtual uint32 data_length() { return pack_length(); }
   virtual uint32 sort_length() const { return pack_length(); }
 
+  /*
+    sort_suffix_length() return the length bytes needed to store the length
+    for binary charset
+  */
+  virtual uint32 sort_suffix_length() const { return 0; }
+
   /* 
     Get the number bytes occupied by the value in the field.
     CHAR values are stripped of trailing spaces.
@@ -1410,7 +1418,18 @@ public:
     return bytes;
   }
 
-  void make_sort_key(uchar *buff, uint length);
+  /*
+    Create mem-comparable sort key part for a sort key
+  */
+  void make_sort_key_part(uchar *buff, uint length);
+
+  /*
+    create a compact sort key which can be compared with a comparison
+    function. They are called packed sort keys
+  */
+  virtual uint make_packed_sort_key_part(uchar *buff,
+                                         const SORT_FIELD_ATTR *sort_field);
+
   virtual void make_send_field(Send_field *);
   virtual void sort_string(uchar *buff,uint length)=0;
   virtual bool optimize_range(uint idx, uint part) const;
@@ -2140,7 +2159,10 @@ public:
   bool can_optimize_range(const Item_bool_func *cond,
                           const Item *item,
                           bool is_eq_func) const;
-  bool is_packable() { return true; }
+  bool is_packable() override { return true; }
+  uint make_packed_sort_key_part(uchar *buff,
+                                 const SORT_FIELD_ATTR *sort_field)override;
+  uchar* pack_sort_string(uchar *to, const SORT_FIELD_ATTR *sort_field);
 };
 
 /* base class for float and double and decimal (old one) */
@@ -4042,8 +4064,11 @@ public:
   uint32 key_length() const override { return (uint32) field_length; }
   uint32 sort_length() const override
   {
-    return (uint32) field_length + (field_charset() == &my_charset_bin ?
-                                    length_bytes : 0);
+    return (uint32) field_length + sort_suffix_length();
+  }
+  virtual uint32 sort_suffix_length() const override
+  {
+    return (field_charset() == &my_charset_bin ? length_bytes : 0);
   }
   Copy_func *get_copy_func(const Field *from) const override;
   bool memcpy_field_possible(const Field *from) const override;
@@ -4187,6 +4212,30 @@ static inline longlong read_bigendian(const uchar *from, uint bytes)
   }
 }
 
+static inline void store_lowendian(ulonglong num, uchar *to, uint bytes)
+{
+  switch(bytes) {
+  case 1: *to= (uchar)num;    break;
+  case 2: int2store(to, num); break;
+  case 3: int3store(to, num); break;
+  case 4: int4store(to, num); break;
+  case 8: int8store(to, num); break;
+  default: DBUG_ASSERT(0);
+  }
+}
+
+static inline longlong read_lowendian(const uchar *from, uint bytes)
+{
+  switch(bytes) {
+  case 1: return from[0];
+  case 2: return uint2korr(from);
+  case 3: return uint3korr(from);
+  case 4: return uint4korr(from);
+  case 8: return sint8korr(from);
+  default: DBUG_ASSERT(0); return 0;
+  }
+}
+
 
 extern LEX_CSTRING temp_lex_str;
 
@@ -4353,6 +4402,7 @@ public:
   { return (uint32) (packlength); }
   uint row_pack_length() const override { return pack_length_no_ptr(); }
   uint32 sort_length() const override;
+  uint32 sort_suffix_length() const override;
   uint32 value_length() override { return get_length(); }
   virtual uint32 max_data_length() const override
   {