Add the "sorter-reference" optimization, allowing SQLite to be configured so

that some required values may be loaded from the database after external
sorting occurs for SELECT statements with ORDER BY clauses that are not
satisfied by database indexes.

FossilOrigin-Name: ef74090a40ceaef2fd93a7613ec99a191ce986811c852e96f4a19719f18af4f0

10 files changed, 302 insertions, 23 deletions

diff --git a/src/build.c b/src/build.c
index c286b4bbe..b032ff9f2 100644
--- a/src/build.c
+++ b/src/build.c
@@ -1095,15 +1095,20 @@ void sqlite3AddColumn(Parse *pParse, Token *pName, Token *pType){
  
   if( pType->n==0 ){
     /* If there is no type specified, columns have the default affinity
-    ** 'BLOB'. */
+    ** 'BLOB' with a default size of 4 bytes. */
     pCol->affinity = SQLITE_AFF_BLOB;
     pCol->szEst = 1;
+#ifdef SQLITE_ENABLE_SORTER_REFERENCES
+    if( 4>=sqlite3GlobalConfig.szSorterRef ){
+      pCol->colFlags |= COLFLAG_SORTERREF;
+    }
+#endif
   }else{
     zType = z + sqlite3Strlen30(z) + 1;
     memcpy(zType, pType->z, pType->n);
     zType[pType->n] = 0;
     sqlite3Dequote(zType);
-    pCol->affinity = sqlite3AffinityType(zType, &pCol->szEst);
+    pCol->affinity = sqlite3AffinityType(zType, pCol);
     pCol->colFlags |= COLFLAG_HASTYPE;
   }
   p->nCol++;
@@ -1163,7 +1168,7 @@ void sqlite3AddNotNull(Parse *pParse, int onError){
 ** If none of the substrings in the above table are found,
 ** SQLITE_AFF_NUMERIC is returned.
 */
-char sqlite3AffinityType(const char *zIn, u8 *pszEst){
+char sqlite3AffinityType(const char *zIn, Column *pCol){
   u32 h = 0;
   char aff = SQLITE_AFF_NUMERIC;
   const char *zChar = 0;
@@ -1200,27 +1205,32 @@ char sqlite3AffinityType(const char *zIn, u8 *pszEst){
     }
   }
 
-  /* If pszEst is not NULL, store an estimate of the field size.  The
+  /* If pCol is not NULL, store an estimate of the field size.  The
   ** estimate is scaled so that the size of an integer is 1.  */
-  if( pszEst ){
-    *pszEst = 1;   /* default size is approx 4 bytes */
+  if( pCol ){
+    int v = 0;   /* default size is approx 4 bytes */
     if( aff<SQLITE_AFF_NUMERIC ){
       if( zChar ){
         while( zChar[0] ){
           if( sqlite3Isdigit(zChar[0]) ){
-            int v = 0;
+            /* BLOB(k), VARCHAR(k), CHAR(k) -> r=(k/4+1) */
             sqlite3GetInt32(zChar, &v);
-            v = v/4 + 1;
-            if( v>255 ) v = 255;
-            *pszEst = v; /* BLOB(k), VARCHAR(k), CHAR(k) -> r=(k/4+1) */
             break;
           }
           zChar++;
         }
       }else{
-        *pszEst = 5;   /* BLOB, TEXT, CLOB -> r=5  (approx 20 bytes)*/
+        v = 16;   /* BLOB, TEXT, CLOB -> r=5  (approx 20 bytes)*/
       }
     }
+#ifdef SQLITE_ENABLE_SORTER_REFERENCES
+    if( v>=sqlite3GlobalConfig.szSorterRef ){
+      pCol->colFlags |= COLFLAG_SORTERREF;
+    }
+#endif
+    v = v/4 + 1;
+    if( v>255 ) v = 255;
+    pCol->szEst = v;
   }
   return aff;
 }
diff --git a/src/ctime.c b/src/ctime.c
index 1877aee10..da79f3a35 100644
--- a/src/ctime.c
+++ b/src/ctime.c
@@ -286,6 +286,9 @@ static const char * const sqlite3azCompileOpt[] = {
 #if SQLITE_ENABLE_SNAPSHOT
   "ENABLE_SNAPSHOT",
 #endif
+#if SQLITE_ENABLE_SORTER_REFERENCES
+  "ENABLE_SORTER_REFERENCES",
+#endif
 #if SQLITE_ENABLE_SQLLOG
   "ENABLE_SQLLOG",
 #endif
diff --git a/src/expr.c b/src/expr.c
index 534fdfe6b..6997e8430 100644
--- a/src/expr.c
+++ b/src/expr.c
@@ -1363,6 +1363,7 @@ ExprList *sqlite3ExprListDup(sqlite3 *db, ExprList *p, int flags){
     pItem->sortOrder = pOldItem->sortOrder;
     pItem->done = 0;
     pItem->bSpanIsTab = pOldItem->bSpanIsTab;
+    pItem->bSorterRef = pOldItem->bSorterRef;
     pItem->u = pOldItem->u;
   }
   return pNew;
@@ -4373,6 +4374,12 @@ int sqlite3ExprCodeExprList(
   if( !ConstFactorOk(pParse) ) flags &= ~SQLITE_ECEL_FACTOR;
   for(pItem=pList->a, i=0; i<n; i++, pItem++){
     Expr *pExpr = pItem->pExpr;
+#ifdef SQLITE_ENABLE_SORTER_REFERENCES
+    if( pItem->bSorterRef ){
+      i--;
+      n--;
+    }else
+#endif
     if( (flags & SQLITE_ECEL_REF)!=0 && (j = pItem->u.x.iOrderByCol)>0 ){
       if( flags & SQLITE_ECEL_OMITREF ){
         i--;
diff --git a/src/global.c b/src/global.c
index 04a3d185a..f0362d1e0 100644
--- a/src/global.c
+++ b/src/global.c
@@ -240,7 +240,8 @@ SQLITE_WSD struct Sqlite3Config sqlite3Config = {
    0,                         /* xTestCallback */
 #endif
    0,                         /* bLocaltimeFault */
-   0x7ffffffe                 /* iOnceResetThreshold */
+   0x7ffffffe,                /* iOnceResetThreshold */
+   SQLITE_DEFAULT_SORTERREF_SIZE   /* szSorterRef */
 };
 
 /*
diff --git a/src/main.c b/src/main.c
index 5b6c86709..99e3e6f97 100644
--- a/src/main.c
+++ b/src/main.c
@@ -642,6 +642,17 @@ int sqlite3_config(int op, ...){
       break;
     }
 
+#ifdef SQLITE_ENABLE_SORTER_REFERENCES
+    case SQLITE_CONFIG_SORTERREF_SIZE: {
+      int iVal = va_arg(ap, int);
+      if( iVal<0 ){
+        iVal = SQLITE_DEFAULT_SORTERREF_SIZE;
+      }
+      sqlite3GlobalConfig.szSorterRef = (u32)iVal;
+      break;
+    }
+#endif /* SQLITE_ENABLE_SORTER_REFERENCES */
+
     default: {
       rc = SQLITE_ERROR;
       break;
diff --git a/src/select.c b/src/select.c
index c2686e0fe..570b066dd 100644
--- a/src/select.c
+++ b/src/select.c
@@ -44,6 +44,20 @@ struct DistinctCtx {
 /*
 ** An instance of the following object is used to record information about
 ** the ORDER BY (or GROUP BY) clause of query is being coded.
+**
+** The aDefer[] array is used by the sorter-references optimization. For
+** example, assuming there is no index that can be used for the ORDER BY,
+** for the query:
+**
+**     SELECT a, bigblob FROM t1 ORDER BY a LIMIT 10;
+**
+** it may be more efficient to add just the "a" values to the sorter, and
+** retrieve the associated "bigblob" values directly from table t1 as the
+** 10 smallest "a" values are extracted from the sorter.
+**
+** When the sorter-reference optimization is used, there is one entry in the
+** aDefer[] array for each database table that may be read as values are
+** extracted from the sorter.
 */
 typedef struct SortCtx SortCtx;
 struct SortCtx {
@@ -56,6 +70,14 @@ struct SortCtx {
   int labelDone;        /* Jump here when done, ex: LIMIT reached */
   u8 sortFlags;         /* Zero or more SORTFLAG_* bits */
   u8 bOrderedInnerLoop; /* ORDER BY correctly sorts the inner loop */
+#ifdef SQLITE_ENABLE_SORTER_REFERENCES
+  u8 nDefer;            /* Number of valid entries in aDefer[] */
+  struct DeferredCsr {
+    Table *pTab;        /* Table definition */
+    int iCsr;           /* Cursor number for table */
+    int nKey;           /* Number of PK columns for table pTab (>=1) */
+  } aDefer[4];
+#endif
 };
 #define SORTFLAG_UseSorter  0x01   /* Use SorterOpen instead of OpenEphemeral */
 
@@ -678,6 +700,90 @@ static void codeDistinct(
   sqlite3ReleaseTempReg(pParse, r1);
 }
 
+#ifdef SQLITE_ENABLE_SORTER_REFERENCES
+/*
+** This function is called as part of inner-loop generation for a SELECT
+** statement with an ORDER BY that is not optimized by an index. It 
+** determines the expressions, if any, that the sorter-reference 
+** optimization should be used for. The sorter-reference optimization
+** is used for SELECT queries like:
+**
+**   SELECT a, bigblob FROM t1 ORDER BY a LIMIT 10
+**
+** If the optimization is used for expression "bigblob", then instead of
+** storing values read from that column in the sorter records, the PK of
+** the row from table t1 is stored instead. Then, as records are extracted from
+** the sorter to return to the user, the required value of bigblob is
+** retrieved directly from table t1. If the values are very large, this 
+** can be more efficient than storing them directly in the sorter records.
+**
+** The ExprList_item.bSorterRef flag is set for each expression in pEList 
+** for which the sorter-reference optimization should be enabled. 
+** Additionally, the pSort->aDefer[] array is populated with entries
+** for all cursors required to evaluate all selected expressions. Finally.
+** output variable (*ppExtra) is set to an expression list containing
+** expressions for all extra PK values that should be stored in the
+** sorter records.
+*/
+static void selectExprDefer(
+  Parse *pParse,                  /* Leave any error here */
+  SortCtx *pSort,                 /* Sorter context */
+  ExprList *pEList,               /* Expressions destined for sorter */
+  ExprList **ppExtra              /* Expressions to append to sorter record */
+){
+  int i;
+  int nDefer = 0;
+  ExprList *pExtra = 0;
+  for(i=0; i<pEList->nExpr; i++){
+    struct ExprList_item *pItem = &pEList->a[i];
+    if( pItem->u.x.iOrderByCol==0 ){
+      Expr *pExpr = pItem->pExpr;
+      Table *pTab = pExpr->pTab;
+      if( pExpr->op==TK_COLUMN && pTab && !IsVirtual(pTab)
+       && (pTab->aCol[pExpr->iColumn].colFlags & COLFLAG_SORTERREF)
+#if 0
+          && pTab->pSchema && pTab->pSelect==0 && !IsVirtual(pTab)
+#endif
+      ){
+        int j;
+        for(j=0; j<nDefer; j++){
+          if( pSort->aDefer[j].iCsr==pExpr->iTable ) break;
+        }
+        if( j==nDefer ){
+          if( nDefer==ArraySize(pSort->aDefer) ){
+            continue;
+          }else{
+            int nKey = 1;
+            int k;
+            Index *pPk = 0;
+            if( !HasRowid(pTab) ){
+              pPk = sqlite3PrimaryKeyIndex(pTab);
+              nKey = pPk->nKeyCol;
+            }
+            for(k=0; k<nKey; k++){
+              Expr *pNew = sqlite3PExpr(pParse, TK_COLUMN, 0, 0);
+              if( pNew ){
+                pNew->iTable = pExpr->iTable;
+                pNew->pTab = pExpr->pTab;
+                pNew->iColumn = pPk ? pPk->aiColumn[k] : -1;
+                pExtra = sqlite3ExprListAppend(pParse, pExtra, pNew);
+              }
+            }
+            pSort->aDefer[nDefer].pTab = pExpr->pTab;
+            pSort->aDefer[nDefer].iCsr = pExpr->iTable;
+            pSort->aDefer[nDefer].nKey = nKey;
+            nDefer++;
+          }
+        }
+        pItem->bSorterRef = 1;
+      }
+    }
+  }
+  pSort->nDefer = (u8)nDefer;
+  *ppExtra = pExtra;
+}
+#endif
+
 /*
 ** This routine generates the code for the inside of the inner loop
 ** of a SELECT.
@@ -750,6 +856,9 @@ static void selectInnerLoop(
       VdbeComment((v, "%s", p->pEList->a[i].zName));
     }
   }else if( eDest!=SRT_Exists ){
+#ifdef SQLITE_ENABLE_SORTER_REFERENCES
+    ExprList *pExtra = 0;
+#endif
     /* If the destination is an EXISTS(...) expression, the actual
     ** values returned by the SELECT are not required.
     */
@@ -773,12 +882,34 @@ static void selectInnerLoop(
           p->pEList->a[j-1].u.x.iOrderByCol = i+1-pSort->nOBSat;
         }
       }
+#ifdef SQLITE_ENABLE_SORTER_REFERENCES
+      selectExprDefer(pParse, pSort, p->pEList, &pExtra);
+      if( pExtra && pParse->db->mallocFailed==0 ){
+        /* If there are any extra PK columns to add to the sorter records,
+        ** allocate extra memory cells and adjust the OpenEphemeral 
+        ** instruction to account for the larger records. This is only
+        ** required if there are one or more WITHOUT ROWID tables with
+        ** composite primary keys in the SortCtx.aDefer[] array.  */
+        VdbeOp *pOp = sqlite3VdbeGetOp(v, pSort->addrSortIndex);
+        pOp->p2 += (pExtra->nExpr - pSort->nDefer);
+        pOp->p4.pKeyInfo->nAllField += (pExtra->nExpr - pSort->nDefer);
+        pParse->nMem += pExtra->nExpr;
+      }
+#endif
       regOrig = 0;
       assert( eDest==SRT_Set || eDest==SRT_Mem 
            || eDest==SRT_Coroutine || eDest==SRT_Output );
     }
     nResultCol = sqlite3ExprCodeExprList(pParse,p->pEList,regResult,
                                          0,ecelFlags);
+#ifdef SQLITE_ENABLE_SORTER_REFERENCES
+    if( pExtra ){
+      nResultCol += sqlite3ExprCodeExprList(
+          pParse, pExtra, regResult + nResultCol, 0, 0
+      );
+      sqlite3ExprListDelete(pParse->db, pExtra);
+    }
+#endif
   }
 
   /* If the DISTINCT keyword was present on the SELECT statement
@@ -1236,7 +1367,7 @@ static void generateSortTail(
   Vdbe *v = pParse->pVdbe;                     /* The prepared statement */
   int addrBreak = pSort->labelDone;            /* Jump here to exit loop */
   int addrContinue = sqlite3VdbeMakeLabel(v);  /* Jump here for next cycle */
-  int addr;
+  int addr;                       /* Top of output loop. Jump for Next. */
   int addrOnce = 0;
   int iTab;
   ExprList *pOrderBy = pSort->pOrderBy;
@@ -1245,10 +1376,11 @@ static void generateSortTail(
   int regRow;
   int regRowid;
   int iCol;
-  int nKey;
+  int nKey;                       /* Number of key columns in sorter record */
   int iSortTab;                   /* Sorter cursor to read from */
   int i;
   int bSeq;                       /* True if sorter record includes seq. no. */
+  int nRefKey = 0;
   struct ExprList_item *aOutEx = p->pEList->a;
 
   assert( addrBreak<0 );
@@ -1257,6 +1389,17 @@ static void generateSortTail(
     sqlite3VdbeGoto(v, addrBreak);
     sqlite3VdbeResolveLabel(v, pSort->labelBkOut);
   }
+
+#ifdef SQLITE_ENABLE_SORTER_REFERENCES
+  /* Open any cursors needed for sorter-reference expressions */
+  for(i=0; i<pSort->nDefer; i++){
+    Table *pTab = pSort->aDefer[i].pTab;
+    int iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
+    sqlite3OpenTable(pParse, pSort->aDefer[i].iCsr, iDb, pTab, OP_OpenRead);
+    nRefKey = MAX(nRefKey, pSort->aDefer[i].nKey);
+  }
+#endif
+
   iTab = pSort->iECursor;
   if( eDest==SRT_Output || eDest==SRT_Coroutine || eDest==SRT_Mem ){
     regRowid = 0;
@@ -1272,7 +1415,8 @@ static void generateSortTail(
     if( pSort->labelBkOut ){
       addrOnce = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v);
     }
-    sqlite3VdbeAddOp3(v, OP_OpenPseudo, iSortTab, regSortOut, nKey+1+nColumn);
+    sqlite3VdbeAddOp3(v, OP_OpenPseudo, iSortTab, regSortOut, 
+        nKey+1+nColumn+nRefKey);
     if( addrOnce ) sqlite3VdbeJumpHere(v, addrOnce);
     addr = 1 + sqlite3VdbeAddOp2(v, OP_SorterSort, iTab, addrBreak);
     VdbeCoverage(v);
@@ -1286,17 +1430,58 @@ static void generateSortTail(
     bSeq = 1;
   }
   for(i=0, iCol=nKey+bSeq-1; i<nColumn; i++){
+#ifdef SQLITE_ENABLE_SORTER_REFERENCES
+    if( aOutEx[i].bSorterRef ) continue;
+#endif
     if( aOutEx[i].u.x.iOrderByCol==0 ) iCol++;
   }
+#ifdef SQLITE_ENABLE_SORTER_REFERENCES
+  if( pSort->nDefer ){
+    int iKey = iCol+1;
+    int regKey = sqlite3GetTempRange(pParse, nRefKey);
+
+    for(i=0; i<pSort->nDefer; i++){
+      int iCsr = pSort->aDefer[i].iCsr;
+      Table *pTab = pSort->aDefer[i].pTab;
+      int nKey = pSort->aDefer[i].nKey;
+
+      sqlite3VdbeAddOp1(v, OP_NullRow, iCsr);
+      if( HasRowid(pTab) ){
+        sqlite3VdbeAddOp3(v, OP_Column, iSortTab, iKey++, regKey);
+        sqlite3VdbeAddOp3(v, OP_SeekRowid, iCsr, 
+            sqlite3VdbeCurrentAddr(v)+1, regKey);
+      }else{
+        int k;
+        int iJmp;
+        assert( sqlite3PrimaryKeyIndex(pTab)->nKeyCol==nKey );
+        for(k=0; k<nKey; k++){
+          sqlite3VdbeAddOp3(v, OP_Column, iSortTab, iKey++, regKey+k);
+        }
+        iJmp = sqlite3VdbeCurrentAddr(v);
+        sqlite3VdbeAddOp4Int(v, OP_SeekGE, iCsr, iJmp+2, regKey, nKey);
+        sqlite3VdbeAddOp4Int(v, OP_IdxLE, iCsr, iJmp+3, regKey, nKey);
+        sqlite3VdbeAddOp1(v, OP_NullRow, iCsr);
+      }
+    }
+    sqlite3ReleaseTempRange(pParse, regKey, nRefKey);
+  }
+#endif
   for(i=nColumn-1; i>=0; i--){
-    int iRead;
-    if( aOutEx[i].u.x.iOrderByCol ){
-      iRead = aOutEx[i].u.x.iOrderByCol-1;
-    }else{
-      iRead = iCol--;
+#ifdef SQLITE_ENABLE_SORTER_REFERENCES
+    if( aOutEx[i].bSorterRef ){
+      sqlite3ExprCode(pParse, aOutEx[i].pExpr, regRow+i);
+    }else
+#endif
+    {
+      int iRead;
+      if( aOutEx[i].u.x.iOrderByCol ){
+        iRead = aOutEx[i].u.x.iOrderByCol-1;
+      }else{
+        iRead = iCol--;
+      }
+      sqlite3VdbeAddOp3(v, OP_Column, iSortTab, iRead, regRow+i);
+      VdbeComment((v, "%s", aOutEx[i].zName?aOutEx[i].zName : aOutEx[i].zSpan));
     }
-    sqlite3VdbeAddOp3(v, OP_Column, iSortTab, iRead, regRow+i);
-    VdbeComment((v, "%s", aOutEx[i].zName ? aOutEx[i].zName : aOutEx[i].zSpan));
   }
   switch( eDest ){
     case SRT_Table:
@@ -6073,6 +6258,7 @@ int sqlite3Select(
   if( sSort.pOrderBy ){
     explainTempTable(pParse,
                      sSort.nOBSat>0 ? "RIGHT PART OF ORDER BY":"ORDER BY");
+    assert( p->pEList==pEList );
     generateSortTail(pParse, p, &sSort, pEList->nExpr, pDest);
   }
 
diff --git a/src/shell.c.in b/src/shell.c.in
index 87087ed45..38e5c5cbe 100644
--- a/src/shell.c.in
+++ b/src/shell.c.in
@@ -8074,6 +8074,9 @@ static const char zOptions[] =
   "   -quote               set output mode to 'quote'\n"
   "   -readonly            open the database read-only\n"
   "   -separator SEP       set output column separator. Default: '|'\n"
+#ifdef SQLITE_ENABLE_SORTER_REFERENCES
+  "   -sorterref SIZE      sorter references threshold size\n"
+#endif
   "   -stats               print memory stats before each finalize\n"
   "   -version             show SQLite version\n"
   "   -vfs NAME            use NAME as the default VFS\n"
@@ -8343,6 +8346,11 @@ int SQLITE_CDECL wmain(int argc, wchar_t **wargv){
     }else if( strcmp(z,"-mmap")==0 ){
       sqlite3_int64 sz = integerValue(cmdline_option_value(argc,argv,++i));
       sqlite3_config(SQLITE_CONFIG_MMAP_SIZE, sz, sz);
+#ifdef SQLITE_ENABLE_SORTER_REFERENCES
+    }else if( strcmp(z,"-sorterref")==0 ){
+      sqlite3_int64 sz = integerValue(cmdline_option_value(argc,argv,++i));
+      sqlite3_config(SQLITE_CONFIG_SORTERREF_SIZE, (int)sz);
+#endif
     }else if( strcmp(z,"-vfs")==0 ){
       zVfs = cmdline_option_value(argc, argv, ++i);
 #ifdef SQLITE_HAVE_ZLIB
@@ -8489,6 +8497,10 @@ int SQLITE_CDECL wmain(int argc, wchar_t **wargv){
       i+=2;
     }else if( strcmp(z,"-mmap")==0 ){
       i++;
+#ifdef SQLITE_ENABLE_SORTER_REFERENCES
+    }else if( strcmp(z,"-sorterref")==0 ){
+      i++;
+#endif
     }else if( strcmp(z,"-vfs")==0 ){
       i++;
 #ifdef SQLITE_ENABLE_VFSTRACE
diff --git a/src/sqlite.h.in b/src/sqlite.h.in
index 202155df7..02dc8944b 100644
--- a/src/sqlite.h.in
+++ b/src/sqlite.h.in
@@ -1930,6 +1930,22 @@ struct sqlite3_mem_methods {
 ** I/O required to support statement rollback.
 ** The default value for this setting is controlled by the
 ** [SQLITE_STMTJRNL_SPILL] compile-time option.
+**
+** [[SQLITE_CONFIG_SORTERREF_SIZE]]
+** <dt>SQLITE_CONFIG_SORTERREF_SIZE
+** <dd>The SQLITE_CONFIG_SORTERREF_SIZE option accepts a single parameter
+** of type (int) - the new value of the sorter-reference size threshold.
+** Usually, when SQLite uses an external sort to order records according
+** to an ORDER BY clause, all fields required by the caller are present in the
+** sorted records. However, if SQLite determines based on the declared type
+** of a table column that its values are likely to be very large - larger
+** than the configured sorter-reference size threshold - then a reference
+** is stored in each sorted record and the required column values loaded
+** from the database as records are returned in sorted order. The default
+** value for this option is to never use this optimization. Specifying a 
+** negative value for this option restores the default behaviour.
+** This option is only available if SQLite is compiled with the
+** [SQLITE_ENABLE_SORTER_REFERENCES] compile-time option.
 ** </dl>
 */
 #define SQLITE_CONFIG_SINGLETHREAD  1  /* nil */
@@ -1959,6 +1975,7 @@ struct sqlite3_mem_methods {
 #define SQLITE_CONFIG_PMASZ               25  /* unsigned int szPma */
 #define SQLITE_CONFIG_STMTJRNL_SPILL      26  /* int nByte */
 #define SQLITE_CONFIG_SMALL_MALLOC        27  /* boolean */
+#define SQLITE_CONFIG_SORTERREF_SIZE      28  /* int nByte */
 
 /*
 ** CAPI3REF: Database Connection Configuration Options
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index ae703ae76..73cb6299d 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -638,6 +638,13 @@
 #endif
 
 /*
+** Default value for the SQLITE_CONFIG_SORTERREF_SIZE option.
+*/
+#ifndef SQLITE_DEFAULT_SORTERREF_SIZE
+# define SQLITE_DEFAULT_SORTERREF_SIZE 0x7fffffff
+#endif
+
+/*
 ** The compile-time options SQLITE_MMAP_READWRITE and 
 ** SQLITE_ENABLE_BATCH_ATOMIC_WRITE are not compatible with one another.
 ** You must choose one or the other (or neither) but not both.
@@ -1760,6 +1767,7 @@ struct Column {
 #define COLFLAG_HIDDEN   0x0002    /* A hidden column in a virtual table */
 #define COLFLAG_HASTYPE  0x0004    /* Type name follows column name */
 #define COLFLAG_UNIQUE   0x0008    /* Column def contains "UNIQUE" or "PK" */
+#define COLFLAG_SORTERREF 0x0010   /* Use sorter-refs with this column */
 
 /*
 ** A "Collating Sequence" is defined by an instance of the following
@@ -2499,6 +2507,7 @@ struct ExprList {
     unsigned done :1;       /* A flag to indicate when processing is finished */
     unsigned bSpanIsTab :1; /* zSpan holds DB.TABLE.COLUMN */
     unsigned reusable :1;   /* Constant expression is reusable */
+    unsigned bSorterRef :1; /* Defer evaluation until after sorting */
     union {
       struct {
         u16 iOrderByCol;      /* For ORDER BY, column number in result set */
@@ -3351,6 +3360,7 @@ struct Sqlite3Config {
 #endif
   int bLocaltimeFault;              /* True to fail localtime() calls */
   int iOnceResetThreshold;          /* When to reset OP_Once counters */
+  u32 szSorterRef;                  /* Min size in bytes to use sorter-refs */
 };
 
 /*
@@ -4135,7 +4145,7 @@ void sqlite3ColumnDefault(Vdbe *, Table *, int, int);
 void sqlite3AlterFinishAddColumn(Parse *, Token *);
 void sqlite3AlterBeginAddColumn(Parse *, SrcList *);
 CollSeq *sqlite3GetCollSeq(Parse*, u8, CollSeq *, const char*);
-char sqlite3AffinityType(const char*, u8*);
+char sqlite3AffinityType(const char*, Column*);
 void sqlite3Analyze(Parse*, Token*, Token*);
 int sqlite3InvokeBusyHandler(BusyHandler*, sqlite3_file*);
 int sqlite3FindDb(sqlite3*, Token*);
diff --git a/src/test1.c b/src/test1.c
index bc8f389db..0f139ceba 100644
--- a/src/test1.c
+++ b/src/test1.c
@@ -2257,6 +2257,27 @@ static int SQLITE_TCLAPI test_config_sqllog(
 #endif
 
 /*
+** Usage:  sqlite3_config_sorterref
+**
+** Set the SQLITE_CONFIG_SORTERREF_SIZE configuration option
+*/
+static int SQLITE_TCLAPI test_config_sorterref(
+  void * clientData,
+  Tcl_Interp *interp,
+  int objc,
+  Tcl_Obj *CONST objv[]
+){
+  int iVal;
+  if( objc!=2 ){
+    Tcl_WrongNumArgs(interp, 1, objv, "NBYTE");
+    return TCL_ERROR;
+  }
+  if( Tcl_GetIntFromObj(interp, objv[1], &iVal) ) return TCL_ERROR;
+  sqlite3_config(SQLITE_CONFIG_SORTERREF_SIZE, iVal);
+  return TCL_OK;
+}
+
+/*
 ** Usage: vfs_current_time_int64
 **
 ** Return the value returned by the default VFS's xCurrentTimeInt64 method.
@@ -7751,6 +7772,7 @@ int Sqlitetest1_Init(Tcl_Interp *interp){
      { "sqlite3_delete_database", test_delete_database,    0 },
      { "atomic_batch_write",      test_atomic_batch_write, 0 },
      { "sqlite3_mmap_warm",       test_mmap_warm,          0 },
+     { "sqlite3_config_sorterref", test_config_sorterref,   0 },
   };
   static int bitmask_size = sizeof(Bitmask)*8;
   static int longdouble_size = sizeof(LONGDOUBLE_TYPE);