Merge the latest trunk changes, including the multi-threaded sorter, into

the sessions branch.

FossilOrigin-Name: d4cce2c71e64ab7b6a65a81b88b69445ed859351

12 files changed, 831 insertions, 5 deletions

diff --git a/test/index7.test b/test/index7.test
index 1c81f6024..0f341a312 100644
--- a/test/index7.test
+++ b/test/index7.test
@@ -248,4 +248,34 @@ do_execsql_test index7-5.0 {
   SELECT stat+0 FROM sqlite_stat1 WHERE idx='t3b';
 } {6 6}
 
+# Verify that the problem identified by ticket [98d973b8f5] has been fixed.
+#
+do_execsql_test index7-6.1 {
+  CREATE TABLE t5(a, b);
+  CREATE TABLE t4(c, d);
+  INSERT INTO t5 VALUES(1, 'xyz');
+  INSERT INTO t4 VALUES('abc', 'not xyz');
+  SELECT * FROM (SELECT * FROM t5 WHERE a=1 AND b='xyz'), t4 WHERE c='abc';
+} {
+  1 xyz abc {not xyz}
+}
+do_execsql_test index7-6.2 {
+  CREATE INDEX i4 ON t4(c) WHERE d='xyz';
+  SELECT * FROM (SELECT * FROM t5 WHERE a=1 AND b='xyz'), t4 WHERE c='abc';
+} {
+  1 xyz abc {not xyz}
+}
+do_execsql_test index7-6.3 {
+  CREATE VIEW v4 AS SELECT * FROM t4;
+  INSERT INTO t4 VALUES('def', 'xyz');
+  SELECT * FROM v4 WHERE d='xyz' AND c='def'
+} {
+  def xyz
+}
+do_eqp_test index7-6.4 {
+  SELECT * FROM v4 WHERE d='xyz' AND c='def'
+} {
+  0 0 0 {SEARCH TABLE t4 USING INDEX i4 (c=?)}
+}
+
 finish_test
diff --git a/test/malloc.test b/test/malloc.test
index 4276b58bb..86145672a 100644
--- a/test/malloc.test
+++ b/test/malloc.test
@@ -881,6 +881,48 @@ do_malloc_test 39 -tclprep {
   db close
 }
 
+reset_db
+add_test_utf16bin_collate db
+do_execsql_test 40.1 {
+  CREATE TABLE t1(a);
+  INSERT INTO t1 VALUES('fghij');
+  INSERT INTO t1 VALUES('pqrst');
+  INSERT INTO t1 VALUES('abcde');
+  INSERT INTO t1 VALUES('uvwxy');
+  INSERT INTO t1 VALUES('klmno');
+}
+do_execsql_test 40.2 {
+  SELECT * FROM t1 ORDER BY 1 COLLATE utf16bin;
+} {abcde fghij klmno pqrst uvwxy}
+do_faultsim_test 40.3 -faults oom-trans* -body {
+  execsql {
+    SELECT * FROM t1 ORDER BY 1 COLLATE utf16bin;
+  }
+} -test {
+  faultsim_test_result {0 {abcde fghij klmno pqrst uvwxy}} 
+  faultsim_integrity_check
+}
+
+reset_db
+add_test_utf16bin_collate db
+set big [string repeat x 200]
+do_execsql_test 41.1 {
+  DROP TABLE IF EXISTS t1;
+  CREATE TABLE t1(a COLLATE utf16bin);
+  INSERT INTO t1 VALUES('fghij' || $::big);
+  INSERT INTO t1 VALUES('pqrst' || $::big);
+  INSERT INTO t1 VALUES('abcde' || $::big);
+  INSERT INTO t1 VALUES('uvwxy' || $::big);
+  INSERT INTO t1 VALUES('klmno' || $::big);
+  CREATE INDEX i1 ON t1(a);
+}
+do_faultsim_test 41.2 -faults oom* -body {
+  execsql { SELECT * FROM t1 WHERE a = ('abcde' || $::big)}
+} -test {
+  faultsim_test_result [list 0 "abcde$::big"]
+  faultsim_integrity_check
+}
+
 # Ensure that no file descriptors were leaked.
 do_test malloc-99.X {
   catch {db close}
diff --git a/test/mallocA.test b/test/mallocA.test
index 61e88a61e..d6d6de822 100644
--- a/test/mallocA.test
+++ b/test/mallocA.test
@@ -25,7 +25,6 @@ if {!$MEMDEBUG} {
    return
 }
 
-
 # Construct a test database
 #
 forcedelete test.db.bu
@@ -116,6 +115,28 @@ ifcapable stat3 {
   }
 }
 
+do_execsql_test 7.0 {
+  PRAGMA cache_size = 5;
+}
+do_faultsim_test 7 -faults oom-trans* -prep {
+  if {$iFail < 500} { set iFail 2000 }
+  if {$iFail > 1215} { set iFail 2000 }
+} -body {
+  execsql {
+    WITH r(x,y) AS (
+      SELECT 1, randomblob(100)
+      UNION ALL
+      SELECT x+1, randomblob(100) FROM r
+      LIMIT 1000
+    )
+    SELECT count(x), length(y) FROM r GROUP BY (x%5)
+  }
+} -test {
+  set res [list 200 100 200 100 200 100 200 100 200 100]
+  faultsim_test_result [list 0 $res]
+}
+
+
 # Ensure that no file descriptors were leaked.
 do_test malloc-99.X {
   catch {db close}
diff --git a/test/permutations.test b/test/permutations.test
index efa27468e..7bea39eb7 100644
--- a/test/permutations.test
+++ b/test/permutations.test
@@ -115,7 +115,7 @@ set allquicktests [test_set $alltests -exclude {
   incrvacuum_ioerr.test autovacuum_crash.test btree8.test shared_err.test
   vtab_err.test walslow.test walcrash.test walcrash3.test
   walthread.test rtree3.test indexfault.test securedel2.test
-  fts4growth.test fts4growth2.test
+  sort3.test sort4.test fts4growth.test fts4growth2.test
 }]
 if {[info exists ::env(QUICKTEST_INCLUDE)]} {
   set allquicktests [concat $allquicktests $::env(QUICKTEST_INCLUDE)]
@@ -358,6 +358,12 @@ test_suite "coverage-analyze" -description {
   analyze.test analyzeB.test mallocA.test
 } 
 
+test_suite "coverage-sorter" -description {
+  Coverage tests for file vdbesort.c.
+} -files {
+  sort.test sortfault.test
+} 
+
 
 lappend ::testsuitelist xxx
 #-------------------------------------------------------------------------
@@ -489,7 +495,7 @@ test_suite "multithread" -description {
 } -files {
   delete.test   delete2.test  insert.test  rollback.test  select1.test
   select2.test  trans.test    update.test  vacuum.test    types.test
-  types2.test   types3.test
+  types2.test   types3.test   sort4.test
 } -shutdown {
   catch {db close}
   sqlite3_shutdown
diff --git a/test/sort.test b/test/sort.test
index 08d496b25..1c89552bb 100644
--- a/test/sort.test
+++ b/test/sort.test
@@ -8,10 +8,10 @@
 #    May you share freely, never taking more than you give.
 #
 #***********************************************************************
+#
 # This file implements regression tests for SQLite library.  The
-# focus of this file is testing the CREATE TABLE statement.
+# focus of this file is testing the sorter (code in vdbesort.c).
 #
-# $Id: sort.test,v 1.25 2005/11/14 22:29:06 drh Exp $
 
 set testdir [file dirname $argv0]
 source $testdir/tester.tcl
@@ -464,4 +464,175 @@ do_test sort-12.1 {
   }
 } {1 2 xxx 1 3 yyy 1 1 zzz}
 
+#-------------------------------------------------------------------------
+# Check that the sorter in vdbesort.c sorts in a stable fashion.
+#
+do_execsql_test sort-13.0 {
+  CREATE TABLE t10(a, b);
+}
+do_test sort-13.1 {
+  db transaction {
+    for {set i 0} {$i < 100000} {incr i} {
+      execsql { INSERT INTO t10 VALUES( $i/10, $i%10 ) }
+    }
+  }
+} {}
+do_execsql_test sort-13.2 {
+  SELECT a, b FROM t10 ORDER BY a;
+} [db eval {SELECT a, b FROM t10 ORDER BY a, b}]
+do_execsql_test sort-13.3 {
+  PRAGMA cache_size = 5;
+  SELECT a, b FROM t10 ORDER BY a;
+} [db eval {SELECT a, b FROM t10 ORDER BY a, b}]
+
+#-------------------------------------------------------------------------
+# Sort some large ( > 4KiB) records.
+#
+proc cksum {x} {
+  set i1 1
+  set i2 2
+  binary scan $x c* L
+  foreach {a b} $L {
+    set i1 [expr (($i2<<3) + $a) & 0x7FFFFFFF]
+    set i2 [expr (($i1<<3) + $b) & 0x7FFFFFFF]
+  }
+  list $i1 $i2
+}
+db func cksum cksum
+
+do_execsql_test sort-14.0 {
+  PRAGMA cache_size = 5;
+  CREATE TABLE t11(a, b);
+  INSERT INTO t11 VALUES(randomblob(5000), NULL);
+  INSERT INTO t11 SELECT randomblob(5000), NULL FROM t11; --2
+  INSERT INTO t11 SELECT randomblob(5000), NULL FROM t11; --3
+  INSERT INTO t11 SELECT randomblob(5000), NULL FROM t11; --4
+  INSERT INTO t11 SELECT randomblob(5000), NULL FROM t11; --5
+  INSERT INTO t11 SELECT randomblob(5000), NULL FROM t11; --6
+  INSERT INTO t11 SELECT randomblob(5000), NULL FROM t11; --7
+  INSERT INTO t11 SELECT randomblob(5000), NULL FROM t11; --8
+  INSERT INTO t11 SELECT randomblob(5000), NULL FROM t11; --9
+  UPDATE t11 SET b = cksum(a);
+}
+
+foreach {tn mmap_limit} {
+  1 0
+  2 1000000
+} {
+  do_test sort-14.$tn {
+    sqlite3_test_control SQLITE_TESTCTRL_SORTER_MMAP db $mmap_limit
+    set prev ""
+    db eval { SELECT * FROM t11 ORDER BY b } {
+      if {$b != [cksum $a]} {error "checksum failed"}
+      if {[string compare $b $prev] < 0} {error "sort failed"}
+      set prev $b
+    }
+    set {} {}
+  } {}
+}
+
+#-------------------------------------------------------------------------
+#
+foreach {tn mmap_limit nWorker tmpstore coremutex fakeheap softheaplimit} {
+          1          0       3     file      true    false             0
+          2          0       3     file      true     true             0
+          3          0       0     file      true    false             0
+          4    1000000       3     file      true    false             0
+          5          0       0   memory     false     true             0
+          6          0       0     file     false     true       1000000     
+          7          0       0     file     false     true         10000
+} {
+  db close
+  sqlite3_shutdown
+  if {$coremutex} {
+    sqlite3_config multithread
+  } else {
+    sqlite3_config singlethread
+  }
+  sqlite3_initialize
+  sorter_test_fakeheap $fakeheap
+  sqlite3_soft_heap_limit $softheaplimit
+
+  reset_db
+  sqlite3_test_control SQLITE_TESTCTRL_SORTER_MMAP db $mmap_limit
+  execsql "PRAGMA temp_store = $tmpstore; PRAGMA threads = $nWorker"
+  
+  
+  set ten [string repeat X 10300]
+  set one [string repeat y   200]
+
+  if {$softheaplimit} {
+    execsql { PRAGMA cache_size = 20 };
+  } else {
+    execsql { PRAGMA cache_size = 5 };
+  }
+
+  do_execsql_test 15.$tn.1 {
+    WITH rr AS (
+      SELECT 4, $ten UNION ALL
+      SELECT 2, $one UNION ALL
+      SELECT 1, $ten UNION ALL
+      SELECT 3, $one
+    )
+    SELECT * FROM rr ORDER BY 1;
+  } [list 1 $ten 2 $one 3 $one 4 $ten]
+
+  do_execsql_test 15.$tn.2 {
+    CREATE TABLE t1(a);
+    INSERT INTO t1 VALUES(4);
+    INSERT INTO t1 VALUES(5);
+    INSERT INTO t1 VALUES(3);
+    INSERT INTO t1 VALUES(2);
+    INSERT INTO t1 VALUES(6);
+    INSERT INTO t1 VALUES(1);
+    CREATE INDEX i1 ON t1(a);
+    SELECT * FROM t1 ORDER BY a;
+  } {1 2 3 4 5 6}
+
+  do_execsql_test 15.$tn.3 {
+    WITH rr AS (
+      SELECT 4, $ten UNION ALL
+      SELECT 2, $one
+    )
+    SELECT * FROM rr ORDER BY 1;
+  } [list 2 $one 4 $ten]
+
+  sorter_test_fakeheap 0
+}
+
+db close
+sqlite3_shutdown
+set t(0) singlethread
+set t(1) multithread
+set t(2) serialized
+sqlite3_config $t($sqlite_options(threadsafe))
+sqlite3_initialize
+sqlite3_soft_heap_limit 0
+
+reset_db
+do_catchsql_test 16.1 {
+  CREATE TABLE t1(a, b, c);
+  INSERT INTO t1 VALUES(1, 2, 3);
+  INSERT INTO t1 VALUES(1, NULL, 3);
+  INSERT INTO t1 VALUES(NULL, 2, 3);
+  INSERT INTO t1 VALUES(1, 2, NULL);
+  INSERT INTO t1 VALUES(4, 5, 6);
+  CREATE UNIQUE INDEX i1 ON t1(b, a, c);
+} {0 {}}
+reset_db
+do_catchsql_test 16.2 {
+  CREATE TABLE t1(a, b, c);
+  INSERT INTO t1 VALUES(1, 2, 3);
+  INSERT INTO t1 VALUES(1, NULL, 3);
+  INSERT INTO t1 VALUES(1, 2, 3);
+  INSERT INTO t1 VALUES(1, 2, NULL);
+  INSERT INTO t1 VALUES(4, 5, 6);
+  CREATE UNIQUE INDEX i1 ON t1(b, a, c);
+} {1 {UNIQUE constraint failed: t1.b, t1.a, t1.c}}
+
+reset_db
+do_execsql_test 17.1 {
+  SELECT * FROM sqlite_master ORDER BY sql;
+} {}
+
 finish_test
diff --git a/test/sort2.test b/test/sort2.test
new file mode 100644
index 000000000..29001f009
--- /dev/null
+++ b/test/sort2.test
@@ -0,0 +1,80 @@
+# 2014 March 25.
+#
+# The author disclaims copyright to this source code.  In place of
+# a legal notice, here is a blessing:
+#
+#    May you do good and not evil.
+#    May you find forgiveness for yourself and forgive others.
+#    May you share freely, never taking more than you give.
+#
+#***********************************************************************
+# This file implements regression tests for SQLite library. 
+#
+# Specifically, the tests in this file attempt to verify that 
+# multi-threaded sorting works.
+#
+
+set testdir [file dirname $argv0]
+source $testdir/tester.tcl
+set testprefix sort2
+
+foreach {tn script} {
+  1 { }
+  2 {
+    catch { db close }
+    reset_db
+    catch { db eval {PRAGMA threads=7} }
+  }
+} {
+
+  eval $script
+
+  do_execsql_test $tn.1 {
+    PRAGMA cache_size = 5;
+    WITH r(x,y) AS (
+      SELECT 1, randomblob(100)
+      UNION ALL
+      SELECT x+1, randomblob(100) FROM r
+      LIMIT 100000
+    )
+    SELECT count(x), length(y) FROM r GROUP BY (x%5)
+  } {
+    20000 100 20000 100 20000 100 20000 100 20000 100
+  }
+
+  do_execsql_test $tn.2.1 {
+    CREATE TABLE t1(a, b);
+    WITH r(x,y) AS (
+      SELECT 1, randomblob(100)
+      UNION ALL
+      SELECT x+1, randomblob(100) FROM r
+      LIMIT 10000
+    ) INSERT INTO t1 SELECT * FROM r;
+  }
+  
+  do_execsql_test $tn.2.2 {
+    CREATE UNIQUE INDEX i1 ON t1(b, a);
+  }
+  
+  do_execsql_test $tn.2.3 {
+    CREATE UNIQUE INDEX i2 ON t1(a);
+  }
+  
+  do_execsql_test $tn.2.4 { PRAGMA integrity_check } {ok}
+  
+  breakpoint
+  do_execsql_test $tn.3 {
+    PRAGMA cache_size = 5;
+    WITH r(x,y) AS (
+      SELECT 1, randomblob(100)
+      UNION ALL
+      SELECT x+1, randomblob(100) FROM r
+      LIMIT 1000000
+    )
+    SELECT count(x), length(y) FROM r GROUP BY (x%5)
+  } {
+    200000 100 200000 100 200000 100 200000 100 200000 100
+  }
+}
+
+finish_test
diff --git a/test/sort3.test b/test/sort3.test
new file mode 100644
index 000000000..80d8bbca3
--- /dev/null
+++ b/test/sort3.test
@@ -0,0 +1,67 @@
+# 2014 March 25.
+#
+# The author disclaims copyright to this source code.  In place of
+# a legal notice, here is a blessing:
+#
+#    May you do good and not evil.
+#    May you find forgiveness for yourself and forgive others.
+#    May you share freely, never taking more than you give.
+#
+#***********************************************************************
+# This file implements regression tests for SQLite library. 
+#
+# The tests in this file verify that sorting works when the library is
+# configured to use mmap(), but the temporary files generated by the
+# sorter are too large to be completely mapped.
+#
+
+set testdir [file dirname $argv0]
+source $testdir/tester.tcl
+set testprefix sort3
+
+# Sort roughly 20MB of data. Once with a mmap limit of 5MB and once without.
+#
+foreach {itest limit} {
+  1 5000000
+  2 0x7FFFFFFF
+} {
+  sqlite3_test_control SQLITE_TESTCTRL_SORTER_MMAP db $limit
+  do_execsql_test 1.$itest {
+    WITH r(x,y) AS (
+        SELECT 1, randomblob(1000)
+        UNION ALL
+        SELECT x+1, randomblob(1000) FROM r
+        LIMIT 20000
+    )
+    SELECT count(*), sum(length(y)) FROM r GROUP BY (x%5);
+  } {
+    4000 4000000 
+    4000 4000000 
+    4000 4000000 
+    4000 4000000 
+    4000 4000000
+  }
+}
+
+# Sort more than 2GB of data. At one point this was causing a problem.
+# This test might take one minute or more to run.
+#
+do_execsql_test 2 {
+  PRAGMA cache_size = 20000;
+  WITH r(x,y) AS (
+    SELECT 1, randomblob(1000)
+    UNION ALL
+    SELECT x+1, randomblob(1000) FROM r
+    LIMIT 2200000
+  )
+  SELECT count(*), sum(length(y)) FROM r GROUP BY (x%5);
+} {
+  440000 440000000 
+  440000 440000000 
+  440000 440000000 
+  440000 440000000 
+  440000 440000000
+}
+
+finish_test
+
diff --git a/test/sort4.test b/test/sort4.test
new file mode 100644
index 000000000..01fcbfee9
--- /dev/null
+++ b/test/sort4.test
@@ -0,0 +1,189 @@
+# 2014 May 6.
+#
+# The author disclaims copyright to this source code.  In place of
+# a legal notice, here is a blessing:
+#
+#    May you do good and not evil.
+#    May you find forgiveness for yourself and forgive others.
+#    May you share freely, never taking more than you give.
+#
+#***********************************************************************
+# This file implements regression tests for SQLite library. 
+#
+# The tests in this file are brute force tests of the multi-threaded
+# sorter.
+#
+
+set testdir [file dirname $argv0]
+source $testdir/tester.tcl
+set testprefix sort4
+
+# Configure the sorter to use 3 background threads.
+db eval {PRAGMA threads=3}
+
+# Minimum number of seconds to run for. If the value is 0, each test
+# is run exactly once. Otherwise, tests are repeated until the timeout
+# expires.
+set SORT4TIMEOUT 0
+if {[permutation] == "multithread"} { set SORT4TIMEOUT 300 }
+
+#--------------------------------------------------------------------
+# Set up a table "t1" containing $nRow rows. Each row contains also
+# contains blob fields that collectively contain at least $nPayload 
+# bytes of content. The table schema is as follows:
+#
+#   CREATE TABLE t1(a INTEGER, <extra-columns>, b INTEGER);
+#
+# For each row, the values of columns "a" and "b" are set to the same
+# pseudo-randomly selected integer. The "extra-columns", of which there
+# are at most eight, are named c0, c1, c2 etc. Column c0 contains a 4
+# byte string. Column c1 an 8 byte string. Field c2 16 bytes, and so on.
+#
+# This table is intended to be used for testing queries of the form: 
+#
+#   SELECT a, <cols>, b FROM t1 ORDER BY a;
+#
+# The test code checks that rows are returned in order, and that the 
+# values of "a" and "b" are the same for each row (the idea being that
+# if field "b" at the end of the sorter record has not been corrupted, 
+# the rest of the record is probably Ok as well).
+#
+proc populate_table {nRow nPayload} {
+  set nCol 0
+
+  set n 0
+  for {set nCol 0} {$n < $nPayload} {incr nCol} {
+    incr n [expr (4 << $nCol)]
+  }
+
+  set cols [lrange [list xxx c0 c1 c2 c3 c4 c5 c6 c7] 1 $nCol]
+  set data [lrange [list xxx \
+      randomblob(4) randomblob(8) randomblob(16) randomblob(32) \
+      randomblob(64) randomblob(128) randomblob(256) randomblob(512) \
+  ] 1 $nCol]
+
+  execsql { DROP TABLE IF EXISTS t1 }
+
+  db transaction {
+    execsql "CREATE TABLE t1(a, [join $cols ,], b);"
+    set insert "INSERT INTO t1 VALUES(:k, [join $data ,], :k)"
+    for {set i 0} {$i < $nRow} {incr i} {
+      set k [expr int(rand()*1000000000)]
+      execsql $insert
+    }
+  }
+}
+
+# Helper for [do_sorter_test]
+#
+proc sorter_test {nRow nRead nPayload} {
+  set res [list]
+
+  set nLoad [expr ($nRow > $nRead) ? $nRead : $nRow]
+
+  set nPayload [expr (($nPayload+3)/4) * 4]
+  set cols [list]
+  foreach {mask col} { 
+    0x04  c0 0x08  c1 0x10  c2 0x20  c3 
+    0x40  c4 0x80  c5 0x100 c6 0x200 c7 
+  } {
+    if {$nPayload & $mask} { lappend cols $col }
+  }
+
+  # Create two SELECT statements. Statement $sql1 uses the sorter to sort
+  # $nRow records of a bit over $nPayload bytes each read from the "t1"
+  # table created by [populate_table] proc above. Rows are sorted in order
+  # of the integer field in each "t1" record.
+  #
+  # The second SQL statement sorts the same set of rows as the first, but
+  # uses a LIMIT clause, causing SQLite to use a temp table instead of the
+  # sorter for sorting.
+  #
+  set sql1 "SELECT a, [join $cols ,], b FROM t1 WHERE rowid<=$nRow ORDER BY a"
+  set sql2 "SELECT a FROM t1 WHERE rowid<=$nRow ORDER BY a LIMIT $nRead"
+
+  # Pass the two SQL statements to a helper command written in C. This
+  # command steps statement $sql1 $nRead times and compares the integer
+  # values in the rows returned with the results of executing $sql2. If
+  # the comparison fails (indicating some bug in the sorter), a Tcl
+  # exception is thrown.
+  #
+  sorter_test_sort4_helper db $sql1 $nRead $sql2
+  set {} {} 
+}
+
+# Usage:
+#
+#   do_sorter_test <testname> <args>...
+#
+# where <args> are any of the following switches:
+#
+#   -rows N          (number of rows to have sorter sort)
+#   -read N          (number of rows to read out of sorter)
+#   -payload N       (bytes of payload to read with each row)
+#   -cachesize N     (Value for "PRAGMA cache_size = ?")
+#   -repeats N       (number of times to repeat test)
+#   -fakeheap BOOL   (true to use separate allocations for in-memory records)
+#
+proc do_sorter_test {tn args} {
+  set a(-rows)      1000
+  set a(-repeats)   1
+  set a(-read)      100
+  set a(-payload)   100
+  set a(-cachesize) 100
+  set a(-fakeheap)  0
+
+  foreach {s val} $args {
+    if {[info exists a($s)]==0} { 
+      unset a(-cachesize)
+      set optlist "[join [array names a] ,] or -cachesize"
+      error "Unknown option $s, expected $optlist"
+    }
+    set a($s) $val
+  }
+  if {[permutation] == "memsys3" || [permutation] == "memsys5"} {
+    set a(-fakeheap) 0
+  }
+  if {$a(-fakeheap)} { sorter_test_fakeheap 1 }
+
+
+  db eval "PRAGMA cache_size = $a(-cachesize)"
+  do_test $tn [subst -nocommands {
+    for {set i 0} {[set i] < $a(-repeats)} {incr i} {
+      sorter_test $a(-rows) $a(-read) $a(-payload)
+    }
+  }] {}
+
+  if {$a(-fakeheap)} { sorter_test_fakeheap 0 }
+}
+
+proc clock_seconds {} {
+  db one {SELECT strftime('%s')}
+}
+
+#-------------------------------------------------------------------------
+# Begin tests here.
+
+# Create a test database.
+do_test 1 {
+  execsql "PRAGMA page_size = 4096"
+  populate_table 100000 500
+} {}
+
+set iTimeLimit [expr [clock_seconds] + $SORT4TIMEOUT]
+
+for {set t 2} {1} {incr tn} {
+  do_sorter_test $t.2 -repeats 10 -rows 1000   -read 100
+  do_sorter_test $t.3 -repeats 10 -rows 100000 -read 1000
+  do_sorter_test $t.4 -repeats 10 -rows 100000 -read 1000 -payload 500
+  do_sorter_test $t.5 -repeats 10 -rows 100000 -read 100000 -payload 8
+  do_sorter_test $t.6 -repeats 10 -rows 100000 -read 10 -payload 8
+  do_sorter_test $t.7 -repeats 10 -rows 10000 -read 10000 -payload 8 -fakeheap 1
+  do_sorter_test $t.8 -repeats 10 -rows 100000 -read 10000 -cachesize 250
+
+  set iNow [clock_seconds]
+  if {$iNow>=$iTimeLimit} break
+  do_test "$testprefix-([expr $iTimeLimit-$iNow] seconds remain)" {} {}
+}
+
+finish_test
diff --git a/test/sortfault.test b/test/sortfault.test
new file mode 100644
index 000000000..a1983ac1c
--- /dev/null
+++ b/test/sortfault.test
@@ -0,0 +1,165 @@
+# 2014 March 25.
+#
+# The author disclaims copyright to this source code.  In place of
+# a legal notice, here is a blessing:
+#
+#    May you do good and not evil.
+#    May you find forgiveness for yourself and forgive others.
+#    May you share freely, never taking more than you give.
+#
+#***********************************************************************
+# This file implements regression tests for SQLite library. 
+#
+# Specifically, it tests the effects of fault injection on the sorter
+# module (code in vdbesort.c).
+#
+
+set testdir [file dirname $argv0]
+source $testdir/tester.tcl
+set testprefix sortfault
+
+do_execsql_test 1.0 {
+  PRAGMA cache_size = 5;
+}
+
+foreach {tn mmap_limit nWorker tmpstore threadsmode fakeheap lookaside} {
+          1          0       0     file multithread    false     false
+          2     100000       0     file multithread    false     false
+          3     100000       1     file multithread    false     false
+          4    2000000       0     file singlethread   false      true
+} {
+  if {$sqlite_options(threadsafe)} { set threadsmode singlethread }
+
+  db eval "PRAGMA threads=$nWorker"
+  sqlite3_config $threadsmode
+  if { $lookaside } {
+    sqlite3_config_lookaside 100 500
+  } else {
+    sqlite3_config_lookaside 0 0
+  }
+  sqlite3_initialize
+  sorter_test_fakeheap $fakeheap
+
+  set str [string repeat a 1000]
+  puts $threadsmode
+
+  do_faultsim_test 1.$tn -prep {
+    sqlite3 db test.db
+    sqlite3_test_control SQLITE_TESTCTRL_SORTER_MMAP db $::mmap_limit
+    execsql { PRAGMA cache_size = 5 }
+  } -body {
+    execsql { 
+      WITH r(x,y) AS (
+          SELECT 1, $::str
+          UNION ALL
+          SELECT x+1, $::str FROM r
+          LIMIT 200
+      )
+      SELECT count(x), length(y) FROM r GROUP BY (x%5)
+    }
+  } -test {
+    faultsim_test_result {0 {40 1000 40 1000 40 1000 40 1000 40 1000}}
+  }
+
+  do_faultsim_test 2.$tn -faults oom* -prep {
+    sqlite3 db test.db
+    sqlite3_test_control SQLITE_TESTCTRL_SORTER_MMAP db $::mmap_limit
+    add_test_utf16bin_collate db
+    execsql { PRAGMA cache_size = 5 }
+  } -body {
+    execsql { 
+      WITH r(x,y) AS (
+          SELECT 100, $::str
+          UNION ALL
+          SELECT x-1, $::str FROM r
+          LIMIT 100
+      )
+      SELECT count(x), length(y) FROM r GROUP BY y COLLATE utf16bin, (x%5)
+    }
+  } -test {
+    faultsim_test_result {0 {20 1000 20 1000 20 1000 20 1000 20 1000}}
+  }
+
+  if {$mmap_limit > 1000000} {
+    set str2 [string repeat $str 10]
+
+    sqlite3_memdebug_vfs_oom_test 0
+    sqlite3 db test.db
+    sqlite3_test_control SQLITE_TESTCTRL_SORTER_MMAP db $::mmap_limit
+    execsql { PRAGMA cache_size = 5 }
+
+    do_faultsim_test 3.$tn -faults oom-trans* -body {
+      execsql { 
+        WITH r(x,y) AS (
+            SELECT 300, $::str2
+            UNION ALL
+            SELECT x-1, $::str2 FROM r
+            LIMIT 300
+        )
+        SELECT count(x), length(y) FROM r GROUP BY y, (x%5)
+      }
+    } -test {
+      faultsim_test_result {0 {60 10000 60 10000 60 10000 60 10000 60 10000}}
+    }
+
+    sqlite3_memdebug_vfs_oom_test 1
+  }
+}
+
+catch { db close }
+sqlite3_shutdown
+set t(0) singlethread
+set t(1) multithread
+set t(2) serialized
+sqlite3_config $t($sqlite_options(threadsafe))
+sqlite3_config_lookaside 100 500
+sqlite3_initialize
+
+#-------------------------------------------------------------------------
+#
+reset_db
+do_execsql_test 4.0 { 
+  CREATE TABLE t1(a, b, c); 
+  INSERT INTO t1 VALUES(1, 2, 3);
+}
+do_test 4.1 { 
+  for {set i 0} {$i < 256} {incr i} {
+    execsql { 
+      INSERT INTO t1 SELECT
+        ((a<<3) + b) & 2147483647,
+        ((b<<3) + c) & 2147483647,
+        ((c<<3) + a) & 2147483647
+      FROM t1 ORDER BY rowid DESC LIMIT 1;
+    }
+  }
+} {}
+
+faultsim_save_and_close
+
+do_faultsim_test 4.2 -faults oom* -prep {
+  faultsim_restore_and_reopen
+} -body {
+  execsql { CREATE UNIQUE INDEX i1 ON t1(a,b,c) }
+} -test {
+  faultsim_test_result {0 {}}
+}
+
+#-------------------------------------------------------------------------
+#
+reset_db
+set a [string repeat a 500]
+set b [string repeat b 500]
+set c [string repeat c 500]
+do_execsql_test 5.0 { 
+  CREATE TABLE t1(a, b, c); 
+  INSERT INTO t1 VALUES($a, $b, $c); 
+  INSERT INTO t1 VALUES($c, $b, $a); 
+}
+
+do_faultsim_test 5.1 -faults oom* -body {
+  execsql { SELECT * FROM t1 ORDER BY a }
+} -test {
+  faultsim_test_result [list 0 [list $::a $::b $::c $::c $::b $::a]]
+}
+
+finish_test
diff --git a/test/speedtest1.c b/test/speedtest1.c
index 383f5809a..8589b1633 100644
--- a/test/speedtest1.c
+++ b/test/speedtest1.c
@@ -27,6 +27,7 @@ static const char zHelp[] =
   "  --stats             Show statistics at the end\n"
   "  --testset T         Run test-set T\n"
   "  --trace             Turn on SQL tracing\n"
+  "  --threads N         Use up to N threads for sorting\n"
   "  --utf16be           Set text encoding to UTF-16BE\n"
   "  --utf16le           Set text encoding to UTF-16LE\n"
   "  --verify            Run additional verification steps.\n"
@@ -1141,6 +1142,7 @@ int main(int argc, char **argv){
   int nPCache = 0, szPCache = 0;/* --pcache configuration */
   int nScratch = 0, szScratch=0;/* --scratch configuration */
   int showStats = 0;            /* True for --stats */
+  int nThread = 0;              /* --threads value */
   const char *zTSet = "main";   /* Which --testset torun */
   int doTrace = 0;              /* True for --trace */
   const char *zEncoding = 0;    /* --utf16be or --utf16le */
@@ -1225,6 +1227,9 @@ int main(int argc, char **argv){
         zTSet = argv[++i];
       }else if( strcmp(z,"trace")==0 ){
         doTrace = 1;
+      }else if( strcmp(z,"threads")==0 ){
+        if( i>=argc-1 ) fatal_error("missing argument on %s\n", argv[i]);
+        nThread = integerValue(argv[++i]);
       }else if( strcmp(z,"utf16le")==0 ){
         zEncoding = "utf16le";
       }else if( strcmp(z,"utf16be")==0 ){
@@ -1290,6 +1295,7 @@ int main(int argc, char **argv){
   /* Set database connection options */
   sqlite3_create_function(g.db, "random", 0, SQLITE_UTF8, 0, randomFunc, 0, 0);
   if( doTrace ) sqlite3_trace(g.db, traceCallback, 0);
+  speedtest1_exec("PRAGMA threads=%d", nThread);
   if( zKey ){
     speedtest1_exec("PRAGMA key('%s')", zKey);
   }
diff --git a/test/tester.tcl b/test/tester.tcl
index d19658d38..05c2aaeb0 100644
--- a/test/tester.tcl
+++ b/test/tester.tcl
@@ -1083,6 +1083,7 @@ proc explain_i {sql {db db}} {
   foreach opcode {
       Seek SeekGe SeekGt SeekLe SeekLt NotFound Last Rewind
       NoConflict Next Prev VNext VPrev VFilter
+      SorterSort SorterNext
   } {
     set color($opcode) $B
   }
@@ -1105,6 +1106,7 @@ proc explain_i {sql {db db}} {
 
     if {$opcode=="Next"  || $opcode=="Prev" 
      || $opcode=="VNext" || $opcode=="VPrev"
+     || $opcode=="SorterNext"
     } {
       for {set i $p2} {$i<$addr} {incr i} {
         incr x($i) 2
diff --git a/test/whereJ.test b/test/whereJ.test
index 5209f1619..7c37321cb 100644
--- a/test/whereJ.test
+++ b/test/whereJ.test
@@ -371,5 +371,52 @@ do_execsql_test whereJ-2.2 {
   ORDER BY t4.x;
 } {~/SCAN/}
 
+############################################################################
+
+ifcapable stat4 {
+  # Create and populate table.
+  do_execsql_test 3.1 { CREATE TABLE t1(a, b, c) }
+  for {set i 0} {$i < 32} {incr i 2} {
+    for {set x 0} {$x < 100} {incr x} {
+      execsql { INSERT INTO t1 VALUES($i, $x, $c) }
+      incr c
+    }
+    execsql { INSERT INTO t1 VALUES($i+1, 5, $c) }
+    incr c
+  }
+  
+  do_execsql_test 3.2 {
+    SELECT a, count(*) FROM t1 GROUP BY a HAVING a < 8;
+  } {
+    0 100 1 1 2 100 3 1 4 100 5 1 6 100 7 1
+  }
+  
+  do_execsql_test 3.3 {
+    CREATE INDEX idx_ab ON t1(a, b);
+    CREATE INDEX idx_c ON t1(c);
+    ANALYZE;
+  } {}
+  
+  # This one should use index "idx_c".
+  do_eqp_test 3.4 {
+    SELECT * FROM t1 WHERE 
+      a = 4 AND b BETWEEN 20 AND 80           -- Matches 80 rows
+        AND
+      c BETWEEN 150 AND 160                   -- Matches 10 rows
+  } {
+    0 0 0 {SEARCH TABLE t1 USING INDEX idx_c (c>? AND c<?)}
+  }
+  
+  # This one should use index "idx_ab".
+  do_eqp_test 3.5 {
+    SELECT * FROM t1 WHERE 
+      a = 5 AND b BETWEEN 20 AND 80           -- Matches 1 row
+        AND
+      c BETWEEN 150 AND 160                   -- Matches 10 rows
+  } {
+    0 0 0 {SEARCH TABLE t1 USING INDEX idx_ab (a=? AND b>? AND b<?)}
+  }
+}
+
 
 finish_test