SQLite

Check-in [c4734b881a]
Login

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

Overview
Comment:Combine the rowid and WITHOUT ROWID paths for DELETE into a single path.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | optimize-delete
Files: files | file ages | folders
SHA1: c4734b881a64a9d21d03a14e901785797577fbd8
User & Date: drh 2013-11-16 22:48:52.173
Context
2013-11-16
23:03
Fix an OOM-recovery problem in the DELETE code generator. (check-in: dc7be158b8 user: drh tags: optimize-delete)
22:48
Combine the rowid and WITHOUT ROWID paths for DELETE into a single path. (check-in: c4734b881a user: drh tags: optimize-delete)
20:45
The one-pass optimization is now working for DELETE on WITHOUT ROWID tables. (check-in: e4d220a381 user: drh tags: optimize-delete)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/delete.c.
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246











247
248
249
250
251
252
253
254
  Parse *pParse,         /* The parser context */
  SrcList *pTabList,     /* The table from which we should delete things */
  Expr *pWhere           /* The WHERE clause.  May be null */
){
  Vdbe *v;               /* The virtual database engine */
  Table *pTab;           /* The table from which records will be deleted */
  const char *zDb;       /* Name of database holding pTab */
  int end, addr = 0;     /* A couple addresses of generated code */
  int i;                 /* Loop counter */
  WhereInfo *pWInfo;     /* Information about the WHERE clause */
  Index *pIdx;           /* For looping over indices of the table */
  int iTabCur;           /* Cursor number for the table */
  int iDataCur;          /* VDBE cursor for the canonical data source */
  int iIdxCur;           /* Cursor number of the first index */
  int nIdx;              /* Number of indices */
  sqlite3 *db;           /* Main database structure */
  AuthContext sContext;  /* Authorization context */
  NameContext sNC;       /* Name context to resolve expressions in */
  int iDb;               /* Database number */
  int memCnt = -1;       /* Memory cell used for change counting */
  int rcauth;            /* Value returned by authorization callback */
  int okOnePass;         /* True for one-pass algorithm without the FIFO */
  int aiCurOnePass[2];   /* The write cursors opened by WHERE_ONEPASS */
  u8 *aToOpen = 0;       /* Open cursor iTabCur+j if aToOpen[j] is true */












#ifndef SQLITE_OMIT_TRIGGER
  int isView;                  /* True if attempting to delete from a view */
  Trigger *pTrigger;           /* List of table triggers, if required */
#endif

  memset(&sContext, 0, sizeof(sContext));
  db = pParse->db;







<
















>
>
>
>
>
>
>
>
>
>
>
|







223
224
225
226
227
228
229

230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
  Parse *pParse,         /* The parser context */
  SrcList *pTabList,     /* The table from which we should delete things */
  Expr *pWhere           /* The WHERE clause.  May be null */
){
  Vdbe *v;               /* The virtual database engine */
  Table *pTab;           /* The table from which records will be deleted */
  const char *zDb;       /* Name of database holding pTab */

  int i;                 /* Loop counter */
  WhereInfo *pWInfo;     /* Information about the WHERE clause */
  Index *pIdx;           /* For looping over indices of the table */
  int iTabCur;           /* Cursor number for the table */
  int iDataCur;          /* VDBE cursor for the canonical data source */
  int iIdxCur;           /* Cursor number of the first index */
  int nIdx;              /* Number of indices */
  sqlite3 *db;           /* Main database structure */
  AuthContext sContext;  /* Authorization context */
  NameContext sNC;       /* Name context to resolve expressions in */
  int iDb;               /* Database number */
  int memCnt = -1;       /* Memory cell used for change counting */
  int rcauth;            /* Value returned by authorization callback */
  int okOnePass;         /* True for one-pass algorithm without the FIFO */
  int aiCurOnePass[2];   /* The write cursors opened by WHERE_ONEPASS */
  u8 *aToOpen = 0;       /* Open cursor iTabCur+j if aToOpen[j] is true */
  Index *pPk;            /* The PRIMARY KEY index on the table */
  int iPk;               /* First of nPk registerss holding PRIMARY KEY value */
  i16 nPk = 1;           /* Number of components of the PRIMARY KEY */
  int iKey;              /* Memory cell holding row key of to be deleted */
  i16 nKey;              /* Number of memory cells of row key */
  int iEphCur = 0;       /* Ephemeral table holding all primary key values */
  int iRowSet = 0;       /* Register for rowset of rows to delete */
  int addrBypass = 0;    /* Address of jump over the delete logic */
  int addrLoop = 0;      /* Top of the delete loop */
  int addrDelete = 0;    /* Jump directly to the delete logic */
  int addrEphOpen = 0;   /* Instruction to open the Ephermeral table */
 
#ifndef SQLITE_OMIT_TRIGGER
  int isView;                  /* True if attempting to delete from a view */
  Trigger *pTrigger;           /* List of table triggers, if required */
#endif

  memset(&sContext, 0, sizeof(sContext));
  db = pParse->db;
365
366
367
368
369
370
371

372
373
374
375
376



377
378
379
380
381
382
383
384
385
386
387
388
389
390





391
392
393
394
395
396
397

398
399
400















401





402
403
404
405
406
407
408
409
410



411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481

482
483
484
485
486
487
488
489
490
491
492
493
494

495
496
497
498
499
500
501



502







503

504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523





524

525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
    }
    for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
      assert( pIdx->pSchema==pTab->pSchema );
      sqlite3VdbeAddOp2(v, OP_Clear, pIdx->tnum, iDb);
    }
  }else
#endif /* SQLITE_OMIT_TRUNCATE_OPTIMIZATION */

  if( !HasRowid(pTab) ){
    /* There is a WHERE clause on a WITHOUT ROWID table.  
    */
    Index *pPk;      /* The PRIMARY KEY index on the table */
    int iPk;         /* First of nPk memory cells holding PRIMARY KEY value */



    int iEph;        /* Ephemeral table holding all primary key values */
    int iKey;        /* Key value inserting into iEph */
    i16 nPk;         /* Number of components of the PRIMARY KEY */

    pPk = sqlite3PrimaryKeyIndex(pTab);
    assert( pPk!=0 );
    nPk = pPk->nKeyCol;
    iPk = pParse->nMem+1;
    pParse->nMem += nPk;
    iKey = ++pParse->nMem;
    iEph = pParse->nTab++;

    addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, iEph, nPk);
    sqlite3VdbeSetP4KeyInfo(pParse, pPk);





    pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, 0, 0, 
                               WHERE_ONEPASS_DESIRED, iTabCur+1);
    if( pWInfo==0 ) goto delete_from_cleanup;
    okOnePass = sqlite3WhereOkOnePass(pWInfo, aiCurOnePass);
    for(i=0; i<nPk; i++){
      sqlite3ExprCodeGetColumnOfTable(v, pTab, iTabCur, pPk->aiColumn[i],iPk+i);
    }

    if( db->flags & SQLITE_CountRows ){
      sqlite3VdbeAddOp2(v, OP_AddImm, memCnt, 1);
    }















    if( okOnePass ){





      aToOpen = sqlite3DbMallocRaw(db, nIdx+2);
      if( aToOpen==0 ) goto delete_from_cleanup;
      memset(aToOpen, 1, nIdx+1);
      aToOpen[nIdx+1] = 0;
      if( aiCurOnePass[0]>=0 ) aToOpen[aiCurOnePass[0]-iTabCur] = 0;
      if( aiCurOnePass[1]>=0 ) aToOpen[aiCurOnePass[1]-iTabCur] = 0;
      sqlite3VdbeChangeToNoop(v, addr);
      addr = sqlite3VdbeAddOp0(v, OP_Goto);
    }else{



      sqlite3VdbeAddOp4(v, OP_MakeRecord, iPk, nPk, iKey,
                        sqlite3IndexAffinityStr(v, pPk), P4_TRANSIENT);
      sqlite3VdbeAddOp2(v, OP_IdxInsert, iEph, iKey);
    }
    sqlite3WhereEnd(pWInfo);
    if( okOnePass ){
      sqlite3VdbeAddOp0(v, OP_Halt);
      sqlite3VdbeJumpHere(v, addr);
    }

    /* Open cursors for all indices of the table.
    */
    sqlite3OpenTableAndIndices(pParse, pTab, OP_OpenWrite, iTabCur, aToOpen,
                               &iDataCur, &iIdxCur);

    /* Loop over the primary keys to be deleted. */
    if( !okOnePass ){
      addr = sqlite3VdbeAddOp1(v, OP_Rewind, iEph);
      sqlite3VdbeAddOp2(v, OP_RowKey, iEph, iPk);
    }

    /* Delete the row */
    sqlite3GenerateRowDelete(pParse, pTab, pTrigger, iDataCur, iIdxCur,
                             iPk, nPk*okOnePass, 1, OE_Default, okOnePass);

    /* End of the delete loop */
    if( !okOnePass ){
      sqlite3VdbeAddOp2(v, OP_Next, iEph, addr+1);
      sqlite3VdbeJumpHere(v, addr);
    }

    /* Close the cursors open on the table and its indexes. */
    assert( iDataCur>=iIdxCur );
    for(i=0, pIdx=pTab->pIndex; pIdx; i++, pIdx=pIdx->pNext){
      sqlite3VdbeAddOp1(v, OP_Close, iIdxCur+i);
    }
  }else{
    /* There is a WHERE clause on a rowid table.  Run a loop that extracts
    ** all rowids to be deleted into a RowSet.
    */
    int iRowSet = ++pParse->nMem;   /* Register for rowset of rows to delete */
    int regRowid;                   /* Actual register containing rowids */

    /* Collect rowids of every row to be deleted.
    */
    sqlite3VdbeAddOp2(v, OP_Null, 0, iRowSet);
    pWInfo = sqlite3WhereBegin(
        pParse, pTabList, pWhere, 0, 0,
        WHERE_DUPLICATES_OK|WHERE_ONEPASS_DESIRED, iTabCur+1
    );
    if( pWInfo==0 ) goto delete_from_cleanup;
    okOnePass = sqlite3WhereOkOnePass(pWInfo, aiCurOnePass);
    if( db->flags & SQLITE_CountRows ){
      sqlite3VdbeAddOp2(v, OP_AddImm, memCnt, 1);
    }
    regRowid = sqlite3ExprCodeGetColumn(pParse, pTab, -1, iTabCur,
                                        pParse->nMem+1, 0);
    if( regRowid>pParse->nMem ) pParse->nMem = regRowid;
    if( okOnePass ){
      aToOpen = sqlite3DbMallocRaw(db, nIdx+2);
      if( aToOpen==0 ) goto delete_from_cleanup;
      memset(aToOpen, 1, nIdx+1);
      aToOpen[nIdx+1] = 0;
      if( aiCurOnePass[0]>=0 ) aToOpen[aiCurOnePass[0]-iTabCur] = 0;
      if( aiCurOnePass[1]>=0 ) aToOpen[aiCurOnePass[1]-iTabCur] = 0;
      addr = sqlite3VdbeAddOp0(v, OP_Goto);
    }else{
      sqlite3VdbeAddOp2(v, OP_RowSetAdd, iRowSet, regRowid);
    }
    sqlite3WhereEnd(pWInfo);
    if( okOnePass ){

      sqlite3VdbeAddOp0(v, OP_Halt);
      sqlite3VdbeJumpHere(v, addr);
    }

    /* Delete every item whose key was written to the list during the
    ** database scan.  We have to delete items after the scan is complete
    ** because deleting an item can change the scan order.  */
    end = sqlite3VdbeMakeLabel(v);

    /* Unless this is a view, open cursors for the table we are 
    ** deleting from and all its indices. If this is a view, then the
    ** only effect this statement has is to fire the INSTEAD OF 
    ** triggers.  */

    if( !isView ){
      sqlite3OpenTableAndIndices(pParse, pTab, OP_OpenWrite, iTabCur, aToOpen,
                                 &iDataCur, &iIdxCur);
      assert( iDataCur==iTabCur );
      assert( iIdxCur==iDataCur+1 );
    }




    if( !okOnePass ){    







      addr = sqlite3VdbeAddOp3(v, OP_RowSetRead, iRowSet, end, regRowid);

    }

    /* Delete the row */
#ifndef SQLITE_OMIT_VIRTUALTABLE
    if( IsVirtual(pTab) ){
      const char *pVTab = (const char *)sqlite3GetVTable(db, pTab);
      sqlite3VtabMakeWritable(pParse, pTab);
      sqlite3VdbeAddOp4(v, OP_VUpdate, 0, 1, regRowid, pVTab, P4_VTAB);
      sqlite3VdbeChangeP5(v, OE_Abort);
      sqlite3MayAbort(pParse);
    }else
#endif
    {
      int count = (pParse->nested==0);    /* True to count changes */
      sqlite3GenerateRowDelete(pParse, pTab, pTrigger, iDataCur, iIdxCur,
                               regRowid, 1, count, OE_Default, okOnePass);
    }

    /* End of the delete loop */
    if( !okOnePass ){





      sqlite3VdbeAddOp2(v, OP_Goto, 0, addr);

    }
    sqlite3VdbeResolveLabel(v, end);

    /* Close the cursors open on the table and its indexes. */
    if( !isView && !IsVirtual(pTab) ){
      sqlite3VdbeAddOp1(v, OP_Close, iDataCur);
      for(i=0, pIdx=pTab->pIndex; pIdx; i++, pIdx=pIdx->pNext){
        sqlite3VdbeAddOp1(v, OP_Close, iIdxCur + i);
      }
    }
  }

  /* Update the sqlite_sequence table by storing the content of the
  ** maximum rowid counter values recorded while inserting into
  ** autoincrement tables.
  */
  if( pParse->nested==0 && pParse->pTriggerTab==0 ){
    sqlite3AutoincrementEnd(pParse);







>
|
<
|
|
|
>
>
>
|
<
<
|
|
|
|
|
|
<
|
<
|
|
>
>
>
>
>




<
<
|
>



>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

>
>
>
>
>






|
|
|
>
>
>


|
|
<
<
<
<
<
|
<
<
<
<
|
<
<
<
|

|
<
<
<
<
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<


>
|
|

|
<
<
<
<
<



|
>



|
|

|
>
>
>
|
>
>
>
>
>
>
>
|
>
|
|





|







|

|
|
|
>
>
>
>
>
|
>
|
<
|


|




|







375
376
377
378
379
380
381
382
383

384
385
386
387
388
389
390


391
392
393
394
395
396

397

398
399
400
401
402
403
404
405
406
407
408


409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450





451




452



453
454
455




456











































457
458
459
460
461
462
463





464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516

517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
    }
    for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
      assert( pIdx->pSchema==pTab->pSchema );
      sqlite3VdbeAddOp2(v, OP_Clear, pIdx->tnum, iDb);
    }
  }else
#endif /* SQLITE_OMIT_TRUNCATE_OPTIMIZATION */
  {
    if( HasRowid(pTab) ){

      /* For a rowid table, initialize the RowSet to an empty set */
      pPk = 0;
      nPk = 1;
      iRowSet = ++pParse->nMem;
      sqlite3VdbeAddOp2(v, OP_Null, 0, iRowSet);
    }else{
      /* For a WITHOUT ROWID table, create an ephermeral table used to


      ** hold all primary keys for rows to be deleted. */
      pPk = sqlite3PrimaryKeyIndex(pTab);
      assert( pPk!=0 );
      nPk = pPk->nKeyCol;
      iPk = pParse->nMem+1;
      pParse->nMem += nPk;

      iEphCur = pParse->nTab++;

      addrEphOpen = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, iEphCur, nPk);
      sqlite3VdbeSetP4KeyInfo(pParse, pPk);
    }
  
    /* Construct a query to find the rowid or primary key for every row
    ** to be deleted, based on the WHERE clause.
    */
    pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, 0, 0, 
                               WHERE_ONEPASS_DESIRED, iTabCur+1);
    if( pWInfo==0 ) goto delete_from_cleanup;
    okOnePass = sqlite3WhereOkOnePass(pWInfo, aiCurOnePass);


  
    /* Keep track of the number of rows to be deleted */
    if( db->flags & SQLITE_CountRows ){
      sqlite3VdbeAddOp2(v, OP_AddImm, memCnt, 1);
    }
  
    /* Extract the rowid or primary key for the current row */
    if( pPk ){
      for(i=0; i<nPk; i++){
        sqlite3ExprCodeGetColumnOfTable(v, pTab, iTabCur,
                                        pPk->aiColumn[i], iPk+i);
      }
      iKey = iPk;
      nKey = nPk;
    }else{
      iKey = pParse->nMem + 1;
      iKey = sqlite3ExprCodeGetColumn(pParse, pTab, -1, iTabCur, iKey, 0);
      if( iKey>pParse->nMem ) pParse->nMem = iKey;
    }
  
    if( okOnePass ){
      /* For ONEPASS, no need to store the rowid/primary-key.  There is only
      ** one, so just keep it in its register(s) and fall through to the
      ** delete code.
      */
      nKey = nPk; /* OP_Found will use an unpacked key */
      aToOpen = sqlite3DbMallocRaw(db, nIdx+2);
      if( aToOpen==0 ) goto delete_from_cleanup;
      memset(aToOpen, 1, nIdx+1);
      aToOpen[nIdx+1] = 0;
      if( aiCurOnePass[0]>=0 ) aToOpen[aiCurOnePass[0]-iTabCur] = 0;
      if( aiCurOnePass[1]>=0 ) aToOpen[aiCurOnePass[1]-iTabCur] = 0;
      if( addrEphOpen ) sqlite3VdbeChangeToNoop(v, addrEphOpen);
      addrDelete = sqlite3VdbeAddOp0(v, OP_Goto); /* Jump to DELETE logic */
    }else if( pPk ){
      /* Construct a composite key for the row to be deleted and remember it */
      iKey = ++pParse->nMem;
      nKey = 0;   /* Zero tells OP_Found to use a composite key */
      sqlite3VdbeAddOp4(v, OP_MakeRecord, iPk, nPk, iKey,
                        sqlite3IndexAffinityStr(v, pPk), P4_TRANSIENT);
      sqlite3VdbeAddOp2(v, OP_IdxInsert, iEphCur, iKey);
    }else{





      /* Get the rowid of the row to be deleted and remember it in the RowSet */




      nKey = 1;  /* OP_Seek always uses a single rowid */



      sqlite3VdbeAddOp2(v, OP_RowSetAdd, iRowSet, iKey);
    }
  




    /* End of the WHERE loop */











































    sqlite3WhereEnd(pWInfo);
    if( okOnePass ){
      /* Bypass the delete logic below if the WHERE loop found zero rows */
      addrBypass = sqlite3VdbeAddOp0(v, OP_Goto);
      sqlite3VdbeJumpHere(v, addrDelete);
    }
  





    /* Unless this is a view, open cursors for the table we are 
    ** deleting from and all its indices. If this is a view, then the
    ** only effect this statement has is to fire the INSTEAD OF 
    ** triggers.
    */
    if( !isView ){
      sqlite3OpenTableAndIndices(pParse, pTab, OP_OpenWrite, iTabCur, aToOpen,
                                 &iDataCur, &iIdxCur);
      assert( pPk || iDataCur==iTabCur );
      assert( pPk || iIdxCur==iDataCur+1 );
    }
  
    /* Set up a loop over the rowids/primary-keys that were found in the
    ** where-clause loop above.
    */
    if( okOnePass ){
      /* Just one row.  Hence the top-of-loop is a no-op */
      assert( nKey==nPk ); /* OP_Found will use an unpacked key */
    }else if( pPk ){
      addrLoop = sqlite3VdbeAddOp1(v, OP_Rewind, iEphCur);
      sqlite3VdbeAddOp2(v, OP_RowKey, iEphCur, iKey);
      assert( nKey==0 );  /* OP_Found will use a composite key */
    }else{
      addrLoop = sqlite3VdbeAddOp3(v, OP_RowSetRead, iRowSet, 0, iKey);
      assert( nKey==1 );
    }  
  
    /* Delete the row */
#ifndef SQLITE_OMIT_VIRTUALTABLE
    if( IsVirtual(pTab) ){
      const char *pVTab = (const char *)sqlite3GetVTable(db, pTab);
      sqlite3VtabMakeWritable(pParse, pTab);
      sqlite3VdbeAddOp4(v, OP_VUpdate, 0, 1, iKey, pVTab, P4_VTAB);
      sqlite3VdbeChangeP5(v, OE_Abort);
      sqlite3MayAbort(pParse);
    }else
#endif
    {
      int count = (pParse->nested==0);    /* True to count changes */
      sqlite3GenerateRowDelete(pParse, pTab, pTrigger, iDataCur, iIdxCur,
                               iKey, nKey, count, OE_Default, okOnePass);
    }
  
    /* End of the loop over all rowids/primary-keys. */
    if( okOnePass ){
      sqlite3VdbeJumpHere(v, addrBypass);
    }else if( pPk ){
      sqlite3VdbeAddOp2(v, OP_Next, iEphCur, addrLoop+1);
      sqlite3VdbeJumpHere(v, addrLoop);
    }else{
      sqlite3VdbeAddOp2(v, OP_Goto, 0, addrLoop);
      sqlite3VdbeJumpHere(v, addrLoop);
    }     

  
    /* Close the cursors open on the table and its indexes. */
    if( !isView && !IsVirtual(pTab) ){
      if( !pPk ) sqlite3VdbeAddOp1(v, OP_Close, iDataCur);
      for(i=0, pIdx=pTab->pIndex; pIdx; i++, pIdx=pIdx->pNext){
        sqlite3VdbeAddOp1(v, OP_Close, iIdxCur + i);
      }
    }
  } /* End non-truncate path */

  /* Update the sqlite_sequence table by storing the content of the
  ** maximum rowid counter values recorded while inserting into
  ** autoincrement tables.
  */
  if( pParse->nested==0 && pParse->pTriggerTab==0 ){
    sqlite3AutoincrementEnd(pParse);