List:Commits« Previous MessageNext Message »
From:Tor Didriksen Date:December 2 2010 11:23am
Subject:bzr commit into mysql-trunk-bugfixing branch (tor.didriksen:3253)
View as plain text  
#At file:///export/home/didrik/repo/next-mr-opt-team-wl1393-merge/ based on revid:tor.didriksen@stripped

 3253 Tor Didriksen	2010-12-02
      more review comments

    modified:
      sql/bounded_queue.h
      sql/filesort.cc
      sql/filesort_utils.h
      sql/sql_sort.h
      sql/uniques.cc
      unittest/gunit/bounded_queue-t.cc
=== modified file 'sql/bounded_queue.h'
--- a/sql/bounded_queue.h	2010-12-01 14:18:38 +0000
+++ b/sql/bounded_queue.h	2010-12-02 11:23:10 +0000
@@ -34,6 +34,9 @@ class Sort_param;
   For each element, we call a user-supplied keymaker_function,
   to generate a key of type Key_type for the element.
   Instances of Key_type are compared with the user-supplied compare_function.
+
+  The underlying QUEUE implementation needs one extra element for replacing
+  the lowest/highest element when pushing into a full queue.
  */
 template<typename Element_type, typename Key_type>
 class Bounded_queue

=== modified file 'sql/filesort.cc'
--- a/sql/filesort.cc	2010-12-01 14:18:38 +0000
+++ b/sql/filesort.cc	2010-12-02 11:23:10 +0000
@@ -82,9 +82,9 @@ static bool check_if_pq_applicable(Sort_
                                    ha_rows records, ulong memory_available);
 
 
-void Sort_param::init(uint sortlen, TABLE *table,
-                      ulong max_length_for_sort_data,
-                      ha_rows maxrows, bool sort_positions)
+void Sort_param::init_for_filesort(uint sortlen, TABLE *table,
+                                   ulong max_length_for_sort_data,
+                                   ha_rows maxrows, bool sort_positions)
 {
   sort_length= sortlen;
   ref_length= table->file->ref_length;
@@ -194,9 +194,11 @@ ha_rows filesort(THD *thd, TABLE *table,
   buffpek=0;
   error= 1;
 
-  param.init(sortlength(thd, sortorder, s_length, &multi_byte_charset),
-             table,
-             thd->variables.max_length_for_sort_data, max_rows, sort_positions);
+  param.init_for_filesort(sortlength(thd, sortorder, s_length,
+                                     &multi_byte_charset),
+                          table,
+                          thd->variables.max_length_for_sort_data,
+                          max_rows, sort_positions);
   /* filesort cannot handle zero-length records. */
   DBUG_ASSERT(param.sort_length);
 
@@ -232,6 +234,7 @@ ha_rows filesort(THD *thd, TABLE *table,
                 &make_sortkey, &param, table_sort.sort_keys))
     {
       // If failed to init pq, fall back to merge-sort.
+      DBUG_PRINT("info", ("failed to allocate PQ, fallback to sort-merge"));
       my_free(table_sort.sort_keys);
       table_sort.sort_keys= NULL;
     }
@@ -245,8 +248,8 @@ ha_rows filesort(THD *thd, TABLE *table,
     while (memory_available >= min_sort_memory)
     {
       ulong keys= memory_available / (param.rec_length + sizeof(char*));
-      param.num_keys_per_buffer= (uint) min(num_rows, keys);
-      make_char_array(&table_sort, param.num_keys_per_buffer, param.rec_length);
+      param.max_keys_per_buffer= (uint) min(num_rows, keys);
+      make_char_array(&table_sort, param.max_keys_per_buffer, param.rec_length);
       if (table_sort.sort_keys)
         break;
       ulong old_memory_available= memory_available;
@@ -308,7 +311,7 @@ ha_rows filesort(THD *thd, TABLE *table,
       Use also the space previously used by string pointers in sort_buffer
       for temporary key storage.
     */
-    param.num_keys_per_buffer=((param.num_keys_per_buffer *
+    param.max_keys_per_buffer=((param.max_keys_per_buffer *
                                 (param.rec_length + sizeof(char*))) /
                                param.rec_length - 1);
     maxbuffer--;				// Offset from 0
@@ -662,7 +665,7 @@ static ha_rows find_all_keys(Sort_param 
       }
       else
       {
-        if (idx == param->num_keys_per_buffer)
+        if (idx == param->max_keys_per_buffer)
         {
           if (write_keys(param,sort_keys, idx, buffpek_pointers, tempfile))
              DBUG_RETURN(HA_POS_ERROR);
@@ -1111,7 +1114,7 @@ static bool save_index(Sort_param *param
 
 /**
   Test whether priority queue is worth using to get top elements of an
-  ordered result set. If it is then allocates buffer for required amount of
+  ordered result set. If it is, then allocates buffer for required amount of
   records
 
   @param param            Sort parameters.
@@ -1147,11 +1150,7 @@ bool check_if_pq_applicable(Sort_param *
 
   /*
     How much Priority Queue sort is slower than qsort.
-    For qsort we have an average case complexity of O(n*log(n)) comparisons.
-    When using a priority queue, we have log(n) comparisons each time we
-    push a new element. For PQ we also call qsort at the end.
-    Measurements show that there is some extra overhead in QUEUE,
-    so we set it to 3.0 rather than 2.0.
+    Measurements (see unit test) indicate that PQ is roughly 3 times slower.
   */
   const double PQ_slowness= 3.0;
 
@@ -1170,7 +1169,7 @@ bool check_if_pq_applicable(Sort_param *
   ulong num_available_keys=
     memory_available / (param->rec_length + sizeof(char*));
   // We need 1 extra record in the buffer, when using PQ.
-  param->num_keys_per_buffer= (uint) param->max_rows + 1;
+  param->max_keys_per_buffer= (uint) param->max_rows + 1;
 
   if (num_rows < num_available_keys)
   {
@@ -1178,7 +1177,7 @@ bool check_if_pq_applicable(Sort_param *
     if (param->max_rows < num_rows/PQ_slowness )
     {
       make_char_array(filesort_info,
-                      param->num_keys_per_buffer, param->rec_length);
+                      param->max_keys_per_buffer, param->rec_length);
       if (filesort_info->sort_keys)
         DBUG_RETURN(true);
     }
@@ -1189,10 +1188,10 @@ bool check_if_pq_applicable(Sort_param *
     }
   }
 
-  if (param->num_keys_per_buffer < num_available_keys)
+  if (param->max_keys_per_buffer < num_available_keys)
   {
     make_char_array(filesort_info,
-                    param->num_keys_per_buffer, param->rec_length);
+                    param->max_keys_per_buffer, param->rec_length);
     if (filesort_info->sort_keys)
       DBUG_RETURN(true);
   }
@@ -1205,7 +1204,7 @@ bool check_if_pq_applicable(Sort_param *
     num_available_keys= memory_available / row_length;
 
     // Can we fit all the keys in memory?
-    if (param->num_keys_per_buffer < num_available_keys)
+    if (param->max_keys_per_buffer < num_available_keys)
     {
       const double sort_merge_cost=
         get_merge_many_buffs_cost_fast(num_rows,
@@ -1218,7 +1217,7 @@ bool check_if_pq_applicable(Sort_param *
         cost of file lookup afterwards.
       */
       const double pq_cost=
-        (PQ_slowness * num_rows + param->num_keys_per_buffer) *
+        (PQ_slowness * num_rows + param->max_keys_per_buffer) *
         log(param->max_rows + 1.0) / TIME_FOR_COMPARE_ROWID +
         param->max_rows * table->file->scan_time();
 
@@ -1226,7 +1225,7 @@ bool check_if_pq_applicable(Sort_param *
         DBUG_RETURN(false);
 
       make_char_array(filesort_info,
-                      param->num_keys_per_buffer, param->rec_length);
+                      param->max_keys_per_buffer, param->rec_length);
       if (filesort_info->sort_keys)
       {
         // Make attached data to be references instead of fields.
@@ -1413,7 +1412,7 @@ int merge_buffers(Sort_param *param, IO_
   res_length= param->res_length;
   sort_length= param->sort_length;
   offset= rec_length-res_length;
-  maxcount= (ulong) (param->num_keys_per_buffer / ((uint) (Tb-Fb) +1));
+  maxcount= (ulong) (param->max_keys_per_buffer / ((uint) (Tb-Fb) +1));
   to_start_filepos= my_b_tell(to_file);
   strpos= (uchar*) sort_buffer;
   org_max_rows=max_rows= param->max_rows;
@@ -1529,7 +1528,7 @@ int merge_buffers(Sort_param *param, IO_
   }
   buffpek= (BUFFPEK*) queue_top(&queue);
   buffpek->base= sort_buffer;
-  buffpek->max_keys= param->num_keys_per_buffer;
+  buffpek->max_keys= param->max_keys_per_buffer;
 
   /*
     As we know all entries in the buffer are unique, we only have to

=== modified file 'sql/filesort_utils.h'
--- a/sql/filesort_utils.h	2010-12-01 14:18:38 +0000
+++ b/sql/filesort_utils.h	2010-12-02 11:23:10 +0000
@@ -12,11 +12,13 @@
     Calculates cost of merge sort by simulating call to merge_many_buff().
 
   @retval
-    computed cost of merge sort
+    Computed cost of merge sort in disk seeks.
 
   @note
     Declared here in order to be able to unit test it,
     since library dependencies have not been sorted out yet.
+
+    See also comments get_merge_many_buffs_cost().
 */
 
 #define FILESORT_UTILS_INCLUDED

=== modified file 'sql/sql_sort.h'
--- a/sql/sql_sort.h	2010-11-29 11:21:22 +0000
+++ b/sql/sql_sort.h	2010-12-02 11:23:10 +0000
@@ -73,22 +73,22 @@ struct BUFFPEK_COMPARE_CONTEXT
 
 class Sort_param {
 public:
-  uint rec_length;            /* Length of sorted records */
-  uint sort_length;           /* Length of sorted columns */
-  uint ref_length;            /* Length of record ref. */
-  uint addon_length;          /* Length of added packed fields */
-  uint res_length;            /* Length of records in final sorted file/buffer */
-  uint num_keys_per_buffer;   /* Max keys / buffer */
-  ha_rows max_rows;           /* Select limit, or HA_POS_ERROR if unlimited */
-  ha_rows examined_rows;      /* Number of examined rows */
-  TABLE *sort_form;           /* For quicker make_sortkey */
+  uint rec_length;            // Length of sorted records.
+  uint sort_length;           // Length of sorted columns.
+  uint ref_length;            // Length of record ref.
+  uint addon_length;          // Length of added packed fields.
+  uint res_length;            // Length of records in final sorted file/buffer.
+  uint max_keys_per_buffer;   // Max keys / buffer.
+  ha_rows max_rows;           // Select limit, or HA_POS_ERROR if unlimited.
+  ha_rows examined_rows;      // Number of examined rows.
+  TABLE *sort_form;           // For quicker make_sortkey.
   SORT_FIELD *local_sortorder;
   SORT_FIELD *end;
-  SORT_ADDON_FIELD *addon_field; /* Descriptors for companion fields */
+  SORT_ADDON_FIELD *addon_field; // Descriptors for companion fields.
   uchar *unique_buff;
   bool not_killable;
   char* tmp_buffer;
-  /* The fields below are used only by Unique class */
+  // The fields below are used only by Unique class.
   qsort2_cmp compare;
   BUFFPEK_COMPARE_CONTEXT cmp_context;
 
@@ -96,8 +96,9 @@ public:
   {
     memset(this, 0, sizeof(*this));
   }
-  void init(uint sortlen, TABLE *table, ulong max_length_for_sort_data,
-            ha_rows maxrows, bool sort_positions);
+  void init_for_filesort(uint sortlen, TABLE *table,
+                         ulong max_length_for_sort_data,
+                         ha_rows maxrows, bool sort_positions);
 };
 
 

=== modified file 'sql/uniques.cc'
--- a/sql/uniques.cc	2010-11-29 11:21:22 +0000
+++ b/sql/uniques.cc	2010-12-02 11:23:10 +0000
@@ -614,18 +614,17 @@ bool Unique::get(TABLE *table)
   Sort_param sort_param;
   sort_param.max_rows= elements;
   sort_param.sort_form=table;
-  sort_param.rec_length= sort_param.sort_length= sort_param.ref_length=
-    size;
-  sort_param.num_keys_per_buffer=
+  sort_param.rec_length= sort_param.sort_length= sort_param.ref_length= size;
+  sort_param.max_keys_per_buffer=
     (uint) (max_in_memory_size / sort_param.sort_length);
   sort_param.not_killable=1;
 
-  if (!(sort_buffer=(uchar*) my_malloc((sort_param.num_keys_per_buffer + 1) *
-				       sort_param.sort_length,
-				       MYF(0))))
+  if (!(sort_buffer=(uchar*) my_malloc((sort_param.max_keys_per_buffer + 1) *
+                                       sort_param.sort_length,
+                                       MYF(0))))
     return 1;
-  sort_param.unique_buff= sort_buffer+(sort_param.num_keys_per_buffer *
-				       sort_param.sort_length);
+  sort_param.unique_buff= sort_buffer+(sort_param.max_keys_per_buffer *
+                                       sort_param.sort_length);
 
   sort_param.compare= (qsort2_cmp) buffpek_compare;
   sort_param.cmp_context.key_compare= tree.compare;

=== modified file 'unittest/gunit/bounded_queue-t.cc'
--- a/unittest/gunit/bounded_queue-t.cc	2010-12-01 14:18:38 +0000
+++ b/unittest/gunit/bounded_queue-t.cc	2010-12-02 11:23:10 +0000
@@ -246,6 +246,7 @@ TEST_F(BoundedQueueTest, push_and_pop_ke
 
 /*
   Verifies that push and bounded size works, and that pop() gives sorted order.
+  Note that with max_at_top == true, we will pop() in reverse order.
  */
 TEST_F(BoundedQueueTest, push_and_pop_keep_smallest)
 {


Attachment: [text/bzr-bundle] bzr/tor.didriksen@oracle.com-20101202112310-ci7ox8dqag2uv1sp.bundle
Thread
bzr commit into mysql-trunk-bugfixing branch (tor.didriksen:3253) Tor Didriksen2 Dec