/ Check-in [68e26c44]
Login

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

Overview
Comment:The build works again with -DSQLITE_OMIT_MERGE_SORT. The merge-sorter now avoids spilling to disk (letting the in-memory linked list grow without bound) if PRAGMA temp_store=3.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | merge-sort
Files: files | file ages | folders
SHA1: 68e26c4487696d194ee85370380e4b0e56d206ee
User & Date: drh 2011-09-03 00:17:51
Context
2011-09-03
14:36
Reduce the number of VdbeRecordUnpack() calls made in vdbesort.c. check-in: 666c2c3c user: dan tags: merge-sort
00:17
The build works again with -DSQLITE_OMIT_MERGE_SORT. The merge-sorter now avoids spilling to disk (letting the in-memory linked list grow without bound) if PRAGMA temp_store=3. check-in: 68e26c44 user: drh tags: merge-sort
2011-09-02
21:42
Remove some dead code. Fix a faulty assert(). Improve some variable names. check-in: a9a64592 user: drh tags: merge-sort
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/build.c.

  2331   2331     Vdbe *v;                       /* Generate code into this virtual machine */
  2332   2332     KeyInfo *pKey;                 /* KeyInfo for index */
  2333   2333     int regIdxKey;                 /* Registers containing the index key */
  2334   2334     int regRecord;                 /* Register holding assemblied index record */
  2335   2335     sqlite3 *db = pParse->db;      /* The database connection */
  2336   2336     int iDb = sqlite3SchemaToIndex(db, pIndex->pSchema);
  2337   2337   
  2338         -  /* Set bUseSorter to use OP_OpenSorter, or clear it to insert directly 
  2339         -  ** into the index. The sorter is used unless either OMIT_MERGE_SORT is
  2340         -  ** defined or the system is configured to store temp files in-memory. */
  2341         -#ifdef SQLITE_OMIT_MERGE_SORT
  2342         -  static const int bUseSorter = 0;
  2343         -#else
  2344         -  const int bUseSorter = !sqlite3TempInMemory(pParse->db);
  2345         -#endif
  2346         -
  2347   2338   #ifndef SQLITE_OMIT_AUTHORIZATION
  2348   2339     if( sqlite3AuthCheck(pParse, SQLITE_REINDEX, pIndex->zName, 0,
  2349   2340         db->aDb[iDb].zName ) ){
  2350   2341       return;
  2351   2342     }
  2352   2343   #endif
  2353   2344   
................................................................................
  2365   2356     pKey = sqlite3IndexKeyinfo(pParse, pIndex);
  2366   2357     sqlite3VdbeAddOp4(v, OP_OpenWrite, iIdx, tnum, iDb, 
  2367   2358                       (char *)pKey, P4_KEYINFO_HANDOFF);
  2368   2359     if( memRootPage>=0 ){
  2369   2360       sqlite3VdbeChangeP5(v, 1);
  2370   2361     }
  2371   2362   
         2363  +#ifndef SQLITE_OMIT_MERGE_SORT
  2372   2364     /* Open the sorter cursor if we are to use one. */
  2373         -  if( bUseSorter ){
  2374         -    iSorter = pParse->nTab++;
  2375         -    sqlite3VdbeAddOp4(v, OP_OpenSorter, iSorter, 0, 0, (char*)pKey, P4_KEYINFO);
  2376         -  }
         2365  +  iSorter = pParse->nTab++;
         2366  +  sqlite3VdbeAddOp4(v, OP_SorterOpen, iSorter, 0, 0, (char*)pKey, P4_KEYINFO);
         2367  +#endif
  2377   2368   
  2378   2369     /* Open the table. Loop through all rows of the table, inserting index
  2379   2370     ** records into the sorter. */
  2380   2371     sqlite3OpenTable(pParse, iTab, iDb, pTab, OP_OpenRead);
  2381   2372     addr1 = sqlite3VdbeAddOp2(v, OP_Rewind, iTab, 0);
  2382   2373     addr2 = addr1 + 1;
  2383   2374     regRecord = sqlite3GetTempReg(pParse);
  2384   2375     regIdxKey = sqlite3GenerateIndexKey(pParse, pIndex, iTab, regRecord, 1);
  2385   2376   
  2386         -  if( bUseSorter ){
  2387         -    sqlite3VdbeAddOp2(v, OP_SorterInsert, iSorter, regRecord);
  2388         -    sqlite3VdbeAddOp2(v, OP_Next, iTab, addr1+1);
  2389         -    sqlite3VdbeJumpHere(v, addr1);
  2390         -    addr1 = sqlite3VdbeAddOp2(v, OP_SorterSort, iSorter, 0);
  2391         -    if( pIndex->onError!=OE_None ){
  2392         -      int j2 = sqlite3VdbeCurrentAddr(v) + 3;
  2393         -      sqlite3VdbeAddOp2(v, OP_Goto, 0, j2);
  2394         -      addr2 = sqlite3VdbeCurrentAddr(v);
  2395         -      sqlite3VdbeAddOp3(v, OP_SorterCompare, iSorter, j2, regRecord);
  2396         -      sqlite3HaltConstraint(
  2397         -          pParse, OE_Abort, "indexed columns are not unique", P4_STATIC
  2398         -      );
  2399         -    }else{
  2400         -      addr2 = sqlite3VdbeCurrentAddr(v);
  2401         -    }
  2402         -    sqlite3VdbeAddOp2(v, OP_SorterData, iSorter, regRecord);
  2403         -  }else if( pIndex->onError!=OE_None ){
         2377  +#ifndef SQLITE_OMIT_MERGE_SORT
         2378  +  sqlite3VdbeAddOp2(v, OP_SorterInsert, iSorter, regRecord);
         2379  +  sqlite3VdbeAddOp2(v, OP_Next, iTab, addr1+1);
         2380  +  sqlite3VdbeJumpHere(v, addr1);
         2381  +  addr1 = sqlite3VdbeAddOp2(v, OP_SorterSort, iSorter, 0);
         2382  +  if( pIndex->onError!=OE_None ){
         2383  +    int j2 = sqlite3VdbeCurrentAddr(v) + 3;
         2384  +    sqlite3VdbeAddOp2(v, OP_Goto, 0, j2);
         2385  +    addr2 = sqlite3VdbeCurrentAddr(v);
         2386  +    sqlite3VdbeAddOp3(v, OP_SorterCompare, iSorter, j2, regRecord);
         2387  +    sqlite3HaltConstraint(
         2388  +        pParse, OE_Abort, "indexed columns are not unique", P4_STATIC
         2389  +    );
         2390  +  }else{
         2391  +    addr2 = sqlite3VdbeCurrentAddr(v);
         2392  +  }
         2393  +  sqlite3VdbeAddOp2(v, OP_SorterData, iSorter, regRecord);
         2394  +  sqlite3VdbeAddOp3(v, OP_IdxInsert, iIdx, regRecord, 1);
         2395  +  sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);
         2396  +#else
         2397  +  if( pIndex->onError!=OE_None ){
  2404   2398       const int regRowid = regIdxKey + pIndex->nColumn;
  2405   2399       const int j2 = sqlite3VdbeCurrentAddr(v) + 2;
  2406   2400       void * const pRegKey = SQLITE_INT_TO_PTR(regIdxKey);
  2407   2401   
  2408   2402       /* The registers accessed by the OP_IsUnique opcode were allocated
  2409   2403       ** using sqlite3GetTempRange() inside of the sqlite3GenerateIndexKey()
  2410   2404       ** call above. Just before that function was freed they were released
................................................................................
  2414   2408       ** we can be sure that no other temp registers have been allocated
  2415   2409       ** since sqlite3ReleaseTempRange() was called, it is safe to do so.
  2416   2410       */
  2417   2411       sqlite3VdbeAddOp4(v, OP_IsUnique, iIdx, j2, regRowid, pRegKey, P4_INT32);
  2418   2412       sqlite3HaltConstraint(
  2419   2413           pParse, OE_Abort, "indexed columns are not unique", P4_STATIC);
  2420   2414     }
  2421         -  sqlite3VdbeAddOp3(v, OP_IdxInsert, iIdx, regRecord, bUseSorter);
         2415  +  sqlite3VdbeAddOp3(v, OP_IdxInsert, iIdx, regRecord, 0);
  2422   2416     sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);
         2417  +#endif
  2423   2418     sqlite3ReleaseTempReg(pParse, regRecord);
  2424         -  sqlite3VdbeAddOp2(v, bUseSorter ? OP_SorterNext : OP_Next, iSorter, addr2);
         2419  +  sqlite3VdbeAddOp2(v, OP_SorterNext, iSorter, addr2);
  2425   2420     sqlite3VdbeJumpHere(v, addr1);
  2426   2421   
  2427   2422     sqlite3VdbeAddOp1(v, OP_Close, iTab);
  2428   2423     sqlite3VdbeAddOp1(v, OP_Close, iIdx);
  2429   2424     sqlite3VdbeAddOp1(v, OP_Close, iSorter);
  2430   2425   }
  2431   2426   

Changes to src/sqliteInt.h.

   368    368   ** Provide a default value for SQLITE_TEMP_STORE in case it is not specified
   369    369   ** on the command-line
   370    370   */
   371    371   #ifndef SQLITE_TEMP_STORE
   372    372   # define SQLITE_TEMP_STORE 1
   373    373   #endif
   374    374   
   375         -/*
   376         -** If all temporary storage is in-memory, then omit the external merge-sort
   377         -** logic since it is superfluous.
   378         -*/
   379         -#if SQLITE_TEMP_STORE==3 && !defined(SQLITE_OMIT_MERGE_SORT)
   380         -# define SQLITE_OMIT_MERGE_SORT
   381         -#endif
   382         -
   383    375   /*
   384    376   ** GCC does not define the offsetof() macro so we'll have to do it
   385    377   ** ourselves.
   386    378   */
   387    379   #ifndef offsetof
   388    380   #define offsetof(STRUCTURE,FIELD) ((int)((char*)&((STRUCTURE*)0)->FIELD))
   389    381   #endif

Changes to src/vdbe.c.

  3211   3211   
  3212   3212   /* Opcode: OpenSorter P1 P2 * P4 *
  3213   3213   **
  3214   3214   ** This opcode works like OP_OpenEphemeral except that it opens
  3215   3215   ** a transient index that is specifically designed to sort large
  3216   3216   ** tables using an external merge-sort algorithm.
  3217   3217   */
  3218         -case OP_SorterOpen:
  3219         -case OP_OpenSorter: {
         3218  +case OP_SorterOpen: {
  3220   3219     VdbeCursor *pCx;
         3220  +#ifndef SQLITE_OMIT_MERGE_SORT
  3221   3221     pCx = allocateCursor(p, pOp->p1, pOp->p2, -1, 1);
  3222   3222     if( pCx==0 ) goto no_mem;
  3223   3223     pCx->pKeyInfo = pOp->p4.pKeyInfo;
  3224   3224     pCx->pKeyInfo->enc = ENC(p->db);
  3225   3225     pCx->isSorter = 1;
  3226   3226     rc = sqlite3VdbeSorterInit(db, pCx);
         3227  +#else
         3228  +  pOp->opcode = OP_OpenEphemeral;
         3229  +  pc--;
         3230  +#endif
  3227   3231     break;
  3228   3232   }
  3229   3233   
  3230   3234   /* Opcode: OpenPseudo P1 P2 P3 * *
  3231   3235   **
  3232   3236   ** Open a new cursor that points to a fake table that contains a single
  3233   3237   ** row of data.  The content of that one row in the content of memory
................................................................................
  4098   4102   
  4099   4103   /* Opcode: SorterData P1 P2 * * *
  4100   4104   **
  4101   4105   ** Write into register P2 the current sorter data for sorter cursor P1.
  4102   4106   */
  4103   4107   case OP_SorterData: {
  4104   4108     VdbeCursor *pC;
         4109  +#ifndef SQLITE_OMIT_MERGE_SORT
  4105   4110     pOut = &aMem[pOp->p2];
  4106   4111     pC = p->apCsr[pOp->p1];
  4107   4112     assert( pC->isSorter );
  4108   4113     rc = sqlite3VdbeSorterRowkey(pC, pOut);
         4114  +#else
         4115  +  pOp->opcode = OP_RowKey;
         4116  +  pc--;
         4117  +#endif
  4109   4118     break;
  4110   4119   }
  4111   4120   
  4112   4121   /* Opcode: RowData P1 P2 * * *
  4113   4122   **
  4114   4123   ** Write into register P2 the complete row data for cursor P1.
  4115   4124   ** There is no interpretation of the data.  
................................................................................
  4144   4153     pC = p->apCsr[pOp->p1];
  4145   4154     assert( pC->isSorter==0 );
  4146   4155     assert( pC->isTable || pOp->opcode!=OP_RowData );
  4147   4156     assert( pC->isIndex || pOp->opcode==OP_RowData );
  4148   4157     assert( pC!=0 );
  4149   4158     assert( pC->nullRow==0 );
  4150   4159     assert( pC->pseudoTableReg==0 );
  4151         -  assert( pC->isSorter==(pOp->opcode==OP_SorterData) );
  4152         -
         4160  +  assert( !pC->isSorter );
  4153   4161     assert( pC->pCursor!=0 );
  4154   4162     pCrsr = pC->pCursor;
  4155   4163     assert( sqlite3BtreeCursorIsValid(pCrsr) );
  4156   4164   
  4157   4165     /* The OP_RowKey and OP_RowData opcodes always follow OP_NotExists or
  4158   4166     ** OP_Rewind/Op_Next with no intervening instructions that might invalidate
  4159   4167     ** the cursor.  Hence the following sqlite3VdbeCursorMoveto() call is always
................................................................................
  4303   4311   ** then rewinding that index and playing it back from beginning to
  4304   4312   ** end.  We use the OP_Sort opcode instead of OP_Rewind to do the
  4305   4313   ** rewinding so that the global variable will be incremented and
  4306   4314   ** regression tests can determine whether or not the optimizer is
  4307   4315   ** correctly optimizing out sorts.
  4308   4316   */
  4309   4317   case OP_SorterSort:    /* jump */
         4318  +#ifdef SQLITE_OMIT_MERGE_SORT
         4319  +  pOp->opcode = OP_Sort;
         4320  +#endif
  4310   4321   case OP_Sort: {        /* jump */
  4311   4322   #ifdef SQLITE_TEST
  4312   4323     sqlite3_sort_count++;
  4313   4324     sqlite3_search_count--;
  4314   4325   #endif
  4315   4326     p->aCounter[SQLITE_STMTSTATUS_SORT-1]++;
  4316   4327     /* Fall through into OP_Rewind */
................................................................................
  4381   4392   ** P4 is always of type P4_ADVANCE. The function pointer points to
  4382   4393   ** sqlite3BtreePrevious().
  4383   4394   **
  4384   4395   ** If P5 is positive and the jump is taken, then event counter
  4385   4396   ** number P5-1 in the prepared statement is incremented.
  4386   4397   */
  4387   4398   case OP_SorterNext:    /* jump */
         4399  +#ifdef SQLITE_OMIT_MERGE_SORT
         4400  +  pOp->opcode = OP_Next;
         4401  +#endif
  4388   4402   case OP_Prev:          /* jump */
  4389   4403   case OP_Next: {        /* jump */
  4390   4404     VdbeCursor *pC;
  4391   4405     int res;
  4392   4406   
  4393   4407     CHECK_FOR_INTERRUPT;
  4394   4408     assert( pOp->p1>=0 && pOp->p1<p->nCursor );
................................................................................
  4430   4444   **
  4431   4445   ** P3 is a flag that provides a hint to the b-tree layer that this
  4432   4446   ** insert is likely to be an append.
  4433   4447   **
  4434   4448   ** This instruction only works for indices.  The equivalent instruction
  4435   4449   ** for tables is OP_Insert.
  4436   4450   */
  4437         -case OP_SorterInsert:
         4451  +case OP_SorterInsert:       /* in2 */
         4452  +#ifdef SQLITE_OMIT_MERGE_SORT
         4453  +  pOp->opcode = OP_IdxInsert;
         4454  +#endif
  4438   4455   case OP_IdxInsert: {        /* in2 */
  4439   4456     VdbeCursor *pC;
  4440   4457     BtCursor *pCrsr;
  4441   4458     int nKey;
  4442   4459     const char *zKey;
  4443   4460   
  4444   4461     assert( pOp->p1>=0 && pOp->p1<p->nCursor );

Changes to src/vdbeInt.h.

    61     61     Bool isOrdered;       /* True if the underlying table is BTREE_UNORDERED */
    62     62     Bool isSorter;        /* True if a new-style sorter */
    63     63     sqlite3_vtab_cursor *pVtabCursor;  /* The cursor for a virtual table */
    64     64     const sqlite3_module *pModule;     /* Module for cursor pVtabCursor */
    65     65     i64 seqCount;         /* Sequence counter */
    66     66     i64 movetoTarget;     /* Argument to the deferred sqlite3BtreeMoveto() */
    67     67     i64 lastRowid;        /* Last rowid from a Next or NextIdx operation */
    68         -  VdbeSorter *pSorter;  /* Sorter object for OP_OpenSorter cursors */
           68  +  VdbeSorter *pSorter;  /* Sorter object for OP_SorterOpen cursors */
    69     69   
    70     70     /* Result of last sqlite3BtreeMoveto() done by an OP_NotExists or 
    71     71     ** OP_IsUnique opcode on this cursor. */
    72     72     int seekResult;
    73     73   
    74     74     /* Cached information about the header for the data record that the
    75     75     ** cursor is currently pointing to.  Only valid if cacheStatus matches

Changes to src/vdbesort.c.

   405    405   
   406    406     assert( pCsr->pKeyInfo && pCsr->pBt==0 );
   407    407     pCsr->pSorter = pSorter = sqlite3DbMallocZero(db, sizeof(VdbeSorter));
   408    408     if( pSorter==0 ){
   409    409       return SQLITE_NOMEM;
   410    410     }
   411    411   
   412         -  pgsz = sqlite3BtreeGetPageSize(db->aDb[0].pBt);
   413         -  pSorter->mnPmaSize = SORTER_MIN_WORKING * pgsz;
   414         -  mxCache = db->aDb[0].pSchema->cache_size;
   415         -  if( mxCache<SORTER_MIN_WORKING ) mxCache = SORTER_MIN_WORKING;
   416         -  pSorter->mxPmaSize = mxCache * pgsz;
          412  +  if( !sqlite3TempInMemory(db) ){
          413  +    pgsz = sqlite3BtreeGetPageSize(db->aDb[0].pBt);
          414  +    pSorter->mnPmaSize = SORTER_MIN_WORKING * pgsz;
          415  +    mxCache = db->aDb[0].pSchema->cache_size;
          416  +    if( mxCache<SORTER_MIN_WORKING ) mxCache = SORTER_MIN_WORKING;
          417  +    pSorter->mxPmaSize = mxCache * pgsz;
          418  +  }
   417    419   
   418    420     return SQLITE_OK;
   419    421   }
   420    422   
   421    423   /*
   422    424   ** Free the list of sorted records starting at pRecord.
   423    425   */
................................................................................
   662    664     **
   663    665     **   * The total memory allocated for the in-memory list is greater 
   664    666     **     than (page-size * cache-size), or
   665    667     **
   666    668     **   * The total memory allocated for the in-memory list is greater 
   667    669     **     than (page-size * 10) and sqlite3HeapNearlyFull() returns true.
   668    670     */
   669         -  if( rc==SQLITE_OK && (
          671  +  if( rc==SQLITE_OK && pSorter->mxPmaSize>0 && (
   670    672           (pSorter->nInMemory>pSorter->mxPmaSize)
   671    673        || (pSorter->nInMemory>pSorter->mnPmaSize && sqlite3HeapNearlyFull())
   672    674     )){
   673    675       rc = vdbeSorterListToPMA(db, pCsr);
   674    676       pSorter->nInMemory = 0;
   675    677     }
   676    678