Hi Tor,
I will approve this worklog now. See in-line for some minor
suggestions that I hope you will consider.
I am still not sure we have fully understood the cost aspects, but I
seems we can be confident that it does much more good than harm, and
that the risk of performance regressions are small.
--
Øystein
On 11/29/10 12:21 PM, Tor Didriksen wrote:
> #At file:///export/home/didrik/repo/next-mr-opt-team-wl1393-merge/
based on revid:tor.didriksen@stripped
>
> 3250 Tor Didriksen 2010-11-29
> WL#1393 Optimizing filesort with small limit
>
> Many web customers have to do
> "SELECT ... ORDER BY non_index_column LIMIT X",
>
> When X *<Row Size> is smaller than sort_buff_size we can use
> the following algoritm to speed up the sort:
>
> - Create a queue to hold 'limit' keys.
> - Scan through the table and store the first (last if DESC)
keys in the queue
> - Return values from queue
> @ libmysqld/CMakeLists.txt
> Add Bounded_queue
> @ libmysqld/Makefile.am.THIS
> Add Bounded_queue
???
> @ mysql-test/include/order_by.inc
> Add new tests.
> @ mysql-test/include/select.inc
> Fix typo in bug number.
> @ mysql-test/r/order_by_none.result
> Added new tests.
> @ mysql-test/r/order_by_sortkey.result
> New test.
> @ mysql-test/r/select_none.result
> Fix typo in bug number.
> @ mysql-test/t/order_by_sortkey.test
> New test.
> @ mysys/CMakeLists.txt
> Compile standalone queues test executable.
> @ mysys/queues.c
> Fix un-maintained code: s/bool/my_bool/
> @ sql/CMakeLists.txt
> Add Bounded_queue to gunit tests.
> @ sql/Makefile.am.THIS
> Add Bounded_queue
???
...
> + /**
> + Function for comparing two keys.
> + @param n Pointer to number of bytes to compare.
> + @param a First key.
> + @param b Second key.
> + @retval -1, 0, or 1 depending on whether the left argument is
> + less than, equal to, or greater than the right argument.
> + */
> + typedef int (*compare_function)(size_t *n, Key_type **a, Key_type
**b);
> +
> + /**
> + Initialize the queue.
> +
> + @param max_elements The size of the queue.
> + @param offset_to_key Offset to key in elements stored in the queue.
Didn't we agree to drop offset_to_key?
> + @param max_at_top Set to 1 if you want biggest element on top.
> + @param compare Compare function for elements, takes 3
arguments.
> + If NULL, we use
get_ptr_compare(compare_length).
> + @param compare_length Length of the data (i.e. the keys) used
for sorting.
> + @param keymaker Function which generates keys for elements.
> + @param sort_param Sort parameters.
> + @param sort_keys Array of pointers to keys to sort.
> +
> + @retval 0 OK, 1 Could not allocate memory.
> +
> + We do *not* take ownership of any of the input pointer arguments.
> + */
> + int init(ha_rows max_elements, uint offset_to_key, bool max_at_top,
> + compare_function compare, size_t compare_length,
> + keymaker_function keymaker, Sort_param *sort_param,
> + Key_type **sort_keys);
> +
> + /**
> + Pushes an element on the queue.
> + If the queue is already full, we discard one element.
> + Calls keymaker_function to generate a key for the element.
> +
> + @param element The element to be pushed.
> + */
> + void push(Element_type *element);
> +
> + /**
> + Removes the top element from the queue.
> +
> + @retval Pointer to the (key of the) removed element.
> + */
> + Key_type **pop()
> + {
> + // Don't return the extra element to the client code.
> + if (queue_is_full((&m_queue)))
> + queue_remove(&m_queue, 0);
> + return reinterpret_cast<Key_type**>(queue_remove(&m_queue, 0));
> + }
I think we agreed to add a comment that said that pop() had been
implemented for testing purposes, and is not fully tested.
...
> + /*
> + PQ has cost:
> + (insert + qsort) * log(queue size) / TIME_FOR_COMPARE_ROWID +
> + cost of file lookup afterwards.
> + */
> + const double pq_cost=
> + (PQ_slowness * num_rows + param->num_keys_per_buffer) *
> + log(param->max_rows + 1.0) / TIME_FOR_COMPARE_ROWID +
> + param->max_rows * table->file->scan_time();
As discussed on Friday, param->num_keys_per_buffer == param->max_rows + 1.0
at this point. I think it would be more obvious if just one of these
variables are used in this formula.
...
> +
> +/*
> + Some basic performance testing, to compute the overhead of
Bounded_queue.
> + Run the with 'bounded_queue-t --disable-tap-output' to see the
> + millisecond output from Google Test.
> + */
> +const int num_rows= 10000;
> +const int row_limit= 100;
> +const int num_iterations= 1000;
> +
> +class PerfTestSmall : public ::testing::Test
> +{
> +public:
> + /*
> + The extra overhead of malloc/free should be part of the measurement,
> + so we do not define the key container as a member here.
> + */
> + typedef Key_container<row_limit, int> Container;
> + enum { limit= row_limit };
> +};
> +
> +class PerfTestLarge : public ::testing::Test
> +{
> +public:
> + /*
> + The extra overhead of malloc/free should be part of the measurement,
> + so we do not define the key container as a member here.
> + */
> + typedef Key_container<num_rows, int> Container;
> + enum { limit= num_rows };
> +};
> +
> +
> +template<int limit>
> +void insert_and_sort()
> +{
> + typedef Key_container<limit, int> Container;
> + for (int it= 0; it< num_iterations; ++it)
> + {
> + Container *keys= new Container;
> + srand(0);
> + Bounded_queue<int, int> queue;
> + EXPECT_EQ(0, queue.init(limit, 0, true, int_ptr_compare,
> + sizeof(int),&int_keymaker, NULL,
keys->key_ptrs));
> + for (int ix= 0; ix< limit; ++ix)
Should not this loop do num_rows iterations?
Otherwise, the name of the constants are a bit misleading.
The way it is now, it should rather be num_rows_large instead of
num_rows and num_rows_small instead of row_limit.
> + {
> + int data= rand();
> + queue.push(&data);
> + }
> + my_string_ptr_sort((uchar*)&keys->key_ptrs[0],
> + queue.num_elements(), sizeof(int));
> + delete keys;
> + }
> +}
