/ Check-in [09db0a24]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Sorting is now done using a sorting index rather than loading the entire result set into memory and doing a merge sort. The old merge sort technique was a carry-over from SQLite version 1. The new method uses a bounded amount of memory and scales to much larger result sets. There are still errors: some 39 regression tests fail. (CVS 2653)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 09db0a24241f9248584250d1728117b8a3159626
User & Date: drh 2005-09-01 03:07:44
Context
2005-09-01
12:16
All regression tests now pass with the new bounded-memory sort code. There is still lots of opportunity for optimization, however. (CVS 2654) check-in: 81259a01 user: drh tags: trunk
03:07
Sorting is now done using a sorting index rather than loading the entire result set into memory and doing a merge sort. The old merge sort technique was a carry-over from SQLite version 1. The new method uses a bounded amount of memory and scales to much larger result sets. There are still errors: some 39 regression tests fail. (CVS 2653) check-in: 09db0a24 user: drh tags: trunk
2005-08-31
18:20
{quote: KeyInfo} generation moved to a common subroutine. (CVS 2652) check-in: a25801df user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/expr.c.

     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** This file contains routines used for analyzing expressions and
    13     13   ** for generating VDBE code that evaluates expressions in SQLite.
    14     14   **
    15         -** $Id: expr.c,v 1.222 2005/08/30 00:54:02 drh Exp $
           15  +** $Id: expr.c,v 1.223 2005/09/01 03:07:44 drh Exp $
    16     16   */
    17     17   #include "sqliteInt.h"
    18     18   #include <ctype.h>
    19     19   
    20     20   /*
    21     21   ** Return the 'affinity' of the expression pExpr if any.
    22     22   **
................................................................................
   542    542     pNew->pOrderBy = sqlite3ExprListDup(p->pOrderBy);
   543    543     pNew->op = p->op;
   544    544     pNew->pPrior = sqlite3SelectDup(p->pPrior);
   545    545     pNew->pLimit = sqlite3ExprDup(p->pLimit);
   546    546     pNew->pOffset = sqlite3ExprDup(p->pOffset);
   547    547     pNew->iLimit = -1;
   548    548     pNew->iOffset = -1;
   549         -  pNew->ppOpenVirtual = 0;
   550    549     pNew->isResolved = p->isResolved;
   551    550     pNew->isAgg = p->isAgg;
          551  +  pNew->pRightmost = 0;
          552  +  pNew->addrOpenVirt[0] = -1;
          553  +  pNew->addrOpenVirt[1] = -1;
          554  +  pNew->addrOpenVirt[2] = -1;
   552    555     return pNew;
   553    556   }
   554    557   #else
   555    558   Select *sqlite3SelectDup(Select *p){
   556    559     assert( p==0 );
   557    560     return 0;
   558    561   }

Changes to src/select.c.

     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** This file contains C code routines that are called by the parser
    13     13   ** to handle SELECT statements in SQLite.
    14     14   **
    15         -** $Id: select.c,v 1.257 2005/08/31 18:20:00 drh Exp $
           15  +** $Id: select.c,v 1.258 2005/09/01 03:07:44 drh Exp $
    16     16   */
    17     17   #include "sqliteInt.h"
    18     18   
    19     19   
    20     20   /*
    21     21   ** Allocate a new Select structure and return a pointer to that
    22     22   ** structure.
................................................................................
    56     56       pNew->pOrderBy = pOrderBy;
    57     57       pNew->isDistinct = isDistinct;
    58     58       pNew->op = TK_SELECT;
    59     59       pNew->pLimit = pLimit;
    60     60       pNew->pOffset = pOffset;
    61     61       pNew->iLimit = -1;
    62     62       pNew->iOffset = -1;
           63  +    pNew->addrOpenVirt[0] = -1;
           64  +    pNew->addrOpenVirt[1] = -1;
           65  +    pNew->addrOpenVirt[2] = -1;
    63     66     }
    64     67     return pNew;
    65     68   }
    66     69   
    67     70   /*
    68     71   ** Given 1 to 3 identifiers preceeding the JOIN keyword, determine the
    69     72   ** type of join.  Return an integer constant that expresses that type
................................................................................
   323    326   
   324    327   /*
   325    328   ** Insert code into "v" that will push the record on the top of the
   326    329   ** stack into the sorter.
   327    330   */
   328    331   static void pushOntoSorter(Parse *pParse, Vdbe *v, ExprList *pOrderBy){
   329    332     sqlite3ExprCodeExprList(pParse, pOrderBy);
   330         -  sqlite3VdbeAddOp(v, OP_MakeRecord, pOrderBy->nExpr, 0);
   331         -  sqlite3VdbeAddOp(v, OP_SortInsert, 0, 0);
          333  +  sqlite3VdbeAddOp(v, OP_Pull, pOrderBy->nExpr, 0);
          334  +  sqlite3VdbeAddOp(v, OP_MakeRecord, pOrderBy->nExpr + 1, 0);
          335  +  sqlite3VdbeAddOp(v, OP_IdxInsert, pOrderBy->iTab, 0);
   332    336   }
   333    337   
   334    338   /*
   335    339   ** Add code to implement the OFFSET and LIMIT
   336    340   */
   337    341   static void codeLimiter(
   338    342     Vdbe *v,          /* Generate code into this VM */
................................................................................
   550    554     }
   551    555     return 0;
   552    556   }
   553    557   
   554    558   /*
   555    559   ** Given an expression list, generate a KeyInfo structure that records
   556    560   ** the collating sequence for each expression in that expression list.
          561  +**
          562  +** If the ExprList is an ORDER BY or GROUP BY clause then the resulting
          563  +** KeyInfo structure is appropriate for initializing a virtual index to
          564  +** implement that clause.  If the ExprList is the result set of a SELECT
          565  +** then the KeyInfo structure is appropriate for initializing a virtual
          566  +** index to implement a DISTINCT test.
   557    567   **
   558    568   ** Space to hold the KeyInfo structure is obtain from malloc.  The calling
   559    569   ** function is responsible for seeing that this structure is eventually
   560    570   ** freed.  Add the KeyInfo structure to the P3 field of an opcode using
   561    571   ** P3_KEYINFO_HANDOFF is the usual way of dealing with this.
   562    572   */
   563    573   static KeyInfo *keyInfoFromExprList(Parse *pParse, ExprList *pList){
................................................................................
   597    607     Parse *pParse,   /* The parsing context */
   598    608     Select *p,       /* The SELECT statement */
   599    609     Vdbe *v,         /* Generate code into this VDBE */
   600    610     int nColumn,     /* Number of columns of data */
   601    611     int eDest,       /* Write the sorted results here */
   602    612     int iParm        /* Optional parameter associated with eDest */
   603    613   ){
   604         -  int end1 = sqlite3VdbeMakeLabel(v);
   605         -  int end2 = sqlite3VdbeMakeLabel(v);
          614  +  int brk = sqlite3VdbeMakeLabel(v);
          615  +  int cont = sqlite3VdbeMakeLabel(v);
   606    616     int addr;
   607         -  KeyInfo *pInfo;
          617  +  int iTab;
          618  +  ExprList *pOrderBy = p->pOrderBy;
   608    619   
   609    620     if( eDest==SRT_Sorter ) return;
   610         -  pInfo = keyInfoFromExprList(pParse, p->pOrderBy);
   611         -  if( pInfo==0 ) return;
   612         -  sqlite3VdbeOp3(v, OP_Sort, 0, 0, (char*)pInfo, P3_KEYINFO_HANDOFF);
   613         -  addr = sqlite3VdbeAddOp(v, OP_SortNext, 0, end1);
   614         -  codeLimiter(v, p, addr, end2, 1);
          621  +  iTab = pOrderBy->iTab;
          622  +  addr = 1 + sqlite3VdbeAddOp(v, OP_Sort, iTab, brk);
          623  +  codeLimiter(v, p, cont, brk, 0);
          624  +  sqlite3VdbeAddOp(v, OP_Column, iTab, pOrderBy->nExpr);
   615    625     switch( eDest ){
   616    626       case SRT_Table:
   617    627       case SRT_TempTable: {
   618    628         sqlite3VdbeAddOp(v, OP_NewRowid, iParm, 0);
   619    629         sqlite3VdbeAddOp(v, OP_Pull, 1, 0);
   620    630         sqlite3VdbeAddOp(v, OP_Insert, iParm, 0);
   621    631         break;
................................................................................
   630    640         sqlite3VdbeAddOp(v, OP_IdxInsert, (iParm&0x0000FFFF), 0);
   631    641         break;
   632    642       }
   633    643       case SRT_Exists:
   634    644       case SRT_Mem: {
   635    645         assert( nColumn==1 );
   636    646         sqlite3VdbeAddOp(v, OP_MemStore, iParm, 1);
   637         -      sqlite3VdbeAddOp(v, OP_Goto, 0, end1);
          647  +      sqlite3VdbeAddOp(v, OP_Goto, 0, brk);
   638    648         break;
   639    649       }
   640    650   #endif
   641    651       case SRT_Callback:
   642    652       case SRT_Subroutine: {
   643    653         int i;
   644    654         sqlite3VdbeAddOp(v, OP_Integer, p->pEList->nExpr, 0);
................................................................................
   655    665         break;
   656    666       }
   657    667       default: {
   658    668         /* Do nothing */
   659    669         break;
   660    670       }
   661    671     }
   662         -  sqlite3VdbeAddOp(v, OP_Goto, 0, addr);
   663         -  sqlite3VdbeResolveLabel(v, end2);
   664         -  sqlite3VdbeAddOp(v, OP_Pop, 1, 0);
   665         -  sqlite3VdbeResolveLabel(v, end1);
   666         -  sqlite3VdbeAddOp(v, OP_SortReset, 0, 0);
          672  +  sqlite3VdbeResolveLabel(v, cont);
          673  +  sqlite3VdbeAddOp(v, OP_Next, iTab, addr);
          674  +  sqlite3VdbeResolveLabel(v, brk);
   667    675   }
   668    676   
   669    677   /*
   670    678   ** Return a pointer to a string containing the 'declaration type' of the
   671    679   ** expression pExpr. The string may be treated as static by the caller.
   672    680   **
   673    681   ** If the declaration type is the exact datatype definition extracted from
................................................................................
  1323   1331       sqlite3VdbeAddOp(v, OP_MemStore, iMem, 1);
  1324   1332       VdbeComment((v, "# OFFSET counter"));
  1325   1333       p->iOffset = iMem;
  1326   1334     }
  1327   1335   }
  1328   1336   
  1329   1337   /*
  1330         -** Generate VDBE instructions that will open a transient table that
  1331         -** will be used for an index or to store keyed results for a compound
  1332         -** select.  In other words, open a transient table that needs a
  1333         -** KeyInfo structure.  The number of columns in the KeyInfo is determined
  1334         -** by the result set of the SELECT statement in the second argument.
  1335         -**
  1336         -** Specifically, this routine is called to open an index table for
  1337         -** DISTINCT, UNION, INTERSECT and EXCEPT select statements (but not 
  1338         -** UNION ALL).
  1339         -**
  1340         -** The value returned is the address of the OP_OpenVirtual instruction.
         1338  +** Allocate a virtual index to use for sorting.
  1341   1339   */
  1342         -static int openVirtualIndex(Parse *pParse, Select *p, int iTab){
  1343         -  KeyInfo *pKeyInfo;
  1344         -  Vdbe *v = pParse->pVdbe;
  1345         -  int addr;
  1346         -
  1347         -  if( prepSelectStmt(pParse, p) ){
  1348         -    return 0;
         1340  +static createSortingIndex(Parse *pParse, Select *p, ExprList *pOrderBy){
         1341  +  if( pOrderBy ){
         1342  +    int addr;
         1343  +    assert( pOrderBy->iTab==0 );
         1344  +    pOrderBy->iTab = pParse->nTab++;
         1345  +    addr = sqlite3VdbeAddOp(pParse->pVdbe, OP_OpenVirtual,
         1346  +                            pOrderBy->iTab, pOrderBy->nExpr+1);
         1347  +    assert( p->addrOpenVirt[2] == -1 );
         1348  +    p->addrOpenVirt[2] = addr;
  1349   1349     }
  1350         -  pKeyInfo = keyInfoFromExprList(pParse, p->pEList);
  1351         -  if( pKeyInfo==0 ) return 0;
  1352         -  addr = sqlite3VdbeOp3(v, OP_OpenVirtual, iTab, 0, 
  1353         -                        (char*)pKeyInfo, P3_KEYINFO_HANDOFF);
  1354         -  return addr;
  1355   1350   }
  1356   1351   
  1357         -#ifndef SQLITE_OMIT_COMPOUND_SELECT
  1358         -/*
  1359         -** Add the address "addr" to the set of all OpenVirtual opcode addresses
  1360         -** that are being accumulated in p->ppOpenVirtual.
  1361         -*/
  1362         -static int multiSelectOpenVirtualAddr(Select *p, int addr){
  1363         -  IdList *pList = *p->ppOpenVirtual = sqlite3IdListAppend(*p->ppOpenVirtual, 0);
  1364         -  if( pList==0 ){
  1365         -    return SQLITE_NOMEM;
  1366         -  }
  1367         -  pList->a[pList->nId-1].idx = addr;
  1368         -  return SQLITE_OK;
  1369         -}
  1370         -#endif /* SQLITE_OMIT_COMPOUND_SELECT */
  1371         -
  1372   1352   #ifndef SQLITE_OMIT_COMPOUND_SELECT
  1373   1353   /*
  1374   1354   ** Return the appropriate collating sequence for the iCol-th column of
  1375   1355   ** the result set for the compound-select statement "p".  Return NULL if
  1376   1356   ** the column has no default collating sequence.
  1377   1357   **
  1378   1358   ** The collating sequence for the compound select is taken from the
................................................................................
  1429   1409     int eDest,            /* \___  Store query results as specified */
  1430   1410     int iParm,            /* /     by these two parameters.         */
  1431   1411     char *aff             /* If eDest is SRT_Union, the affinity string */
  1432   1412   ){
  1433   1413     int rc = SQLITE_OK;   /* Success code from a subroutine */
  1434   1414     Select *pPrior;       /* Another SELECT immediately to our left */
  1435   1415     Vdbe *v;              /* Generate code to this VDBE */
  1436         -  IdList *pOpenVirtual = 0;/* OP_OpenVirtual opcodes that need a KeyInfo */
  1437         -  int aAddr[5];         /* Addresses of SetNumColumns operators */
  1438         -  int nAddr = 0;        /* Number used */
  1439   1416     int nCol;             /* Number of columns in the result set */
         1417  +  ExprList *pOrderBy;   /* The ORDER BY clause on p */
         1418  +  int aSetP2[2];        /* Set P2 value of these op to number of columns */
         1419  +  int nSetP2 = 0;       /* Number of slots in aSetP2[] used */
  1440   1420   
  1441   1421     /* Make sure there is no ORDER BY or LIMIT clause on prior SELECTs.  Only
  1442   1422     ** the last (right-most) SELECT in the series may have an ORDER BY or LIMIT.
  1443   1423     */
  1444   1424     if( p==0 || p->pPrior==0 ){
  1445   1425       rc = 1;
  1446   1426       goto multi_select_end;
  1447   1427     }
  1448   1428     pPrior = p->pPrior;
         1429  +  assert( pPrior->pRightmost!=pPrior );
         1430  +  assert( pPrior->pRightmost==p->pRightmost );
  1449   1431     if( pPrior->pOrderBy ){
  1450   1432       sqlite3ErrorMsg(pParse,"ORDER BY clause should come after %s not before",
  1451   1433         selectOpName(p->op));
  1452   1434       rc = 1;
  1453   1435       goto multi_select_end;
  1454   1436     }
  1455   1437     if( pPrior->pLimit ){
................................................................................
  1463   1445     */
  1464   1446     v = sqlite3GetVdbe(pParse);
  1465   1447     if( v==0 ){
  1466   1448       rc = 1;
  1467   1449       goto multi_select_end;
  1468   1450     }
  1469   1451   
  1470         -  /* If *p this is the right-most select statement, then initialize
  1471         -  ** p->ppOpenVirtual to point to pOpenVirtual.  If *p is not the right most
  1472         -  ** statement then p->ppOpenVirtual will have already been initialized
  1473         -  ** by a prior call to this same procedure.  Pass along the pOpenVirtual
  1474         -  ** pointer to pPrior, the next statement to our left.
  1475         -  */
  1476         -  if( p->ppOpenVirtual==0 ){
  1477         -    p->ppOpenVirtual = &pOpenVirtual;
  1478         -  }
  1479         -  pPrior->ppOpenVirtual = p->ppOpenVirtual;
  1480         -
  1481   1452     /* Create the destination temporary table if necessary
  1482   1453     */
  1483   1454     if( eDest==SRT_TempTable ){
  1484   1455       assert( p->pEList );
  1485         -    sqlite3VdbeAddOp(v, OP_OpenVirtual, iParm, 0);
  1486         -    assert( nAddr==0 );
  1487         -    aAddr[nAddr++] = sqlite3VdbeAddOp(v, OP_SetNumColumns, iParm, 0);
         1456  +    assert( nSetP2<sizeof(aSetP2)/sizeof(aSetP2[0]) );
         1457  +    aSetP2[nSetP2++] = sqlite3VdbeAddOp(v, OP_OpenVirtual, iParm, 0);
  1488   1458       eDest = SRT_Table;
  1489   1459     }
  1490   1460   
  1491   1461     /* Generate code for the left and right SELECT statements.
  1492   1462     */
         1463  +  pOrderBy = p->pOrderBy;
  1493   1464     switch( p->op ){
  1494   1465       case TK_ALL: {
  1495         -      if( p->pOrderBy==0 ){
         1466  +      if( pOrderBy==0 ){
  1496   1467           assert( !pPrior->pLimit );
  1497   1468           pPrior->pLimit = p->pLimit;
  1498   1469           pPrior->pOffset = p->pOffset;
  1499   1470           rc = sqlite3Select(pParse, pPrior, eDest, iParm, 0, 0, 0, aff);
  1500   1471           if( rc ){
  1501   1472             goto multi_select_end;
  1502   1473           }
................................................................................
  1516   1487       }
  1517   1488       case TK_EXCEPT:
  1518   1489       case TK_UNION: {
  1519   1490         int unionTab;    /* Cursor number of the temporary table holding result */
  1520   1491         int op = 0;      /* One of the SRT_ operations to apply to self */
  1521   1492         int priorOp;     /* The SRT_ operation to apply to prior selects */
  1522   1493         Expr *pLimit, *pOffset; /* Saved values of p->nLimit and p->nOffset */
  1523         -      ExprList *pOrderBy;     /* The ORDER BY clause for the right SELECT */
  1524   1494         int addr;
  1525   1495   
  1526   1496         priorOp = p->op==TK_ALL ? SRT_Table : SRT_Union;
  1527         -      if( eDest==priorOp && p->pOrderBy==0 && !p->pLimit && !p->pOffset ){
         1497  +      if( eDest==priorOp && pOrderBy==0 && !p->pLimit && !p->pOffset ){
  1528   1498           /* We can reuse a temporary table generated by a SELECT to our
  1529   1499           ** right.
  1530   1500           */
  1531   1501           unionTab = iParm;
  1532   1502         }else{
  1533   1503           /* We will need to create our own temporary table to hold the
  1534   1504           ** intermediate results.
  1535   1505           */
  1536   1506           unionTab = pParse->nTab++;
  1537         -        if( p->pOrderBy 
  1538         -        && matchOrderbyToColumn(pParse, p, p->pOrderBy, unionTab, 1) ){
         1507  +        if( pOrderBy && matchOrderbyToColumn(pParse, p, pOrderBy, unionTab,1) ){
  1539   1508             rc = 1;
  1540   1509             goto multi_select_end;
  1541   1510           }
  1542   1511           addr = sqlite3VdbeAddOp(v, OP_OpenVirtual, unionTab, 0);
  1543         -        if( p->op!=TK_ALL ){
  1544         -          rc = multiSelectOpenVirtualAddr(p, addr);
  1545         -          if( rc!=SQLITE_OK ){
  1546         -            goto multi_select_end;
  1547         -          }
         1512  +        if( priorOp==SRT_Table ){
         1513  +          assert( nSetP2<sizeof(aSetP2)/sizeof(aSetP2[0]) );
         1514  +          aSetP2[nSetP2++] = addr;
         1515  +        }else{
         1516  +          assert( p->addrOpenVirt[0] == -1 );
         1517  +          p->addrOpenVirt[0] = addr;
         1518  +          p->pRightmost->usesVirt = 1;
  1548   1519           }
  1549         -	assert( nAddr<sizeof(aAddr)/sizeof(aAddr[0]) );
  1550         -        aAddr[nAddr++] = sqlite3VdbeAddOp(v, OP_SetNumColumns, unionTab, 0);
         1520  +        createSortingIndex(pParse, p, pOrderBy);
  1551   1521           assert( p->pEList );
  1552   1522         }
  1553   1523   
  1554   1524         /* Code the SELECT statements to our left
  1555   1525         */
  1556   1526         assert( !pPrior->pOrderBy );
  1557   1527         rc = sqlite3Select(pParse, pPrior, priorOp, unionTab, 0, 0, 0, aff);
................................................................................
  1563   1533         */
  1564   1534         switch( p->op ){
  1565   1535            case TK_EXCEPT:  op = SRT_Except;   break;
  1566   1536            case TK_UNION:   op = SRT_Union;    break;
  1567   1537            case TK_ALL:     op = SRT_Table;    break;
  1568   1538         }
  1569   1539         p->pPrior = 0;
  1570         -      pOrderBy = p->pOrderBy;
  1571   1540         p->pOrderBy = 0;
  1572   1541         pLimit = p->pLimit;
  1573   1542         p->pLimit = 0;
  1574   1543         pOffset = p->pOffset;
  1575   1544         p->pOffset = 0;
  1576   1545         rc = sqlite3Select(pParse, p, op, unionTab, 0, 0, 0, aff);
  1577   1546         p->pPrior = pPrior;
................................................................................
  1597   1566           }
  1598   1567           iBreak = sqlite3VdbeMakeLabel(v);
  1599   1568           iCont = sqlite3VdbeMakeLabel(v);
  1600   1569           sqlite3VdbeAddOp(v, OP_Rewind, unionTab, iBreak);
  1601   1570           computeLimitRegisters(pParse, p);
  1602   1571           iStart = sqlite3VdbeCurrentAddr(v);
  1603   1572           rc = selectInnerLoop(pParse, p, p->pEList, unionTab, p->pEList->nExpr,
  1604         -                             p->pOrderBy, -1, eDest, iParm, 
         1573  +                             pOrderBy, -1, eDest, iParm, 
  1605   1574                                iCont, iBreak, 0);
  1606   1575           if( rc ){
  1607   1576             rc = 1;
  1608   1577             goto multi_select_end;
  1609   1578           }
  1610   1579           sqlite3VdbeResolveLabel(v, iCont);
  1611   1580           sqlite3VdbeAddOp(v, OP_Next, unionTab, iStart);
................................................................................
  1622   1591   
  1623   1592         /* INTERSECT is different from the others since it requires
  1624   1593         ** two temporary tables.  Hence it has its own case.  Begin
  1625   1594         ** by allocating the tables we will need.
  1626   1595         */
  1627   1596         tab1 = pParse->nTab++;
  1628   1597         tab2 = pParse->nTab++;
  1629         -      if( p->pOrderBy && matchOrderbyToColumn(pParse,p,p->pOrderBy,tab1,1) ){
         1598  +      if( pOrderBy && matchOrderbyToColumn(pParse,p,pOrderBy,tab1,1) ){
  1630   1599           rc = 1;
  1631   1600           goto multi_select_end;
  1632   1601         }
         1602  +      createSortingIndex(pParse, p, pOrderBy);
  1633   1603   
  1634   1604         addr = sqlite3VdbeAddOp(v, OP_OpenVirtual, tab1, 0);
  1635         -      rc = multiSelectOpenVirtualAddr(p, addr);
  1636         -      if( rc!=SQLITE_OK ){
  1637         -        goto multi_select_end;
  1638         -      }
  1639         -      assert( nAddr<sizeof(aAddr)/sizeof(aAddr[0]) );
  1640         -      aAddr[nAddr++] = sqlite3VdbeAddOp(v, OP_SetNumColumns, tab1, 0);
         1605  +      assert( p->addrOpenVirt[0] == -1 );
         1606  +      p->addrOpenVirt[0] = addr;
         1607  +      p->pRightmost->usesVirt = 1;
  1641   1608         assert( p->pEList );
  1642   1609   
  1643   1610         /* Code the SELECTs to our left into temporary table "tab1".
  1644   1611         */
  1645   1612         rc = sqlite3Select(pParse, pPrior, SRT_Union, tab1, 0, 0, 0, aff);
  1646   1613         if( rc ){
  1647   1614           goto multi_select_end;
  1648   1615         }
  1649   1616   
  1650   1617         /* Code the current SELECT into temporary table "tab2"
  1651   1618         */
  1652   1619         addr = sqlite3VdbeAddOp(v, OP_OpenVirtual, tab2, 0);
  1653         -      rc = multiSelectOpenVirtualAddr(p, addr);
  1654         -      if( rc!=SQLITE_OK ){
  1655         -        goto multi_select_end;
  1656         -      }
  1657         -      assert( nAddr<sizeof(aAddr)/sizeof(aAddr[0]) );
  1658         -      aAddr[nAddr++] = sqlite3VdbeAddOp(v, OP_SetNumColumns, tab2, 0);
         1620  +      assert( p->addrOpenVirt[1] == -1 );
         1621  +      p->addrOpenVirt[1] = addr;
  1659   1622         p->pPrior = 0;
  1660   1623         pLimit = p->pLimit;
  1661   1624         p->pLimit = 0;
  1662   1625         pOffset = p->pOffset;
  1663   1626         p->pOffset = 0;
  1664   1627         rc = sqlite3Select(pParse, p, SRT_Union, tab2, 0, 0, 0, aff);
  1665   1628         p->pPrior = pPrior;
................................................................................
  1680   1643         iBreak = sqlite3VdbeMakeLabel(v);
  1681   1644         iCont = sqlite3VdbeMakeLabel(v);
  1682   1645         sqlite3VdbeAddOp(v, OP_Rewind, tab1, iBreak);
  1683   1646         computeLimitRegisters(pParse, p);
  1684   1647         iStart = sqlite3VdbeAddOp(v, OP_RowKey, tab1, 0);
  1685   1648         sqlite3VdbeAddOp(v, OP_NotFound, tab2, iCont);
  1686   1649         rc = selectInnerLoop(pParse, p, p->pEList, tab1, p->pEList->nExpr,
  1687         -                             p->pOrderBy, -1, eDest, iParm, 
         1650  +                             pOrderBy, -1, eDest, iParm, 
  1688   1651                                iCont, iBreak, 0);
  1689   1652         if( rc ){
  1690   1653           rc = 1;
  1691   1654           goto multi_select_end;
  1692   1655         }
  1693   1656         sqlite3VdbeResolveLabel(v, iCont);
  1694   1657         sqlite3VdbeAddOp(v, OP_Next, tab1, iStart);
................................................................................
  1709   1672       rc = 1;
  1710   1673       goto multi_select_end;
  1711   1674     }
  1712   1675   
  1713   1676     /* Set the number of columns in temporary tables
  1714   1677     */
  1715   1678     nCol = p->pEList->nExpr;
  1716         -  while( nAddr>0 ){
  1717         -    nAddr--;
  1718         -    sqlite3VdbeChangeP2(v, aAddr[nAddr], nCol);
         1679  +  while( nSetP2 ){
         1680  +    sqlite3VdbeChangeP2(v, aSetP2[--nSetP2], nCol);
  1719   1681     }
  1720   1682   
  1721   1683     /* Compute collating sequences used by either the ORDER BY clause or
  1722   1684     ** by any temporary tables needed to implement the compound select.
  1723   1685     ** Attach the KeyInfo structure to all temporary tables.  Invoke the
  1724   1686     ** ORDER BY processing if there is an ORDER BY clause.
  1725   1687     **
  1726   1688     ** This section is run by the right-most SELECT statement only.
  1727   1689     ** SELECT statements to the left always skip this part.  The right-most
  1728   1690     ** SELECT might also skip this part if it has no ORDER BY clause and
  1729   1691     ** no temp tables are required.
  1730   1692     */
  1731         -  if( p->pOrderBy || (pOpenVirtual && pOpenVirtual->nId>0) ){
         1693  +  if( pOrderBy || p->usesVirt ){
  1732   1694       int i;                        /* Loop counter */
  1733   1695       KeyInfo *pKeyInfo;            /* Collating sequence for the result set */
         1696  +    Select *pLoop;                /* For looping through SELECT statements */
         1697  +    CollSeq **apColl;
         1698  +    CollSeq **aCopy;
  1734   1699   
  1735         -    assert( p->ppOpenVirtual == &pOpenVirtual );
  1736         -    pKeyInfo = sqliteMalloc(sizeof(*pKeyInfo)+nCol*sizeof(CollSeq*));
         1700  +    assert( p->pRightmost==p );
         1701  +    pKeyInfo = sqliteMalloc(sizeof(*pKeyInfo)+nCol*2*sizeof(CollSeq*));
  1737   1702       if( !pKeyInfo ){
  1738   1703         rc = SQLITE_NOMEM;
  1739   1704         goto multi_select_end;
  1740   1705       }
  1741   1706   
  1742   1707       pKeyInfo->enc = pParse->db->enc;
  1743   1708       pKeyInfo->nField = nCol;
  1744   1709   
  1745         -    for(i=0; i<nCol; i++){
  1746         -      pKeyInfo->aColl[i] = multiSelectCollSeq(pParse, p, i);
  1747         -      if( !pKeyInfo->aColl[i] ){
  1748         -        pKeyInfo->aColl[i] = pParse->db->pDfltColl;
         1710  +    for(i=0, apColl=pKeyInfo->aColl; i<nCol; i++, apColl++){
         1711  +      *apColl = multiSelectCollSeq(pParse, p, i);
         1712  +      if( 0==*apColl ){
         1713  +        *apColl = pParse->db->pDfltColl;
         1714  +      }
         1715  +    }
         1716  +
         1717  +    for(pLoop=p; pLoop; pLoop=pLoop->pPrior){
         1718  +      for(i=0; i<2; i++){
         1719  +        int addr = pLoop->addrOpenVirt[i];
         1720  +        if( addr<0 ){
         1721  +          /* If [0] is unused then [1] is also unused.  So we can
         1722  +          ** always safely abort as soon as the first unused slot is found */
         1723  +          assert( pLoop->addrOpenVirt[1]<0 );
         1724  +          break;
         1725  +        }
         1726  +        sqlite3VdbeChangeP2(v, addr, nCol);
         1727  +        sqlite3VdbeChangeP3(v, addr, (char*)pKeyInfo, P3_KEYINFO);
  1749   1728         }
  1750   1729       }
  1751   1730   
  1752         -    for(i=0; pOpenVirtual && i<pOpenVirtual->nId; i++){
  1753         -      int p3type = (i==0?P3_KEYINFO_HANDOFF:P3_KEYINFO);
  1754         -      int addr = pOpenVirtual->a[i].idx;
  1755         -      sqlite3VdbeChangeP3(v, addr, (char *)pKeyInfo, p3type);
  1756         -    }
         1731  +    if( pOrderBy ){
         1732  +      struct ExprList_item *pOTerm = pOrderBy->a;
         1733  +      int nExpr = pOrderBy->nExpr;
         1734  +      int addr;
  1757   1735   
  1758         -    if( p->pOrderBy ){
  1759         -      struct ExprList_item *pOrderByTerm = p->pOrderBy->a;
  1760         -      for(i=0; i<p->pOrderBy->nExpr; i++, pOrderByTerm++){
  1761         -        Expr *pExpr = pOrderByTerm->pExpr;
  1762         -        char *zName = pOrderByTerm->zName;
         1736  +      aCopy = (CollSeq**)&pKeyInfo[1];
         1737  +      memcpy(aCopy, pKeyInfo->aColl, nCol*sizeof(CollSeq*));
         1738  +      apColl = pKeyInfo->aColl;
         1739  +      for(i=0; i<pOrderBy->nExpr; i++, pOTerm++, apColl++){
         1740  +        Expr *pExpr = pOTerm->pExpr;
         1741  +        char *zName = pOTerm->zName;
  1763   1742           assert( pExpr->op==TK_COLUMN && pExpr->iColumn<nCol );
  1764         -        /* assert( !pExpr->pColl ); */
  1765   1743           if( zName ){
  1766         -          pExpr->pColl = sqlite3LocateCollSeq(pParse, zName, -1);
         1744  +          *apColl = sqlite3LocateCollSeq(pParse, zName, -1);
  1767   1745           }else{
  1768         -          pExpr->pColl = pKeyInfo->aColl[pExpr->iColumn];
         1746  +          *apColl = aCopy[pExpr->iColumn];
  1769   1747           }
  1770   1748         }
         1749  +      assert( p->pRightmost==p );
         1750  +      assert( p->addrOpenVirt[2]>=0 );
         1751  +      addr = p->addrOpenVirt[2];
         1752  +      sqlite3VdbeChangeP2(v, addr, p->pEList->nExpr+1);
         1753  +      sqlite3VdbeChangeP3(v, addr, (char*)pKeyInfo, P3_KEYINFO);
  1771   1754         generateSortTail(pParse, p, v, p->pEList->nExpr, eDest, iParm);
  1772   1755       }
  1773   1756   
  1774         -    if( !pOpenVirtual ){
  1775         -      /* This happens for UNION ALL ... ORDER BY */
  1776         -      sqliteFree(pKeyInfo);
  1777         -    }
         1757  +    sqliteFree(pKeyInfo);
  1778   1758     }
  1779   1759   
  1780   1760   multi_select_end:
  1781         -  if( pOpenVirtual ){
  1782         -    sqlite3IdListDelete(pOpenVirtual);
  1783         -  }
  1784         -  p->ppOpenVirtual = 0;
  1785   1761     return rc;
  1786   1762   }
  1787   1763   #endif /* SQLITE_OMIT_COMPOUND_SELECT */
  1788   1764   
  1789   1765   #ifndef SQLITE_OMIT_VIEW
  1790   1766   /*
  1791   1767   ** Scan through the expression pExpr.  Replace every reference to
................................................................................
  2513   2489     if( sqlite3_malloc_failed || pParse->nErr || p==0 ) return 1;
  2514   2490     if( sqlite3AuthCheck(pParse, SQLITE_SELECT, 0, 0, 0) ) return 1;
  2515   2491   
  2516   2492   #ifndef SQLITE_OMIT_COMPOUND_SELECT
  2517   2493     /* If there is are a sequence of queries, do the earlier ones first.
  2518   2494     */
  2519   2495     if( p->pPrior ){
         2496  +    if( p->pRightmost==0 ){
         2497  +      Select *pLoop;
         2498  +      for(pLoop=p; pLoop; pLoop=pLoop->pPrior){
         2499  +        pLoop->pRightmost = p;
         2500  +      }
         2501  +    }
  2520   2502       return multiSelect(pParse, p, eDest, iParm, aff);
  2521   2503     }
  2522   2504   #endif
  2523   2505   
  2524   2506     saveAggregateInfo(pParse, &sAggInfo);
  2525   2507     pOrderBy = p->pOrderBy;
  2526   2508     if( eDest==SRT_Union || eDest==SRT_Except || eDest==SRT_Discard ){
................................................................................
  2635   2617   #endif
  2636   2618   
  2637   2619     /* If there is an ORDER BY clause, resolve any collation sequences
  2638   2620     ** names that have been explicitly specified.
  2639   2621     */
  2640   2622     if( pOrderBy ){
  2641   2623       struct ExprList_item *pTerm;
         2624  +    KeyInfo *pKeyInfo;
         2625  +    int addr;
  2642   2626       for(i=0, pTerm=pOrderBy->a; i<pOrderBy->nExpr; i++, pTerm++){
  2643   2627         if( pTerm->zName ){
  2644   2628           pTerm->pExpr->pColl = sqlite3LocateCollSeq(pParse, pTerm->zName, -1);
  2645   2629         }
  2646   2630       }
  2647   2631       if( pParse->nErr ){
  2648   2632         goto select_end;
  2649   2633       }
         2634  +    pKeyInfo = keyInfoFromExprList(pParse, pOrderBy);
         2635  +    pOrderBy->iTab = pParse->nTab++;
         2636  +    addr = sqlite3VdbeOp3(v, OP_OpenVirtual, pOrderBy->iTab, pOrderBy->nExpr+1, 
         2637  +                        (char*)pKeyInfo, P3_KEYINFO_HANDOFF);
         2638  +    p->addrOpenVirt[2] = addr;
  2650   2639     }
  2651   2640   
  2652   2641     /* Set the limiter.
  2653   2642     */
  2654   2643     computeLimitRegisters(pParse, p);
  2655   2644   
  2656   2645     /* If the output is destined for a temporary table, open that table.
  2657   2646     */
  2658   2647     if( eDest==SRT_TempTable ){
  2659         -    sqlite3VdbeAddOp(v, OP_OpenVirtual, iParm, 0);
  2660         -    sqlite3VdbeAddOp(v, OP_SetNumColumns, iParm, pEList->nExpr);
         2648  +    sqlite3VdbeAddOp(v, OP_OpenVirtual, iParm, pEList->nExpr);
  2661   2649     }
  2662   2650   
  2663   2651     /* Do an analysis of aggregate expressions.
  2664   2652     */
  2665   2653     if( isAgg || pGroupBy ){
  2666   2654       NameContext sNC;
  2667   2655       memset(&sNC, 0, sizeof(sNC));
................................................................................
  2716   2704       sqlite3VdbeAddOp(v, eDest==SRT_Mem ? OP_Null : OP_Integer, 0, 0);
  2717   2705       sqlite3VdbeAddOp(v, OP_MemStore, iParm, 1);
  2718   2706     }
  2719   2707   
  2720   2708     /* Open a virtual index to use for the distinct set.
  2721   2709     */
  2722   2710     if( isDistinct ){
         2711  +    KeyInfo *pKeyInfo;
  2723   2712       distinct = pParse->nTab++;
  2724         -    openVirtualIndex(pParse, p, distinct);
         2713  +    pKeyInfo = keyInfoFromExprList(pParse, p->pEList);
         2714  +    sqlite3VdbeOp3(v, OP_OpenVirtual, distinct, 0, 
         2715  +                        (char*)pKeyInfo, P3_KEYINFO_HANDOFF);
  2725   2716     }else{
  2726   2717       distinct = -1;
  2727   2718     }
  2728   2719   
  2729   2720     /* Begin the database scan
  2730   2721     */
  2731   2722     pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere,

Changes to src/sqliteInt.h.

     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** Internal interface definitions for SQLite.
    13     13   **
    14         -** @(#) $Id: sqliteInt.h,v 1.406 2005/08/30 00:54:03 drh Exp $
           14  +** @(#) $Id: sqliteInt.h,v 1.407 2005/09/01 03:07:44 drh Exp $
    15     15   */
    16     16   #ifndef _SQLITEINT_H_
    17     17   #define _SQLITEINT_H_
    18     18   
    19     19   /*
    20     20   ** These #defines should enable >2GB file support on Posix if the
    21     21   ** underlying operating system supports it.  If the OS lacks
................................................................................
   882    882   ** list of "ID = expr" items in an UPDATE.  A list of expressions can
   883    883   ** also be used as the argument to a function, in which case the a.zName
   884    884   ** field is not used.
   885    885   */
   886    886   struct ExprList {
   887    887     int nExpr;             /* Number of expressions on the list */
   888    888     int nAlloc;            /* Number of entries allocated below */
          889  +  int iTab;              /* VDBE Cursor associated with this ExprList */
   889    890     struct ExprList_item {
   890    891       Expr *pExpr;           /* The list of expressions */
   891    892       char *zName;           /* Token associated with this expression */
   892    893       u8 sortOrder;          /* 1 for DESC or 0 for ASC */
   893    894       u8 isAgg;              /* True if this is an aggregate like count(*) */
   894    895       u8 done;               /* A flag to indicate when processing is finished */
   895         -    u8 orderByDup[2];      /* Corresponding term in OrderBy/GroupBy clause */
   896    896     } *a;                  /* One entry for each expression */
   897    897   };
   898    898   
   899    899   /*
   900    900   ** An instance of this structure can hold a simple list of identifiers,
   901    901   ** such as the list "a,b,c" in the following statements:
   902    902   **
................................................................................
  1041   1041   ** needed to generate code for a single SELECT statement.
  1042   1042   **
  1043   1043   ** nLimit is set to -1 if there is no LIMIT clause.  nOffset is set to 0.
  1044   1044   ** If there is a LIMIT clause, the parser sets nLimit to the value of the
  1045   1045   ** limit and nOffset to the value of the offset (or 0 if there is not
  1046   1046   ** offset).  But later on, nLimit and nOffset become the memory locations
  1047   1047   ** in the VDBE that record the limit and offset counters.
         1048  +**
         1049  +** addrOpenVirt[] entries contain the address of OP_OpenVirtual opcodes.
         1050  +** These addresses must be stored so that we can go back and fill in
         1051  +** the P3_KEYINFO and P2 parameters later.  Neither the KeyInfo nor
         1052  +** the number of columns in P2 can be computed at the same time
         1053  +** as the OP_OpenVirtual instruction is coded because not
         1054  +** enough information about the compound query is known at that point.
         1055  +** The KeyInfo for addrOpenVirt[0] and [1] contains collating sequences
         1056  +** for the result set.  The KeyInfo for addrOpenVirt[2] contains collating
         1057  +** sequences for the ORDER BY clause.
  1048   1058   */
  1049   1059   struct Select {
  1050   1060     ExprList *pEList;      /* The fields of the result */
  1051   1061     u8 op;                 /* One of: TK_UNION TK_ALL TK_INTERSECT TK_EXCEPT */
  1052   1062     u8 isDistinct;         /* True if the DISTINCT keyword is present */
         1063  +  u8 isResolved;         /* True once sqlite3SelectResolve() has run. */
         1064  +  u8 isAgg;              /* True if this is an aggregate query */
         1065  +  u8 usesVirt;           /* True if uses an OpenVirtual opcode */
  1053   1066     SrcList *pSrc;         /* The FROM clause */
  1054   1067     Expr *pWhere;          /* The WHERE clause */
  1055   1068     ExprList *pGroupBy;    /* The GROUP BY clause */
  1056   1069     Expr *pHaving;         /* The HAVING clause */
  1057   1070     ExprList *pOrderBy;    /* The ORDER BY clause */
  1058   1071     Select *pPrior;        /* Prior select in a compound select statement */
         1072  +  Select *pRightmost;    /* Right-most select in a compound select statement */
  1059   1073     Expr *pLimit;          /* LIMIT expression. NULL means not used. */
  1060   1074     Expr *pOffset;         /* OFFSET expression. NULL means not used. */
  1061   1075     int iLimit, iOffset;   /* Memory registers holding LIMIT & OFFSET counters */
  1062         -  IdList **ppOpenVirtual;/* OP_OpenVirtual addresses used by multi-selects */
  1063         -  u8 isResolved;         /* True once sqlite3SelectResolve() has run. */
  1064         -  u8 isAgg;              /* True if this is an aggregate query */
         1076  +  int addrOpenVirt[3];   /* OP_OpenVirtual opcodes related to this select */
  1065   1077   };
  1066   1078   
  1067   1079   /*
  1068   1080   ** The results of a select can be distributed in several ways.
  1069   1081   */
  1070   1082   #define SRT_Callback     1  /* Invoke a callback with each row of result */
  1071   1083   #define SRT_Mem          2  /* Store result in a memory cell */

Changes to src/vdbe.c.

    39     39   **
    40     40   ** Various scripts scan this source file in order to generate HTML
    41     41   ** documentation, headers files, or other derived files.  The formatting
    42     42   ** of the code in this file is, therefore, important.  See other comments
    43     43   ** in this file for details.  If in doubt, do not deviate from existing
    44     44   ** commenting and indentation practices when changing or adding code.
    45     45   **
    46         -** $Id: vdbe.c,v 1.478 2005/07/28 20:51:19 drh Exp $
           46  +** $Id: vdbe.c,v 1.479 2005/09/01 03:07:44 drh Exp $
    47     47   */
    48     48   #include "sqliteInt.h"
    49     49   #include "os.h"
    50     50   #include <ctype.h>
    51     51   #include "vdbeInt.h"
    52     52   
    53     53   /*
................................................................................
   201    201       N--;
   202    202       Release(pTos);
   203    203       pTos--;
   204    204     }
   205    205     *ppTos = pTos;
   206    206   }
   207    207   
   208         -/*
   209         -** The parameters are pointers to the head of two sorted lists
   210         -** of Sorter structures.  Merge these two lists together and return
   211         -** a single sorted list.  This routine forms the core of the merge-sort
   212         -** algorithm.
   213         -**
   214         -** In the case of a tie, left sorts in front of right.
   215         -*/
   216         -static Sorter *Merge(Sorter *pLeft, Sorter *pRight, KeyInfo *pKeyInfo){
   217         -  Sorter sHead;
   218         -  Sorter *pTail;
   219         -  pTail = &sHead;
   220         -  pTail->pNext = 0;
   221         -  while( pLeft && pRight ){
   222         -    int c = sqlite3VdbeRecordCompare(pKeyInfo, pLeft->nKey, pLeft->zKey,
   223         -                                     pRight->nKey, pRight->zKey);
   224         -    if( c<=0 ){
   225         -      pTail->pNext = pLeft;
   226         -      pLeft = pLeft->pNext;
   227         -    }else{
   228         -      pTail->pNext = pRight;
   229         -      pRight = pRight->pNext;
   230         -    }
   231         -    pTail = pTail->pNext;
   232         -  }
   233         -  if( pLeft ){
   234         -    pTail->pNext = pLeft;
   235         -  }else if( pRight ){
   236         -    pTail->pNext = pRight;
   237         -  }
   238         -  return sHead.pNext;
   239         -}
   240         -
   241    208   /*
   242    209   ** Allocate cursor number iCur.  Return a pointer to it.  Return NULL
   243    210   ** if we run out of memory.
   244    211   */
   245    212   static Cursor *allocateCursor(Vdbe *p, int iCur){
   246    213     Cursor *pCx;
   247    214     assert( iCur<p->nCursor );
................................................................................
   631    598     p->returnDepth--;
   632    599     pc = p->returnStack[p->returnDepth] - 1;
   633    600     break;
   634    601   }
   635    602   
   636    603   /* Opcode:  Halt P1 P2 P3
   637    604   **
   638         -** Exit immediately.  All open cursors, Lists, Sorts, etc are closed
          605  +** Exit immediately.  All open cursors, Fifos, etc are closed
   639    606   ** automatically.
   640    607   **
   641    608   ** P1 is the result code returned by sqlite3_exec(), sqlite3_reset(),
   642    609   ** or sqlite3_finalize().  For a normal halt, this should be SQLITE_OK (0).
   643    610   ** For errors, it can be some other value.  If P1!=0 then P2 will determine
   644    611   ** whether or not to rollback the current transaction.  Do not rollback
   645    612   ** if P2==OE_Fail. Do the rollback if P2==OE_Rollback.  If P2==OE_Abort,
................................................................................
  2599   2566       default: {
  2600   2567         goto abort_due_to_error;
  2601   2568       }
  2602   2569     }
  2603   2570     break;
  2604   2571   }
  2605   2572   
  2606         -/* Opcode: OpenVirtual P1 * P3
         2573  +/* Opcode: OpenVirtual P1 P2 P3
  2607   2574   **
  2608         -** Open a new cursor to a transient or virtual table.
         2575  +** Open a new cursor P1 to a transient or virtual table.
  2609   2576   ** The cursor is always opened read/write even if 
  2610   2577   ** the main database is read-only.  The transient or virtual
  2611   2578   ** table is deleted automatically when the cursor is closed.
  2612   2579   **
         2580  +** P2 is the number of columns in the virtual table.
  2613   2581   ** The cursor points to a BTree table if P3==0 and to a BTree index
  2614   2582   ** if P3 is not 0.  If P3 is not NULL, it points to a KeyInfo structure
  2615   2583   ** that defines the format of keys in the index.
  2616   2584   */
  2617   2585   case OP_OpenVirtual: {       /* no-push */
  2618   2586     int i = pOp->p1;
  2619   2587     Cursor *pCx;
................................................................................
  2646   2614         pCx->isTable = 0;
  2647   2615       }else{
  2648   2616         rc = sqlite3BtreeCursor(pCx->pBt, MASTER_ROOT, 1, 0, 0, &pCx->pCursor);
  2649   2617         pCx->isTable = 1;
  2650   2618         pCx->pIncrKey = &pCx->bogusIncrKey;
  2651   2619       }
  2652   2620     }
         2621  +  pCx->nField = pOp->p2;
  2653   2622     pCx->isIndex = !pCx->isTable;
  2654   2623     break;
  2655   2624   }
  2656   2625   
  2657   2626   #ifndef SQLITE_OMIT_TRIGGER
  2658   2627   /* Opcode: OpenPseudo P1 * *
  2659   2628   **
................................................................................
  3460   3429       }
  3461   3430     }else{
  3462   3431       pC->nullRow = 0;
  3463   3432     }
  3464   3433     break;
  3465   3434   }
  3466   3435   
         3436  +
         3437  +/* Opcode: Sort P1 P2 *
         3438  +**
         3439  +** This opcode does exactly the same thing as OP_Rewind except that
         3440  +** it increments an undocumented global variable used for testing.
         3441  +**
         3442  +** Sorting is accomplished by writing records into a sorting index,
         3443  +** then rewinding that index and playing it back from beginning to
         3444  +** end.  We use the OP_Sort opcode instead of OP_Rewind to do the
         3445  +** rewinding so that the global variable will be incremented and
         3446  +** regression tests can determine whether or not the optimizer is
         3447  +** correctly optimizing out sorts.
         3448  +*/
         3449  +case OP_Sort: {        /* no-push */
         3450  +  sqlite3_sort_count++;
         3451  +  /* Fall through into OP_Rewind */
         3452  +}
  3467   3453   /* Opcode: Rewind P1 P2 *
  3468   3454   **
  3469   3455   ** The next use of the Rowid or Column or Next instruction for P1 
  3470   3456   ** will refer to the first entry in the database table or index.
  3471   3457   ** If the table or index is empty and P2>0, then jump immediately to P2.
  3472   3458   ** If P2 is 0 or if the table or index is not empty, fall through
  3473   3459   ** to the following instruction.
................................................................................
  4087   4073     p->nChange = pContext->nChange;
  4088   4074     sqlite3VdbeFifoClear(&p->sFifo);
  4089   4075     p->sFifo = pContext->sFifo;
  4090   4076     break;
  4091   4077   }
  4092   4078   #endif /* #ifndef SQLITE_OMIT_TRIGGER */
  4093   4079   
  4094         -/* Opcode: SortInsert * * *
  4095         -**
  4096         -** The TOS is the key and the NOS is the data.  Pop both from the stack
  4097         -** and put them on the sorter.  The key and data should have been
  4098         -** made using the MakeRecord opcode.
  4099         -*/
  4100         -case OP_SortInsert: {        /* no-push */
  4101         -  Mem *pNos = &pTos[-1];
  4102         -  Sorter *pSorter;
  4103         -  assert( pNos>=p->aStack );
  4104         -  if( Dynamicify(pTos, db->enc) ) goto no_mem;
  4105         -  pSorter = sqliteMallocRaw( sizeof(Sorter) );
  4106         -  if( pSorter==0 ) goto no_mem;
  4107         -  pSorter->pNext = 0;
  4108         -  if( p->pSortTail ){
  4109         -    p->pSortTail->pNext = pSorter;
  4110         -  }else{
  4111         -    p->pSort = pSorter;
  4112         -  }
  4113         -  p->pSortTail = pSorter;
  4114         -  assert( pTos->flags & MEM_Dyn );
  4115         -  pSorter->nKey = pTos->n;
  4116         -  pSorter->zKey = pTos->z;
  4117         -  pSorter->data.flags = MEM_Null;
  4118         -  rc = sqlite3VdbeMemMove(&pSorter->data, pNos);
  4119         -  pTos -= 2;
  4120         -  break;
  4121         -}
  4122         -
  4123         -/* Opcode: Sort * * P3
  4124         -**
  4125         -** Sort all elements on the sorter.  The algorithm is a
  4126         -** mergesort.  The P3 argument is a pointer to a KeyInfo structure
  4127         -** that describes the keys to be sorted.
  4128         -*/
  4129         -case OP_Sort: {        /* no-push */
  4130         -  int i;
  4131         -  KeyInfo *pKeyInfo = (KeyInfo*)pOp->p3;
  4132         -  Sorter *pElem;
  4133         -  Sorter *apSorter[NSORT];
  4134         -  sqlite3_sort_count++;
  4135         -  pKeyInfo->enc = p->db->enc;
  4136         -  for(i=0; i<NSORT; i++){
  4137         -    apSorter[i] = 0;
  4138         -  }
  4139         -  while( p->pSort ){
  4140         -    pElem = p->pSort;
  4141         -    p->pSort = pElem->pNext;
  4142         -    pElem->pNext = 0;
  4143         -    for(i=0; i<NSORT-1; i++){
  4144         -      if( apSorter[i]==0 ){
  4145         -        apSorter[i] = pElem;
  4146         -        break;
  4147         -      }else{
  4148         -        pElem = Merge(apSorter[i], pElem, pKeyInfo);
  4149         -        apSorter[i] = 0;
  4150         -      }
  4151         -    }
  4152         -    if( i>=NSORT-1 ){
  4153         -      apSorter[NSORT-1] = Merge(apSorter[NSORT-1],pElem, pKeyInfo);
  4154         -    }
  4155         -  }
  4156         -  pElem = 0;
  4157         -  for(i=0; i<NSORT; i++){
  4158         -    pElem = Merge(apSorter[i], pElem, pKeyInfo);
  4159         -  }
  4160         -  p->pSort = pElem;
  4161         -  break;
  4162         -}
  4163         -
  4164         -/* Opcode: SortNext * P2 *
  4165         -**
  4166         -** Push the data for the topmost element in the sorter onto the
  4167         -** stack, then remove the element from the sorter.  If the sorter
  4168         -** is empty, push nothing on the stack and instead jump immediately 
  4169         -** to instruction P2.
  4170         -*/
  4171         -case OP_SortNext: {
  4172         -  Sorter *pSorter = p->pSort;
  4173         -  CHECK_FOR_INTERRUPT;
  4174         -  if( pSorter!=0 ){
  4175         -    p->pSort = pSorter->pNext;
  4176         -    pTos++;
  4177         -    pTos->flags = MEM_Null;
  4178         -    rc = sqlite3VdbeMemMove(pTos, &pSorter->data);
  4179         -    sqliteFree(pSorter->zKey);
  4180         -    sqliteFree(pSorter);
  4181         -  }else{
  4182         -    pc = pOp->p2 - 1;
  4183         -  }
  4184         -  break;
  4185         -}
  4186         -
  4187         -/* Opcode: SortReset * * *
  4188         -**
  4189         -** Remove any elements that remain on the sorter.
  4190         -*/
  4191         -case OP_SortReset: {        /* no-push */
  4192         -  sqlite3VdbeSorterReset(p);
  4193         -  break;
  4194         -}
  4195         -
  4196   4080   /* Opcode: MemStore P1 P2 *
  4197   4081   **
  4198   4082   ** Write the top of the stack into memory location P1.
  4199   4083   ** P1 should be a small integer since space is allocated
  4200   4084   ** for all memory locations between 0 and P1 inclusive.
  4201   4085   **
  4202   4086   ** After the data is stored in the memory location, the

Changes to src/vdbeInt.h.

   121    121     double r;           /* Real value */
   122    122     char *z;            /* String or BLOB value */
   123    123     void (*xDel)(void *);  /* If not null, call this function to delete Mem.z */
   124    124     char zShort[NBFS];  /* Space for short strings */
   125    125   };
   126    126   typedef struct Mem Mem;
   127    127   
   128         -/*
   129         -** A sorter builds a list of elements to be sorted.  Each element of
   130         -** the list is an instance of the following structure.
   131         -*/
   132         -typedef struct Sorter Sorter;
   133         -struct Sorter {
   134         -  int nKey;           /* Number of bytes in the key */
   135         -  char *zKey;         /* The key by which we will sort */
   136         -  Mem data;
   137         -  Sorter *pNext;      /* Next in the list */
   138         -};
   139         -
   140         -/* 
   141         -** Number of buckets used for merge-sort.  
   142         -*/
   143         -#define NSORT 30
   144         -
   145    128   /* One or more of the following flags are set to indicate the validOK
   146    129   ** representations of the value stored in the Mem struct.
   147    130   **
   148    131   ** If the MEM_Null flag is set, then the value is an SQL NULL value.
   149    132   ** No other flags may be set in this case.
   150    133   **
   151    134   ** If the MEM_Str flag is set then Mem.z points at a string representation.
................................................................................
   320    303     int *aLabel;        /* Space to hold the labels */
   321    304     Mem *aStack;        /* The operand stack, except string values */
   322    305     Mem *pTos;          /* Top entry in the operand stack */
   323    306     Mem **apArg;        /* Arguments to currently executing user function */
   324    307     Mem *aColName;      /* Column names to return */
   325    308     int nCursor;        /* Number of slots in apCsr[] */
   326    309     Cursor **apCsr;     /* One element of this array for each open cursor */
   327         -  Sorter *pSort;      /* A linked list of objects to be sorted */
   328         -  Sorter *pSortTail;  /* Last element on the pSort list */
   329    310     int nVar;           /* Number of entries in aVar[] */
   330    311     Mem *aVar;          /* Values for the OP_Variable opcode. */
   331    312     char **azVar;       /* Name of variables */
   332    313     int okVar;          /* True if azVar[] has been initialized */
   333    314     int magic;              /* Magic number for sanity checking */
   334    315     int nMem;               /* Number of memory locations currently allocated */
   335    316     Mem *aMem;              /* The memory locations */
................................................................................
   369    350   #define VDBE_MAGIC_HALT     0x519c2973    /* VDBE has completed execution */
   370    351   #define VDBE_MAGIC_DEAD     0xb606c3c8    /* The VDBE has been deallocated */
   371    352   
   372    353   /*
   373    354   ** Function prototypes
   374    355   */
   375    356   void sqlite3VdbeFreeCursor(Cursor*);
   376         -void sqlite3VdbeSorterReset(Vdbe*);
   377    357   int sqlite3VdbeAggReset(sqlite3*, Agg *, KeyInfo *);
   378    358   void sqliteVdbePopStack(Vdbe*,int);
   379    359   int sqlite3VdbeCursorMoveto(Cursor*);
   380    360   #if defined(SQLITE_DEBUG) || defined(VDBE_PROFILE)
   381    361   void sqlite3VdbePrintOp(FILE*, int, Op*);
   382    362   #endif
   383    363   #ifdef SQLITE_DEBUG

Changes to src/vdbeaux.c.

   759    759         p->aOp[i].cnt = 0;
   760    760         p->aOp[i].cycles = 0;
   761    761       }
   762    762     }
   763    763   #endif
   764    764   }
   765    765   
   766         -
   767         -/*
   768         -** Remove any elements that remain on the sorter for the VDBE given.
   769         -*/
   770         -void sqlite3VdbeSorterReset(Vdbe *p){
   771         -  while( p->pSort ){
   772         -    Sorter *pSorter = p->pSort;
   773         -    p->pSort = pSorter->pNext;
   774         -    sqliteFree(pSorter->zKey);
   775         -    sqlite3VdbeMemRelease(&pSorter->data);
   776         -    sqliteFree(pSorter);
   777         -  }
   778         -  p->pSortTail = 0;
   779         -}
   780         -
   781    766   /*
   782    767   ** Free all resources allociated with AggElem pElem, an element of
   783    768   ** aggregate pAgg.
   784    769   */
   785    770   static void freeAggElem(AggElem *pElem, Agg *pAgg){
   786    771     int i;
   787    772     for(i=0; i<pAgg->nMem; i++){
................................................................................
   961    946     sqlite3VdbeFifoClear(&p->sFifo);
   962    947     if( p->contextStack ){
   963    948       for(i=0; i<p->contextStackTop; i++){
   964    949         sqlite3VdbeFifoClear(&p->contextStack[i].sFifo);
   965    950       }
   966    951       sqliteFree(p->contextStack);
   967    952     }
   968         -  sqlite3VdbeSorterReset(p);
   969    953     for(i=0; i<p->nAgg; i++){
   970    954       sqlite3VdbeAggReset(0, &p->apAgg[i], 0);
   971    955     }
   972    956     p->contextStack = 0;
   973    957     p->contextStackDepth = 0;
   974    958     p->contextStackTop = 0;
   975    959     sqliteFree(p->zErrMsg);

Changes to test/conflict.test.

     9      9   #
    10     10   #***********************************************************************
    11     11   # This file implements regression tests for SQLite library.
    12     12   #
    13     13   # This file implements tests for the conflict resolution extension
    14     14   # to SQLite.
    15     15   #
    16         -# $Id: conflict.test,v 1.24 2005/06/07 02:12:30 drh Exp $
           16  +# $Id: conflict.test,v 1.25 2005/09/01 03:07:45 drh Exp $
    17     17   
    18     18   set testdir [file dirname $argv0]
    19     19   source $testdir/tester.tcl
    20     20   
    21     21   # Create tables for the first group of tests.
    22     22   #
    23     23   do_test conflict-1.0 {
................................................................................
   277    277   #   t0     True if there is an error from $cmd
   278    278   #   t1     Content of "b" column of t1 assuming no error in $cmd
   279    279   #   t2     Content of "x" column of t3
   280    280   #   t3     Number of temporary files created
   281    281   #
   282    282   foreach {i conf1 cmd t0 t1 t2 t3} {
   283    283     1 {}       UPDATE                  1 {6 7 8 9}  1 1
   284         -  2 REPLACE  UPDATE                  0 {7 6 9}    1 0
   285         -  3 IGNORE   UPDATE                  0 {6 7 3 9}  1 0
          284  +  2 REPLACE  UPDATE                  0 {7 6 9}    1 1
          285  +  3 IGNORE   UPDATE                  0 {6 7 3 9}  1 1
   286    286     4 FAIL     UPDATE                  1 {6 7 3 4}  1 0
   287    287     5 ABORT    UPDATE                  1 {1 2 3 4}  1 1
   288    288     6 ROLLBACK UPDATE                  1 {1 2 3 4}  0 0
   289         -  7 REPLACE  {UPDATE OR IGNORE}      0 {6 7 3 9}  1 0
   290         -  8 IGNORE   {UPDATE OR REPLACE}     0 {7 6 9}    1 0
   291         -  9 FAIL     {UPDATE OR IGNORE}      0 {6 7 3 9}  1 0
   292         - 10 ABORT    {UPDATE OR REPLACE}     0 {7 6 9}    1 0
   293         - 11 ROLLBACK {UPDATE OR IGNORE}      0 {6 7 3 9}  1 0
   294         - 12 {}       {UPDATE OR IGNORE}      0 {6 7 3 9}  1 0
   295         - 13 {}       {UPDATE OR REPLACE}     0 {7 6 9}    1 0
          289  +  7 REPLACE  {UPDATE OR IGNORE}      0 {6 7 3 9}  1 1
          290  +  8 IGNORE   {UPDATE OR REPLACE}     0 {7 6 9}    1 1
          291  +  9 FAIL     {UPDATE OR IGNORE}      0 {6 7 3 9}  1 1
          292  + 10 ABORT    {UPDATE OR REPLACE}     0 {7 6 9}    1 1
          293  + 11 ROLLBACK {UPDATE OR IGNORE}      0 {6 7 3 9}  1 1
          294  + 12 {}       {UPDATE OR IGNORE}      0 {6 7 3 9}  1 1
          295  + 13 {}       {UPDATE OR REPLACE}     0 {7 6 9}    1 1
   296    296    14 {}       {UPDATE OR FAIL}        1 {6 7 3 4}  1 0
   297    297    15 {}       {UPDATE OR ABORT}       1 {1 2 3 4}  1 1
   298    298    16 {}       {UPDATE OR ROLLBACK}    1 {1 2 3 4}  0 0
   299    299   } {
   300    300     if {$t0} {set t1 {column a is not unique}}
   301    301     do_test conflict-6.$i {
   302    302       db close