From: Tor Didriksen
Date: December 10 2010 3:06pm
Subject: bzr commit into mysql-trunk-bugfixing branch (tor.didriksen:3259) WL#1393
List-Archive: http://lists.mysql.com/commits/126535
Message-Id: <20101210150628.769C8ADD@atum07.norway.sun.com>
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="===============0899943541472716123=="

--===============0899943541472716123==
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

 3259 Tor Didriksen	2010-12-10
      WL#1393 Optimizing filesort with small limit
     @ sql/filesort.cc
        Adjust, and comment on, cost function.

    modified:
      mysql-test/r/order_by_sortkey.result
      mysql-test/t/order_by_sortkey.test
      sql/filesort.cc
=== modified file 'mysql-test/r/order_by_sortkey.result'
--- a/mysql-test/r/order_by_sortkey.result	2010-11-30 11:54:00 +0000
+++ b/mysql-test/r/order_by_sortkey.result	2010-12-10 15:06:03 +0000
@@ -40,8 +40,6 @@ INSERT INTO tmp SELECT f1,f2 FROM t1;
 INSERT INTO t1(f1,f2) SELECT * FROM tmp;
 INSERT INTO tmp SELECT f1,f2 FROM t1;
 INSERT INTO t1(f1,f2) SELECT * FROM tmp;
-INSERT INTO tmp SELECT f1,f2 FROM t1;
-INSERT INTO t1(f1,f2) SELECT * FROM tmp;
 set sort_buffer_size= 32768;
 FLUSH STATUS;
 SHOW SESSION STATUS LIKE 'Sort%';

=== modified file 'mysql-test/t/order_by_sortkey.test'
--- a/mysql-test/t/order_by_sortkey.test	2010-11-30 11:54:00 +0000
+++ b/mysql-test/t/order_by_sortkey.test	2010-12-10 15:06:03 +0000
@@ -50,8 +50,6 @@ INSERT INTO tmp SELECT f1,f2 FROM t1;
 INSERT INTO t1(f1,f2) SELECT * FROM tmp; 
 INSERT INTO tmp SELECT f1,f2 FROM t1;
 INSERT INTO t1(f1,f2) SELECT * FROM tmp; 
-INSERT INTO tmp SELECT f1,f2 FROM t1;
-INSERT INTO t1(f1,f2) SELECT * FROM tmp;
 
 # Test when only sortkeys fits to memory
 set sort_buffer_size= 32768; 

=== modified file 'sql/filesort.cc'
--- a/sql/filesort.cc	2010-12-09 11:54:39 +0000
+++ b/sql/filesort.cc	2010-12-10 15:06:03 +0000
@@ -218,7 +218,8 @@ ha_rows filesort(THD *thd, TABLE *table,
       !(param.tmp_buffer= (char*) my_malloc(param.sort_length,MYF(MY_WME))))
     goto err;
 
-  if (check_if_pq_applicable(&param, &table_sort,
+  if (param.max_rows != HA_POS_ERROR &&
+      check_if_pq_applicable(&param, &table_sort,
                              table, num_rows, memory_available))
   {
     DBUG_PRINT("info", ("filesort PQ is applicable"));
@@ -1174,8 +1175,7 @@ bool check_if_pq_applicable(Sort_param *
     {
       make_char_array(filesort_info,
                       param->max_keys_per_buffer, param->rec_length);
-      if (filesort_info->sort_keys)
-        DBUG_RETURN(true);
+      DBUG_RETURN(filesort_info->sort_keys != NULL);
     }
     else
     {
@@ -1189,8 +1189,7 @@ bool check_if_pq_applicable(Sort_param *
   {
     make_char_array(filesort_info,
                     param->max_keys_per_buffer, param->rec_length);
-    if (filesort_info->sort_keys)
-      DBUG_RETURN(true);
+    DBUG_RETURN(filesort_info->sort_keys != NULL);
   }
 
   // Try to strip off addon fields.
@@ -1211,11 +1210,17 @@ bool check_if_pq_applicable(Sort_param *
         PQ has cost:
         (insert + qsort) * log(queue size) / TIME_FOR_COMPARE_ROWID +
         cost of file lookup afterwards.
+        The lookup cost is a bit pessimistic: we take scan_time and assume
+        that on average we find the row after scanning half of the file.
+        A better estimate would be lookup cost, but note that we are doing
+        random lookups here, rather than sequential scan.
       */
-      const double pq_cost=
+      const double pq_cpu_cost= 
         (PQ_slowness * num_rows + param->max_keys_per_buffer) *
-        log((double) param->max_keys_per_buffer) / TIME_FOR_COMPARE_ROWID +
-        param->max_rows * table->file->scan_time();
+        log((double) param->max_keys_per_buffer) / TIME_FOR_COMPARE_ROWID;
+      const double pq_io_cost=
+        param->max_rows * table->file->scan_time() / 2.0;
+      const double pq_cost= pq_cpu_cost + pq_io_cost;
 
       if (sort_merge_cost < pq_cost)
         DBUG_RETURN(false);


--===============0899943541472716123==
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\
#   cxd7s460s5kbf0ar
# target_branch: file:///export/home/didrik/repo/next-mr-opt-team-\
#   wl1393-merge/
# testament_sha1: 9808686324694ba67b9717298212ed4c463f64a9
# timestamp: 2010-12-10 16:06:27 +0100
# source_branch: bzr+ssh://bk-internal.mysql.com/bzrroot/server/mysql-\
#   next-mr-opt-team/
# base_revision_id: tor.didriksen@stripped\
#   xpi8jizo6f6hzc7n
# 
# Begin bundle
IyBCYXphYXIgcmV2aXNpb24gYnVuZGxlIHY0CiMKQlpoOTFBWSZTWTAQ8IgAA0pfgFQQeX///3/n
3oC////wYAbvvGwGg6s973bK1iqj77Hp6Ekk0mIaBNpNtJo00hP0pkDIGnoRpo0DQEpJT0xlPaim
2SIaMgGmgANANAABhqp5TamQyGgDRoGgyNDIAGmmg0G1GGJAUwmmVNvVJ6np6JlDT1ADQ0DJo0NP
SaAaSIaGgxGgGQ0aAaADTQ0YjQ0aBJIE00TJk00ajQTIyeiNRoekyNGm1A0DR/WyRDTps1lF50Wd
jwhB3iYMDzPM5sGEt7ceGOQJorKcNCRAYD52rpnW86peYh1RhbuBYMAnoXzXjpX8YX4ms/Q3FEpJ
JHr6ib6TjXRn0ZyDUZ4g0p7pvEA8NRBKL8iclGvGhjVf26c66si9H2g5bxHObWA411/2D7ddT98x
2Yl+tCzW8ujRepXwAapT4N/rfEGDWZbHexmzHHFudtd45LbHSTqS6fQh7JLu6MXU2StovoPLopo5
SMy62IRxMUx0BIA4Y5FUBtxUI0VljRgiaftOGvpfCyHFUo3LdbNEUBUgJ0FijXBUhJUJIRyFg7ie
pXKIbzumE0wBBGsYEnqAiAPVVQioISCQSfUpievXZtEbStRcPKxHjcCsKDW6ouf1WJI6noTl7tpv
65xC/AuRKqD4iTCo6/CNU6rYkPbSfei4O+E7UKtc/PCstUTpHnIPWuRpzfOI/epSIGC5TBMU3vUe
crvfw4M1tspOZwI5gvnHgM4QbB0hin8D9DXjic7QZSn5u64GqQ7NhuNrGOCk0EBYCVOI9awdDDdo
VFmaqNkIZHRu5Ijb+2hPYf2stCKue4sT9zBAiWEf8IhDdO8w7BFZWRuwah90whuKMVm8jWSFfgxZ
ba9MhaazBnqJqzH7o6ULTrFjDmlRT122f9qxqzEQcHLVfNasRKwQz0Zy6HjthBxfjrJDysn6cZG+
smbaIeAxfh6FcsTlriE2M9RPSu3aPqKCseOKCAs2er5EIilVI40UWSpKBB00GzuYxpGYWbCI8LjN
2BAqnrcUIENlp0KD47FWcnbbIuvPG7gMrcQNByR5gbYxIlxc59lUslhPTOUkW2hbzoZsFchW5gqq
7VKTw4CEXEQaSYiMwZyUyeUcU+nYBR45yhnOUrBJIDcVp5jybQYEAc/6/Gyq5IIpKgOx4YIKiRnx
6IWIGOcnIICbEkER8L9plQTTRIIZglSVTCRxoo9J3mYkfN5S4fId8uCXX8RolSuZNZ3RDxjhGLs7
Hu+UR4o/ATqzfID2k/ftefae48SK+nvIWlXyzQFmuXMwuhAIGfTmXK8yWBjGovyBN4Kx0Im0CLMQ
GrmGIpXdkbly8KMaq08dQ0cxqEZDTFWomYyk3FGwupJUaMuBQY5SnvNB5zLmqG+FA8kbDHV0VeNz
tHIBlNAbMpLJ6YU6vcId8WrbZks8H9BA5dZUjIpWjziLxHxGshwowJZrRQLVSgNwb80MbL7YEg2K
6rAd+Ldonu+T070Q4+TRm02AXPwMM5k394/pv7Tm4lJZK9PqYVpsoEQVhq1SeXxPGrcNrgLDDv9x
cNQDtvDNlX2t5DyCC2oO76JyIYmOflvh2PFOVdK5UJnViBIjBO88rbXCz3kqEEl+/ugphDi0cXaI
FJoI3QV7aMQnvjmDDBDw08f9WrZDYnOCznXhcPxQTVhES5mdEoao1rGFLqC2jFqXJy2hbys3IBli
VY3vbPedG0+1QERLJWnZN6Hb9ngB5bUA+rVGAVCDNCIo2UdVDQV1ZSGjFqs0SymKdkT0CqqBubnd
eXE7xXTcqqa10CLZcgsq3MKPpEGivvruNS1tEUbnr9eO+xZCZYoBknOXAIgJ9tLiE3B6dlMeiyqi
+wAwUp6kH0bTG3n6W2K6JYvYrctxEctTiDXaK840rC+kGMQrnObDMfUMnoBnm1NexJJvBRtglTsl
PO6asF0gyrZDLtw3jLrWT6pFdnE5erUm6UgiVJWPUlMx7t6A+iAYFn0AxgoSZAC/JJEAVk11AMNE
lhVRBK+zMtWzyMClA3VlXoSs1lnmQobKN7oHPiSx4l2WAYi7tTMSCLvm3E1ucwwNjlBAQUBDkAzC
cEd22AoRYR3rP1SCKr4CCa255xxm4kkTZLBMtniN2TkHcI7xErNv18hO48Gp6xA7acWWKneJy9ep
Gc2VIslYOF2ncq7FeJHTTQUHamIY5lIFXs4hpIiLSe3i8sWQul2ZxR4SCclAHyE2XFnX1Xywz7m6
lrKCbCt/Wyd5vB2rC/BsjM28YiqqCIuQ5AZO9lBRU2myN2F5yRU5OFce+59M420c2ffukdkT4erM
LepsOAKg2Nc8mffW4Q5UA2jCa4LxYkF2k+9QWgb4g61lVl/4u5IpwoSBgIeEQA==


--===============0899943541472716123==--