/ Check-in [55e703ec]
Login

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

Overview
Comment:Reduce memory requirements for ORDER BY combined with LIMIT. Ticket #1586. (CVS 2887)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 55e703ecac6e03d7364c2d919ba18d7293d6b7f6
User & Date: drh 2006-01-08 05:02:55
Context
2006-01-08
05:26
Remove some cruft from the VDBE. Bring comments up to date. (CVS 2888) check-in: 41aef649 user: drh tags: trunk
05:02
Reduce memory requirements for ORDER BY combined with LIMIT. Ticket #1586. (CVS 2887) check-in: 55e703ec user: drh tags: trunk
2006-01-07
18:48
Invalidate all VDBE cursor row caches in between calls to sqlite3_step() since the emphemeral content that those caches point to might change if the statement is READ UNCOMMITTED. (CVS 2886) check-in: 0ae46131 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

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.286 2006/01/07 13:21:04 danielk1977 Exp $
           15  +** $Id: select.c,v 1.287 2006/01/08 05:02:55 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.
................................................................................
   347    347     sqliteFree(p);
   348    348   }
   349    349   
   350    350   /*
   351    351   ** Insert code into "v" that will push the record on the top of the
   352    352   ** stack into the sorter.
   353    353   */
   354         -static void pushOntoSorter(Parse *pParse, Vdbe *v, ExprList *pOrderBy){
          354  +static void pushOntoSorter(
          355  +  Parse *pParse,         /* Parser context */
          356  +  ExprList *pOrderBy,    /* The ORDER BY clause */
          357  +  Select *pSelect        /* The whole SELECT statement */
          358  +){
          359  +  Vdbe *v = pParse->pVdbe;
   355    360     sqlite3ExprCodeExprList(pParse, pOrderBy);
   356    361     sqlite3VdbeAddOp(v, OP_Sequence, pOrderBy->iECursor, 0);
   357    362     sqlite3VdbeAddOp(v, OP_Pull, pOrderBy->nExpr + 1, 0);
   358    363     sqlite3VdbeAddOp(v, OP_MakeRecord, pOrderBy->nExpr + 2, 0);
   359    364     sqlite3VdbeAddOp(v, OP_IdxInsert, pOrderBy->iECursor, 0);
          365  +  if( pSelect->iLimit>=0 ){
          366  +    int addr1;
          367  +    sqlite3VdbeAddOp(v, OP_MemIncr, pSelect->iLimit+1, 0);
          368  +    addr1 = sqlite3VdbeAddOp(v, OP_IfMemPos, pSelect->iLimit+1, 0);
          369  +    sqlite3VdbeAddOp(v, OP_Goto, 0, 0);
          370  +    sqlite3VdbeJumpHere(v, addr1);
          371  +    sqlite3VdbeAddOp(v, OP_Last, pOrderBy->iECursor, 0);
          372  +    sqlite3VdbeAddOp(v, OP_Delete, pOrderBy->iECursor, 0);
          373  +    sqlite3VdbeJumpHere(v, addr1+1);
          374  +    pSelect->iLimit = -1;
          375  +  }
   360    376   }
   361    377   
   362    378   /*
   363    379   ** Add code to implement the OFFSET
   364    380   */
   365    381   static void codeOffset(
   366    382     Vdbe *v,          /* Generate code into this VM */
................................................................................
   500    516   
   501    517       /* Store the result as data using a unique key.
   502    518       */
   503    519       case SRT_Table:
   504    520       case SRT_VirtualTab: {
   505    521         sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0);
   506    522         if( pOrderBy ){
   507         -        pushOntoSorter(pParse, v, pOrderBy);
          523  +        pushOntoSorter(pParse, pOrderBy, p);
   508    524         }else{
   509    525           sqlite3VdbeAddOp(v, OP_NewRowid, iParm, 0);
   510    526           sqlite3VdbeAddOp(v, OP_Pull, 1, 0);
   511    527           sqlite3VdbeAddOp(v, OP_Insert, iParm, 0);
   512    528         }
   513    529         break;
   514    530       }
................................................................................
   527    543         sqlite3VdbeAddOp(v, OP_Pop, 1, 0);
   528    544         addr2 = sqlite3VdbeAddOp(v, OP_Goto, 0, 0);
   529    545         if( pOrderBy ){
   530    546           /* At first glance you would think we could optimize out the
   531    547           ** ORDER BY in this case since the order of entries in the set
   532    548           ** does not matter.  But there might be a LIMIT clause, in which
   533    549           ** case the order does matter */
   534         -        pushOntoSorter(pParse, v, pOrderBy);
          550  +        pushOntoSorter(pParse, pOrderBy, p);
   535    551         }else{
   536    552           char aff = (iParm>>16)&0xFF;
   537    553           aff = sqlite3CompareAffinity(pEList->a[0].pExpr, aff);
   538    554           sqlite3VdbeOp3(v, OP_MakeRecord, 1, 0, &aff, 1);
   539    555           sqlite3VdbeAddOp(v, OP_IdxInsert, (iParm&0x0000FFFF), 0);
   540    556         }
   541    557         sqlite3VdbeJumpHere(v, addr2);
................................................................................
   554    570       /* If this is a scalar select that is part of an expression, then
   555    571       ** store the results in the appropriate memory cell and break out
   556    572       ** of the scan loop.
   557    573       */
   558    574       case SRT_Mem: {
   559    575         assert( nColumn==1 );
   560    576         if( pOrderBy ){
   561         -        pushOntoSorter(pParse, v, pOrderBy);
          577  +        pushOntoSorter(pParse, pOrderBy, p);
   562    578         }else{
   563    579           sqlite3VdbeAddOp(v, OP_MemStore, iParm, 1);
   564    580           /* The LIMIT clause will jump out of the loop for us */
   565    581         }
   566    582         break;
   567    583       }
   568    584   #endif /* #ifndef SQLITE_OMIT_SUBQUERY */
................................................................................
   571    587       ** case of a subroutine, the subroutine itself is responsible for
   572    588       ** popping the data from the stack.
   573    589       */
   574    590       case SRT_Subroutine:
   575    591       case SRT_Callback: {
   576    592         if( pOrderBy ){
   577    593           sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0);
   578         -        pushOntoSorter(pParse, v, pOrderBy);
          594  +        pushOntoSorter(pParse, pOrderBy, p);
   579    595         }else if( eDest==SRT_Subroutine ){
   580    596           sqlite3VdbeAddOp(v, OP_Gosub, 0, iParm);
   581    597         }else{
   582    598           sqlite3VdbeAddOp(v, OP_Callback, nColumn, 0);
   583    599         }
   584    600         break;
   585    601       }
................................................................................
  1354   1370   ** pLimit and pOffset expressions.  pLimit and pOffset hold the expressions
  1355   1371   ** that appear in the original SQL statement after the LIMIT and OFFSET
  1356   1372   ** keywords.  Or NULL if those keywords are omitted. iLimit and iOffset 
  1357   1373   ** are the integer memory register numbers for counters used to compute 
  1358   1374   ** the limit and offset.  If there is no limit and/or offset, then 
  1359   1375   ** iLimit and iOffset are negative.
  1360   1376   **
  1361         -** This routine changes the values if iLimit and iOffset only if
         1377  +** This routine changes the values of iLimit and iOffset only if
  1362   1378   ** a limit or offset is defined by pLimit and pOffset.  iLimit and
  1363   1379   ** iOffset should have been preset to appropriate default values
  1364   1380   ** (usually but not always -1) prior to calling this routine.
  1365   1381   ** Only if pLimit!=0 or pOffset!=0 do the limit registers get
  1366   1382   ** redefined.  The UNION ALL operator uses this property to force
  1367   1383   ** the reuse of the same limit and offset registers across multiple
  1368   1384   ** SELECT statements.
................................................................................
  1371   1387     /* 
  1372   1388     ** "LIMIT -1" always shows all rows.  There is some
  1373   1389     ** contraversy about what the correct behavior should be.
  1374   1390     ** The current implementation interprets "LIMIT 0" to mean
  1375   1391     ** no rows.
  1376   1392     */
  1377   1393     if( p->pLimit ){
  1378         -    int iMem = pParse->nMem++;
         1394  +    int iMem = pParse->nMem;
         1395  +    pParse->nMem += 2;
  1379   1396       Vdbe *v = sqlite3GetVdbe(pParse);
  1380   1397       if( v==0 ) return;
  1381   1398       sqlite3ExprCode(pParse, p->pLimit);
  1382   1399       sqlite3VdbeAddOp(v, OP_MustBeInt, 0, 0);
  1383   1400       sqlite3VdbeAddOp(v, OP_Negative, 0, 0);
  1384         -    sqlite3VdbeAddOp(v, OP_MemStore, iMem, 1);
         1401  +    sqlite3VdbeAddOp(v, OP_MemStore, iMem, 0);
  1385   1402       VdbeComment((v, "# LIMIT counter"));
  1386   1403       sqlite3VdbeAddOp(v, OP_IfMemZero, iMem, iBreak);
  1387   1404       p->iLimit = iMem;
  1388   1405     }
  1389   1406     if( p->pOffset ){
  1390   1407       int iMem = pParse->nMem++;
  1391   1408       Vdbe *v = sqlite3GetVdbe(pParse);
  1392   1409       if( v==0 ) return;
  1393   1410       sqlite3ExprCode(pParse, p->pOffset);
  1394   1411       sqlite3VdbeAddOp(v, OP_MustBeInt, 0, 0);
  1395   1412       sqlite3VdbeAddOp(v, OP_Negative, 0, 0);
  1396         -    sqlite3VdbeAddOp(v, OP_MemStore, iMem, 1);
         1413  +    sqlite3VdbeAddOp(v, OP_MemStore, iMem, p->pLimit==0);
  1397   1414       VdbeComment((v, "# OFFSET counter"));
         1415  +    if( p->pLimit ){
         1416  +      sqlite3VdbeAddOp(v, OP_Add, 0, 0);
         1417  +    }
  1398   1418       p->iOffset = iMem;
  1399   1419     }
         1420  +  if( p->pLimit ){
         1421  +    Vdbe *v = pParse->pVdbe;
         1422  +    sqlite3VdbeAddOp(v, OP_MemStore, p->iLimit+1, 1);
         1423  +    VdbeComment((v, "# LIMIT+OFFSET"));
         1424  +  }
  1400   1425   }
  1401   1426   
  1402   1427   /*
  1403   1428   ** Allocate a virtual index to use for sorting.
  1404   1429   */
  1405   1430   static void createSortingIndex(Parse *pParse, Select *p, ExprList *pOrderBy){
  1406   1431     if( pOrderBy ){