ORDER BY on aggregates seem to work, at least for simple smoke tests. Lots

more testing is needed though.  Surely there are many bugs.

FossilOrigin-Name: 64c12a835b6f1df8f2f5f4a41de083f6b3fc7f8030042c6aac0082382cd9cc4d

5 files changed, 173 insertions, 35 deletions

diff --git a/manifest b/manifest
index 45e7a5f7a..24129053b 100644
--- a/manifest
+++ b/manifest
@@ -1,5 +1,5 @@
-C Basic\serror\schecking.\s\sResolve\ssymbols\sin\sthe\saggregate\sORDER\sBY\sexpressions.
-D 2023-10-18T13:58:31.861
+C ORDER\sBY\son\saggregates\sseem\sto\swork,\sat\sleast\sfor\ssimple\ssmoke\stests.\s\sLots\nmore\stesting\sis\sneeded\sthough.\s\sSurely\sthere\sare\smany\sbugs.
+D 2023-10-18T18:11:11.181
 F .fossil-settings/empty-dirs dbb81e8fc0401ac46a1491ab34a7f2c7c0452f2f06b54ebb845d024ca8283ef1
 F .fossil-settings/ignore-glob 35175cdfcf539b2318cb04a9901442804be81cd677d8b889fcc9149c21f239ea
 F LICENSE.md df5091916dbb40e6e9686186587125e1b2ff51f022cc334e886c19a0e9982724
@@ -668,7 +668,7 @@ F src/date.c eebc54a00e888d3c56147779e9f361b77d62fd69ff2008c5373946aa1ba1d574
 F src/dbpage.c 80e46e1df623ec40486da7a5086cb723b0275a6e2a7b01d9f9b5da0f04ba2782
 F src/dbstat.c 3b677254d512fcafd4d0b341bf267b38b235ccfddbef24f9154e19360fa22e43
 F src/delete.c cb766727c78e715f9fb7ec8a7d03658ed2a3016343ca687acfcec9083cdca500
-F src/expr.c dbe1be4833e5d1737bc3b685fcc4b8849023b93ebd82538fcd3a5029ea685106
+F src/expr.c 7210855080a90215508cada806ee2aba2138907ca5fca19ba047955a3f094e04
 F src/fault.c 460f3e55994363812d9d60844b2a6de88826e007
 F src/fkey.c a7fcbf7e66d14dbb73cf49f31489ebf66d0e6006c62b95246924a3bae9f37b36
 F src/func.c e8d7b3587a225f4f1116f720b72090511fe9feb936e960bd26a053cea6a17a63
@@ -718,12 +718,12 @@ F src/printf.c 9da63b9ae1c14789bcae12840f5d800fd9302500cd2d62733fac77f0041b4750
 F src/random.c 606b00941a1d7dd09c381d3279a058d771f406c5213c9932bbd93d5587be4b9c
 F src/resolve.c ee4011c8ed177de113e617e514f66ec5c38772cf2f00efa33f9576cbf076361c
 F src/rowset.c 8432130e6c344b3401a8874c3cb49fefe6873fec593294de077afea2dce5ec97
-F src/select.c 7f9155185be78902818b21c2cd3e33f01b4306279a15d6719eb1bbb9779034aa
+F src/select.c dd0f0ed89668f298e12226127ac4d977a696475a4b6572218c14511022001d42
 F src/shell.c.in cf0a3387c5bb05ca2fe6073fa7df21aaa11e749ca5b3846b80b586a447e728aa
 F src/sqlite.h.in 60e5698417e674f44be17d5ceeb4c2d395ccedba18d6de05435dec0135d9eff1
 F src/sqlite3.rc 5121c9e10c3964d5755191c80dd1180c122fc3a8
 F src/sqlite3ext.h 2f30b2671f4c03cd27a43f039e11251391066c97d11385f5f963bb40b03038ac
-F src/sqliteInt.h bc1da6f5605dd0f8433904c2b4e6f9960f6cf327b42f00d1885dc11a290e0641
+F src/sqliteInt.h 8eac2e94e597add7bbef6bab315dc8e761410a599be7a344aba8b7af615ff2a6
 F src/sqliteLimit.h 33b1c9baba578d34efe7dfdb43193b366111cdf41476b1e82699e14c11ee1fb6
 F src/status.c 160c445d7d28c984a0eae38c144f6419311ed3eace59b44ac6dafc20db4af749
 F src/table.c 0f141b58a16de7e2fbe81c308379e7279f4c6b50eb08efeec5892794a0ba30d1
@@ -2133,8 +2133,8 @@ F vsixtest/vsixtest.tcl 6a9a6ab600c25a91a7acc6293828957a386a8a93
 F vsixtest/vsixtest.vcxproj.data 2ed517e100c66dc455b492e1a33350c1b20fbcdc
 F vsixtest/vsixtest.vcxproj.filters 37e51ffedcdb064aad6ff33b6148725226cd608e
 F vsixtest/vsixtest_TemporaryKey.pfx e5b1b036facdb453873e7084e1cae9102ccc67a0
-P 3a98ff24bf468ed42d410a9a12d9f9b2ca154c7babe99fd6bc6f7b0565e0d132
-R 151cfa4119235187f9a8c82d8ecde04d
+P c83a53a574d312130d1238c05ffa449d8bed2535d5ef5b5d9cf02f894494cca4
+R c20d0fa6dc56e340bbaa31e8a36615e8
 U drh
-Z 7081aae7959eb43f46824edbdfe856c6
+Z 66c7548e2f839878f6f4ddcf4735c183
 # Remove this line to create a well-formed Fossil manifest.
diff --git a/manifest.uuid b/manifest.uuid
index 2c8835c07..312ea1e8a 100644
--- a/manifest.uuid
+++ b/manifest.uuid
@@ -1 +1 @@
-c83a53a574d312130d1238c05ffa449d8bed2535d5ef5b5d9cf02f894494cca4
\ No newline at end of file
+64c12a835b6f1df8f2f5f4a41de083f6b3fc7f8030042c6aac0082382cd9cc4d
\ No newline at end of file
diff --git a/src/expr.c b/src/expr.c
index 6ae6dc331..dd543a98d 100644
--- a/src/expr.c
+++ b/src/expr.c
@@ -1209,6 +1209,12 @@ void sqlite3ExprAddFunctionOrderBy(
   }
   assert( pExpr->op==TK_FUNCTION );
   assert( pExpr->pLeft==0 );
+  assert( ExprUseXList(pExpr) );
+  if( pExpr->x.pList==0 || NEVER(pExpr->x.pList->nExpr==0) ){
+    /* Ignore ORDER BY on zero-argument aggregates */
+    sqlite3ExprListDelete(db, pOrderBy);
+    return;
+  }
   pOB = sqlite3ExprAlloc(db, TK_ORDER, 0, 0);
   if( pOB==0 ){
     sqlite3ExprListDelete(db, pOrderBy);
@@ -1902,11 +1908,7 @@ Select *sqlite3SelectDup(sqlite3 *db, const Select *p, int flags){
 ** initially NULL, then create a new expression list.
 **
 ** The pList argument must be either NULL or a pointer to an ExprList
-** obtained from a prior call to sqlite3ExprListAppend().  This routine
-** may not be used with an ExprList obtained from sqlite3ExprListDup().
-** Reason:  This routine assumes that the number of slots in pList->a[]
-** is a power of two.  That is true for sqlite3ExprListAppend() returns
-** but is not necessarily true from the return value of sqlite3ExprListDup().
+** obtained from a prior call to sqlite3ExprListAppend().
 **
 ** If a memory allocation error occurs, the entire list is freed and
 ** NULL is returned.  If non-NULL is returned, then it is guaranteed
@@ -6712,14 +6714,37 @@ static int analyzeAggregate(Walker *pWalker, Expr *pExpr){
           u8 enc = ENC(pParse->db);
           i = addAggInfoFunc(pParse->db, pAggInfo);
           if( i>=0 ){
+            int nArg;
             assert( !ExprHasProperty(pExpr, EP_xIsSelect) );
             pItem = &pAggInfo->aFunc[i];
             pItem->pFExpr = pExpr;
             assert( ExprUseUToken(pExpr) );
+            nArg = pExpr->x.pList ? pExpr->x.pList->nExpr : 0;
             pItem->pFunc = sqlite3FindFunction(pParse->db,
-                   pExpr->u.zToken,
-                   pExpr->x.pList ? pExpr->x.pList->nExpr : 0, enc, 0);
-            if( pExpr->flags & EP_Distinct ){
+                                         pExpr->u.zToken, nArg, enc, 0);
+            assert( pItem->bOBUnique==0 );
+            if( pExpr->pLeft ){
+              ExprList *pOBList;
+              assert( nArg>0 );
+              assert( pExpr->pLeft->op==TK_ORDER );
+              assert( ExprUseXList(pExpr->pLeft) );
+              pItem->iOBTab = pParse->nTab++;
+              pOBList = pExpr->pLeft->x.pList;
+              assert( pOBList->nExpr>0 );
+              if( pOBList->nExpr==1
+               && nArg==1
+               && sqlite3ExprCompare(0,pOBList->a[0].pExpr,
+                               pExpr->x.pList->a[0].pExpr,0)==0
+              ){
+                pItem->bOBPayload = 0;
+                pItem->bOBUnique = ExprHasProperty(pExpr, EP_Distinct);
+              }else{
+                pItem->bOBPayload = 1;
+              }
+            }else{
+              pItem->iOBTab = -1;
+            }
+            if( ExprHasProperty(pExpr, EP_Distinct) && !pItem->bOBUnique ){
               pItem->iDistinct = pParse->nTab++;
             }else{
               pItem->iDistinct = -1;
diff --git a/src/select.c b/src/select.c
index a55545d51..36b6e0dd7 100644
--- a/src/select.c
+++ b/src/select.c
@@ -6646,6 +6646,32 @@ static void resetAccumulator(Parse *pParse, AggInfo *pAggInfo){
                           pFunc->pFunc->zName));
       }
     }
+    if( pFunc->iOBTab>=0 ){
+      ExprList *pOBList;
+      KeyInfo *pKeyInfo;
+      int nExtra = 0;
+      assert( pFunc->pFExpr->pLeft!=0 );
+      assert( pFunc->pFExpr->pLeft->op==TK_ORDER );
+      assert( ExprUseXList(pFunc->pFExpr->pLeft) );
+      pOBList = pFunc->pFExpr->pLeft->x.pList;
+      if( !pFunc->bOBUnique ){
+        nExtra++;  /* One extra column for the OP_Sequence */
+      }
+      if( pFunc->bOBPayload ){
+        /* extra columns for the function arguments */
+        assert( ExprUseXList(pFunc->pFExpr) );
+        nExtra += pFunc->pFExpr->x.pList->nExpr;
+      }
+      pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pOBList, 0, nExtra);
+      if( !pFunc->bOBUnique ){
+        pKeyInfo->nKeyField++;
+      }
+      sqlite3VdbeAddOp4(v, OP_OpenEphemeral,
+            pFunc->iOBTab, pOBList->nExpr+nExtra, 0,
+            (char*)pKeyInfo, P4_KEYINFO);
+      ExplainQueryPlan((pParse, 0, "USE TEMP B-TREE FOR %s(ORDER BY)",
+                          pFunc->pFunc->zName));
+    }
   }
 }
 
@@ -6661,13 +6687,46 @@ static void finalizeAggFunctions(Parse *pParse, AggInfo *pAggInfo){
     ExprList *pList;
     assert( ExprUseXList(pF->pFExpr) );
     pList = pF->pFExpr->x.pList;
+    if( pF->iOBTab ){
+      /* For an ORDER BY aggregate, calls to OP_AggStep where deferred and
+      ** all content was stored in emphermal table pF->iOBTab.  Extract that
+      ** content now (in ORDER BY order) and make all calls to OP_AggStep
+      ** before doing the OP_AggFinal call. */
+      int iTop;        /* Start of loop for extracting columns */
+      int nArg;        /* Number of columns to extract */
+      int nKey;        /* Key columns to be skipped */
+      int regAgg;      /* Extract into this array */
+      int j;           /* Loop counter */
+      
+      nArg = pList->nExpr;
+      regAgg = sqlite3GetTempRange(pParse, nArg);
+
+      if( pF->bOBPayload==0 ){
+        nKey = 0;
+      }else{
+        assert( pF->pFExpr->pLeft!=0 );
+        assert( ExprUseXList(pF->pFExpr->pLeft) );
+        assert( pF->pFExpr->pLeft->x.pList!=0 );
+        nKey = pF->pFExpr->pLeft->x.pList->nExpr;
+        if( !pF->bOBUnique ) nKey++;
+      }
+      iTop = sqlite3VdbeAddOp1(v, OP_Rewind, pF->iOBTab);
+      for(j=nArg-1; j>=0; j--){
+        sqlite3VdbeAddOp3(v, OP_Column, pF->iOBTab, nKey+j, regAgg+j);
+      }
+      sqlite3VdbeAddOp3(v, OP_AggStep, 0, regAgg, AggInfoFuncReg(pAggInfo,i));
+      sqlite3VdbeAppendP4(v, pF->pFunc, P4_FUNCDEF);
+      sqlite3VdbeChangeP5(v, (u8)nArg);
+      sqlite3VdbeAddOp2(v, OP_Next, pF->iOBTab, iTop+1);
+      sqlite3VdbeJumpHere(v, iTop);
+      sqlite3ReleaseTempRange(pParse, regAgg, nArg);
+    }
     sqlite3VdbeAddOp2(v, OP_AggFinal, AggInfoFuncReg(pAggInfo,i),
                       pList ? pList->nExpr : 0);
     sqlite3VdbeAppendP4(v, pF->pFunc, P4_FUNCDEF);
   }
 }
 
-
 /*
 ** Generate code that will update the accumulator memory cells for an
 ** aggregate based on the current cursor position.
@@ -6676,6 +6735,13 @@ static void finalizeAggFunctions(Parse *pParse, AggInfo *pAggInfo){
 ** in pAggInfo, then only populate the pAggInfo->nAccumulator accumulator
 ** registers if register regAcc contains 0. The caller will take care
 ** of setting and clearing regAcc.
+**
+** For an ORDER BY aggregate, the actually accumulator memory cell update
+** is deferred until after all input rows have been received, so that they
+** can be run in the requested order.  In that case, instead of invoking
+** OP_AggStep to update accumulator, just add the arguments that would
+** have been passed into OP_AggStep into the sorting ephemeral table
+** (along with the appropriate sort key).
 */
 static void updateAccumulator(
   Parse *pParse,
@@ -6697,6 +6763,7 @@ static void updateAccumulator(
     int nArg;
     int addrNext = 0;
     int regAgg;
+    int regAggSz = 0;
     ExprList *pList;
     assert( ExprUseXList(pF->pFExpr) );
     assert( !IsWindowFunc(pF->pFExpr) );
@@ -6723,7 +6790,39 @@ static void updateAccumulator(
       addrNext = sqlite3VdbeMakeLabel(pParse);
       sqlite3ExprIfFalse(pParse, pFilter, addrNext, SQLITE_JUMPIFNULL);
     }
-    if( pList ){
+    if( pF->iOBTab>=0 ){
+      /* Instead of invoking AggStep, we must push the arguments that would
+      ** have been passed to AggStep onto the sorting table. */
+      int jj;                /* Registered used so far in building the record */
+      ExprList *pOBList;     /* The ORDER BY clause */
+      assert( pList!=0 );
+      nArg = pList->nExpr;
+      assert( nArg>0 );
+      assert( pF->pFExpr->pLeft!=0 );
+      assert( pF->pFExpr->pLeft->op==TK_ORDER );
+      assert( ExprUseXList(pF->pFExpr->pLeft) );
+      pOBList = pF->pFExpr->pLeft->x.pList;
+      assert( pOBList!=0 );
+      assert( pOBList->nExpr>0 );
+      regAggSz = pOBList->nExpr;
+      if( !pF->bOBUnique ){
+        regAggSz++;   /* One register for OP_Sequence */
+      }
+      if( pF->bOBPayload ){
+        regAggSz += nArg;
+      }
+      regAggSz++;  /* One extra register to hold result of MakeRecord */
+      regAgg = sqlite3GetTempRange(pParse, regAggSz);
+      sqlite3ExprCodeExprList(pParse, pOBList, regAgg, 0, SQLITE_ECEL_DUP);
+      jj = pOBList->nExpr;
+      if( !pF->bOBUnique ){
+        sqlite3VdbeAddOp2(v, OP_Sequence, pF->iOBTab, regAgg+jj);
+        jj++;
+      }
+      if( pF->bOBPayload ){
+        sqlite3ExprCodeExprList(pParse, pList, regAgg+jj, 0, SQLITE_ECEL_DUP);
+      }
+    }else if( pList ){
       nArg = pList->nExpr;
       regAgg = sqlite3GetTempRange(pParse, nArg);
       sqlite3ExprCodeExprList(pParse, pList, regAgg, 0, SQLITE_ECEL_DUP);
@@ -6738,24 +6837,35 @@ static void updateAccumulator(
       pF->iDistinct = codeDistinct(pParse, eDistinctType,
           pF->iDistinct, addrNext, pList, regAgg);
     }
-    if( pF->pFunc->funcFlags & SQLITE_FUNC_NEEDCOLL ){
-      CollSeq *pColl = 0;
-      struct ExprList_item *pItem;
-      int j;
-      assert( pList!=0 );  /* pList!=0 if pF->pFunc has NEEDCOLL */
-      for(j=0, pItem=pList->a; !pColl && j<nArg; j++, pItem++){
-        pColl = sqlite3ExprCollSeq(pParse, pItem->pExpr);
-      }
-      if( !pColl ){
-        pColl = pParse->db->pDfltColl;
+    if( pF->iOBTab>=0 ){
+      /* Insert a new record into the ORDER BY table */
+      sqlite3VdbeAddOp3(v, OP_MakeRecord, regAgg, regAggSz-1,
+                        regAgg+regAggSz-1);
+      sqlite3VdbeAddOp4Int(v, OP_IdxInsert, pF->iOBTab, regAgg+regAggSz-1,
+                           regAgg, regAggSz-1);
+      sqlite3ReleaseTempRange(pParse, regAgg, regAggSz);
+    }else{
+      /* Invoke the AggStep function */
+      if( pF->pFunc->funcFlags & SQLITE_FUNC_NEEDCOLL ){
+        CollSeq *pColl = 0;
+        struct ExprList_item *pItem;
+        int j;
+        assert( pList!=0 );  /* pList!=0 if pF->pFunc has NEEDCOLL */
+        for(j=0, pItem=pList->a; !pColl && j<nArg; j++, pItem++){
+          pColl = sqlite3ExprCollSeq(pParse, pItem->pExpr);
+        }
+        if( !pColl ){
+          pColl = pParse->db->pDfltColl;
+        }
+        if( regHit==0 && pAggInfo->nAccumulator ) regHit = ++pParse->nMem;
+        sqlite3VdbeAddOp4(v, OP_CollSeq, regHit, 0, 0,
+                         (char *)pColl, P4_COLLSEQ);
       }
-      if( regHit==0 && pAggInfo->nAccumulator ) regHit = ++pParse->nMem;
-      sqlite3VdbeAddOp4(v, OP_CollSeq, regHit, 0, 0, (char *)pColl, P4_COLLSEQ);
+      sqlite3VdbeAddOp3(v, OP_AggStep, 0, regAgg, AggInfoFuncReg(pAggInfo,i));
+      sqlite3VdbeAppendP4(v, pF->pFunc, P4_FUNCDEF);
+      sqlite3VdbeChangeP5(v, (u8)nArg);
+      sqlite3ReleaseTempRange(pParse, regAgg, nArg);
     }
-    sqlite3VdbeAddOp3(v, OP_AggStep, 0, regAgg, AggInfoFuncReg(pAggInfo,i));
-    sqlite3VdbeAppendP4(v, pF->pFunc, P4_FUNCDEF);
-    sqlite3VdbeChangeP5(v, (u8)nArg);
-    sqlite3ReleaseTempRange(pParse, regAgg, nArg);
     if( addrNext ){
       sqlite3VdbeResolveLabel(v, addrNext);
     }
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index 16da1db4c..cb90fba4a 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -2860,6 +2860,9 @@ struct AggInfo {
     FuncDef *pFunc;          /* The aggregate function implementation */
     int iDistinct;           /* Ephemeral table used to enforce DISTINCT */
     int iDistAddr;           /* Address of OP_OpenEphemeral */
+    int iOBTab;              /* Ephemeral table to implement ORDER BY */
+    u8 bOBPayload;           /* iOBTab has payload columns separate from key */
+    u8 bOBUnique;            /* Enforce uniqueness on iOBTab keys */
   } *aFunc;
   int nFunc;              /* Number of entries in aFunc[] */
   u32 selId;              /* Select to which this AggInfo belongs */