summaryrefslogtreecommitdiff
path: root/sql/filesort_utils.cc
diff options
context:
space:
mode:
authorIgor Babaev <igor@askmonty.org>2012-09-01 14:21:59 -0700
committerIgor Babaev <igor@askmonty.org>2012-09-01 14:21:59 -0700
commita6b88f1431238152643e41979ce10b9bbdac2a82 (patch)
tree42482ef66f3c59b255d299fc58ace8c1b0c518ea /sql/filesort_utils.cc
parent5a86a61219826aadf8d08cbc447fe438f2bf50c3 (diff)
downloadmariadb-git-a6b88f1431238152643e41979ce10b9bbdac2a82.tar.gz
MDEV-415: Back-port of the WL task #1393 from the mysql-5.6 code line.
The task adds a more efficient handling of the queries with ORDER BY order LIMIT n, such that n is small enough and no indexes are used for order.
Diffstat (limited to 'sql/filesort_utils.cc')
-rw-r--r--sql/filesort_utils.cc140
1 files changed, 140 insertions, 0 deletions
diff --git a/sql/filesort_utils.cc b/sql/filesort_utils.cc
new file mode 100644
index 00000000000..059e8e3e68e
--- /dev/null
+++ b/sql/filesort_utils.cc
@@ -0,0 +1,140 @@
+/* Copyright (c) 2010, Oracle and/or its affiliates. All rights reserved.
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; version 2 of the License.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
+
+#include "filesort_utils.h"
+#include "sql_const.h"
+#include "sql_sort.h"
+#include "table.h"
+#include "my_sys.h"
+
+
+namespace {
+/**
+ A local helper function. See comments for get_merge_buffers_cost().
+ */
+double get_merge_cost(ha_rows num_elements, ha_rows num_buffers, uint elem_size)
+{
+ return
+ 2.0 * ((double) num_elements * elem_size) / IO_SIZE
+ + (double) num_elements * log((double) num_buffers) /
+ (TIME_FOR_COMPARE_ROWID * M_LN2);
+}
+}
+
+/**
+ This is a simplified, and faster version of @see get_merge_many_buffs_cost().
+ We calculate the cost of merging buffers, by simulating the actions
+ of @see merge_many_buff. For explanations of formulas below,
+ see comments for get_merge_buffers_cost().
+ TODO: Use this function for Unique::get_use_cost().
+*/
+double get_merge_many_buffs_cost_fast(ha_rows num_rows,
+ ha_rows num_keys_per_buffer,
+ uint elem_size)
+{
+ ha_rows num_buffers= num_rows / num_keys_per_buffer;
+ ha_rows last_n_elems= num_rows % num_keys_per_buffer;
+ double total_cost;
+
+ // Calculate CPU cost of sorting buffers.
+ total_cost=
+ ( num_buffers * num_keys_per_buffer * log(1.0 + num_keys_per_buffer) +
+ last_n_elems * log(1.0 + last_n_elems) )
+ / TIME_FOR_COMPARE_ROWID;
+
+ // Simulate behavior of merge_many_buff().
+ while (num_buffers >= MERGEBUFF2)
+ {
+ // Calculate # of calls to merge_buffers().
+ const ha_rows loop_limit= num_buffers - MERGEBUFF*3/2;
+ const ha_rows num_merge_calls= 1 + loop_limit/MERGEBUFF;
+ const ha_rows num_remaining_buffs=
+ num_buffers - num_merge_calls * MERGEBUFF;
+
+ // Cost of merge sort 'num_merge_calls'.
+ total_cost+=
+ num_merge_calls *
+ get_merge_cost(num_keys_per_buffer * MERGEBUFF, MERGEBUFF, elem_size);
+
+ // # of records in remaining buffers.
+ last_n_elems+= num_remaining_buffs * num_keys_per_buffer;
+
+ // Cost of merge sort of remaining buffers.
+ total_cost+=
+ get_merge_cost(last_n_elems, 1 + num_remaining_buffs, elem_size);
+
+ num_buffers= num_merge_calls;
+ num_keys_per_buffer*= MERGEBUFF;
+ }
+
+ // Simulate final merge_buff call.
+ last_n_elems+= num_keys_per_buffer * num_buffers;
+ total_cost+= get_merge_cost(last_n_elems, 1 + num_buffers, elem_size);
+ return total_cost;
+}
+
+uchar **Filesort_buffer::alloc_sort_buffer(uint num_records, uint record_length)
+{
+ DBUG_ENTER("alloc_sort_buffer");
+
+ DBUG_EXECUTE_IF("alloc_sort_buffer_fail",
+ DBUG_SET("+d,simulate_out_of_memory"););
+
+ if (m_idx_array.is_null())
+ {
+ uchar **sort_keys=
+ (uchar**) my_malloc(num_records * (record_length + sizeof(uchar*)),
+ MYF(0));
+ m_idx_array= Idx_array(sort_keys, num_records);
+ m_record_length= record_length;
+ uchar **start_of_data= m_idx_array.array() + m_idx_array.size();
+ m_start_of_data= reinterpret_cast<uchar*>(start_of_data);
+ }
+ else
+ {
+ DBUG_ASSERT(num_records == m_idx_array.size());
+ DBUG_ASSERT(record_length == m_record_length);
+ }
+ DBUG_RETURN(m_idx_array.array());
+}
+
+
+void Filesort_buffer::free_sort_buffer()
+{
+ my_free(m_idx_array.array());
+ m_idx_array= Idx_array();
+ m_record_length= 0;
+ m_start_of_data= NULL;
+}
+
+
+void Filesort_buffer::sort_buffer(const Sort_param *param, uint count)
+{
+ if (count <= 1)
+ return;
+ uchar **keys= get_sort_keys();
+ uchar **buffer= NULL;
+ if (radixsort_is_appliccable(count, param->sort_length) &&
+ (buffer= (uchar**) my_malloc(count*sizeof(char*), MYF(0))))
+ {
+ radixsort_for_str_ptr(keys, count, param->sort_length, buffer);
+ my_free(buffer);
+ return;
+ }
+
+ size_t size= param->sort_length;
+ my_qsort2(keys, count, sizeof(uchar*), get_ptr_compare(size), &size);
+}
+