SQLite

Check-in [e8b7ea8202]
Login

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

Overview
Comment:Make sure that disabling the covering index scan optimization does not prevent a covering index from being used to satisfy an ORDER BY clause.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1: e8b7ea8202c443bfc8a978588c7d2cfaa14a8fea
User & Date: drh 2013-06-13 17:28:22.026
Context
2013-06-13
17:58
An index might be useful for ORDER BY if any indexed column is in the ORDER BY clause, not just the first indexed column. (check-in: ade473b5ae user: drh tags: nextgen-query-plan-exp)
17:28
Make sure that disabling the covering index scan optimization does not prevent a covering index from being used to satisfy an ORDER BY clause. (check-in: e8b7ea8202 user: drh tags: nextgen-query-plan-exp)
15:50
Restore the ability to do a BETWEEN query on the rowid. Also fix a nearby comment. (check-in: 459a7b9068 user: drh tags: nextgen-query-plan-exp)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/where.c.
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
#define WHERE_IPK          0x00000100  /* x is the INTEGER PRIMARY KEY */
#define WHERE_INDEXED      0x00000200  /* WhereLoop.u.btree.pIndex is valid */
#define WHERE_VIRTUALTABLE 0x00000400  /* WhereLoop.u.vtab is valid */
#define WHERE_IN_ABLE      0x00000800  /* Able to support an IN operator */
#define WHERE_ONEROW       0x00001000  /* Selects no more than one row */
#define WHERE_MULTI_OR     0x00002000  /* OR using multiple indices */
#define WHERE_TEMP_INDEX   0x00004000  /* Uses an ephemeral index */
#define WHERE_COVER_SCAN   0x00008000  /* Full scan of a covering index */


/* Convert a WhereCost value (10 times log2(X)) into its integer value X.
** A rough approximation is used.  The value returned is not exact.
*/
static u64 whereCostToInt(WhereCost x){
  u64 n;







<







441
442
443
444
445
446
447

448
449
450
451
452
453
454
#define WHERE_IPK          0x00000100  /* x is the INTEGER PRIMARY KEY */
#define WHERE_INDEXED      0x00000200  /* WhereLoop.u.btree.pIndex is valid */
#define WHERE_VIRTUALTABLE 0x00000400  /* WhereLoop.u.vtab is valid */
#define WHERE_IN_ABLE      0x00000800  /* Able to support an IN operator */
#define WHERE_ONEROW       0x00001000  /* Selects no more than one row */
#define WHERE_MULTI_OR     0x00002000  /* OR using multiple indices */
#define WHERE_TEMP_INDEX   0x00004000  /* Uses an ephemeral index */



/* Convert a WhereCost value (10 times log2(X)) into its integer value X.
** A rough approximation is used.  The value returned is not exact.
*/
static u64 whereCostToInt(WhereCost x){
  u64 n;
3610
3611
3612
3613
3614
3615
3616
3617
3618
3619
3620
3621
3622
3623
3624
3625
      pLevel->op = OP_Noop;
    }else if( bRev ){
      pLevel->op = OP_Prev;
    }else{
      pLevel->op = OP_Next;
    }
    pLevel->p1 = iIdxCur;
    if( (pLoop->wsFlags & (WHERE_COLUMN_EQ | WHERE_COLUMN_RANGE | 
                          WHERE_COLUMN_NULL | WHERE_COLUMN_IN))==0 ){
      pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
    }else{
      assert( pLevel->p5==0 );
    }
  }else

#ifndef SQLITE_OMIT_OR_OPTIMIZATION







|
<







3609
3610
3611
3612
3613
3614
3615
3616

3617
3618
3619
3620
3621
3622
3623
      pLevel->op = OP_Noop;
    }else if( bRev ){
      pLevel->op = OP_Prev;
    }else{
      pLevel->op = OP_Next;
    }
    pLevel->p1 = iIdxCur;
    if( (pLoop->wsFlags & WHERE_CONSTRAINT)==0 ){

      pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
    }else{
      assert( pLevel->p5==0 );
    }
  }else

#ifndef SQLITE_OMIT_OR_OPTIMIZATION
4371
4372
4373
4374
4375
4376
4377

4378
4379
4380
4381
4382
4383
4384
  Index *pIndex,
  int iCursor
){
  ExprList *pOB;
  int iCol;
  int ii;


  if( (pOB = pBuilder->pWInfo->pOrderBy)==0 ) return 0;
  iCol = pIndex->aiColumn[0];
  for(ii=0; ii<pOB->nExpr; ii++){
    Expr *pExpr = sqlite3ExprSkipCollate(pOB->a[ii].pExpr);
    if( pExpr->op!=TK_COLUMN ) return 0;
    if( pExpr->iTable==iCursor ){
      if( pExpr->iColumn==iCol ) return 1;







>







4369
4370
4371
4372
4373
4374
4375
4376
4377
4378
4379
4380
4381
4382
4383
  Index *pIndex,
  int iCursor
){
  ExprList *pOB;
  int iCol;
  int ii;

  if( pIndex->bUnordered ) return 0;
  if( (pOB = pBuilder->pWInfo->pOrderBy)==0 ) return 0;
  iCol = pIndex->aiColumn[0];
  for(ii=0; ii<pOB->nExpr; ii++){
    Expr *pExpr = sqlite3ExprSkipCollate(pOB->a[ii].pExpr);
    if( pExpr->op!=TK_COLUMN ) return 0;
    if( pExpr->iTable==iCursor ){
      if( pExpr->iColumn==iCol ) return 1;
4499
4500
4501
4502
4503
4504
4505


4506
4507
4508
4509
4510
4511
4512
4513
4514
4515
4516
4517
4518
4519
4520
4521
4522
4523
4524
4525
4526

4527
4528
4529
4530

4531
4532
4533
4534
4535
4536
4537
    pNew->u.btree.nEq = 0;
    pNew->nLTerm = 0;
    pNew->iSortIdx = 0;
    pNew->rSetup = 0;
    pNew->prereq = mExtra;
    pNew->u.btree.pIndex = pProbe;
    b = indexMightHelpWithOrderBy(pBuilder, pProbe, pSrc->iCursor);


    if( pProbe->tnum<=0 ){
      /* Integer primary key index */
      pNew->wsFlags = WHERE_IPK;

      /* Full table scan */
      pNew->iSortIdx = b ? iSortIdx : 0;
      pNew->nOut = rSize;
      /* TUNING: Cost of full table scan is 3*(N + log2(N)).
      **  +  The extra 3 factor is to encourage the use of indexed lookups
      **     over full scans.  A smaller constant 2 is used for covering
      **     index scans so that a covering index scan will be favored over
      **     a table scan. */
      pNew->rRun = whereCostAdd(rSize,rLogSize) + 16;
      rc = whereLoopInsert(pBuilder, pNew);
      if( rc ) break;
    }else{
      Bitmask m = pSrc->colUsed & ~columnsInIndex(pProbe);
      pNew->wsFlags = (m==0) ? (WHERE_IDX_ONLY|WHERE_INDEXED) : WHERE_INDEXED;

      /* Full scan via index */
      if( (m==0 || b)

       && pProbe->bUnordered==0
       && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
       && sqlite3GlobalConfig.bUseCis
       && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan)

      ){
        pNew->iSortIdx = b ? iSortIdx : 0;
        pNew->nOut = rSize;
        if( m==0 ){
          /* TUNING: Cost of a covering index scan is 2*(N + log2(N)).
          **  +  The extra 2 factor is to encourage the use of indexed lookups
          **     over index scans.  A table scan uses a factor of 3 so that







>
>




















|
>
|
|
|
|
>







4498
4499
4500
4501
4502
4503
4504
4505
4506
4507
4508
4509
4510
4511
4512
4513
4514
4515
4516
4517
4518
4519
4520
4521
4522
4523
4524
4525
4526
4527
4528
4529
4530
4531
4532
4533
4534
4535
4536
4537
4538
4539
4540
    pNew->u.btree.nEq = 0;
    pNew->nLTerm = 0;
    pNew->iSortIdx = 0;
    pNew->rSetup = 0;
    pNew->prereq = mExtra;
    pNew->u.btree.pIndex = pProbe;
    b = indexMightHelpWithOrderBy(pBuilder, pProbe, pSrc->iCursor);
    /* The ONEPASS_DESIRED flags never occurs together with ORDER BY */
    assert( (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || b==0 );
    if( pProbe->tnum<=0 ){
      /* Integer primary key index */
      pNew->wsFlags = WHERE_IPK;

      /* Full table scan */
      pNew->iSortIdx = b ? iSortIdx : 0;
      pNew->nOut = rSize;
      /* TUNING: Cost of full table scan is 3*(N + log2(N)).
      **  +  The extra 3 factor is to encourage the use of indexed lookups
      **     over full scans.  A smaller constant 2 is used for covering
      **     index scans so that a covering index scan will be favored over
      **     a table scan. */
      pNew->rRun = whereCostAdd(rSize,rLogSize) + 16;
      rc = whereLoopInsert(pBuilder, pNew);
      if( rc ) break;
    }else{
      Bitmask m = pSrc->colUsed & ~columnsInIndex(pProbe);
      pNew->wsFlags = (m==0) ? (WHERE_IDX_ONLY|WHERE_INDEXED) : WHERE_INDEXED;

      /* Full scan via index */
      if( b
       || ( m==0
         && pProbe->bUnordered==0
         && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
         && sqlite3GlobalConfig.bUseCis
         && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan)
          )
      ){
        pNew->iSortIdx = b ? iSortIdx : 0;
        pNew->nOut = rSize;
        if( m==0 ){
          /* TUNING: Cost of a covering index scan is 2*(N + log2(N)).
          **  +  The extra 2 factor is to encourage the use of indexed lookups
          **     over index scans.  A table scan uses a factor of 3 so that