/ Check-in [d3e96da2]
Login

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

Overview
Comment:Defer the {quote: MoveTo} opcode in VDBE until the data is actually needed. Sometimes the data is never needed, resulting in a performance increase. On an indexed order search with a large OFFSET, queries times can be an order of magnitude faster. (CVS 1165)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:d3e96da20d269a068188915b3cc0eb02d330d316
User & Date: drh 2004-01-07 18:52:57
Context
2004-01-07
19:24
Permit sqlite_exec() to be called from within user-defined functions. (CVS 1166) check-in: 03636c94 user: drh tags: trunk
18:52
Defer the {quote: MoveTo} opcode in VDBE until the data is actually needed. Sometimes the data is never needed, resulting in a performance increase. On an indexed order search with a large OFFSET, queries times can be an order of magnitude faster. (CVS 1165) check-in: d3e96da2 user: drh tags: trunk
03:41
Make it safe to call sqliteMalloc() with a request for 0 bytes. Ticket #534. (CVS 1164) check-in: 6c858db2 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Show Whitespace Changes Patch

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.246 2003/12/23 02:17:35 drh Exp $
           46  +** $Id: vdbe.c,v 1.247 2004/01/07 18:52:57 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   /*
................................................................................
   358    358       pTail->pNext = pLeft;
   359    359     }else if( pRight ){
   360    360       pTail->pNext = pRight;
   361    361     }
   362    362     return sHead.pNext;
   363    363   }
   364    364   
   365         -/*
   366         -** Convert an integer in between the native integer format and
   367         -** the bigEndian format used as the record number for tables.
   368         -**
   369         -** The bigEndian format (most significant byte first) is used for
   370         -** record numbers so that records will sort into the correct order
   371         -** even though memcmp() is used to compare the keys.  On machines
   372         -** whose native integer format is little endian (ex: i486) the
   373         -** order of bytes is reversed.  On native big-endian machines
   374         -** (ex: Alpha, Sparc, Motorola) the byte order is the same.
   375         -**
   376         -** This function is its own inverse.  In other words
   377         -**
   378         -**         X == byteSwap(byteSwap(X))
   379         -*/
   380         -static int byteSwap(int x){
   381         -  union {
   382         -     char zBuf[sizeof(int)];
   383         -     int i;
   384         -  } ux;
   385         -  ux.zBuf[3] = x&0xff;
   386         -  ux.zBuf[2] = (x>>8)&0xff;
   387         -  ux.zBuf[1] = (x>>16)&0xff;
   388         -  ux.zBuf[0] = (x>>24)&0xff;
   389         -  return ux.i;
   390         -}
   391         -
   392         -/*
   393         -** When converting from the native format to the key format and back
   394         -** again, in addition to changing the byte order we invert the high-order
   395         -** bit of the most significant byte.  This causes negative numbers to
   396         -** sort before positive numbers in the memcmp() function.
   397         -*/
   398         -#define keyToInt(X)   (byteSwap(X) ^ 0x80000000)
   399         -#define intToKey(X)   (byteSwap((X) ^ 0x80000000))
   400         -
   401    365   /*
   402    366   ** Code contained within the VERIFY() macro is not needed for correct
   403    367   ** execution.  It is there only to catch errors.  So when we compile
   404    368   ** with NDEBUG=1, the VERIFY() code is omitted.
   405    369   */
   406    370   #ifdef NDEBUG
   407    371   # define VERIFY(X)
................................................................................
  2593   2557     Cursor *pC;
  2594   2558   
  2595   2559     VERIFY( if( tos<0 ) goto not_enough_stack; )
  2596   2560     assert( i>=0 && i<p->nCursor );
  2597   2561     pC = &p->aCsr[i];
  2598   2562     if( pC->pCursor!=0 ){
  2599   2563       int res, oc;
         2564  +    pC->nullRow = 0;
  2600   2565       if( aStack[tos].flags & STK_Int ){
  2601   2566         int iKey = intToKey(aStack[tos].i);
         2567  +      if( pOp->p2==0 && pOp->opcode==OP_MoveTo ){
         2568  +        pC->movetoTarget = iKey;
         2569  +        pC->deferredMoveto = 1;
         2570  +        POPSTACK;
         2571  +        break;
         2572  +      }
  2602   2573         sqliteBtreeMoveto(pC->pCursor, (char*)&iKey, sizeof(int), &res);
  2603   2574         pC->lastRecno = aStack[tos].i;
  2604   2575         pC->recnoIsValid = res==0;
  2605   2576       }else{
  2606   2577         Stringify(p, tos);
  2607   2578         sqliteBtreeMoveto(pC->pCursor, zStack[tos], aStack[tos].n, &res);
  2608   2579         pC->recnoIsValid = 0;
  2609   2580       }
  2610         -    pC->nullRow = 0;
         2581  +    pC->deferredMoveto = 0;
  2611   2582       sqlite_search_count++;
  2612   2583       oc = pOp->opcode;
  2613   2584       if( oc==OP_MoveTo && res<0 ){
  2614   2585         sqliteBtreeNext(pC->pCursor, &res);
  2615   2586         pC->recnoIsValid = 0;
  2616   2587         if( res && pOp->p2>0 ){
  2617   2588           pc = pOp->p2 - 1;
................................................................................
  2678   2649     Cursor *pC;
  2679   2650     VERIFY( if( tos<0 ) goto not_enough_stack; )
  2680   2651     if( VERIFY( i>=0 && i<p->nCursor && ) (pC = &p->aCsr[i])->pCursor!=0 ){
  2681   2652       int res, rx;
  2682   2653       Stringify(p, tos);
  2683   2654       rx = sqliteBtreeMoveto(pC->pCursor, zStack[tos], aStack[tos].n, &res);
  2684   2655       alreadyExists = rx==SQLITE_OK && res==0;
         2656  +    pC->deferredMoveto = 0;
  2685   2657     }
  2686   2658     if( pOp->opcode==OP_Found ){
  2687   2659       if( alreadyExists ) pc = pOp->p2 - 1;
  2688   2660     }else{
  2689   2661       if( !alreadyExists ) pc = pOp->p2 - 1;
  2690   2662     }
  2691   2663     if( pOp->opcode!=OP_Distinct ){
................................................................................
  2739   2711       zKey = zStack[nos];
  2740   2712       nKey = aStack[nos].n;
  2741   2713       assert( nKey >= 4 );
  2742   2714   
  2743   2715       /* Search for an entry in P1 where all but the last four bytes match K.
  2744   2716       ** If there is no such entry, jump immediately to P2.
  2745   2717       */
         2718  +    assert( p->aCsr[i].deferredMoveto==0 );
  2746   2719       rc = sqliteBtreeMoveto(pCrsr, zKey, nKey-4, &res);
  2747   2720       if( rc!=SQLITE_OK ) goto abort_due_to_error;
  2748   2721       if( res<0 ){
  2749   2722         rc = sqliteBtreeNext(pCrsr, &res);
  2750   2723         if( res ){
  2751   2724           pc = pOp->p2 - 1;
  2752   2725           break;
................................................................................
  2907   2880         db->priorNewRowid = v;
  2908   2881         if( rx==SQLITE_OK && res==0 ){
  2909   2882           rc = SQLITE_FULL;
  2910   2883           goto abort_due_to_error;
  2911   2884         }
  2912   2885       }
  2913   2886       pC->recnoIsValid = 0;
         2887  +    pC->deferredMoveto = 0;
  2914   2888     }
  2915   2889     p->tos++;
  2916   2890     aStack[p->tos].i = v;
  2917   2891     aStack[p->tos].flags = STK_Int;
  2918   2892     break;
  2919   2893   }
  2920   2894   
................................................................................
  2989   2963         }
  2990   2964         pC->nullRow = 0;
  2991   2965       }else{
  2992   2966         rc = sqliteBtreeInsert(pC->pCursor, zKey, nKey,
  2993   2967                             zStack[tos], aStack[tos].n);
  2994   2968       }
  2995   2969       pC->recnoIsValid = 0;
         2970  +    pC->deferredMoveto = 0;
  2996   2971     }
  2997   2972     POPSTACK;
  2998   2973     POPSTACK;
  2999   2974     break;
  3000   2975   }
  3001   2976   
  3002   2977   /* Opcode: Delete P1 P2 *
................................................................................
  3015   2990   */
  3016   2991   case OP_Delete: {
  3017   2992     int i = pOp->p1;
  3018   2993     Cursor *pC;
  3019   2994     assert( i>=0 && i<p->nCursor );
  3020   2995     pC = &p->aCsr[i];
  3021   2996     if( pC->pCursor!=0 ){
         2997  +    sqliteVdbeCursorMoveto(pC);
  3022   2998       rc = sqliteBtreeDelete(pC->pCursor);
  3023   2999       pC->nextRowidValid = 0;
  3024   3000     }
  3025   3001     if( pOp->p2 ) db->nChange++;
  3026   3002     break;
  3027   3003   }
  3028   3004   
................................................................................
  3057   3033   
  3058   3034     assert( i>=0 && i<p->nCursor );
  3059   3035     pC = &p->aCsr[i];
  3060   3036     if( pC->nullRow ){
  3061   3037       aStack[tos].flags = STK_Null;
  3062   3038     }else if( pC->pCursor!=0 ){
  3063   3039       BtCursor *pCrsr = pC->pCursor;
         3040  +    sqliteVdbeCursorMoveto(pC);
  3064   3041       if( pC->nullRow ){
  3065   3042         aStack[tos].flags = STK_Null;
  3066   3043         break;
  3067   3044       }else if( pC->keyAsData ){
  3068   3045         sqliteBtreeKeySize(pCrsr, &n);
  3069   3046       }else{
  3070   3047         sqliteBtreeDataSize(pCrsr, &n);
................................................................................
  3127   3104     assert( i<p->nCursor );
  3128   3105     if( i<0 ){
  3129   3106       VERIFY( if( tos+i<0 ) goto bad_instruction; )
  3130   3107       VERIFY( if( (aStack[tos+i].flags & STK_Str)==0 ) goto bad_instruction; )
  3131   3108       zRec = zStack[tos+i];
  3132   3109       payloadSize = aStack[tos+i].n;
  3133   3110     }else if( (pC = &p->aCsr[i])->pCursor!=0 ){
         3111  +    sqliteVdbeCursorMoveto(pC);
  3134   3112       zRec = 0;
  3135   3113       pCrsr = pC->pCursor;
  3136   3114       if( pC->nullRow ){
  3137   3115         payloadSize = 0;
  3138   3116       }else if( pC->keyAsData ){
  3139   3117         sqliteBtreeKeySize(pCrsr, &payloadSize);
  3140   3118       }else{
................................................................................
  3233   3211   case OP_Recno: {
  3234   3212     int i = pOp->p1;
  3235   3213     int tos = ++p->tos;
  3236   3214     Cursor *pC;
  3237   3215     int v;
  3238   3216   
  3239   3217     assert( i>=0 && i<p->nCursor );
  3240         -  if( (pC = &p->aCsr[i])->recnoIsValid ){
         3218  +  pC = &p->aCsr[i];
         3219  +  sqliteVdbeCursorMoveto(pC);
         3220  +  if( pC->recnoIsValid ){
  3241   3221       v = pC->lastRecno;
  3242   3222     }else if( pC->pseudoTable ){
  3243   3223       v = keyToInt(pC->iKey);
  3244   3224     }else if( pC->nullRow || pC->pCursor==0 ){
  3245   3225       aStack[tos].flags = STK_Null;
  3246   3226       break;
  3247   3227     }else{
................................................................................
  3272   3252   
  3273   3253     VERIFY( if( !p->aCsr[i].keyAsData ) goto bad_instruction; )
  3274   3254     VERIFY( if( p->aCsr[i].pseudoTable ) goto bad_instruction; )
  3275   3255     if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
  3276   3256       int amt;
  3277   3257       char *z;
  3278   3258   
         3259  +    sqliteVdbeCursorMoveto(&p->aCsr[i]);
  3279   3260       sqliteBtreeKeySize(pCrsr, &amt);
  3280   3261       if( amt<=0 ){
  3281   3262         rc = SQLITE_CORRUPT;
  3282   3263         goto abort_due_to_error;
  3283   3264       }
  3284   3265       if( amt>NBFS ){
  3285   3266         z = sqliteMallocRaw( amt );
................................................................................
  3325   3306     BtCursor *pCrsr;
  3326   3307   
  3327   3308     assert( i>=0 && i<p->nCursor );
  3328   3309     pC = &p->aCsr[i];
  3329   3310     if( (pCrsr = pC->pCursor)!=0 ){
  3330   3311       int res;
  3331   3312       rc = sqliteBtreeLast(pCrsr, &res);
  3332         -    p->aCsr[i].nullRow = res;
         3313  +    pC->nullRow = res;
         3314  +    pC->deferredMoveto = 0;
  3333   3315       if( res && pOp->p2>0 ){
  3334   3316         pc = pOp->p2 - 1;
  3335   3317       }
  3336   3318     }else{
  3337   3319       pC->nullRow = 0;
  3338   3320     }
  3339   3321     break;
................................................................................
  3355   3337     assert( i>=0 && i<p->nCursor );
  3356   3338     pC = &p->aCsr[i];
  3357   3339     if( (pCrsr = pC->pCursor)!=0 ){
  3358   3340       int res;
  3359   3341       rc = sqliteBtreeFirst(pCrsr, &res);
  3360   3342       pC->atFirst = res==0;
  3361   3343       pC->nullRow = res;
         3344  +    pC->deferredMoveto = 0;
  3362   3345       if( res && pOp->p2>0 ){
  3363   3346         pc = pOp->p2 - 1;
  3364   3347       }
  3365   3348     }else{
  3366   3349       pC->nullRow = 0;
  3367   3350     }
  3368   3351     break;
................................................................................
  3393   3376     assert( pOp->p1>=0 && pOp->p1<p->nCursor );
  3394   3377     pC = &p->aCsr[pOp->p1];
  3395   3378     if( (pCrsr = pC->pCursor)!=0 ){
  3396   3379       int res;
  3397   3380       if( pC->nullRow ){
  3398   3381         res = 1;
  3399   3382       }else{
         3383  +      assert( pC->deferredMoveto==0 );
  3400   3384         rc = pOp->opcode==OP_Next ? sqliteBtreeNext(pCrsr, &res) :
  3401   3385                                     sqliteBtreePrevious(pCrsr, &res);
  3402   3386         pC->nullRow = res;
  3403   3387       }
  3404   3388       if( res==0 ){
  3405   3389         pc = pOp->p2 - 1;
  3406   3390         sqlite_search_count++;
................................................................................
  3454   3438             res = +1;
  3455   3439           }else{
  3456   3440             break;
  3457   3441           }
  3458   3442         }
  3459   3443       }
  3460   3444       rc = sqliteBtreeInsert(pCrsr, zKey, nKey, "", 0);
         3445  +    assert( p->aCsr[i].deferredMoveto==0 );
  3461   3446     }
  3462   3447     POPSTACK;
  3463   3448     break;
  3464   3449   }
  3465   3450   
  3466   3451   /* Opcode: IdxDelete P1 * *
  3467   3452   **
................................................................................
  3475   3460     VERIFY( if( tos<0 ) goto not_enough_stack; )
  3476   3461     if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
  3477   3462       int rx, res;
  3478   3463       rx = sqliteBtreeMoveto(pCrsr, zStack[tos], aStack[tos].n, &res);
  3479   3464       if( rx==SQLITE_OK && res==0 ){
  3480   3465         rc = sqliteBtreeDelete(pCrsr);
  3481   3466       }
         3467  +    assert( p->aCsr[i].deferredMoveto==0 );
  3482   3468     }
  3483   3469     POPSTACK;
  3484   3470     break;
  3485   3471   }
  3486   3472   
  3487   3473   /* Opcode: IdxRecno P1 * *
  3488   3474   **
................................................................................
  3497   3483     int i = pOp->p1;
  3498   3484     int tos = ++p->tos;
  3499   3485     BtCursor *pCrsr;
  3500   3486   
  3501   3487     if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
  3502   3488       int v;
  3503   3489       int sz;
         3490  +    assert( p->aCsr[i].deferredMoveto==0 );
  3504   3491       sqliteBtreeKeySize(pCrsr, &sz);
  3505   3492       if( sz<sizeof(u32) ){
  3506   3493         aStack[tos].flags = STK_Null;
  3507   3494       }else{
  3508   3495         sqliteBtreeKey(pCrsr, sz - sizeof(u32), sizeof(u32), (char*)&v);
  3509   3496         v = keyToInt(v);
  3510   3497         aStack[tos].i = v;
................................................................................
  3546   3533     int tos = p->tos;
  3547   3534     BtCursor *pCrsr;
  3548   3535   
  3549   3536     if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
  3550   3537       int res, rc;
  3551   3538    
  3552   3539       Stringify(p, tos);
         3540  +    assert( p->aCsr[i].deferredMoveto==0 );
  3553   3541       rc = sqliteBtreeKeyCompare(pCrsr, zStack[tos], aStack[tos].n, 4, &res);
  3554   3542       if( rc!=SQLITE_OK ){
  3555   3543         break;
  3556   3544       }
  3557   3545       if( pOp->opcode==OP_IdxLT ){
  3558   3546         res = -res;
  3559   3547       }else if( pOp->opcode==OP_IdxGE ){

Changes to src/vdbeInt.h.

    12     12   ** This is the header file for information that is private to the
    13     13   ** VDBE.  This information used to all be at the top of the single
    14     14   ** source code file "vdbe.c".  When that file became too big (over
    15     15   ** 6000 lines long) it was split up into several smaller files and
    16     16   ** this header information was factored out.
    17     17   */
    18     18   
           19  +/*
           20  +** When converting from the native format to the key format and back
           21  +** again, in addition to changing the byte order we invert the high-order
           22  +** bit of the most significant byte.  This causes negative numbers to
           23  +** sort before positive numbers in the memcmp() function.
           24  +*/
           25  +#define keyToInt(X)   (sqliteVdbeByteSwap(X) ^ 0x80000000)
           26  +#define intToKey(X)   (sqliteVdbeByteSwap((X) ^ 0x80000000))
           27  +
    19     28   /*
    20     29   ** The makefile scans this source file and creates the following
    21     30   ** array of string constants which are the names of all VDBE opcodes.
    22     31   ** This array is defined in a separate source code file named opcode.c
    23     32   ** which is automatically generated by the makefile.
    24     33   */
    25     34   extern char *sqliteOpcodeNames[];
................................................................................
    58     67     Bool recnoIsValid;    /* True if lastRecno is valid */
    59     68     Bool keyAsData;       /* The OP_Column command works on key instead of data */
    60     69     Bool atFirst;         /* True if pointing to first entry */
    61     70     Bool useRandomRowid;  /* Generate new record numbers semi-randomly */
    62     71     Bool nullRow;         /* True if pointing to a row with no data */
    63     72     Bool nextRowidValid;  /* True if the nextRowid field is valid */
    64     73     Bool pseudoTable;     /* This is a NEW or OLD pseudo-tables of a trigger */
           74  +  Bool deferredMoveto;  /* A call to sqliteBtreeMoveto() is needed */
           75  +  int movetoTarget;     /* Argument to the deferred sqliteBtreeMoveto() */
    65     76     Btree *pBt;           /* Separate file holding temporary table */
    66     77     int nData;            /* Number of bytes in pData */
    67     78     char *pData;          /* Data for a NEW or OLD pseudo-table */
    68     79     int iKey;             /* Key for the NEW or OLD pseudo-table row */
    69     80   };
    70     81   typedef struct Cursor Cursor;
    71     82   
................................................................................
   290    301   ** Function prototypes
   291    302   */
   292    303   void sqliteVdbeCleanupCursor(Cursor*);
   293    304   void sqliteVdbeSorterReset(Vdbe*);
   294    305   void sqliteVdbeAggReset(Agg*);
   295    306   void sqliteVdbeKeylistFree(Keylist*);
   296    307   void sqliteVdbePopStack(Vdbe*,int);
          308  +int sqliteVdbeCursorMoveto(Cursor*);
          309  +int sqliteVdbeByteSwap(int);
   297    310   #if !defined(NDEBUG) || defined(VDBE_PROFILE)
   298    311   void sqliteVdbePrintOp(FILE*, int, Op*);
   299    312   #endif

Changes to src/vdbeaux.c.

   988    988     }
   989    989     sqliteFree(p->aOp);
   990    990     sqliteFree(p->aLabel);
   991    991     sqliteFree(p->aStack);
   992    992     p->magic = VDBE_MAGIC_DEAD;
   993    993     sqliteFree(p);
   994    994   }
          995  +
          996  +/*
          997  +** Convert an integer in between the native integer format and
          998  +** the bigEndian format used as the record number for tables.
          999  +**
         1000  +** The bigEndian format (most significant byte first) is used for
         1001  +** record numbers so that records will sort into the correct order
         1002  +** even though memcmp() is used to compare the keys.  On machines
         1003  +** whose native integer format is little endian (ex: i486) the
         1004  +** order of bytes is reversed.  On native big-endian machines
         1005  +** (ex: Alpha, Sparc, Motorola) the byte order is the same.
         1006  +**
         1007  +** This function is its own inverse.  In other words
         1008  +**
         1009  +**         X == byteSwap(byteSwap(X))
         1010  +*/
         1011  +int sqliteVdbeByteSwap(int x){
         1012  +  union {
         1013  +     char zBuf[sizeof(int)];
         1014  +     int i;
         1015  +  } ux;
         1016  +  ux.zBuf[3] = x&0xff;
         1017  +  ux.zBuf[2] = (x>>8)&0xff;
         1018  +  ux.zBuf[1] = (x>>16)&0xff;
         1019  +  ux.zBuf[0] = (x>>24)&0xff;
         1020  +  return ux.i;
         1021  +}
         1022  +
         1023  +/*
         1024  +** If a MoveTo operation is pending on the given cursor, then do that
         1025  +** MoveTo now.  Return an error code.  If no MoveTo is pending, this
         1026  +** routine does nothing and returns SQLITE_OK.
         1027  +*/
         1028  +int sqliteVdbeCursorMoveto(Cursor *p){
         1029  +  if( p->deferredMoveto ){
         1030  +    int res;
         1031  +    extern int sqlite_search_count;
         1032  +    sqliteBtreeMoveto(p->pCursor, (char*)&p->movetoTarget, sizeof(int), &res);
         1033  +    p->lastRecno = keyToInt(p->movetoTarget);
         1034  +    p->recnoIsValid = res==0;
         1035  +    if( res<0 ){
         1036  +      sqliteBtreeNext(p->pCursor, &res);
         1037  +    }
         1038  +    sqlite_search_count++;
         1039  +    p->deferredMoveto = 0;
         1040  +  }
         1041  +  return SQLITE_OK;
         1042  +}