From 343d754a76349eff3ca0374d8c43e0d8795779e2 Mon Sep 17 00:00:00 2001
From: drh <drh@noemail.net>
Date: Wed, 24 Sep 2014 04:38:14 +0000
Subject: [PATCH] Experiment using linear interpolation, instead of a strict
 binary search, when looking for integer-keyed rows on a single b-tree page. 
 The experiment was not successful.  The number of key comparisons is reduced
 by about 15%, but the added complexity of the search logic causes an overall
 reduction in performance.  The patch is saved for historical reference only.

FossilOrigin-Name: c705cf856d314d1e9e5371b7758d3c8a46099391
---
 manifest      | 15 +++++++++------
 manifest.uuid |  2 +-
 src/btree.c   | 19 +++++++++++++++++--
 3 files changed, 27 insertions(+), 9 deletions(-)

diff --git a/manifest b/manifest
index 209072a802..1283a6770f 100644
--- a/manifest
+++ b/manifest
@@ -1,5 +1,5 @@
-C Have\sthe\sclearCell()\sroutine\sreturn\sthe\scell\ssize\sto\sthe\scaller,\srather\nthan\shave\sthe\scaller\smake\sa\sseparate\scall\sto\scellSizePtr().
-D 2014-09-24T02:05:41.968
+C Experiment\susing\slinear\sinterpolation,\sinstead\sof\sa\sstrict\sbinary\ssearch,\nwhen\slooking\sfor\sinteger-keyed\srows\son\sa\ssingle\sb-tree\spage.\s\sThe\nexperiment\swas\snot\ssuccessful.\s\sThe\snumber\sof\skey\scomparisons\sis\sreduced\nby\sabout\s15%,\sbut\sthe\sadded\scomplexity\sof\sthe\ssearch\slogic\scauses\san\s\noverall\sreduction\sin\sperformance.\s\sThe\spatch\sis\ssaved\sfor\shistorical\sreference\nonly.
+D 2014-09-24T04:38:14.865
 F Makefile.arm-wince-mingw32ce-gcc d6df77f1f48d690bd73162294bbba7f59507c72f
 F Makefile.in cf57f673d77606ab0f2d9627ca52a9ba1464146a
 F Makefile.linux-gcc 91d710bdc4998cb015f39edf3cb314ec4f4d7e23
@@ -172,7 +172,7 @@ F src/auth.c d8abcde53426275dab6243b441256fcd8ccbebb2
 F src/backup.c a31809c65623cc41849b94d368917f8bb66e6a7e
 F src/bitvec.c 19a4ba637bd85f8f63fc8c9bae5ade9fb05ec1cb
 F src/btmutex.c 49ca66250c7dfa844a4d4cb8272b87420d27d3a5
-F src/btree.c 183d62b37358f95d2ffac796f8491591a3456362
+F src/btree.c f1b4d64c99769477fd3cab1f0f058a2d146e4c14
 F src/btree.h a79aa6a71e7f1055f01052b7f821bd1c2dce95c8
 F src/btreeInt.h 9db0d303b203d18871dc9a1d78a3e1ae4d62c1ef
 F src/build.c 8dbca25988045fbf2a33c9631c42706fa6449e60
@@ -1200,7 +1200,10 @@ F tool/vdbe_profile.tcl 67746953071a9f8f2f668b73fe899074e2c6d8c1
 F tool/warnings-clang.sh f6aa929dc20ef1f856af04a730772f59283631d4
 F tool/warnings.sh 0abfd78ceb09b7f7c27c688c8e3fe93268a13b32
 F tool/win/sqlite.vsix deb315d026cc8400325c5863eef847784a219a2f
-P 5dd41cdbfebdd088ebd9a90a394ee296c207ad90
-R c3c34442c09fda273806b002932cda25
+P f21d217583c205dc17f98bb4877fd4ed98cefcb1
+R 57ef17a58ef685784b3f9bebc4b1cc14
+T *branch * linear-interpolation
+T *sym-linear-interpolation *
+T -sym-trunk *
 U drh
-Z 4d0ec3d41d82b7fff44b33f0ea314f2b
+Z c2ae9214f9fc214001752b0150fe1166
diff --git a/manifest.uuid b/manifest.uuid
index 1ee8b65c87..169bc135be 100644
--- a/manifest.uuid
+++ b/manifest.uuid
@@ -1 +1 @@
-f21d217583c205dc17f98bb4877fd4ed98cefcb1
\ No newline at end of file
+c705cf856d314d1e9e5371b7758d3c8a46099391
\ No newline at end of file
diff --git a/src/btree.c b/src/btree.c
index 9af99dd8ad..3e18bca0d6 100644
--- a/src/btree.c
+++ b/src/btree.c
@@ -4695,6 +4695,8 @@ int sqlite3BtreeMovetoUnpacked(
     idx = upr>>(1-biasRight); /* idx = biasRight ? upr : (lwr+upr)/2; */
     pCur->aiIdx[pCur->iPage] = (u16)idx;
     if( xRecordCompare==0 ){
+      u8 bits = 0;
+      i64 iLwr = 0, iUpr = 0;
       for(;;){
         i64 nCellKey;
         pCell = findCell(pPage, idx) + pPage->childPtrSize;
@@ -4707,9 +4709,13 @@ int sqlite3BtreeMovetoUnpacked(
         if( nCellKey<intKey ){
           lwr = idx+1;
           if( lwr>upr ){ c = -1; break; }
+          iLwr = nCellKey;
+          bits |= 1;
         }else if( nCellKey>intKey ){
           upr = idx-1;
           if( lwr>upr ){ c = +1; break; }
+          iUpr = nCellKey;
+          bits |= 2;
         }else{
           assert( nCellKey==intKey );
           pCur->curFlags |= BTCF_ValidNKey;
@@ -4724,8 +4730,17 @@ int sqlite3BtreeMovetoUnpacked(
             goto moveto_finish;
           }
         }
-        assert( lwr+upr>=0 );
-        idx = (lwr+upr)>>1;  /* idx = (lwr+upr)/2; */
+        assert( lwr>=0 && upr>=lwr );
+        if( bits<3 || upr<=lwr+2 ){
+          idx = (lwr+upr)>>1;  /* idx = (lwr+upr)/2; */
+        }else if( (iUpr - iLwr)>100000 ){
+          i64 spacing = (iUpr-iLwr)/(upr-lwr);
+          idx = (intKey-iLwr)/spacing+lwr;
+          assert( idx>=lwr && idx<=upr );
+        }else{
+          idx = (intKey-iLwr)*(upr-lwr)/(iUpr-iLwr)+lwr;
+          assert( idx>=lwr && idx<=upr );
+        }
       }
     }else{
       for(;;){
-- 
2.39.5