From 52576b78f6bb0cf9e88a861c14225480abc835fb Mon Sep 17 00:00:00 2001
From: drh <>
Date: Tue, 14 Dec 2021 20:13:28 +0000
Subject: [PATCH] Enhance the virtual table query planner so that it is able to
 deal with ORDER BY terms that contain COLLATE clauses as long as the
 specified collation matches the virtual table.  This is especially important
 for UNION ALL since a "COLLATE binary" is added to ORDER BY clauses if no
 COLLATE clause exists in the original SQL.

FossilOrigin-Name: 5c3d398d20b86a1558720e995eddf11403aec2d160590571fa9525fe8f6efff9
---
 manifest            | 14 +++++++-------
 manifest.uuid       |  2 +-
 src/where.c         | 37 ++++++++++++++++++++++++++++++++++++-
 test/tabfunc01.test | 17 +++++++++++++++++
 4 files changed, 61 insertions(+), 9 deletions(-)

diff --git a/manifest b/manifest
index edd28753b3..19da831492 100644
--- a/manifest
+++ b/manifest
@@ -1,5 +1,5 @@
-C Minor\sfix\sto\sthe\sORDER\sBY\selimination\slogic\sin\sgenerate_series().
-D 2021-12-14T18:11:46.057
+C Enhance\sthe\svirtual\stable\squery\splanner\sso\sthat\sit\sis\sable\sto\sdeal\swith\nORDER\sBY\sterms\sthat\scontain\sCOLLATE\sclauses\sas\slong\sas\sthe\sspecified\ncollation\smatches\sthe\svirtual\stable.\s\sThis\sis\sespecially\simportant\sfor\nUNION\sALL\ssince\sa\s"COLLATE\sbinary"\sis\sadded\sto\sORDER\sBY\sclauses\sif\sno\nCOLLATE\sclause\sexists\sin\sthe\soriginal\sSQL.
+D 2021-12-14T20:13:28.303
 F .fossil-settings/empty-dirs dbb81e8fc0401ac46a1491ab34a7f2c7c0452f2f06b54ebb845d024ca8283ef1
 F .fossil-settings/ignore-glob 35175cdfcf539b2318cb04a9901442804be81cd677d8b889fcc9149c21f239ea
 F LICENSE.md df5091916dbb40e6e9686186587125e1b2ff51f022cc334e886c19a0e9982724
@@ -638,7 +638,7 @@ F src/vxworks.h d2988f4e5a61a4dfe82c6524dd3d6e4f2ce3cdb9
 F src/wal.c ed0398a7adf02c31e34aada42cc86c58f413a7afe5f741a5d373ad087abde028
 F src/wal.h c3aa7825bfa2fe0d85bef2db94655f99870a285778baa36307c0a16da32b226a
 F src/walker.c f890a3298418d7cba3b69b8803594fdc484ea241206a8dfa99db6dd36f8cbb3b
-F src/where.c c3299a18bb95a0189629aaad1207e2214251181e4c71763c2c0a2575a5e4a4c2
+F src/where.c c69fed81e5dfd38e261e9af8c3faba133434b233757b0b2814db71eba86a0a62
 F src/whereInt.h e83f7ba73db5b1b2685118fad67d178fbe04751a25419f0f6ff73e58b4807325
 F src/wherecode.c 6a594ed25bfbeb60d455868b7be62637575e4f1949152de4336e4825e0c54ba6
 F src/whereexpr.c 791544603b254cf11f8e84e3b50b0863c57322e9f213b828680f658e232ebc57
@@ -1453,7 +1453,7 @@ F test/sync.test 89539f4973c010eda5638407e71ca7fddbcd8e0594f4c9980229f804d433309
 F test/sync2.test 8f9f7d4f6d5be8ca8941a8dadcc4299e558cb6a1ff653a9469146c7a76ef2039
 F test/syscall.test a39d9a36f852ae6e4800f861bc2f2e83f68bbc2112d9399931ecfadeabd2d69d
 F test/sysfault.test c9f2b0d8d677558f74de750c75e12a5454719d04
-F test/tabfunc01.test 2708073a405ee3989cfc87a9ee47b2f231b8996529b48ba111ed15fa9106d22c
+F test/tabfunc01.test 241425ce3998687ab24adba09cb95e8012e17499b84a0ed47e128ab45e588bef
 F test/table.test eb3463b7add9f16a5bb836badf118cf391b809d09fdccd1f79684600d07ec132
 F test/tableapi.test ecbcc29c4ab62c1912c3717c48ea5c5e59f7d64e4a91034e6148bd2b82f177f4
 F test/tableopts.test dba698ba97251017b7c80d738c198d39ab747930
@@ -1934,7 +1934,7 @@ F vsixtest/vsixtest.tcl 6a9a6ab600c25a91a7acc6293828957a386a8a93
 F vsixtest/vsixtest.vcxproj.data 2ed517e100c66dc455b492e1a33350c1b20fbcdc
 F vsixtest/vsixtest.vcxproj.filters 37e51ffedcdb064aad6ff33b6148725226cd608e
 F vsixtest/vsixtest_TemporaryKey.pfx e5b1b036facdb453873e7084e1cae9102ccc67a0
-P 788e79f881d443fc1b3a213a7ba4f19bfd245e96c15bb21fcb6bffd92c4320b8
-R 842bfdb0c978a51950e5dd7fb39c0333
+P a2e50712fca9dff1b8d19631f792270c82da3c8696a5d9890cf0d1e13e950d60
+R 1e0532988fdf8f21a62bc70005049044
 U drh
-Z d877d022570b657f3f70fd02d0845d09
+Z 0d6fc2fca37175245191cba6d8527f4e
diff --git a/manifest.uuid b/manifest.uuid
index fd6e39c5d8..17670695af 100644
--- a/manifest.uuid
+++ b/manifest.uuid
@@ -1 +1 @@
-a2e50712fca9dff1b8d19631f792270c82da3c8696a5d9890cf0d1e13e950d60
\ No newline at end of file
+5c3d398d20b86a1558720e995eddf11403aec2d160590571fa9525fe8f6efff9
\ No newline at end of file
diff --git a/src/where.c b/src/where.c
index 982685738a..33e0e43a4c 100644
--- a/src/where.c
+++ b/src/where.c
@@ -1114,6 +1114,10 @@ static sqlite3_index_info *allocateIndexInfo(
   sqlite3_index_info *pIdxInfo;
   u16 mNoOmit = 0;
 
+  assert( pSrc!=0 );
+  assert( pSrc->pTab!=0 );
+  assert( IsVirtual(pSrc->pTab) );
+
   /* Count the number of possible WHERE clause constraints referring
   ** to this virtual table */
   for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
@@ -1140,8 +1144,36 @@ static sqlite3_index_info *allocateIndexInfo(
     int n = pOrderBy->nExpr;
     for(i=0; i<n; i++){
       Expr *pExpr = pOrderBy->a[i].pExpr;
-      if( pExpr->op!=TK_COLUMN || pExpr->iTable!=pSrc->iCursor ) break;
+      Expr *pE2;
+
+      /* Virtual tables are unable to deal with NULLS FIRST */
       if( pOrderBy->a[i].sortFlags & KEYINFO_ORDER_BIGNULL ) break;
+
+      /* First case - a direct column references without a COLLATE operator */
+      if( pExpr->op==TK_COLUMN && pExpr->iTable==pSrc->iCursor ){
+        assert( pExpr->iColumn>=XN_ROWID && pExpr->iColumn<pSrc->pTab->nCol );
+        continue;
+      }
+
+      /* 2nd case - a column reference with a COLLATE operator.  Only match
+      ** of the COLLATE operator matches the collation of the column. */
+      if( pExpr->op==TK_COLLATE
+       && (pE2 = pExpr->pLeft)->op==TK_COLUMN
+       && pE2->iTable==pSrc->iCursor
+      ){
+        const char *zColl;  /* The collating sequence name */
+        assert( !ExprHasProperty(pExpr, EP_IntValue) );
+        assert( pExpr->u.zToken!=0 );
+        assert( pE2->iColumn>=XN_ROWID && pE2->iColumn<pSrc->pTab->nCol );
+        pExpr->iColumn = pE2->iColumn;
+        if( pE2->iColumn<0 ) continue;  /* Collseq does not matter for rowid */
+        zColl = sqlite3ColumnColl(&pSrc->pTab->aCol[pE2->iColumn]);
+        if( zColl==0 ) zColl = sqlite3StrBINARY;
+        if( sqlite3_stricmp(pExpr->u.zToken, zColl)==0 ) continue;
+      }
+
+      /* No matches cause a break out of the loop */
+      break;
     }
     if( i==n){
       nOrderBy = n;
@@ -1228,6 +1260,9 @@ static sqlite3_index_info *allocateIndexInfo(
   pIdxInfo->nConstraint = j;
   for(i=0; i<nOrderBy; i++){
     Expr *pExpr = pOrderBy->a[i].pExpr;
+    assert( pExpr->op==TK_COLUMN
+         || (pExpr->op==TK_COLLATE && pExpr->pLeft->op==TK_COLUMN
+              && pExpr->iColumn==pExpr->pLeft->iColumn) );
     pIdxOrderBy[i].iColumn = pExpr->iColumn;
     pIdxOrderBy[i].desc = pOrderBy->a[i].sortFlags & KEYINFO_ORDER_DESC;
   }
diff --git a/test/tabfunc01.test b/test/tabfunc01.test
index 1d990efc4a..0a7e3bc245 100644
--- a/test/tabfunc01.test
+++ b/test/tabfunc01.test
@@ -145,6 +145,23 @@ do_eqp_test tabfunc01-3.13 {
 }
 
 
+do_eqp_test tabfunc01-3.20 {
+  WITH t1(a) AS (
+    SELECT value FROM generate_series(0,10,2)
+    UNION ALL
+    SELECT value FROM generate_series(9,18,3)
+  )
+  SELECT * FROM t1 ORDER BY a;
+} {
+  QUERY PLAN
+  `--MERGE (UNION ALL)
+     |--LEFT
+     |  `--SCAN generate_series VIRTUAL TABLE INDEX 23:
+     `--RIGHT
+        `--SCAN generate_series VIRTUAL TABLE INDEX 23:
+}
+  
+
 # Eponymous virtual table exists in all schemas.
 #
 do_execsql_test tabfunc01-4.1 {
-- 
2.47.2