Where possible, transform the DISTINCT qualifier to a GROUP BY clause. GROUP BY clauses may be optimized by indices, DISTINCT qualifiers cannot. (CVS 4538)

FossilOrigin-Name: e56331234791cf3d830a30e4cfa66682bdf2eed1

6 files changed, 42 insertions, 21 deletions

diff --git a/manifest b/manifest
index 6a753742d..48bf70707 100644
--- a/manifest
+++ b/manifest
@@ -1,5 +1,5 @@
-C Allow\scollation\ssequence\snames\sto\sbe\squoted.\sTicket\s#2744.\s(CVS\s4537)
-D 2007-11-12T09:50:26
+C Where\spossible,\stransform\sthe\sDISTINCT\squalifier\sto\sa\sGROUP\sBY\sclause.\sGROUP\sBY\sclauses\smay\sbe\soptimized\sby\sindices,\sDISTINCT\squalifiers\scannot.\s(CVS\s4538)
+D 2007-11-12T15:29:19
 F Makefile.in 30c7e3ba426ddb253b8ef037d1873425da6009a8
 F Makefile.linux-gcc 65241babba6faf1152bf86574477baab19190499
 F README 9c4e2d6706bdcc3efdd773ce752a8cdab4f90028
@@ -128,7 +128,7 @@ F src/pragma.c 363e548dafb52327face8d99757ab56a7b1c1b26
 F src/prepare.c 663284f62a73a48b89f5f4e769e155fefba60384
 F src/printf.c 96c8d55315a13fc53cb3754cb15046f3ff891ea2
 F src/random.c 4a22746501bf36b0a088c66e38dde5daba6a35da
-F src/select.c 4706a6115da1bdc09a2be5991168a6cc2c0df267
+F src/select.c 19fb48509aa5dbdda5f31b92eec6743535dc0316
 F src/server.c 087b92a39d883e3fa113cae259d64e4c7438bc96
 F src/shell.c 0b9dd90afc34f28b8786638155d32f6248d0bf0a
 F src/sqlite.h.in 3844177d389d58bd4a8be4ee81eefb01a084ed72
@@ -225,7 +225,7 @@ F test/collate1.test e3eaa48c21e150814be1a7b852d2a8af24458d04
 F test/collate2.test 701d9651c5707024fd86a20649af9ea55e2c0eb8
 F test/collate3.test 947a77f5b8227e037a7094d0e338a5504f155cc4
 F test/collate4.test daf498e294dcd596b961d425c3f2dda117e4717e
-F test/collate5.test 8fb4e7e0241839356bd8710f437c32efb47bfff8
+F test/collate5.test e54df13eb9e1140273680b3153c6e19b39e59888
 F test/collate6.test 8be65a182abaac8011a622131486dafb8076e907
 F test/collate7.test e23677b1fd271505302643a98178952bb65b6f21
 F test/collate8.test 7ed2461305ac959886a064dc1e3cf15e155a183f
@@ -329,7 +329,7 @@ F test/index3.test f66718cd92ce1216819d47e6a156755e4b2c4ca1
 F test/insert.test aef273dd1cee84cc92407469e6bd1b3cdcb76908
 F test/insert2.test 5a20e1ace5fa0800b58d28284212290189b49aed
 F test/insert3.test 9a4ef3526fd3cca8b05278020ec3100448b4c677
-F test/insert4.test ac36af0ea9e6a2447f0d9b65da512498018a7743
+F test/insert4.test 6919ddacd79c2cfeb9785b0f84217f9cb14853b5
 F test/interrupt.test 81555fb0f8179bb2d0dc7151fd75428223f93cf2
 F test/intpkey.test af4fd826c4784ec5c93b444de07adea0254d0d30
 F test/io.test 835b0ec66166312ff743e2fd11a878c65068de9f
@@ -375,7 +375,7 @@ F test/misc1.test 1b89c02c4a33b49dee4cd1d20d161aaaba719075
 F test/misc2.test 1ee89298de9c16b61454658b24999c403e86afe4
 F test/misc3.test 7bd937e2c62bcc6be71939faf068d506467b1e03
 F test/misc4.test 21e8a275cadcf2ba2a9ac2c33ae024ecc5eaff3a
-F test/misc5.test ef90b03ae715b718f07fd084cccb4ef9eb1658e3
+F test/misc5.test 33b95f12f18b7b9558c79545503f05728fbf2c22
 F test/misc6.test 953cc693924d88e6117aeba16f46f0bf5abede91
 F test/misc7.test 3fbd0a9e3dd03331d9d76acd47bc179e1a97e15e
 F test/misuse.test 30b3a458e5a70c31e74c291937b6c82204c59f33
@@ -586,7 +586,7 @@ F www/tclsqlite.tcl 8be95ee6dba05eabcd27a9d91331c803f2ce2130
 F www/vdbe.tcl 87a31ace769f20d3627a64fa1fade7fed47b90d0
 F www/version3.tcl 890248cf7b70e60c383b0e84d77d5132b3ead42b
 F www/whentouse.tcl fc46eae081251c3c181bd79c5faef8195d7991a5
-P af5af5dc2608f369f0f4274ca06974b365424e72
-R 6609950e4e33ca146fe5280a3d429455
+P 06749ac7afeea4adbdeb9315f3819d5224534c66
+R d3236e16fe589d623a588d0fca905a2c
 U danielk1977
-Z 68349a41f440456331fc2acbb07fcff1
+Z e2a2364ba8c7fed549c957127a8396b6
diff --git a/manifest.uuid b/manifest.uuid
index dee1e4d28..d638b79ec 100644
--- a/manifest.uuid
+++ b/manifest.uuid
@@ -1 +1 @@
-06749ac7afeea4adbdeb9315f3819d5224534c66
\ No newline at end of file
+e56331234791cf3d830a30e4cfa66682bdf2eed1
\ No newline at end of file
diff --git a/src/select.c b/src/select.c
index fbe1b066d..7298251c2 100644
--- a/src/select.c
+++ b/src/select.c
@@ -12,7 +12,7 @@
 ** This file contains C code routines that are called by the parser
 ** to handle SELECT statements in SQLite.
 **
-** $Id: select.c,v 1.359 2007/08/31 17:42:48 danielk1977 Exp $
+** $Id: select.c,v 1.360 2007/11/12 15:29:19 danielk1977 Exp $
 */
 #include "sqliteInt.h"
 
@@ -3067,6 +3067,15 @@ int sqlite3Select(
   }
 #endif
 
+  /* If possible, rewrite the query to use GROUP BY instead of 
+  */
+  if( p->isDistinct && !p->isAgg && !p->pGroupBy ){
+    p->pGroupBy = sqlite3ExprListDup(db, p->pEList);
+    pGroupBy = p->pGroupBy;
+    p->isDistinct = 0;
+    isDistinct = 0;
+  }
+
   /* If there is an ORDER BY clause, then this sorting
   ** index might end up being unused if the data can be 
   ** extracted in pre-sorted order.  If that is the case, then the
@@ -3102,6 +3111,7 @@ int sqlite3Select(
   */
   if( isDistinct ){
     KeyInfo *pKeyInfo;
+    assert( isAgg || pGroupBy );
     distinct = pParse->nTab++;
     pKeyInfo = keyInfoFromExprList(pParse, p->pEList);
     sqlite3VdbeOp3(v, OP_OpenEphemeral, distinct, 0, 
@@ -3129,7 +3139,8 @@ int sqlite3Select(
 
     /* Use the standard inner loop
     */
-    if( selectInnerLoop(pParse, p, pEList, 0, 0, pOrderBy, distinct, eDest,
+    assert(!isDistinct);
+    if( selectInnerLoop(pParse, p, pEList, 0, 0, pOrderBy, -1, eDest,
                     iParm, pWInfo->iContinue, pWInfo->iBreak, aff) ){
        goto select_end;
     }
@@ -3191,7 +3202,7 @@ int sqlite3Select(
     if( db->mallocFailed ) goto select_end;
 
     /* Processing for aggregates with GROUP BY is very different and
-    ** much more complex tha aggregates without a GROUP BY.
+    ** much more complex than aggregates without a GROUP BY.
     */
     if( pGroupBy ){
       KeyInfo *pKeyInfo;  /* Keying information for the group by clause */
diff --git a/test/collate5.test b/test/collate5.test
index 5e63c1f4c..b8dc58173 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.5 2005/09/07 22:48:16 drh Exp $
+# $Id: collate5.test,v 1.6 2007/11/12 15:29:19 danielk1977 Exp $
 
 set testdir [file dirname $argv0]
 source $testdir/tester.tcl
@@ -57,17 +57,17 @@ do_test collate5-1.1 {
   execsql {
     SELECT DISTINCT a FROM collate5t1;
   }
-} {a b n}
+} {A B N}
 do_test collate5-1.2 {
   execsql {
     SELECT DISTINCT b FROM collate5t1;
   }
-} {apple Apple banana {}}
+} {{} Apple apple banana}
 do_test collate5-1.3 {
   execsql {
     SELECT DISTINCT a, b FROM collate5t1;
   }
-} {a apple A Apple b banana n {}}
+} {A Apple a apple B banana N {}}
 
 # The remainder of this file tests compound SELECT statements.
 # Omit it if the library is compiled such that they are omitted.
diff --git a/test/insert4.test b/test/insert4.test
index 9d8c78e7c..40d330ab7 100644
--- a/test/insert4.test
+++ b/test/insert4.test
@@ -11,7 +11,7 @@
 # This file implements regression tests for SQLite library.  The
 # focus of this file is testing the INSERT transfer optimization.
 #
-# $Id: insert4.test,v 1.8 2007/10/09 08:29:32 danielk1977 Exp $
+# $Id: insert4.test,v 1.9 2007/11/12 15:29:19 danielk1977 Exp $
 
 set testdir [file dirname $argv0]
 source $testdir/tester.tcl
@@ -112,7 +112,7 @@ do_test insert4-2.4.1 {
     INSERT INTO t3 SELECT DISTINCT * FROM t2;
     SELECT * FROM t3;
   }
-} {9 1 1 9}
+} {1 9 9 1}
 xferopt_test insert4-2.4.2 0
 do_test insert4-2.4.3 {
   catchsql {
diff --git a/test/misc5.test b/test/misc5.test
index 86963b2bf..d7094b147 100644
--- a/test/misc5.test
+++ b/test/misc5.test
@@ -13,7 +13,7 @@
 # This file implements tests for miscellanous features that were
 # left out of other test files.
 #
-# $Id: misc5.test,v 1.17 2007/09/12 17:01:45 danielk1977 Exp $
+# $Id: misc5.test,v 1.18 2007/11/12 15:29:19 danielk1977 Exp $
 
 set testdir [file dirname $argv0]
 source $testdir/tester.tcl
@@ -481,8 +481,18 @@ ifcapable subquery {
         SELECT songid    
         FROM songs    
         WHERE LOWER(artist) = (    
+          -- This sub-query is indeterminate. Because there is no ORDER BY,
+          -- it may return 'one', 'two' or 'three'. Because of this, the
+	  -- outermost parent query may correctly return any of 'one', 'two' 
+          -- or 'three' as well.
           SELECT DISTINCT LOWER(artist)    
           FROM (      
+            -- This sub-query returns the table:
+            --
+            --     two      14
+            --     one      10
+            --     three    5
+            --
             SELECT DISTINCT artist,sum(timesplayed) AS total      
             FROM songs      
             GROUP BY LOWER(artist)      
@@ -495,7 +505,7 @@ ifcapable subquery {
       )  
       ORDER BY LOWER(artist) ASC;
     }
-  } {two}
+  } {one}
 }
 
 # Ticket #1370.  Do not overwrite small files (less than 1024 bytes)