From: Tor Didriksen
Date: December 9 2010 2:09pm
Subject: bzr commit into mysql-trunk-bugfixing branch (tor.didriksen:3259) WL#1393
List-Archive: http://lists.mysql.com/commits/126427
Message-Id: <20101209140939.E6B1BADC@atum07.norway.sun.com>
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="===============8662980334663422605=="

--===============8662980334663422605==
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-09
      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-09 14:09:34 +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-09 14:09:34 +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-09 14:09:34 +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);


--===============8662980334663422605==
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\
#   3ti6e35pbk0zjuep
# target_branch: file:///export/home/didrik/repo/next-mr-opt-team-\
#   wl1393-merge/
# testament_sha1: 4a3657981bdec8431e7715c747931cfa70dc59c9
# timestamp: 2010-12-09 15:09:39 +0100
# source_branch: bzr+ssh://bk-internal.mysql.com/bzrroot/server/mysql-\
#   next-mr-opt-team/
# base_revision_id: tor.didriksen@stripped\
#   fduno7x6gpt9n2tp
# 
# Begin bundle
IyBCYXphYXIgcmV2aXNpb24gYnVuZGxlIHY0CiMKQlpoOTFBWSZTWSXcjUQAA0VfgFQQeX///3/n
3oC////wYAcHF8Bp0G47qtqiDoEjwkkmQmKYnqntE8mpjJJ6aQAGjTIzUyYjagJRTTIT0k9PUbUh
kAAAAPUZHqAAAcNNMjEYTTAQwCaYRgmJkNMjQ0AxIaImhlR+p+qTI/VP0oaHqAAGhkGhp5QBw00y
MRhNMBDAJphGCYmQ0yNDQCSSYEBMIaCj1I8NQ01GjQaAHqAAP6GSLOLi1aCqN0WRjtssd3E87zJg
c09Bf98VEJAwRaq6Kkh4wHjQtUuCIvjuH3wfRmBcLAKJC8V868HW/FSZn5HWUSkkkenoJwrR9FWj
VoINVoiTTptpESEQ1UEnjYoJPo3VL24fvr8C+1i83RKC7YfgOlgNi6f7KOnO2O6g35GOaF2cTB6r
zrCQDWqmO70RcGTXaroepmvOWTeltEZyX6nSWqTbwZkPZJfj1Yfi2PQ0XYPNsWWEpAp0sZ4ZmaY9
ARAPN6RGm4nAbgepc1dc0LUUVWp0y7Kn2vpRvNfhJEEBFASoLNGPJWPkrCKEcy0daexPDgeuQSTA
D0ZjJJwMs5VzCQTCJVISoIomE9eOdhRPctp1EfPgCsKxrdYOq7bEkdrLL37zZ3UiZpjHabESm6Ak
woKyqGb3SjfA+im6YjwRgHGE5i6dMX1lqifAVGhUoHLpg81UBxsXM2JjWupecnfPnzZrbYxczgRy
CQk/IZyMh0Tmz6mW/HWOKEH43plWALjfw7DvOmpgZ4q9nQGYCiGMT1QHiN9teYjhcUgRiyrJbTWK
s48OtBwivE/pY8CKvqcW8hE3EAW9lEkYSuJf2SCPIyiRMbSR80Qza/NCgYNvDhKoKPppCNReViSl
2AzC2ceawmB+i6tYW2f7ppVVENYCI3RVVgOQ/o4wV7xsR5iXkuuyJvoTM60VJMcxDsLclieamYS0
cXXnbXrhpuMJnFVbiq8sLiwvnnfc5FxaXFClT+C2UCW2N8mZqzUMaZnZIgF7V7DhVtxJFt2Ti6WB
EqsHYPzVKzj3lYSYRdEn1BniJmhvqXuDKaxJV6bLM9IOzKF5WZHjn1LxVVVkGC1W6FOcRACTwIk0
0xD0BpNUJ9JPL13BledSYpWFNwszMGxNn51svFBAdXh3XTYmYZMzYz87+/duqlh1ngzvIhv3t0jy
fylJD9u/mRz6KJGO+Yji4YEjjLV7DcUkj8G+WjeO+3Sl0dA0SrWxNq/EQ8Y6YCeVksni0YI3KJJQ
ZzgMlhQpyWdA/rOoyGNrv5R1Rb5aoC/S5YveMKX45N7nqTaKMbU+gzu664IMgauYUZNJ2tkTZpTF
GA4eT1seIaCNVS6YanKJzIiQiqrNwxdxPecjGov4TGrD8EczK7lH3Udq5AMpoDBW5K2Iok8y2rOs
L6QjCSVzTMoWdC0uXEIksC0y36EptIsxpWVAWhtx5sLLunSDWuWlZaDsxXZlE7dEncz+vk0JtNgF
jYZ7eAihR/qKn9p17x+ivVmbFjOvCMTOp4+OSCfBaL3XXM4KFC/JyusnDVljwVMeTYV5xBdzD0/8
nIcIfoaa+XF99QqRnXSNZM7MgIkHp3dG3W4WSNKpBJNNyWJi8mKqy4qH5s5tLZOCOYvY3Ji1EAsr
/q0X23pzg1zrt5h/BnTaAiJcjOiVnHBaRhS2hrqrWK1bK7wv2M3IBTEtY3O1UboNhsEOWNkjzN3O
34+IHlmgKpWQeEhBtQiCMa3SfqK6hXw0v5dNJzL7mRdmLjwBuz2Ois3e3XERv4UEMeeV4sFJheHe
IN6vvpeXrBoChhUvLrusWQmWSAZJzlxCoC7rvca0+t6diYbvPw21sAMHBPUh+3oYN6fkbzK+BYva
rdN5AcrnD2v4LA766BhW9jIKTnNhmPA+JOMSAFEVKvQmSo3QJt5JOZ11WG0HYAjaiEe7hqMs3RuU
SlnqOPwXJuiQQJJdtSipmfp1QH/IBhezxGYzWSA7YKwDLHz5B1wWpxGS1tFu/lu7w6VJhcxEgxVP
XslszPRhGCKWPJ+hfZuPl71rcLY/aHea1xZZK7wNMG0ZZaPQFQhkAzCeEN+14nwZB61u8IhBU5iC
a27t0MpuIpE2SxTLP3Dd84g+mf8akbTxafrEDszqy2KdwnLpcjSbKuDJWDhdq7msuWAmeLHhKEOw
xDG9TBWDQIaaIdpxbk2uyGp+WsiPKxcCjmQEHBWPfTa563wrtWw3i0FYWQ7SLZ+Nru4Rlsybabzb
1gKcggLkcgZO9tYoLtVHUZHDPE5wV5eHSHwiMu+HLAaS7Cpt3Wk3bE/l45C0VLrA5B0b53lH1KtU
A0GE1wXiyHrqRqW8Nzwd7RFoRX8XckU4UJAl3I1E


--===============8662980334663422605==--