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

Changes to main.mk.

    61     61            memjournal.o \
    62     62            mutex.o mutex_noop.o mutex_os2.o mutex_unix.o mutex_w32.o \
    63     63            notify.o opcodes.o os.o os_os2.o os_unix.o os_win.o \
    64     64            pager.o parse.o pcache.o pcache1.o pragma.o prepare.o printf.o \
    65     65            random.o resolve.o rowset.o rtree.o select.o status.o \
    66     66            table.o tokenize.o trigger.o \
    67     67            update.o util.o vacuum.o \
    68         -         vdbe.o vdbeapi.o vdbeaux.o vdbeblob.o vdbemem.o vdbetrace.o \
    69         -         wal.o walker.o where.o utf.o vtab.o
           68  +         vdbe.o vdbeapi.o vdbeaux.o vdbeblob.o vdbemem.o vdbesort.o \
           69  +	 vdbetrace.o wal.o walker.o where.o utf.o vtab.o
    70     70   
    71     71   
    72     72   
    73     73   # All of the source code files.
    74     74   #
    75     75   SRC = \
    76     76     $(TOP)/src/alter.c \
................................................................................
   151    151     $(TOP)/src/vacuum.c \
   152    152     $(TOP)/src/vdbe.c \
   153    153     $(TOP)/src/vdbe.h \
   154    154     $(TOP)/src/vdbeapi.c \
   155    155     $(TOP)/src/vdbeaux.c \
   156    156     $(TOP)/src/vdbeblob.c \
   157    157     $(TOP)/src/vdbemem.c \
          158  +  $(TOP)/src/vdbesort.c \
   158    159     $(TOP)/src/vdbetrace.c \
   159    160     $(TOP)/src/vdbeInt.h \
   160    161     $(TOP)/src/vtab.c \
   161    162     $(TOP)/src/wal.c \
   162    163     $(TOP)/src/wal.h \
   163    164     $(TOP)/src/walker.c \
   164    165     $(TOP)/src/where.c

Changes to src/build.c.

  2304   2304   ** the index already exists and must be cleared before being refilled and
  2305   2305   ** the root page number of the index is taken from pIndex->tnum.
  2306   2306   */
  2307   2307   static void sqlite3RefillIndex(Parse *pParse, Index *pIndex, int memRootPage){
  2308   2308     Table *pTab = pIndex->pTable;  /* The table that is indexed */
  2309   2309     int iTab = pParse->nTab++;     /* Btree cursor used for pTab */
  2310   2310     int iIdx = pParse->nTab++;     /* Btree cursor used for pIndex */
         2311  +  int iSorter = pParse->nTab++;  /* Btree cursor used for sorting */
  2311   2312     int addr1;                     /* Address of top of loop */
  2312   2313     int tnum;                      /* Root page of index */
  2313   2314     Vdbe *v;                       /* Generate code into this virtual machine */
  2314   2315     KeyInfo *pKey;                 /* KeyInfo for index */
  2315   2316     int regIdxKey;                 /* Registers containing the index key */
  2316   2317     int regRecord;                 /* Register holding assemblied index record */
  2317   2318     sqlite3 *db = pParse->db;      /* The database connection */
................................................................................
  2337   2338     }
  2338   2339     pKey = sqlite3IndexKeyinfo(pParse, pIndex);
  2339   2340     sqlite3VdbeAddOp4(v, OP_OpenWrite, iIdx, tnum, iDb, 
  2340   2341                       (char *)pKey, P4_KEYINFO_HANDOFF);
  2341   2342     if( memRootPage>=0 ){
  2342   2343       sqlite3VdbeChangeP5(v, 1);
  2343   2344     }
         2345  +
         2346  +  /* Open the sorter cursor. */
         2347  +  sqlite3VdbeAddOp4(v, OP_OpenSorter, iSorter, 0, 0, (char*)pKey, P4_KEYINFO);
         2348  +
         2349  +  /* Open the table. Loop through all rows of the table, inserting index
         2350  +  ** records into the sorter. */
  2344   2351     sqlite3OpenTable(pParse, iTab, iDb, pTab, OP_OpenRead);
  2345   2352     addr1 = sqlite3VdbeAddOp2(v, OP_Rewind, iTab, 0);
  2346   2353     regRecord = sqlite3GetTempReg(pParse);
  2347   2354     regIdxKey = sqlite3GenerateIndexKey(pParse, pIndex, iTab, regRecord, 1);
         2355  +  sqlite3VdbeAddOp2(v, OP_IdxInsert, iSorter, regRecord);
         2356  +  sqlite3VdbeAddOp2(v, OP_Next, iTab, addr1+1);
         2357  +  sqlite3VdbeJumpHere(v, addr1);
         2358  +
         2359  +  /* Rewind the sorter. Loop through index records in sorted order. */
         2360  +  addr1 = sqlite3VdbeAddOp2(v, OP_Rewind, iSorter, 0);
         2361  +  sqlite3VdbeAddOp2(v, OP_RowKey, iSorter, regRecord);
         2362  +
  2348   2363     if( pIndex->onError!=OE_None ){
  2349   2364       const int regRowid = regIdxKey + pIndex->nColumn;
  2350   2365       const int j2 = sqlite3VdbeCurrentAddr(v) + 2;
  2351   2366       void * const pRegKey = SQLITE_INT_TO_PTR(regIdxKey);
  2352   2367   
  2353   2368       /* The registers accessed by the OP_IsUnique opcode were allocated
  2354   2369       ** using sqlite3GetTempRange() inside of the sqlite3GenerateIndexKey()
................................................................................
  2359   2374       ** we can be sure that no other temp registers have been allocated
  2360   2375       ** since sqlite3ReleaseTempRange() was called, it is safe to do so.
  2361   2376       */
  2362   2377       sqlite3VdbeAddOp4(v, OP_IsUnique, iIdx, j2, regRowid, pRegKey, P4_INT32);
  2363   2378       sqlite3HaltConstraint(
  2364   2379           pParse, OE_Abort, "indexed columns are not unique", P4_STATIC);
  2365   2380     }
  2366         -  sqlite3VdbeAddOp2(v, OP_IdxInsert, iIdx, regRecord);
         2381  +  sqlite3VdbeAddOp3(v, OP_IdxInsert, iIdx, regRecord, 1);
  2367   2382     sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);
  2368   2383     sqlite3ReleaseTempReg(pParse, regRecord);
  2369         -  sqlite3VdbeAddOp2(v, OP_Next, iTab, addr1+1);
         2384  +  sqlite3VdbeAddOp2(v, OP_Next, iSorter, addr1+1);
  2370   2385     sqlite3VdbeJumpHere(v, addr1);
         2386  +
  2371   2387     sqlite3VdbeAddOp1(v, OP_Close, iTab);
         2388  +  sqlite3VdbeAddOp1(v, OP_Close, iSorter);
  2372   2389     sqlite3VdbeAddOp1(v, OP_Close, iIdx);
  2373   2390   }
  2374   2391   
  2375   2392   /*
  2376   2393   ** Create a new index for an SQL table.  pName1.pName2 is the name of the index 
  2377   2394   ** and pTblList is the name of the table that is to be indexed.  Both will 
  2378   2395   ** be NULL for a primary key or an index that is created to satisfy a

Changes to src/vdbe.c.

  3140   3140   /* Opcode: OpenAutoindex P1 P2 * P4 *
  3141   3141   **
  3142   3142   ** This opcode works the same as OP_OpenEphemeral.  It has a
  3143   3143   ** different name to distinguish its use.  Tables created using
  3144   3144   ** by this opcode will be used for automatically created transient
  3145   3145   ** indices in joins.
  3146   3146   */
         3147  +case OP_OpenSorter: 
  3147   3148   case OP_OpenAutoindex: 
  3148   3149   case OP_OpenEphemeral: {
  3149   3150     VdbeCursor *pCx;
  3150   3151     static const int vfsFlags = 
  3151   3152         SQLITE_OPEN_READWRITE |
  3152   3153         SQLITE_OPEN_CREATE |
  3153   3154         SQLITE_OPEN_EXCLUSIVE |
  3154   3155         SQLITE_OPEN_DELETEONCLOSE |
  3155   3156         SQLITE_OPEN_TRANSIENT_DB;
  3156   3157   
         3158  +  int btflags = BTREE_OMIT_JOURNAL | pOp->p5;
         3159  +  if( pOp->opcode!=OP_OpenSorter ) btflags |= BTREE_SINGLE;
         3160  +
  3157   3161     assert( pOp->p1>=0 );
  3158   3162     pCx = allocateCursor(p, pOp->p1, pOp->p2, -1, 1);
  3159   3163     if( pCx==0 ) goto no_mem;
  3160   3164     pCx->nullRow = 1;
  3161         -  rc = sqlite3BtreeOpen(db->pVfs, 0, db, &pCx->pBt, 
  3162         -                        BTREE_OMIT_JOURNAL | BTREE_SINGLE | pOp->p5, vfsFlags);
         3165  +  rc = sqlite3BtreeOpen(db->pVfs, 0, db, &pCx->pBt, btflags, vfsFlags);
  3163   3166     if( rc==SQLITE_OK ){
  3164   3167       rc = sqlite3BtreeBeginTrans(pCx->pBt, 1);
  3165   3168     }
  3166   3169     if( rc==SQLITE_OK ){
  3167   3170       /* If a transient index is required, create it by calling
  3168   3171       ** sqlite3BtreeCreateTable() with the BTREE_BLOBKEY flag before
  3169   3172       ** opening it. If a transient table is required, just use the
................................................................................
  3174   3177         assert( pOp->p4type==P4_KEYINFO );
  3175   3178         rc = sqlite3BtreeCreateTable(pCx->pBt, &pgno, BTREE_BLOBKEY | pOp->p5); 
  3176   3179         if( rc==SQLITE_OK ){
  3177   3180           assert( pgno==MASTER_ROOT+1 );
  3178   3181           rc = sqlite3BtreeCursor(pCx->pBt, pgno, 1, 
  3179   3182                                   (KeyInfo*)pOp->p4.z, pCx->pCursor);
  3180   3183           pCx->pKeyInfo = pOp->p4.pKeyInfo;
  3181         -        pCx->pKeyInfo->enc = ENC(p->db);
         3184  +        pCx->pKeyInfo->enc = ENC(db);
  3182   3185         }
  3183   3186         pCx->isTable = 0;
  3184   3187       }else{
  3185   3188         rc = sqlite3BtreeCursor(pCx->pBt, MASTER_ROOT, 1, 0, pCx->pCursor);
  3186   3189         pCx->isTable = 1;
  3187   3190       }
  3188   3191     }
  3189   3192     pCx->isOrdered = (pOp->p5!=BTREE_UNORDERED);
  3190   3193     pCx->isIndex = !pCx->isTable;
         3194  +  if( rc==SQLITE_OK && pOp->opcode==OP_OpenSorter ){
         3195  +    rc = sqlite3VdbeSorterInit(db, pCx);
         3196  +  }
  3191   3197     break;
  3192   3198   }
  3193   3199   
  3194   3200   /* Opcode: OpenPseudo P1 P2 P3 * *
  3195   3201   **
  3196   3202   ** Open a new cursor that points to a fake table that contains a single
  3197   3203   ** row of data.  The content of that one row in the content of memory
................................................................................
  4073   4079     assert( pOp->p1>=0 && pOp->p1<p->nCursor );
  4074   4080     pC = p->apCsr[pOp->p1];
  4075   4081     assert( pC->isTable || pOp->opcode==OP_RowKey );
  4076   4082     assert( pC->isIndex || pOp->opcode==OP_RowData );
  4077   4083     assert( pC!=0 );
  4078   4084     assert( pC->nullRow==0 );
  4079   4085     assert( pC->pseudoTableReg==0 );
         4086  +
         4087  +  if( pC->pSorter ){
         4088  +    rc = sqlite3VdbeSorterRowkey(db, pC, pOut);
         4089  +    break;
         4090  +  }
         4091  +
  4080   4092     assert( pC->pCursor!=0 );
  4081   4093     pCrsr = pC->pCursor;
  4082   4094     assert( sqlite3BtreeCursorIsValid(pCrsr) );
  4083   4095   
  4084   4096     /* The OP_RowKey and OP_RowData opcodes always follow OP_NotExists or
  4085   4097     ** OP_Rewind/Op_Next with no intervening instructions that might invalidate
  4086   4098     ** the cursor.  Hence the following sqlite3VdbeCursorMoveto() call is always
................................................................................
  4253   4265     BtCursor *pCrsr;
  4254   4266     int res;
  4255   4267   
  4256   4268     assert( pOp->p1>=0 && pOp->p1<p->nCursor );
  4257   4269     pC = p->apCsr[pOp->p1];
  4258   4270     assert( pC!=0 );
  4259   4271     res = 1;
  4260         -  if( (pCrsr = pC->pCursor)!=0 ){
         4272  +  if( pC->pSorter ){
         4273  +    rc = sqlite3VdbeSorterRewind(db, pC, &res);
         4274  +  }else if( (pCrsr = pC->pCursor)!=0 ){
  4261   4275       rc = sqlite3BtreeFirst(pCrsr, &res);
  4262   4276       pC->atFirst = res==0 ?1:0;
  4263   4277       pC->deferredMoveto = 0;
  4264   4278       pC->cacheStatus = CACHE_STALE;
  4265   4279       pC->rowidIsValid = 0;
  4266   4280     }
  4267   4281     pC->nullRow = (u8)res;
................................................................................
  4307   4321     CHECK_FOR_INTERRUPT;
  4308   4322     assert( pOp->p1>=0 && pOp->p1<p->nCursor );
  4309   4323     assert( pOp->p5<=ArraySize(p->aCounter) );
  4310   4324     pC = p->apCsr[pOp->p1];
  4311   4325     if( pC==0 ){
  4312   4326       break;  /* See ticket #2273 */
  4313   4327     }
  4314         -  pCrsr = pC->pCursor;
  4315         -  if( pCrsr==0 ){
  4316         -    pC->nullRow = 1;
  4317         -    break;
         4328  +  if( pC->pSorter ){
         4329  +    assert( pOp->opcode==OP_Next );
         4330  +    rc = sqlite3VdbeSorterNext(db, pC, &res);
         4331  +  }else{
         4332  +    pCrsr = pC->pCursor;
         4333  +    if( pCrsr==0 ){
         4334  +      pC->nullRow = 1;
         4335  +      break;
         4336  +    }
         4337  +    res = 1;
         4338  +    assert( pC->deferredMoveto==0 );
         4339  +    rc = pOp->opcode==OP_Next ? sqlite3BtreeNext(pCrsr, &res) :
         4340  +                                sqlite3BtreePrevious(pCrsr, &res);
  4318   4341     }
  4319         -  res = 1;
  4320         -  assert( pC->deferredMoveto==0 );
  4321         -  rc = pOp->opcode==OP_Next ? sqlite3BtreeNext(pCrsr, &res) :
  4322         -                              sqlite3BtreePrevious(pCrsr, &res);
  4323   4342     pC->nullRow = (u8)res;
  4324   4343     pC->cacheStatus = CACHE_STALE;
         4344  +
  4325   4345     if( res==0 ){
  4326   4346       pc = pOp->p2 - 1;
  4327   4347       if( pOp->p5 ) p->aCounter[pOp->p5-1]++;
  4328   4348   #ifdef SQLITE_TEST
  4329   4349       sqlite3_search_count++;
  4330   4350   #endif
  4331   4351     }
................................................................................
  4350   4370     BtCursor *pCrsr;
  4351   4371     int nKey;
  4352   4372     const char *zKey;
  4353   4373   
  4354   4374     assert( pOp->p1>=0 && pOp->p1<p->nCursor );
  4355   4375     pC = p->apCsr[pOp->p1];
  4356   4376     assert( pC!=0 );
         4377  +  rc = sqlite3VdbeSorterWrite(db, pC);
         4378  +  if( rc!=SQLITE_OK ) goto abort_due_to_error;
  4357   4379     pIn2 = &aMem[pOp->p2];
  4358   4380     assert( pIn2->flags & MEM_Blob );
  4359   4381     pCrsr = pC->pCursor;
  4360   4382     if( ALWAYS(pCrsr!=0) ){
  4361   4383       assert( pC->isTable==0 );
  4362   4384       rc = ExpandBlob(pIn2);
  4363   4385       if( rc==SQLITE_OK ){

Changes to src/vdbeInt.h.

    26     26   typedef struct VdbeOp Op;
    27     27   
    28     28   /*
    29     29   ** Boolean values
    30     30   */
    31     31   typedef unsigned char Bool;
    32     32   
           33  +/* Opaque type used by code in vdbesort.c */
           34  +typedef struct VdbeSorter VdbeSorter;
           35  +
    33     36   /*
    34     37   ** A cursor is a pointer into a single BTree within a database file.
    35     38   ** The cursor can seek to a BTree entry with a particular key, or
    36     39   ** loop over all entries of the Btree.  You can also insert new BTree
    37     40   ** entries or retrieve the key or data from the entry that the cursor
    38     41   ** is currently pointing to.
    39     42   ** 
................................................................................
    57     60     Bool isIndex;         /* True if an index containing keys only - no data */
    58     61     Bool isOrdered;       /* True if the underlying table is BTREE_UNORDERED */
    59     62     sqlite3_vtab_cursor *pVtabCursor;  /* The cursor for a virtual table */
    60     63     const sqlite3_module *pModule;     /* Module for cursor pVtabCursor */
    61     64     i64 seqCount;         /* Sequence counter */
    62     65     i64 movetoTarget;     /* Argument to the deferred sqlite3BtreeMoveto() */
    63     66     i64 lastRowid;        /* Last rowid from a Next or NextIdx operation */
           67  +  VdbeSorter *pSorter;  /* Sorter object for OP_OpenSorter cursors */
    64     68   
    65     69     /* Result of last sqlite3BtreeMoveto() done by an OP_NotExists or 
    66     70     ** OP_IsUnique opcode on this cursor. */
    67     71     int seekResult;
    68     72   
    69     73     /* Cached information about the header for the data record that the
    70     74     ** cursor is currently pointing to.  Only valid if cacheStatus matches
................................................................................
   384    388   const char *sqlite3OpcodeName(int);
   385    389   int sqlite3VdbeMemGrow(Mem *pMem, int n, int preserve);
   386    390   int sqlite3VdbeCloseStatement(Vdbe *, int);
   387    391   void sqlite3VdbeFrameDelete(VdbeFrame*);
   388    392   int sqlite3VdbeFrameRestore(VdbeFrame *);
   389    393   void sqlite3VdbeMemStoreType(Mem *pMem);
   390    394   
          395  +int sqlite3VdbeSorterInit(sqlite3 *, VdbeCursor *);
          396  +int sqlite3VdbeSorterWrite(sqlite3 *, VdbeCursor *);
          397  +void sqlite3VdbeSorterClose(sqlite3 *, VdbeCursor *);
          398  +
   391    399   #if !defined(SQLITE_OMIT_SHARED_CACHE) && SQLITE_THREADSAFE>0
   392    400     void sqlite3VdbeEnter(Vdbe*);
   393    401     void sqlite3VdbeLeave(Vdbe*);
   394    402   #else
   395    403   # define sqlite3VdbeEnter(X)
   396    404   # define sqlite3VdbeLeave(X)
   397    405   #endif

Changes to src/vdbeaux.c.

  1561   1561   ** Close a VDBE cursor and release all the resources that cursor 
  1562   1562   ** happens to hold.
  1563   1563   */
  1564   1564   void sqlite3VdbeFreeCursor(Vdbe *p, VdbeCursor *pCx){
  1565   1565     if( pCx==0 ){
  1566   1566       return;
  1567   1567     }
         1568  +  sqlite3VdbeSorterClose(p->db, pCx);
  1568   1569     if( pCx->pBt ){
  1569   1570       sqlite3BtreeClose(pCx->pBt);
  1570   1571       /* The pCx->pCursor will be close automatically, if it exists, by
  1571   1572       ** the call above. */
  1572   1573     }else if( pCx->pCursor ){
  1573   1574       sqlite3BtreeCloseCursor(pCx->pCursor);
  1574   1575     }

Added src/vdbesort.c.

            1  +/*
            2  +** 2011 July 9
            3  +**
            4  +** The author disclaims copyright to this source code.  In place of
            5  +** a legal notice, here is a blessing:
            6  +**
            7  +**    May you do good and not evil.
            8  +**    May you find forgiveness for yourself and forgive others.
            9  +**    May you share freely, never taking more than you give.
           10  +**
           11  +*************************************************************************
           12  +** This file contains code for the VdbeSorter object, used in concert with
           13  +** a VdbeCursor to sort large numbers of keys (as may be required, for
           14  +** example, by CREATE INDEX statements on tables too large to fit in main
           15  +** memory).
           16  +*/
           17  +
           18  +#include "sqliteInt.h"
           19  +#include "vdbeInt.h"
           20  +
           21  +typedef struct VdbeSorterIter VdbeSorterIter;
           22  +
           23  +/*
           24  +** The aIter[] and aTree[] arrays are used to iterate through the sorter
           25  +** contents after it has been populated. To iterate through the sorter
           26  +** contents, the contents of the nRoot b-trees must be incrementally merged. 
           27  +**
           28  +** The first nRoot elements of the aIter[] array contain cursors open 
           29  +** on each of the b-trees. An aIter[] element either points to a valid
           30  +** key or else is at EOF. For the purposes of the paragraphs below, we
           31  +** assume that the array is actually N elements in size, where N is the
           32  +** smallest power of 2 greater to or equal to nRoot. The extra aIter[]
           33  +** elements are treated as if they are empty trees (always at EOF).
           34  +**
           35  +** The aTree[] array is N elements in size. The value of N is stored in
           36  +** the VdbeSorter.nTree variable.
           37  +**
           38  +** The final (N/2) elements of aTree[] contain the results of comparing
           39  +** pairs of iterator keys together. Element i contains the result of 
           40  +** comparing aIter[2*i-N] and aIter[2*i-N+1]. Whichever key is smaller, the
           41  +** aTree element is set to the index of it. 
           42  +**
           43  +** For the purposes of this comparison, EOF is considered greater than any
           44  +** other key value. If the keys are equal (only possible with two EOF
           45  +** values), it doesn't matter which index is stored.
           46  +**
           47  +** The (N/4) elements of aTree[] that preceed the final (N/2) described 
           48  +** above contains the index of the smallest of each block of 4 iterators.
           49  +** And so on. So that aTree[1] contains the index of the iterator that 
           50  +** currently points to the smallest key value. aTree[0] is unused.
           51  +**
           52  +** Example:
           53  +**
           54  +**     aIter[0] -> Banana
           55  +**     aIter[1] -> Feijoa
           56  +**     aIter[2] -> Elderberry
           57  +**     aIter[3] -> Currant
           58  +**     aIter[4] -> Grapefruit
           59  +**     aIter[5] -> Apple
           60  +**     aIter[6] -> Durian
           61  +**     aIter[7] -> EOF
           62  +**
           63  +**     aTree[] = { X, 5   0, 5    0, 3, 5, 6 }
           64  +**
           65  +** The current element is "Apple" (the value of the key indicated by 
           66  +** iterator 5). When the Next() operation is invoked, iterator 5 will
           67  +** be advanced to the next key in its segment. Say the next key is
           68  +** "Eggplant":
           69  +**
           70  +**     aIter[5] -> Eggplant
           71  +**
           72  +** The contents of aTree[] are updated first by comparing the new iterator
           73  +** 5 key to the current key of iterator 4 (still "Grapefruit"). The iterator
           74  +** 5 value is still smaller, so aTree[6] is set to 5. And so on up the tree.
           75  +** The value of iterator 6 - "Durian" - is now smaller than that of iterator
           76  +** 5, so aTree[3] is set to 6. Key 0 is smaller than key 6 (Banana<Durian),
           77  +** so the value written into element 1 of the array is 0. As follows:
           78  +**
           79  +**     aTree[] = { X, 0   0, 6    0, 3, 5, 6 }
           80  +**
           81  +** In other words, each time we advance to the next sorter element, log2(N)
           82  +** key comparison operations are required, where N is the number of segments
           83  +** being merged (rounded up to the next power of 2).
           84  +*/
           85  +struct VdbeSorter {
           86  +  int nWorking;                   /* Start a new b-tree after this many pages */
           87  +  int nPage;                      /* Pages in file when current tree started */
           88  +  int nRoot;                      /* Total number of segment b-trees */
           89  +  int *aRoot;                     /* Array containing root pages */
           90  +
           91  +  int nAlloc;                     /* Allocated size of aIter[] and aTree[] */
           92  +  int nTree;                      /* Used size of aTree/aIter (power of 2) */
           93  +  VdbeSorterIter *aIter;          /* Array of iterators to merge */
           94  +  int *aTree;                     /* Current state of incremental merge */
           95  +};
           96  +
           97  +/*
           98  +** The following type is a simple wrapper around a BtCursor. It caches the
           99  +** current key in variables nKey/aKey. If possible, aKey points to memory
          100  +** managed by the BtCursor object. In this case variable bFree is zero.
          101  +** Otherwise, aKey[] may point to a block of memory allocated using
          102  +** sqlite3DbMalloc(). In this case, bFree is non-zero.
          103  +*/
          104  +struct VdbeSorterIter {
          105  +  BtCursor *pCsr;                 /* Cursor open on b-tree */
          106  +  int bFree;                      /* True if aKey should be freed */
          107  +  int nKey;                       /* Number of bytes in key */
          108  +  u8 *aKey;                       /* Pointer to current key */
          109  +};
          110  +
          111  +/* Minimum allowable value for the VdbeSorter.nWorking variable */
          112  +#define SORTER_MIN_SEGMENT_SIZE 10
          113  +
          114  +/*
          115  +** Append integer iRoot to the VdbeSorter.aRoot[] array of the sorter object
          116  +** passed as the second argument. SQLITE_NOMEM is returned if an OOM error
          117  +** is encountered, or SQLITE_OK if no error occurs.
          118  +**
          119  +** TODO: The aRoot[] array may grow indefinitely. Fix this.
          120  +*/
          121  +static int vdbeSorterAppendRoot(sqlite3 *db, VdbeSorter *p, int iRoot){
          122  +  int *aNew;                      /* New VdbeSorter.aRoot[] array */
          123  +
          124  +  aNew = sqlite3DbRealloc(db, p->aRoot, (p->nRoot+1)*sizeof(int));
          125  +  if( !aNew ) return SQLITE_NOMEM;
          126  +  aNew[p->nRoot] = iRoot;
          127  +  p->nRoot++;
          128  +  p->aRoot = aNew;
          129  +  return SQLITE_OK;
          130  +}
          131  +
          132  +/*
          133  +** Close any cursor and free all memory belonging to the VdbeSorterIter
          134  +** object passed as the second argument. All structure fields are set
          135  +** to zero before returning.
          136  +*/
          137  +static void vdbeSorterIterZero(sqlite3 *db, VdbeSorterIter *pIter){
          138  +  if( pIter->bFree ){
          139  +    sqlite3DbFree(db, pIter->aKey);
          140  +  }
          141  +  if( pIter->pCsr ){
          142  +    sqlite3BtreeCloseCursor(pIter->pCsr);
          143  +    sqlite3DbFree(db, pIter->pCsr);
          144  +  }
          145  +  memset(pIter, 0, sizeof(VdbeSorterIter));
          146  +}
          147  +
          148  +/*
          149  +** Fetch the current key pointed to by the b-tree cursor managed by pIter
          150  +** into variables VdbeSorterIter.aKey and VdbeSorterIter.nKey. Return
          151  +** SQLITE_OK if no error occurs, or an SQLite error code otherwise.
          152  +*/
          153  +static int vdbeSorterIterLoadkey(sqlite3 *db, VdbeSorterIter *pIter){
          154  +  int rc = SQLITE_OK;
          155  +  assert( pIter->pCsr );
          156  +  if( sqlite3BtreeEof(pIter->pCsr) ){
          157  +    vdbeSorterIterZero(db, pIter);
          158  +  }else{
          159  +    i64 nByte64;
          160  +    sqlite3BtreeKeySize(pIter->pCsr, &nByte64);
          161  +
          162  +    if( pIter->bFree ){
          163  +      sqlite3DbFree(db, pIter->aKey);
          164  +      pIter->aKey = 0;
          165  +    }
          166  +
          167  +    pIter->nKey = nByte64;
          168  +    pIter->aKey = sqlite3DbMallocRaw(db, pIter->nKey);
          169  +    pIter->bFree = 1;
          170  +    if( pIter->aKey==0 ){
          171  +      rc = SQLITE_NOMEM;
          172  +    }else{
          173  +      rc = sqlite3BtreeKey(pIter->pCsr, 0, pIter->nKey, pIter->aKey);
          174  +    }
          175  +
          176  +  }
          177  +  return rc;
          178  +}
          179  +
          180  +/*
          181  +** Initialize iterator pIter to scan through the b-tree with root page
          182  +** iRoot. This function leaves the iterator pointing to the first key
          183  +** in the b-tree (or EOF if the b-tree is empty).
          184  +*/
          185  +static int vdbeSorterIterInit(
          186  +  sqlite3 *db,                    /* Database handle */
          187  +  VdbeCursor *pCsr,               /* Vdbe cursor handle */
          188  +  int iRoot,                      /* Root page of b-tree to iterate */
          189  +  VdbeSorterIter *pIter           /* Pointer to iterator to initialize */
          190  +){
          191  +  VdbeSorter *pSorter = pCsr->pSorter;
          192  +  int rc;
          193  +
          194  +  pIter->pCsr = (BtCursor *)sqlite3DbMallocZero(db, sqlite3BtreeCursorSize());
          195  +  if( !pIter->pCsr ){
          196  +    rc = SQLITE_NOMEM;
          197  +  }else{
          198  +    rc = sqlite3BtreeCursor(pCsr->pBt, iRoot, 1, pCsr->pKeyInfo, pIter->pCsr);
          199  +  }
          200  +  if( rc==SQLITE_OK ){
          201  +    int bDummy;
          202  +    rc = sqlite3BtreeFirst(pIter->pCsr, &bDummy);
          203  +  }
          204  +  if( rc==SQLITE_OK ){
          205  +    rc = vdbeSorterIterLoadkey(db, pIter);
          206  +  }
          207  +
          208  +  return rc;
          209  +}
          210  +
          211  +/*
          212  +** Advance iterator pIter to the next key in its b-tree. 
          213  +*/
          214  +static int vdbeSorterIterNext(
          215  +  sqlite3 *db, 
          216  +  VdbeCursor *pCsr, 
          217  +  VdbeSorterIter *pIter
          218  +){
          219  +  int rc;
          220  +  int bDummy;
          221  +  VdbeSorter *pSorter = pCsr->pSorter;
          222  +
          223  +  rc = sqlite3BtreeNext(pIter->pCsr, &bDummy);
          224  +  if( rc==SQLITE_OK ){
          225  +    rc = vdbeSorterIterLoadkey(db, pIter);
          226  +  }
          227  +
          228  +  return rc;
          229  +}
          230  +
          231  +/*
          232  +** This function is called to compare two iterator keys when merging 
          233  +** multiple b-tree segments. Parameter iOut is the index of the aTree[] 
          234  +** value to recalculate.
          235  +*/
          236  +static int vdbeSorterDoCompare(VdbeCursor *pCsr, int iOut){
          237  +  VdbeSorter *pSorter = pCsr->pSorter;
          238  +  int i1;
          239  +  int i2;
          240  +  int iRes;
          241  +  VdbeSorterIter *p1;
          242  +  VdbeSorterIter *p2;
          243  +
          244  +  assert( iOut<pSorter->nTree && iOut>0 );
          245  +
          246  +  if( iOut>=(pSorter->nTree/2) ){
          247  +    i1 = (iOut - pSorter->nTree/2) * 2;
          248  +    i2 = i1 + 1;
          249  +  }else{
          250  +    i1 = pSorter->aTree[iOut*2];
          251  +    i2 = pSorter->aTree[iOut*2+1];
          252  +  }
          253  +
          254  +  p1 = &pSorter->aIter[i1];
          255  +  p2 = &pSorter->aIter[i2];
          256  +
          257  +  if( p1->pCsr==0 ){
          258  +    iRes = i2;
          259  +  }else if( p2->pCsr==0 ){
          260  +    iRes = i1;
          261  +  }else{
          262  +    char aSpace[150];
          263  +    UnpackedRecord *r1;
          264  +
          265  +    r1 = sqlite3VdbeRecordUnpack(
          266  +        pCsr->pKeyInfo, p1->nKey, p1->aKey, aSpace, sizeof(aSpace)
          267  +    );
          268  +    if( r1==0 ) return SQLITE_NOMEM;
          269  +
          270  +    if( sqlite3VdbeRecordCompare(p2->nKey, p2->aKey, r1)>=0 ){
          271  +      iRes = i1;
          272  +    }else{
          273  +      iRes = i2;
          274  +    }
          275  +    sqlite3VdbeDeleteUnpackedRecord(r1);
          276  +  }
          277  +
          278  +  pSorter->aTree[iOut] = iRes;
          279  +  return SQLITE_OK;
          280  +}
          281  +
          282  +/*
          283  +** Initialize the temporary index cursor just opened as a sorter cursor.
          284  +*/
          285  +int sqlite3VdbeSorterInit(sqlite3 *db, VdbeCursor *pCsr){
          286  +  int rc;                         /* Return code */
          287  +  VdbeSorter *pSorter;            /* Allocated sorter object */
          288  +
          289  +  /* Cursor must be a temp cursor and not open on an intkey table */
          290  +  assert( pCsr->pKeyInfo && pCsr->pBt );
          291  +
          292  +  pSorter = sqlite3DbMallocZero(db, sizeof(VdbeSorter));
          293  +  if( !pSorter ) return SQLITE_NOMEM;
          294  +  pCsr->pSorter = pSorter;
          295  +
          296  +  rc = vdbeSorterAppendRoot(db, pSorter, 2);
          297  +  if( rc!=SQLITE_OK ){
          298  +    sqlite3VdbeSorterClose(db, pCsr);
          299  +  }
          300  +  return rc;
          301  +}
          302  +
          303  +/*
          304  +** Free any cursor components allocated by sqlite3VdbeSorterXXX routines.
          305  +*/
          306  +void sqlite3VdbeSorterClose(sqlite3 *db, VdbeCursor *pCsr){
          307  +  VdbeSorter *pSorter = pCsr->pSorter;
          308  +  if( pSorter ){
          309  +    sqlite3DbFree(db, pSorter->aRoot);
          310  +    if( pSorter->aIter ){
          311  +      int i;
          312  +      for(i=0; i<pSorter->nRoot; i++){
          313  +        vdbeSorterIterZero(db, &pSorter->aIter[i]);
          314  +      }
          315  +      sqlite3DbFree(db, pSorter->aIter);
          316  +      sqlite3DbFree(db, pSorter->aTree);
          317  +    }
          318  +    sqlite3DbFree(db, pSorter);
          319  +    pCsr->pSorter = 0;
          320  +  }
          321  +}
          322  +
          323  +/*
          324  +** This function is called on a sorter cursor before each row is inserted.
          325  +** If the current b-tree being constructed is already considered "full",
          326  +** a new tree is started.
          327  +*/
          328  +int sqlite3VdbeSorterWrite(sqlite3 *db, VdbeCursor *pCsr){
          329  +  int rc = SQLITE_OK;             /* Return code */
          330  +  VdbeSorter *pSorter = pCsr->pSorter;
          331  +  if( pSorter ){
          332  +    Pager *pPager = sqlite3BtreePager(pCsr->pBt);
          333  +    int nPage;                    /* Current size of temporary file in pages */
          334  +
          335  +    sqlite3PagerPagecount(pPager, &nPage);
          336  +
          337  +    /* If pSorter->nWorking is still zero, but the temporary file has been
          338  +    ** created in the file-system, then the most recent insert into the
          339  +    ** current b-tree segment probably caused the cache to overflow (it is
          340  +    ** also possible that sqlite3_release_memory() was called). So set the
          341  +    ** size of the working set to a little less than the current size of the 
          342  +    ** file in pages.  */
          343  +    if( pSorter->nWorking==0 && sqlite3PagerFile(pPager)->pMethods ){
          344  +      pSorter->nWorking = nPage-5;
          345  +      if( pSorter->nWorking<SORTER_MIN_SEGMENT_SIZE ){
          346  +        pSorter->nWorking = SORTER_MIN_SEGMENT_SIZE;
          347  +      }
          348  +    }
          349  +
          350  +    /* If the number of pages used by the current b-tree segment is greater
          351  +    ** than the size of the working set (VdbeSorter.nWorking), start a new
          352  +    ** segment b-tree.  */
          353  +    if( pSorter->nWorking && nPage>=(pSorter->nPage + pSorter->nWorking) ){
          354  +      BtCursor *p = pCsr->pCursor;/* Cursor structure to close and reopen */
          355  +      int iRoot;                  /* Root page of new tree */
          356  +      sqlite3BtreeCloseCursor(p);
          357  +      rc = sqlite3BtreeCreateTable(pCsr->pBt, &iRoot, BTREE_BLOBKEY);
          358  +      if( rc==SQLITE_OK ){
          359  +        rc = vdbeSorterAppendRoot(db, pSorter, iRoot);
          360  +      }
          361  +      if( rc==SQLITE_OK ){
          362  +        rc = sqlite3BtreeCursor(pCsr->pBt, iRoot, 1, pCsr->pKeyInfo, p);
          363  +      }
          364  +      pSorter->nPage = nPage;
          365  +    }
          366  +  }
          367  +  return rc;
          368  +}
          369  +
          370  +/*
          371  +** Extend the pSorter->aIter[] and pSorter->aTree[] arrays using DbRealloc().
          372  +** Return SQLITE_OK if successful, or SQLITE_NOMEM otherwise.
          373  +*/
          374  +static int vdbeSorterGrowArrays(sqlite3* db, VdbeSorter *pSorter){
          375  +  int *aTree;                     /* New aTree[] allocation */
          376  +  VdbeSorterIter *aIter;          /* New aIter[] allocation */
          377  +  int nOld = pSorter->nAlloc;     /* Current size of arrays */
          378  +  int nNew = (nOld?nOld*2:64);    /* Size of arrays after reallocation */
          379  +
          380  +  /* Realloc aTree[]. */
          381  +  aTree = sqlite3DbRealloc(db, pSorter->aTree, sizeof(int)*nNew);
          382  +  if( !aTree ) return SQLITE_NOMEM;
          383  +  memset(&aTree[nOld], 0, (nNew-nOld) * sizeof(int));
          384  +  pSorter->aTree = aTree;
          385  +
          386  +  /* Realloc aIter[]. */
          387  +  aIter = sqlite3DbRealloc(db, pSorter->aIter, sizeof(VdbeSorterIter)*nNew);
          388  +  if( !aIter ) return SQLITE_NOMEM;
          389  +  memset(&aIter[nOld], 0, (nNew-nOld) * sizeof(VdbeSorterIter));
          390  +  pSorter->aIter = aIter;
          391  +
          392  +  /* Set VdbeSorter.nAlloc to the new size of the arrays and return OK. */
          393  +  pSorter->nAlloc = nNew;
          394  +  return SQLITE_OK;
          395  +}
          396  +
          397  +/*
          398  +** Helper function for sqlite3VdbeSorterRewind().
          399  +*/
          400  +static int vdbeSorterInitMerge(
          401  +  sqlite3 *db,
          402  +  VdbeCursor *pCsr,
          403  +  int iFirst,
          404  +  int *piNext
          405  +){
          406  +  Pager *pPager = sqlite3BtreePager(pCsr->pBt);
          407  +  VdbeSorter *pSorter = pCsr->pSorter;
          408  +  int rc = SQLITE_OK;
          409  +  int i;
          410  +  int nMaxRef = (pSorter->nWorking * 9/10);
          411  +  int N = 2;
          412  +
          413  +  /* Initialize as many iterators as possible. */
          414  +  for(i=iFirst; rc==SQLITE_OK && i<pSorter->nRoot; i++){
          415  +    int iIter = i - iFirst;
          416  +
          417  +    assert( iIter<=pSorter->nAlloc );
          418  +    if( iIter==pSorter->nAlloc ){
          419  +      rc = vdbeSorterGrowArrays(db, pSorter);
          420  +    }
          421  +
          422  +    if( rc==SQLITE_OK ){
          423  +      VdbeSorterIter *pIter = &pSorter->aIter[iIter];
          424  +      rc = vdbeSorterIterInit(db, pCsr, pSorter->aRoot[i], pIter);
          425  +      if( i>iFirst+1 ){
          426  +        int nRef = sqlite3PagerRefcount(pPager) + (i+1-iFirst);
          427  +        if( nRef>=nMaxRef ){
          428  +          i++;
          429  +          break;
          430  +        }
          431  +      }
          432  +    }
          433  +  }
          434  +  *piNext = i;
          435  +
          436  +  while( (i-iFirst)>N ) N += N;
          437  +  pSorter->nTree = N;
          438  +
          439  +  /* Populate the aTree[] array. */
          440  +  for(i=N-1; rc==SQLITE_OK && i>0; i--){
          441  +    rc = vdbeSorterDoCompare(pCsr, i);
          442  +  }
          443  +
          444  +  return rc;
          445  +}
          446  +
          447  +/*
          448  +** Once the sorter has been populated, this function is called to prepare
          449  +** for iterating through its contents in sorted order.
          450  +*/
          451  +int sqlite3VdbeSorterRewind(sqlite3 *db, VdbeCursor *pCsr, int *pbEof){
          452  +  int rc = SQLITE_OK;             /* Return code */
          453  +  int N;
          454  +  int i;
          455  +
          456  +  VdbeSorter *pSorter = pCsr->pSorter;
          457  +  BtCursor *p = pCsr->pCursor;    /* Cursor structure */
          458  +
          459  +  assert( pSorter );
          460  +  sqlite3BtreeCloseCursor(p);
          461  +
          462  +  while( rc==SQLITE_OK ){
          463  +    int iNext = 0;                /* Index of next segment to open */
          464  +    int iRoot = 0;                /* aRoot[] slot if merging to a new segment */
          465  +
          466  +    do {
          467  +      rc = vdbeSorterInitMerge(db, pCsr, iNext, &iNext);
          468  +
          469  +      if( rc==SQLITE_OK && (iRoot>0 || iNext<pSorter->nRoot) ){
          470  +        int pgno;
          471  +        int bEof = 0;
          472  +        rc = sqlite3BtreeCreateTable(pCsr->pBt, &pgno, BTREE_BLOBKEY);
          473  +        if( rc==SQLITE_OK ){
          474  +          pSorter->aRoot[iRoot] = pgno;
          475  +          rc = sqlite3BtreeCursor(pCsr->pBt, pgno, 1, pCsr->pKeyInfo, p);
          476  +        }
          477  +
          478  +        while( rc==SQLITE_OK && bEof==0 ){
          479  +          VdbeSorterIter *pIter = &pSorter->aIter[ pSorter->aTree[1] ];
          480  +          rc = sqlite3BtreeInsert(p, pIter->aKey, pIter->nKey, 0, 0, 0, 1, 0);
          481  +          if( rc==SQLITE_OK ){
          482  +            rc = sqlite3VdbeSorterNext(db, pCsr, &bEof);
          483  +          }
          484  +        }
          485  +        sqlite3BtreeCloseCursor(p);
          486  +        iRoot++;
          487  +      }
          488  +    } while( rc==SQLITE_OK && iNext<pSorter->nRoot );
          489  +
          490  +    if( iRoot==0 ) break;
          491  +    pSorter->nRoot = iRoot;
          492  +  }
          493  +
          494  +  *pbEof = (pSorter->aIter[pSorter->aTree[1]].pCsr==0);
          495  +  return rc;
          496  +}
          497  +
          498  +/*
          499  +** Advance to the next element in the sorter.
          500  +*/
          501  +int sqlite3VdbeSorterNext(sqlite3 *db, VdbeCursor *pCsr, int *pbEof){
          502  +  VdbeSorter *pSorter = pCsr->pSorter;
          503  +  int iPrev = pSorter->aTree[1];  /* Index of iterator to advance */
          504  +  int i;                          /* Index of aTree[] to recalculate */
          505  +  int rc;                         /* Return code */
          506  +
          507  +  rc = vdbeSorterIterNext(db, pCsr, &pSorter->aIter[iPrev]);
          508  +  for(i=(pSorter->nTree+iPrev)/2; rc==SQLITE_OK && i>0; i=i/2){
          509  +    rc = vdbeSorterDoCompare(pCsr, i);
          510  +  }
          511  +
          512  +  *pbEof = (pSorter->aIter[pSorter->aTree[1]].pCsr==0);
          513  +  return rc;
          514  +}
          515  +
          516  +/*
          517  +** Copy the current sorter key into the memory cell pOut.
          518  +*/
          519  +int sqlite3VdbeSorterRowkey(sqlite3 *db, VdbeCursor *pCsr, Mem *pOut){
          520  +  VdbeSorter *pSorter = pCsr->pSorter;
          521  +  VdbeSorterIter *pIter;
          522  +
          523  +  pIter = &pSorter->aIter[ pSorter->aTree[1] ];
          524  +  if( sqlite3VdbeMemGrow(pOut, pIter->nKey, 0) ){
          525  +    return SQLITE_NOMEM;
          526  +  }
          527  +  pOut->n = pIter->nKey;
          528  +  MemSetTypeFlag(pOut, MEM_Blob);
          529  +  memcpy(pOut->z, pIter->aKey, pIter->nKey);
          530  +
          531  +  return SQLITE_OK;
          532  +}
          533  +

Added test/index4.test.

            1  +# 2011 July 9
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#***********************************************************************
           11  +# This file implements regression tests for SQLite library.  The
           12  +# focus of this file is testing the CREATE INDEX statement.
           13  +#
           14  +
           15  +set testdir [file dirname $argv0]
           16  +source $testdir/tester.tcl
           17  +
           18  +set testprefix index4
           19  +
           20  +do_execsql_test 1.1 {
           21  +  BEGIN;
           22  +    CREATE TABLE t1(x);
           23  +    INSERT INTO t1 VALUES(randomblob(102));
           24  +    INSERT INTO t1 SELECT randomblob(102) FROM t1;     --     2
           25  +    INSERT INTO t1 SELECT randomblob(102) FROM t1;     --     4
           26  +    INSERT INTO t1 SELECT randomblob(102) FROM t1;     --     8
           27  +    INSERT INTO t1 SELECT randomblob(102) FROM t1;     --    16
           28  +    INSERT INTO t1 SELECT randomblob(102) FROM t1;     --    32
           29  +    INSERT INTO t1 SELECT randomblob(102) FROM t1;     --    64
           30  +    INSERT INTO t1 SELECT randomblob(102) FROM t1;     --   128
           31  +    INSERT INTO t1 SELECT randomblob(102) FROM t1;     --   256
           32  +    INSERT INTO t1 SELECT randomblob(102) FROM t1;     --   512
           33  +    INSERT INTO t1 SELECT randomblob(102) FROM t1;     --  1024
           34  +    INSERT INTO t1 SELECT randomblob(102) FROM t1;     --  2048
           35  +    INSERT INTO t1 SELECT randomblob(102) FROM t1;     --  4096
           36  +    INSERT INTO t1 SELECT randomblob(102) FROM t1;     --  8192
           37  +    INSERT INTO t1 SELECT randomblob(102) FROM t1;     -- 16384
           38  +    INSERT INTO t1 SELECT randomblob(102) FROM t1;     -- 32768
           39  +    INSERT INTO t1 SELECT randomblob(102) FROM t1;     -- 65536
           40  +  COMMIT;
           41  +}
           42  +
           43  +do_execsql_test 1.2 {
           44  +  CREATE INDEX i1 ON t1(x);
           45  +}
           46  +do_execsql_test 1.3 {
           47  +  PRAGMA integrity_check 
           48  +} {ok}
           49  +
           50  +# The same test again - this time with limited memory.
           51  +#
           52  +ifcapable memorymanage {
           53  +  set soft_limit [sqlite3_soft_heap_limit 50000]
           54  +
           55  +  db close
           56  +  sqlite3 db test.db
           57  +
           58  +  do_execsql_test 1.4 {
           59  +    PRAGMA cache_size = 10;
           60  +    CREATE INDEX i2 ON t1(x);
           61  +  }
           62  +  do_execsql_test 1.5 {
           63  +    PRAGMA integrity_check 
           64  +  } {ok}
           65  +
           66  +  sqlite3_soft_heap_limit $soft_limit
           67  +}
           68  +
           69  +
           70  +finish_test