Make the ORDER BY clause return equal elements in the same order they were

seen (a stable sort).  It was returning them in exactly the reverse order. (CVS 2439)

FossilOrigin-Name: e8391491a68018406e30c2a699a4cab9e0de092c

8 files changed, 34 insertions, 27 deletions

diff --git a/manifest b/manifest
index 693ba8715..b58bbcfc1 100644
--- a/manifest
+++ b/manifest
@@ -1,5 +1,5 @@
-C Add\sa\s"const"\sdeclaration\sto\sa\sconstant.\s\sFix\sa\stypo\sin\sa\scomment.\s(CVS\s2438)
-D 2005-03-31T22:26:20
+C Make\sthe\sORDER\sBY\sclause\sreturn\sequal\selements\sin\sthe\ssame\sorder\sthey\swere\nseen\s(a\sstable\ssort).\s\sIt\swas\sreturning\sthem\sin\sexactly\sthe\sreverse\sorder.\s(CVS\s2439)
+D 2005-04-01T10:47:40
 F Makefile.in 5c00d0037104de2a50ac7647a5f12769795957a3
 F Makefile.linux-gcc 06be33b2a9ad4f005a5f42b22c4a19dab3cbb5c7
 F README 9c4e2d6706bdcc3efdd773ce752a8cdab4f90028
@@ -75,11 +75,11 @@ F src/update.c 42823d00865c9fe4f01b3c62647858726345a28e
 F src/utf.c bda5eb85039ef16f2d17004c1e18c96e1ab0a80c
 F src/util.c 02bc2750336b021b3f10e61538f665c4b0033b5d
 F src/vacuum.c 5cf598003191bd91c17a64742bad8e46241698a8
-F src/vdbe.c 8fa793422686f801a9379385278fb5c64563dd92
+F src/vdbe.c d2574042c44baf6b1016c61e8072dec529ac748a
 F src/vdbe.h 7f586cb6d6b57764e5aac1f87107d6a95ddce24c
-F src/vdbeInt.h 97b62807bd001efd82006460ad8a8d72d1c8d36d
+F src/vdbeInt.h 4afaae2f4adcab54ad2a40dabb2e689fba7b1561
 F src/vdbeapi.c 467caa6e6fb9247528b1c7ab9132ae1b4748e8ac
-F src/vdbeaux.c 482ae8225ffa6ef050d07f627846cd2956f6a387
+F src/vdbeaux.c 3efd3cffad110508d1a32c6fa546982007f86e9f
 F src/vdbemem.c 4e853ce3151eaf7906150da85a1b3ce1fe5e8da8
 F src/where.c c4b227458e8993decb515ed9a2fe2d4f5f8e3125
 F tclinstaller.tcl 046e3624671962dc50f0481d7c25b38ef803eb42
@@ -112,8 +112,8 @@ F test/capi3b.test 5b6a66f9f295f79f443b5d3f33187fa5ef6cf336
 F test/collate1.test f79736d2ebf5492167ee4d1f4ab4c09dda776b03
 F test/collate2.test 224a632ba04907c049804b08162efd234aa7871f
 F test/collate3.test 51362bdfb43a72bd2b087d90b2623b0695538e7a
-F test/collate4.test b8668612691c4dcf90f67a8df1eeb1544e7fdaf8
-F test/collate5.test 581775b94604b7435dc6a5c6e72fbbf7d69e3830
+F test/collate4.test daf498e294dcd596b961d425c3f2dda117e4717e
+F test/collate5.test 5a49cd169e7565e4f92b42695667d6d5db25670d
 F test/collate6.test 6c9470d1606ee3e564675b229653e320c49ec638
 F test/conflict.test 3c4ef047070ce495e15d7d267a7d791d6f4ffef5
 F test/corrupt.test 18c7a995b1af76a8c8600b996257f2c7b7bff083
@@ -182,7 +182,7 @@ F test/safety.test 907b64fee719554a3622853812af3886fddbbb4f
 F test/schema.test 21cbe7dac652f6d7eb058f3dec369bdbf46bbde6
 F test/select1.test ad700a2a1c325a23a7206ad4d189e33917de526f
 F test/select2.test 01b9cbc06e5ed662ce0289aa5f47314d54541e82
-F test/select3.test 9de435aa84fc406708cd8dc1b1d60e7f27cea685
+F test/select3.test 44dccad96a1b9940bb8c6f982d4d218dcd262760
 F test/select4.test c239f516aa31f42f2ef7c6d7cd01105f08f934ca
 F test/select5.test 2d414f712bff8e590091e08f9b7287600731be00
 F test/select6.test 6e5a1a70a788cdbe515d1252dd0917d7e9d1d71e
@@ -278,7 +278,7 @@ F www/tclsqlite.tcl e73f8f8e5f20e8277619433f7970060ab01088fc
 F www/vdbe.tcl 87a31ace769f20d3627a64fa1fade7fed47b90d0
 F www/version3.tcl a99cf5f6d8bd4d5537584a2b342f0fb9fa601d8b
 F www/whentouse.tcl 528299b8316726dbcc5548e9aa0648c8b1bd055b
-P 58dd436b6572d38ea67960b8d08a0ca4359602f0
-R 4a1a43f7c6ba3d8bcf50f895dad49b29
+P 67aaa269068ea6b6f784979c09b3deb091928563
+R 63665a3d8858787beef512dcafda04c6
 U drh
-Z 17d8ec0c3783e7460fb9e5ae000b4dbf
+Z 8d91bab4e1f6465dcf7b52f8ad24856a
diff --git a/manifest.uuid b/manifest.uuid
index ef6092155..678e00459 100644
--- a/manifest.uuid
+++ b/manifest.uuid
@@ -1 +1 @@
-67aaa269068ea6b6f784979c09b3deb091928563
\ No newline at end of file
+e8391491a68018406e30c2a699a4cab9e0de092c
\ No newline at end of file
diff --git a/src/vdbe.c b/src/vdbe.c
index c55dbbe62..d25ae75ab 100644
--- a/src/vdbe.c
+++ b/src/vdbe.c
@@ -43,7 +43,7 @@
 ** in this file for details.  If in doubt, do not deviate from existing
 ** commenting and indentation practices when changing or adding code.
 **
-** $Id: vdbe.c,v 1.464 2005/03/31 18:40:05 drh Exp $
+** $Id: vdbe.c,v 1.465 2005/04/01 10:47:40 drh Exp $
 */
 #include "sqliteInt.h"
 #include "os.h"
@@ -4117,8 +4117,13 @@ case OP_SortPut: {        /* no-push */
   if( Dynamicify(pTos, db->enc) ) goto no_mem;
   pSorter = sqliteMallocRaw( sizeof(Sorter) );
   if( pSorter==0 ) goto no_mem;
-  pSorter->pNext = p->pSort;
-  p->pSort = pSorter;
+  pSorter->pNext = 0;
+  if( p->pSortTail ){
+    p->pSortTail->pNext = pSorter;
+  }else{
+    p->pSort = pSorter;
+  }
+  p->pSortTail = pSorter;
   assert( pTos->flags & MEM_Dyn );
   pSorter->nKey = pTos->n;
   pSorter->zKey = pTos->z;
diff --git a/src/vdbeInt.h b/src/vdbeInt.h
index 37dada46d..23a65067c 100644
--- a/src/vdbeInt.h
+++ b/src/vdbeInt.h
@@ -314,6 +314,7 @@ struct Vdbe {
   int nCursor;        /* Number of slots in apCsr[] */
   Cursor **apCsr;     /* One element of this array for each open cursor */
   Sorter *pSort;      /* A linked list of objects to be sorted */
+  Sorter *pSortTail;  /* Last element on the pSort list */
   int nVar;           /* Number of entries in aVar[] */
   Mem *aVar;          /* Values for the OP_Variable opcode. */
   char **azVar;       /* Name of variables */
diff --git a/src/vdbeaux.c b/src/vdbeaux.c
index 2866c3f9b..c4009eae0 100644
--- a/src/vdbeaux.c
+++ b/src/vdbeaux.c
@@ -779,6 +779,7 @@ void sqlite3VdbeSorterReset(Vdbe *p){
     sqlite3VdbeMemRelease(&pSorter->data);
     sqliteFree(pSorter);
   }
+  p->pSortTail = 0;
 }
 
 /*
diff --git a/test/collate4.test b/test/collate4.test
index 3fc3cf8d8..7dcd32d7c 100644
--- a/test/collate4.test
+++ b/test/collate4.test
@@ -12,7 +12,7 @@
 # This file implements regression tests for SQLite library.  The
 # focus of this script is page cache subsystem.
 #
-# $Id: collate4.test,v 1.7 2005/01/21 03:12:16 danielk1977 Exp $
+# $Id: collate4.test,v 1.8 2005/04/01 10:47:40 drh Exp $
 
 set testdir [file dirname $argv0]
 source $testdir/tester.tcl
@@ -95,7 +95,7 @@ do_test collate4-1.1.5 {
 } {{} A B a b nosort}
 do_test collate4-1.1.6 {
   cksort {SELECT b FROM collate4t1 ORDER BY b COLLATE NOCASE}
-} {{} A a B b sort}
+} {{} a A b B sort}
 
 do_test collate4-1.1.7 {
   execsql {
@@ -172,10 +172,10 @@ do_test collate4-1.1.21 {
 } {}
 do_test collate4-1.1.22 {
   cksort {SELECT a FROM collate4t4 ORDER BY a}
-} {{} A a B b sort}
+} {{} a A b B sort}
 do_test collate4-1.1.23 {
   cksort {SELECT a FROM collate4t4 ORDER BY a COLLATE NOCASE}
-} {{} A a B b sort}
+} {{} a A b B sort}
 do_test collate4-1.1.24 {
   cksort {SELECT a FROM collate4t4 ORDER BY a COLLATE TEXT}
 } {{} A B a b nosort}
@@ -223,7 +223,7 @@ do_test collate4-1.2.4 {
 } {{} A a B b nosort}
 do_test collate4-1.2.5 {
   cksort {SELECT a FROM collate4t1 ORDER BY a, b COLLATE nocase}
-} {{} A a B b sort}
+} {{} a A b B sort}
 do_test collate4-1.2.6 {
   cksort {SELECT a FROM collate4t1 ORDER BY a, b COLLATE text}
 } {{} A a B b nosort}
@@ -272,10 +272,10 @@ do_test collate4-1.2.14 {
 } {}
 do_test collate4-1.2.15 {
   cksort {SELECT a FROM collate4t3 ORDER BY a}
-} {{} A a B b sort}
+} {{} a A b B sort}
 do_test collate4-1.2.16 {
   cksort {SELECT a FROM collate4t3 ORDER BY a COLLATE nocase}
-} {{} A a B b sort}
+} {{} a A b B sort}
 do_test collate4-1.2.17 {
   cksort {SELECT a FROM collate4t3 ORDER BY a COLLATE text}
 } {{} A B a b nosort}
diff --git a/test/collate5.test b/test/collate5.test
index 13ac1f2e4..76cc70612 100644
--- a/test/collate5.test
+++ b/test/collate5.test
@@ -14,7 +14,7 @@
 # SELECT statements that use user-defined collation sequences. Also
 # GROUP BY clauses that use user-defined collation sequences.
 #
-# $Id: collate5.test,v 1.3 2005/01/21 04:25:47 danielk1977 Exp $
+# $Id: collate5.test,v 1.4 2005/04/01 10:47:40 drh Exp $
 
 set testdir [file dirname $argv0]
 source $testdir/tester.tcl
@@ -199,7 +199,7 @@ do_test collate5-3.0 {
   execsql {
     SELECT a FROM collate5t1 UNION ALL SELECT a FROM collate5t2 ORDER BY 1;
   }
-} {A a A a B b B b N n}
+} {a A a A b B b B n N}
 do_test collate5-3.1 {
   execsql {
     SELECT a FROM collate5t2 UNION ALL SELECT a FROM collate5t1 ORDER BY 1;
diff --git a/test/select3.test b/test/select3.test
index 2b31329cb..f0be520a2 100644
--- a/test/select3.test
+++ b/test/select3.test
@@ -12,7 +12,7 @@
 # focus of this file is testing aggregate functions and the
 # GROUP BY and HAVING clauses of SELECT statements.
 #
-# $Id: select3.test,v 1.12 2004/08/20 18:34:20 drh Exp $
+# $Id: select3.test,v 1.13 2005/04/01 10:47:40 drh Exp $
 
 set testdir [file dirname $argv0]
 source $testdir/tester.tcl
@@ -76,9 +76,9 @@ do_test select3-2.6 {
 } {1 1 3 1 5 2 7 4 9 8 11 15}
 do_test select3-2.7 {
   execsql {
-    SELECT log*2+1 AS x, count(*) AS y FROM t1 GROUP BY x ORDER BY y
+    SELECT log*2+1 AS x, count(*) AS y FROM t1 GROUP BY x ORDER BY y, x
   }
-} {3 1 1 1 5 2 7 4 9 8 11 15}
+} {1 1 3 1 5 2 7 4 9 8 11 15}
 do_test select3-2.8 {
   execsql {
     SELECT log*2+1 AS x, count(*) AS y FROM t1 GROUP BY x ORDER BY 10-(x+y)