From: Tor Didriksen Date: December 6 2010 9:46am Subject: bzr commit into mysql-trunk-bugfixing branch (tor.didriksen:3254) WL#1393 List-Archive: http://lists.mysql.com/commits/126111 Message-Id: <20101206094654.6A191226E@atum07.norway.sun.com> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="===============0440539756155896720==" --===============0440539756155896720== MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Content-Disposition: inline #At file:///export/home/didrik/repo/next-mr-opt-team-wl1393-merge/ based on revid:tor.didriksen@stripped 3254 Tor Didriksen 2010-12-06 WL#1393 Optimizing filesort with small limit More review comments. modified: sql/bounded_queue.h sql/filesort.cc unittest/gunit/bounded_queue-t.cc === modified file 'sql/bounded_queue.h' --- a/sql/bounded_queue.h 2010-12-02 11:23:10 +0000 +++ b/sql/bounded_queue.h 2010-12-06 09:46:49 +0000 @@ -76,7 +76,6 @@ public: Initialize the queue. @param max_elements The size of the queue. - @param offset_to_key Offset to key in elements stored in the queue. @param max_at_top Set to true if you want biggest element on top. false: We keep the n largest elements. pop() will return the smallest key in the result set. @@ -93,7 +92,7 @@ public: 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, + int init(ha_rows max_elements, bool max_at_top, compare_function compare, size_t compare_length, keymaker_function keymaker, Sort_param *sort_param, Key_type **sort_keys); @@ -111,6 +110,10 @@ public: Removes the top element from the queue. @retval Pointer to the (key of the) removed element. + + @note This function is for unit testing, where we push elements into to the + queue, and test that the appropriate keys are retained. + Interleaving of push() and pop() operations has not been tested. */ Key_type **pop() { @@ -144,7 +147,6 @@ private: template int Bounded_queue::init(ha_rows max_elements, - uint offset_to_key, bool max_at_top, compare_function compare, size_t compare_length, @@ -166,7 +168,7 @@ int Bounded_queue(get_ptr_compare(compare_length)); // We allocate space for one extra element, for replace when queue is full. return init_queue(&m_queue, (uint) max_elements + 1, - offset_to_key, max_at_top, + 0, max_at_top, reinterpret_cast(compare), &m_compare_length); } === modified file 'sql/filesort.cc' --- a/sql/filesort.cc 2010-12-02 11:23:10 +0000 +++ b/sql/filesort.cc 2010-12-06 09:46:49 +0000 @@ -44,11 +44,6 @@ template class Bounded_queue; #endif -/// How to write record_ref. -#define WRITE_REF(file,from) \ -if (my_b_write((file),(uchar*) (from),param->ref_length)) \ - DBUG_RETURN(1); - /* functions defined in this file */ static void make_char_array(FILESORT_INFO *info, uint fields, uint length); @@ -228,8 +223,9 @@ ha_rows filesort(THD *thd, TABLE *table, { DBUG_PRINT("info", ("filesort PQ is applicable")); const size_t compare_length= param.sort_length; - if (pq.init(param.max_rows, 0, true, - NULL, + if (pq.init(param.max_rows, + true, // max_at_top + NULL, // compare_function compare_length, &make_sortkey, ¶m, table_sort.sort_keys)) { @@ -1188,6 +1184,7 @@ bool check_if_pq_applicable(Sort_param * } } + // Do we have space for LIMIT rows in memory? if (param->max_keys_per_buffer < num_available_keys) { make_char_array(filesort_info, @@ -1210,7 +1207,6 @@ bool check_if_pq_applicable(Sort_param * get_merge_many_buffs_cost_fast(num_rows, num_available_keys, row_length); - /* PQ has cost: (insert + qsort) * log(queue size) / TIME_FOR_COMPARE_ROWID + @@ -1218,7 +1214,7 @@ bool check_if_pq_applicable(Sort_param * */ const double pq_cost= (PQ_slowness * num_rows + param->max_keys_per_buffer) * - log(param->max_rows + 1.0) / TIME_FOR_COMPARE_ROWID + + log((double) param->max_keys_per_buffer) / TIME_FOR_COMPARE_ROWID + param->max_rows * table->file->scan_time(); if (sort_merge_cost < pq_cost) === modified file 'unittest/gunit/bounded_queue-t.cc' --- a/unittest/gunit/bounded_queue-t.cc 2010-12-02 11:23:10 +0000 +++ b/unittest/gunit/bounded_queue-t.cc 2010-12-06 09:46:49 +0000 @@ -170,7 +170,7 @@ TEST_F(BoundedQueueDeathTest, die_if_not */ TEST_F(BoundedQueueDeathTest, die_if_popping_empty_queue) { - EXPECT_EQ(0, m_queue.init(0, 0, true, test_key_compare, + EXPECT_EQ(0, m_queue.init(0, true, test_key_compare, m_key_size, &test_keymaker, NULL, m_keys.key_ptrs)); ::testing::FLAGS_gtest_death_test_style = "threadsafe"; @@ -185,7 +185,7 @@ TEST_F(BoundedQueueDeathTest, die_if_pop */ TEST_F(BoundedQueueTest, construct_and_destruct) { - EXPECT_EQ(0, m_queue.init(num_elements/2, 0, true, + EXPECT_EQ(0, m_queue.init(num_elements/2, true, test_key_compare, m_key_size, &test_keymaker, NULL, m_keys.key_ptrs)); @@ -197,11 +197,11 @@ TEST_F(BoundedQueueTest, construct_and_d */ TEST_F(BoundedQueueTest, too_many_elements) { - EXPECT_EQ(1, m_queue.init(UINT_MAX, 0, true, + EXPECT_EQ(1, m_queue.init(UINT_MAX, true, test_key_compare, m_key_size, &test_keymaker, NULL, m_keys.key_ptrs)); - EXPECT_EQ(1, m_queue.init(UINT_MAX - 1, 0, true, + EXPECT_EQ(1, m_queue.init(UINT_MAX - 1, true, test_key_compare, m_key_size, &test_keymaker, NULL, m_keys.key_ptrs)); @@ -213,7 +213,7 @@ TEST_F(BoundedQueueTest, too_many_elemen */ TEST_F(BoundedQueueTest, zero_size_queue) { - EXPECT_EQ(0, m_queue.init(0, 0, true, test_key_compare, + EXPECT_EQ(0, m_queue.init(0, true, test_key_compare, m_key_size, &test_keymaker, NULL, m_keys.key_ptrs)); insert_test_data(); @@ -226,7 +226,7 @@ TEST_F(BoundedQueueTest, zero_size_queue */ TEST_F(BoundedQueueTest, push_and_pop_keep_largest) { - EXPECT_EQ(0, m_queue.init(num_elements/2, 0, false, test_key_compare, + EXPECT_EQ(0, m_queue.init(num_elements/2, false, test_key_compare, m_key_size, &test_keymaker, NULL, m_keys.key_ptrs)); insert_test_data(); @@ -250,7 +250,7 @@ TEST_F(BoundedQueueTest, push_and_pop_ke */ TEST_F(BoundedQueueTest, push_and_pop_keep_smallest) { - EXPECT_EQ(0, m_queue.init(num_elements/2, 0, true, test_key_compare, + EXPECT_EQ(0, m_queue.init(num_elements/2, true, test_key_compare, m_key_size, &test_keymaker, NULL, m_keys.key_ptrs)); insert_test_data(); @@ -272,7 +272,7 @@ TEST_F(BoundedQueueTest, push_and_pop_ke */ TEST_F(BoundedQueueTest, insert_and_sort) { - EXPECT_EQ(0, m_queue.init(num_elements/2, 0, true, test_key_compare, + EXPECT_EQ(0, m_queue.init(num_elements/2, true, test_key_compare, m_key_size, &test_keymaker, NULL, m_keys.key_ptrs)); insert_test_data(); @@ -380,9 +380,9 @@ void insert_and_sort() Container *keys= new Container; srand(0); Bounded_queue queue; - EXPECT_EQ(0, queue.init(limit, 0, true, int_ptr_compare, + EXPECT_EQ(0, queue.init(limit, true, int_ptr_compare, sizeof(int), &int_keymaker, NULL, keys->key_ptrs)); - for (int ix= 0; ix < limit; ++ix) + for (int ix= 0; ix < num_rows; ++ix) { int data= rand(); queue.push(&data); --===============0440539756155896720== MIME-Version: 1.0 Content-Type: text/bzr-bundle; charset="us-ascii"; name="bzr/tor.didriksen@stripped" Content-Transfer-Encoding: 7bit Content-Disposition: inline # Bazaar merge directive format 2 (Bazaar 0.90) # revision_id: tor.didriksen@stripped\ # dwt7fkm6m0esgyzv # target_branch: file:///export/home/didrik/repo/next-mr-opt-team-\ # wl1393-merge/ # testament_sha1: 4b614e809d0d994aacdf69a9128d3c074fbb3c30 # timestamp: 2010-12-06 10:46:54 +0100 # base_revision_id: tor.didriksen@stripped\ # ci7ox8dqag2uv1sp # # Begin bundle IyBCYXphYXIgcmV2aXNpb24gYnVuZGxlIHY0CiMKQlpoOTFBWSZTWWV2uLgAA8R/gEUUQIBYb/// /yf2wL/v//BgB3fObuBoFHTlQqpAABCSUZNRpo1D0T0po8yaBMppkZAGygyNqenqgaEjJNPEamaS AP0oAAAAABpo0DVPBMlI00ManpDQAGgAwjIAaDQOaZGQyYIaMJgjTRoxA0yZGAAIc0yMhkwQ0YTB GmjRiBpkyMAAQSRBNAAgIJtBSfpmqm2p6kenqaaajR6gMjYqCKOTPxqkI32xIvYyuWE98tJ6SqtW 1As3ePzTMRFfRB+CwC5nYFNibJW1LStmlR2jSDNRocq+6ucow3IEOIvGEf7r/T7fH56V9y/qskwD MkMyZjo5/UQbOyehxHTepuLBCozgjKpjeDYnY6IJmZHuGwKcjeZ55LMjCqcimsLJoIKRRWTNYq5L QAOsmxTrn920zSypKjKbMmZAr7Sl9CqpTsyrADjRjJEnS+Fhzk/DsYUEwHxYpb0TTwE2xmcBeihG 7MV44pNEzV2GTartcukTmEt9N7n9Ushhj2bkMJvD7N8jfI9K4IG5XwH4PsNwwnRDnHCREzt/5xIk 9SB+oBE8B6xeYjvLu2z+IdUyF2/y8DZK+BtwrkKaAogGBftTy2sN8iwHXas8K1lJBeyDBhMyDTrF 8mTihvPAgD+Ho4UGAIpBW4nN0oEFHuCMREVMKkUIzj+EhF5QVFbgdJSO4R7h+qpIL4M1kCGEoeug 9nOgnEj5sRPI6xeLt+qcHjrBKaZLZCAmaAAYGAE5UI1siTHH4NtxvRPQInvnxISK6YxIsj2k537i HAYvX7RsI3jmhwgROQq79kajdLvCwMSCETE4yQxTMUHgOzYODiYJss5b7mcn8dXFeMSiHWWlDyFA uwv3Z4QhcVl5OLUpB6siqsUuwek5Fkw29ZIOiR5YEhuJfYOXmJAMfEuqyorrHibSOHS4b2tJjxPc OGwKwuJGygiqq4ziXRvETHGE+JvzqawvDF9k9osGYYnGJMvkCSAbGsrBMEDXk861vNDC0upIk8Ws qHEQr2y1JrHW6A9eFjGWSLEqB0CNo+NleduEL4RIkXIO3qOSWBzDQtaoeRiabCN6JsWNpUKRrt2G eJoQ3jcxHWLOxo0dtMawhwMmNCIdKCoO4YxCjOgIem1lxJx0CiK7ztqIZlFAsBUs10KpFDeG3JcV UItNRzIfhgcK9dRsWuyWoRvvRFrMMotLVwjOCGm0gqFVNqkuc8vkDW8dyuTG8Zg6k2HSstnV64ID h/CWdmGTM3jayDy5h8ED0EYrrFzi637fK0k/b3XHwJi2eI8uPngu39yChB5zTXoSoLR+f0IThQrQ XbEDsN2r26UM/WHSu5N1uiMBeEO4JAGI/b8YPkQS3DZACGw7Tu9w/s/0Z7DcUICZx9vH5C2TFp7b MY2NvU37FswHYA0rZu5WvVGyAvwu9YmPxD2JGA5tN5xz9vxfgfFmbjt+CQrRZWGdwww3aYnsfmLk Qy6+n2FF2QFxUgNc8xPQkxeOX59jnccdMK0OVIzhFKsVh2sRFtKzNus0QHIOfAVyQZz64xFmhqlg 4ObSb2e1SZDI9TKNAMCZUGTH5rgQDtNxA+n0IEDx2Lingxmz43qsUTWcVCZQ7ozCrGDJXAvk2uhn V7zKE3pfY2DjEadSMQnk9UjIDgFiik6N+3jv2HGquMdNojAJyEzHYXMAMlJhcliSkdZ0EpSUGHLH TnqOekJTVFfCjEcFUrwbNRyCMJoMf3gG0zRXKQkPQ2tCyUHOT6ytIq2xMdOcIg8QPPKLMaefcHr0 AiQbLBZrXbuS/XYgIIp5cYhQQb0KR7xtD3i6MvK2fEKmE29huXCkziJudXTYLlvBM3U8v8tWtI9B 3g50omyW4R9ggq7vQ7Fe1wpORY++paYIBxdTkhQC/h0m/x/9C/IAdcxGw1OwRKgWgNrkoB6dnSXL +BLUvYPDltHGItkSMTxHsglQMCuFJu7uhkA1iqyGJCcTRo4VRdIaf//UsKTLAb5s6ZgXEKQWGzwP J9C2rjd1CFYB4t7qre9iuBsw82JIDYgGF9ILIK4rLxMvPAV4fAUQnWjE2wS6IJkOERe+Z4noFWPX 7rbCls3/K2sj2mhoLjkecztND62gWsK9Zt25ugHDg6SInCLwdwCo183CJfZmIIUWhqXTqKOphU2J NA4fjsLNZNiziaT7K+7yEGkBHE7YBirxMq0a5sUD1PZo/zFYSEWJWZ66kM48oIUfTfZJWG4RSpVo agoKUbIRpHOrAS23+YQXwLLcMjK7yJ0u3KoW02gyf76xTVjUX6Mh0rmRlxIGPFw3shkl1AHZ41oY qFZ34YDnIXNBgLc9ivgwpDVh1XXBkIzHFAHoLooBoDI+LGIiUiaI9wj/i7kinChIMrtcXAA= --===============0440539756155896720==--