SQLite

Check-in [8d416091]
Login

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

Overview
Comment:In partial index scans, if the WHERE clause implies a constant value for a table column, replace occurences of that table column with the constant. This increases the likelihood of the partial index being a covering index.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: 8d4160910d6512469cb0a060b89c2509dde1c8e33d9358034d7fb39cd494eabe
User & Date: dan 2023-09-25 17:46:02
References
2023-09-26
14:57
Remove unreachable code from the partial-index constant value optimization ([8d4160910d651246]). (check-in: 7ad38254 user: drh tags: trunk)
Context
2023-09-26
07:43
Minor JNI doc updates. No code changes. (check-in: 63687cc6 user: stephan tags: trunk)
2023-09-25
17:46
In partial index scans, if the WHERE clause implies a constant value for a table column, replace occurences of that table column with the constant. This increases the likelihood of the partial index being a covering index. (check-in: 8d416091 user: dan tags: trunk)
17:21
Another very minor tweak to code on this branch to save cycles. (Closed-Leaf check-in: 2c805dc6 user: dan tags: partial-index-terms)
14:20
Enable -Wall for the compiler on --enable-debug builds. (check-in: 63a7b521 user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/build.c.
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
** and convert them into references to the index.  Hence we always want
** the actual table at hand in order to recompute the virtual column, if
** necessary.
**
** The colNotIdxed mask is AND-ed with the SrcList.a[].colUsed mask
** to determine if the index is covering index.
*/
static void recomputeColumnsNotIndexed(Index *pIdx){
  Bitmask m = 0;
  int j;
  Table *pTab = pIdx->pTable;
  for(j=pIdx->nColumn-1; j>=0; j--){
    int x = pIdx->aiColumn[j];
    if( x>=0 && (pTab->aCol[x].colFlags & COLFLAG_VIRTUAL)==0 ){
      testcase( x==BMS-1 );







|







2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
** and convert them into references to the index.  Hence we always want
** the actual table at hand in order to recompute the virtual column, if
** necessary.
**
** The colNotIdxed mask is AND-ed with the SrcList.a[].colUsed mask
** to determine if the index is covering index.
*/
static void recomputeColumnsNotIndexed(Parse *pParse, Index *pIdx){
  Bitmask m = 0;
  int j;
  Table *pTab = pIdx->pTable;
  for(j=pIdx->nColumn-1; j>=0; j--){
    int x = pIdx->aiColumn[j];
    if( x>=0 && (pTab->aCol[x].colFlags & COLFLAG_VIRTUAL)==0 ){
      testcase( x==BMS-1 );
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
      pPk->aiColumn[j] = i;
      pPk->azColl[j] = sqlite3StrBINARY;
      j++;
    }
  }
  assert( pPk->nColumn==j );
  assert( pTab->nNVCol<=j );
  recomputeColumnsNotIndexed(pPk);
}


#ifndef SQLITE_OMIT_VIRTUALTABLE
/*
** Return true if pTab is a virtual table and zName is a shadow table name
** for that virtual table.







|







2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
      pPk->aiColumn[j] = i;
      pPk->azColl[j] = sqlite3StrBINARY;
      j++;
    }
  }
  assert( pPk->nColumn==j );
  assert( pTab->nNVCol<=j );
  recomputeColumnsNotIndexed(pParse, pPk);
}


#ifndef SQLITE_OMIT_VIRTUALTABLE
/*
** Return true if pTab is a virtual table and zName is a shadow table name
** for that virtual table.
4269
4270
4271
4272
4273
4274
4275
4276
4277
4278
4279
4280
4281
4282
4283
  sqlite3DefaultRowEst(pIndex);
  if( pParse->pNewTable==0 ) estimateIndexWidth(pIndex);

  /* If this index contains every column of its table, then mark
  ** it as a covering index */
  assert( HasRowid(pTab)
      || pTab->iPKey<0 || sqlite3TableColumnToIndex(pIndex, pTab->iPKey)>=0 );
  recomputeColumnsNotIndexed(pIndex);
  if( pTblName!=0 && pIndex->nColumn>=pTab->nCol ){
    pIndex->isCovering = 1;
    for(j=0; j<pTab->nCol; j++){
      if( j==pTab->iPKey ) continue;
      if( sqlite3TableColumnToIndex(pIndex,j)>=0 ) continue;
      pIndex->isCovering = 0;
      break;







|







4269
4270
4271
4272
4273
4274
4275
4276
4277
4278
4279
4280
4281
4282
4283
  sqlite3DefaultRowEst(pIndex);
  if( pParse->pNewTable==0 ) estimateIndexWidth(pIndex);

  /* If this index contains every column of its table, then mark
  ** it as a covering index */
  assert( HasRowid(pTab)
      || pTab->iPKey<0 || sqlite3TableColumnToIndex(pIndex, pTab->iPKey)>=0 );
  recomputeColumnsNotIndexed(pParse, pIndex);
  if( pTblName!=0 && pIndex->nColumn>=pTab->nCol ){
    pIndex->isCovering = 1;
    for(j=0; j<pTab->nCol; j++){
      if( j==pTab->iPKey ) continue;
      if( sqlite3TableColumnToIndex(pIndex,j)>=0 ) continue;
      pIndex->isCovering = 0;
      break;
Changes to src/expr.c.
4247
4248
4249
4250
4251
4252
4253



































4254
4255
4256
4257
4258
4259
4260
      VdbeComment((v, "%s expr-column %d", p->zIdxName, p->iIdxCol));
    }
    return target;
  }
  return -1;  /* Not found */
}





































/*
** Generate code into the current Vdbe to evaluate the given
** expression.  Attempt to store the results in register "target".
** Return the register where results are stored.
**
** With this routine, there is no guarantee that results will







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







4247
4248
4249
4250
4251
4252
4253
4254
4255
4256
4257
4258
4259
4260
4261
4262
4263
4264
4265
4266
4267
4268
4269
4270
4271
4272
4273
4274
4275
4276
4277
4278
4279
4280
4281
4282
4283
4284
4285
4286
4287
4288
4289
4290
4291
4292
4293
4294
4295
      VdbeComment((v, "%s expr-column %d", p->zIdxName, p->iIdxCol));
    }
    return target;
  }
  return -1;  /* Not found */
}


/*
** Expresion pExpr is guaranteed to be a TK_COLUMN or equivalent. This
** function checks the Parse.pIdxPartExpr list to see if this column
** can be replaced with a constant value. If so, it generates code to
** put the constant value in a register (ideally, but not necessarily, 
** register iTarget) and returns the register number.
**
** Or, if the TK_COLUMN cannot be replaced by a constant, zero is 
** returned.
*/
static int exprPartidxExprLookup(Parse *pParse, Expr *pExpr, int iTarget){
  IndexedExpr *p;
  for(p=pParse->pIdxPartExpr; p; p=p->pIENext){
    if( pExpr->iColumn==p->iIdxCol && pExpr->iTable==p->iDataCur ){
      Vdbe *v = pParse->pVdbe;
      int addr = 0;
      int ret;

      if( p->bMaybeNullRow ){
        addr = sqlite3VdbeAddOp1(v, OP_IfNullRow, p->iIdxCur);
      }
      ret = sqlite3ExprCodeTarget(pParse, p->pExpr, iTarget);
      sqlite3VdbeAddOp4(pParse->pVdbe, OP_Affinity, ret, 1, 0,
                        (const char*)&p->aff, 1);
      if( addr ){
        sqlite3VdbeJumpHere(v, addr);
        sqlite3VdbeChangeP3(v, addr, ret);
      }
      return ret;
    }
  }
  return 0;
}


/*
** Generate code into the current Vdbe to evaluate the given
** expression.  Attempt to store the results in register "target".
** Return the register where results are stored.
**
** With this routine, there is no guarantee that results will
4404
4405
4406
4407
4408
4409
4410





4411
4412
4413
4414
4415
4416
4417
            return iSrc;
          }
        }else{
          /* Coding an expression that is part of an index where column names
          ** in the index refer to the table to which the index belongs */
          iTab = pParse->iSelfTab - 1;
        }





      }
      assert( ExprUseYTab(pExpr) );
      assert( pExpr->y.pTab!=0 );
      iReg = sqlite3ExprCodeGetColumn(pParse, pExpr->y.pTab,
                               pExpr->iColumn, iTab, target,
                               pExpr->op2);
      return iReg;







>
>
>
>
>







4439
4440
4441
4442
4443
4444
4445
4446
4447
4448
4449
4450
4451
4452
4453
4454
4455
4456
4457
            return iSrc;
          }
        }else{
          /* Coding an expression that is part of an index where column names
          ** in the index refer to the table to which the index belongs */
          iTab = pParse->iSelfTab - 1;
        }
      }
      else if( pParse->pIdxPartExpr 
       && 0!=(r1 = exprPartidxExprLookup(pParse, pExpr, target))
      ){
        return r1;
      }
      assert( ExprUseYTab(pExpr) );
      assert( pExpr->y.pTab!=0 );
      iReg = sqlite3ExprCodeGetColumn(pParse, pExpr->y.pTab,
                               pExpr->iColumn, iTab, target,
                               pExpr->op2);
      return iReg;
Changes to src/prepare.c.
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
    sqlite3ExprListDelete(db, pParse->pConstExpr);
  }
  assert( db->lookaside.bDisable >= pParse->disableLookaside );
  db->lookaside.bDisable -= pParse->disableLookaside;
  db->lookaside.sz = db->lookaside.bDisable ? 0 : db->lookaside.szTrue;
  assert( pParse->db->pParse==pParse );
  db->pParse = pParse->pOuterParse;
  pParse->db = 0;
  pParse->disableLookaside = 0;
}

/*
** Add a new cleanup operation to a Parser.  The cleanup should happen when
** the parser object is destroyed.  But, beware: the cleanup might happen
** immediately.
**







<
<







594
595
596
597
598
599
600


601
602
603
604
605
606
607
    sqlite3ExprListDelete(db, pParse->pConstExpr);
  }
  assert( db->lookaside.bDisable >= pParse->disableLookaside );
  db->lookaside.bDisable -= pParse->disableLookaside;
  db->lookaside.sz = db->lookaside.bDisable ? 0 : db->lookaside.szTrue;
  assert( pParse->db->pParse==pParse );
  db->pParse = pParse->pOuterParse;


}

/*
** Add a new cleanup operation to a Parser.  The cleanup should happen when
** the parser object is destroyed.  But, beware: the cleanup might happen
** immediately.
**
Changes to src/sqliteInt.h.
3786
3787
3788
3789
3790
3791
3792

3793
3794
3795
3796
3797
3798
3799
  int iSelfTab;        /* Table associated with an index on expr, or negative
                       ** of the base register during check-constraint eval */
  int nLabel;          /* The *negative* of the number of labels used */
  int nLabelAlloc;     /* Number of slots in aLabel */
  int *aLabel;         /* Space to hold the labels */
  ExprList *pConstExpr;/* Constant expressions */
  IndexedExpr *pIdxEpr;/* List of expressions used by active indexes */

  Token constraintName;/* Name of the constraint currently being parsed */
  yDbMask writeMask;   /* Start a write transaction on these databases */
  yDbMask cookieMask;  /* Bitmask of schema verified databases */
  int regRowid;        /* Register holding rowid of CREATE TABLE entry */
  int regRoot;         /* Register holding root page number for new objects */
  int nMaxArg;         /* Max args passed to user function by sub-program */
  int nSelect;         /* Number of SELECT stmts. Counter for Select.selId */







>







3786
3787
3788
3789
3790
3791
3792
3793
3794
3795
3796
3797
3798
3799
3800
  int iSelfTab;        /* Table associated with an index on expr, or negative
                       ** of the base register during check-constraint eval */
  int nLabel;          /* The *negative* of the number of labels used */
  int nLabelAlloc;     /* Number of slots in aLabel */
  int *aLabel;         /* Space to hold the labels */
  ExprList *pConstExpr;/* Constant expressions */
  IndexedExpr *pIdxEpr;/* List of expressions used by active indexes */
  IndexedExpr *pIdxPartExpr; /* Exprs constrained by index WHERE clauses */
  Token constraintName;/* Name of the constraint currently being parsed */
  yDbMask writeMask;   /* Start a write transaction on these databases */
  yDbMask cookieMask;  /* Bitmask of schema verified databases */
  int regRowid;        /* Register holding rowid of CREATE TABLE entry */
  int regRoot;         /* Register holding root page number for new objects */
  int nMaxArg;         /* Max args passed to user function by sub-program */
  int nSelect;         /* Number of SELECT stmts. Counter for Select.selId */
Changes to src/where.c.
1138
1139
1140
1141
1142
1143
1144

1145
1146

1147

1148
1149
1150
1151

1152
1153
1154
1155
1156
1157
1158
  const WhereTerm *pTerm;              /* For looping over WHERE clause terms */
  const WhereTerm *pWCEnd;             /* Last WHERE clause term */
  Parse *pParse = pWInfo->pParse;      /* Parsing context */
  Vdbe *v = pParse->pVdbe;             /* VDBE under construction */
  WhereLoop *pLoop = pLevel->pWLoop;   /* The loop being coded */
  int iCur;                            /* Cursor for table getting the filter */
  IndexedExpr *saved_pIdxEpr;          /* saved copy of Parse.pIdxEpr */


  saved_pIdxEpr = pParse->pIdxEpr;

  pParse->pIdxEpr = 0;


  assert( pLoop!=0 );
  assert( v!=0 );
  assert( pLoop->wsFlags & WHERE_BLOOMFILTER );


  addrOnce = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v);
  do{
    const SrcList *pTabList;
    const SrcItem *pItem;
    const Table *pTab;
    u64 sz;







>


>

>




>







1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
  const WhereTerm *pTerm;              /* For looping over WHERE clause terms */
  const WhereTerm *pWCEnd;             /* Last WHERE clause term */
  Parse *pParse = pWInfo->pParse;      /* Parsing context */
  Vdbe *v = pParse->pVdbe;             /* VDBE under construction */
  WhereLoop *pLoop = pLevel->pWLoop;   /* The loop being coded */
  int iCur;                            /* Cursor for table getting the filter */
  IndexedExpr *saved_pIdxEpr;          /* saved copy of Parse.pIdxEpr */
  IndexedExpr *saved_pIdxPartExpr;     /* saved copy of Parse.pIdxPartExpr */

  saved_pIdxEpr = pParse->pIdxEpr;
  saved_pIdxPartExpr = pParse->pIdxPartExpr;
  pParse->pIdxEpr = 0;
  pParse->pIdxPartExpr = 0;

  assert( pLoop!=0 );
  assert( v!=0 );
  assert( pLoop->wsFlags & WHERE_BLOOMFILTER );
  assert( (pLoop->wsFlags & WHERE_IDX_ONLY)==0 );

  addrOnce = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v);
  do{
    const SrcList *pTabList;
    const SrcItem *pItem;
    const Table *pTab;
    u64 sz;
1234
1235
1236
1237
1238
1239
1240

1241
1242
1243
1244
1245
1246
1247
        ** the IN operator */
        break;
      }
    }
  }while( iLevel < pWInfo->nLevel );
  sqlite3VdbeJumpHere(v, addrOnce);
  pParse->pIdxEpr = saved_pIdxEpr;

}


#ifndef SQLITE_OMIT_VIRTUALTABLE
/*
** Allocate and populate an sqlite3_index_info structure. It is the
** responsibility of the caller to eventually release the structure







>







1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
        ** the IN operator */
        break;
      }
    }
  }while( iLevel < pWInfo->nLevel );
  sqlite3VdbeJumpHere(v, addrOnce);
  pParse->pIdxEpr = saved_pIdxEpr;
  pParse->pIdxPartExpr = saved_pIdxPartExpr;
}


#ifndef SQLITE_OMIT_VIRTUALTABLE
/*
** Allocate and populate an sqlite3_index_info structure. It is the
** responsibility of the caller to eventually release the structure
3492
3493
3494
3495
3496
3497
3498


































































































3499
3500
3501
3502
3503
3504
3505
  }else if( ck.bExpr ){
    rc = WHERE_EXPRIDX;
  }else{
    rc = WHERE_IDX_ONLY;
  }
  return rc;
}



































































































/*
** Add all WhereLoop objects for a single table of the join where the table
** is identified by pBuilder->pNew->iTab.  That table is guaranteed to be
** a b-tree table, not a virtual table.
**
** The costs (WhereLoop.rRun) of the b-tree loops added by this function







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







3497
3498
3499
3500
3501
3502
3503
3504
3505
3506
3507
3508
3509
3510
3511
3512
3513
3514
3515
3516
3517
3518
3519
3520
3521
3522
3523
3524
3525
3526
3527
3528
3529
3530
3531
3532
3533
3534
3535
3536
3537
3538
3539
3540
3541
3542
3543
3544
3545
3546
3547
3548
3549
3550
3551
3552
3553
3554
3555
3556
3557
3558
3559
3560
3561
3562
3563
3564
3565
3566
3567
3568
3569
3570
3571
3572
3573
3574
3575
3576
3577
3578
3579
3580
3581
3582
3583
3584
3585
3586
3587
3588
3589
3590
3591
3592
3593
3594
3595
3596
3597
3598
3599
3600
3601
3602
3603
3604
3605
3606
3607
3608
  }else if( ck.bExpr ){
    rc = WHERE_EXPRIDX;
  }else{
    rc = WHERE_IDX_ONLY;
  }
  return rc;
}

/*
** This is an sqlite3ParserAddCleanup() callback that is invoked to
** free the Parse->pIdxEpr list when the Parse object is destroyed.
*/
static void whereIndexedExprCleanup(sqlite3 *db, void *pObject){
  IndexedExpr **pp = (IndexedExpr**)pObject;
  while( *pp!=0 ){
    IndexedExpr *p = *pp;
    *pp = p->pIENext;
    sqlite3ExprDelete(db, p->pExpr);
    sqlite3DbFreeNN(db, p);
  }
}

/*
** This function is called for a partial index - one with a WHERE clause - in 
** two scenarios. In both cases, it determines whether or not the WHERE 
** clause on the index implies that a column of the table may be safely
** replaced by a constant expression. For example, in the following 
** SELECT:
**
**   CREATE INDEX i1 ON t1(b, c) WHERE a=<expr>;
**   SELECT a, b, c FROM t1 WHERE a=<expr> AND b=?;
**
** The "a" in the select-list may be replaced by <expr>, iff:
**
**    (a) <expr> is a constant expression, and
**    (b) The (a=<expr>) comparison uses the BINARY collation sequence, and
**    (c) Column "a" has an affinity other than NONE or BLOB.
**
** If argument pItem is NULL, then pMask must not be NULL. In this case this 
** function is being called as part of determining whether or not pIdx
** is a covering index. This function clears any bits in (*pMask) 
** corresponding to columns that may be replaced by constants as described
** above.
**
** Otherwise, if pItem is not NULL, then this function is being called
** as part of coding a loop that uses index pIdx. In this case, add entries
** to the Parse.pIdxPartExpr list for each column that can be replaced
** by a constant.
*/
static void wherePartIdxExpr(
  Parse *pParse,                  /* Parse context */
  Index *pIdx,                    /* Partial index being processed */
  Expr *pPart,                    /* WHERE clause being processed */
  Bitmask *pMask,                 /* Mask to clear bits in */
  int iIdxCur,                    /* Cursor number for index */
  SrcItem *pItem                  /* The FROM clause entry for the table */
){
  assert( pItem==0 || (pItem->fg.jointype & JT_RIGHT)==0 );
  assert( (pItem==0 || pMask==0) && (pMask!=0 || pItem!=0) );

  if( pPart->op==TK_AND ){
    wherePartIdxExpr(pParse, pIdx, pPart->pRight, pMask, iIdxCur, pItem);
    pPart = pPart->pLeft;
  }

  if( (pPart->op==TK_EQ || pPart->op==TK_IS) ){
    Expr *pLeft = pPart->pLeft;
    Expr *pRight = pPart->pRight;
    u8 aff;

    if( pRight->op==TK_COLUMN ){
      SWAP(Expr*, pLeft, pRight);
    }

    if( pLeft->op!=TK_COLUMN ) return;
    if( !sqlite3ExprIsConstant(pRight) ) return;
    if( !sqlite3IsBinary(sqlite3ExprCompareCollSeq(pParse, pPart)) ) return;
    if( pLeft->iColumn<0 ) return;
    aff = pIdx->pTable->aCol[pLeft->iColumn].affinity;
    if( aff>=SQLITE_AFF_TEXT ){
      if( pItem ){
        sqlite3 *db = pParse->db;
        IndexedExpr *p = (IndexedExpr*)sqlite3DbMallocRaw(db, sizeof(*p));
        if( p ){
          int bNullRow = (pItem->fg.jointype&(JT_LEFT|JT_LTORJ))!=0;
          p->pExpr = sqlite3ExprDup(db, pRight, 0);
          p->iDataCur = pItem->iCursor;
          p->iIdxCur = iIdxCur;
          p->iIdxCol = pLeft->iColumn;
          p->bMaybeNullRow = bNullRow;
          p->pIENext = pParse->pIdxPartExpr;
          p->aff = aff;
          pParse->pIdxPartExpr = p;
          if( p->pIENext==0 ){
            void *pArg = (void*)&pParse->pIdxPartExpr;
            sqlite3ParserAddCleanup(pParse, whereIndexedExprCleanup, pArg);
          }
        }
      }else if( pLeft->iColumn<(BMS-1) ){
        *pMask &= ~((Bitmask)1 << pLeft->iColumn);
      }
    }
  }
}


/*
** Add all WhereLoop objects for a single table of the join where the table
** is identified by pBuilder->pNew->iTab.  That table is guaranteed to be
** a b-tree table, not a virtual table.
**
** The costs (WhereLoop.rRun) of the b-tree loops added by this function
3708
3709
3710
3711
3712
3713
3714





3715
3716
3717
3718
3719
3720
3721
    }else{
      Bitmask m;
      if( pProbe->isCovering ){
        m = 0;
        pNew->wsFlags = WHERE_IDX_ONLY | WHERE_INDEXED;
      }else{
        m = pSrc->colUsed & pProbe->colNotIdxed;





        pNew->wsFlags = WHERE_INDEXED;
        if( m==TOPBIT || (pProbe->bHasExpr && !pProbe->bHasVCol && m!=0) ){
          u32 isCov = whereIsCoveringIndex(pWInfo, pProbe, pSrc->iCursor);
          if( isCov==0 ){
            WHERETRACE(0x200,
               ("-> %s is not a covering index"
                " according to whereIsCoveringIndex()\n", pProbe->zName));







>
>
>
>
>







3811
3812
3813
3814
3815
3816
3817
3818
3819
3820
3821
3822
3823
3824
3825
3826
3827
3828
3829
    }else{
      Bitmask m;
      if( pProbe->isCovering ){
        m = 0;
        pNew->wsFlags = WHERE_IDX_ONLY | WHERE_INDEXED;
      }else{
        m = pSrc->colUsed & pProbe->colNotIdxed;
        if( pProbe->pPartIdxWhere ){
          wherePartIdxExpr(
              pWInfo->pParse, pProbe, pProbe->pPartIdxWhere, &m, 0, 0
          );
        }
        pNew->wsFlags = WHERE_INDEXED;
        if( m==TOPBIT || (pProbe->bHasExpr && !pProbe->bHasVCol && m!=0) ){
          u32 isCov = whereIsCoveringIndex(pWInfo, pProbe, pSrc->iCursor);
          if( isCov==0 ){
            WHERETRACE(0x200,
               ("-> %s is not a covering index"
                " according to whereIsCoveringIndex()\n", pProbe->zName));
5663
5664
5665
5666
5667
5668
5669
5670
5671
5672
5673
5674
5675
5676
5677
5678
5679
5680
5681
5682
5683
5684
5685
5686
5687
5688
5689
5690
           (double)sqlite3LogEstToInt(pTab->nRowLogEst)));
      }
    }
    nSearch += pLoop->nOut;
  }
}

/*
** This is an sqlite3ParserAddCleanup() callback that is invoked to
** free the Parse->pIdxEpr list when the Parse object is destroyed.
*/
static void whereIndexedExprCleanup(sqlite3 *db, void *pObject){
  Parse *pParse = (Parse*)pObject;
  while( pParse->pIdxEpr!=0 ){
    IndexedExpr *p = pParse->pIdxEpr;
    pParse->pIdxEpr = p->pIENext;
    sqlite3ExprDelete(db, p->pExpr);
    sqlite3DbFreeNN(db, p);
  }
}

/*
** The index pIdx is used by a query and contains one or more expressions.
** In other words pIdx is an index on an expression.  iIdxCur is the cursor
** number for the index and iDataCur is the cursor number for the corresponding
** table.
**
** This routine adds IndexedExpr entries to the Parse->pIdxEpr field for







<
<
<
<
<
<
<
<
<
<
<
<
<
<







5771
5772
5773
5774
5775
5776
5777














5778
5779
5780
5781
5782
5783
5784
           (double)sqlite3LogEstToInt(pTab->nRowLogEst)));
      }
    }
    nSearch += pLoop->nOut;
  }
}















/*
** The index pIdx is used by a query and contains one or more expressions.
** In other words pIdx is an index on an expression.  iIdxCur is the cursor
** number for the index and iDataCur is the cursor number for the corresponding
** table.
**
** This routine adds IndexedExpr entries to the Parse->pIdxEpr field for
5738
5739
5740
5741
5742
5743
5744

5745
5746
5747
5748
5749
5750
5751
5752
      p->aff = pIdx->zColAff[i];
    }
#ifdef SQLITE_ENABLE_EXPLAIN_COMMENTS
    p->zIdxName = pIdx->zName;
#endif
    pParse->pIdxEpr = p;
    if( p->pIENext==0 ){

      sqlite3ParserAddCleanup(pParse, whereIndexedExprCleanup, pParse);
    }
  }
}

/*
** Set the reverse-scan order mask to one for all tables in the query
** with the exception of MATERIALIZED common table expressions that have







>
|







5832
5833
5834
5835
5836
5837
5838
5839
5840
5841
5842
5843
5844
5845
5846
5847
      p->aff = pIdx->zColAff[i];
    }
#ifdef SQLITE_ENABLE_EXPLAIN_COMMENTS
    p->zIdxName = pIdx->zName;
#endif
    pParse->pIdxEpr = p;
    if( p->pIENext==0 ){
      void *pArg = (void*)&pParse->pIdxEpr;
      sqlite3ParserAddCleanup(pParse, whereIndexedExprCleanup, pArg);
    }
  }
}

/*
** Set the reverse-scan order mask to one for all tables in the query
** with the exception of MATERIALIZED common table expressions that have
6349
6350
6351
6352
6353
6354
6355





6356
6357
6358
6359
6360
6361
6362
      }else if( iAuxArg && (wctrlFlags & WHERE_OR_SUBCLAUSE)!=0 ){
        iIndexCur = iAuxArg;
        op = OP_ReopenIdx;
      }else{
        iIndexCur = pParse->nTab++;
        if( pIx->bHasExpr && OptimizationEnabled(db, SQLITE_IndexedExpr) ){
          whereAddIndexedExpr(pParse, pIx, iIndexCur, pTabItem);





        }
      }
      pLevel->iIdxCur = iIndexCur;
      assert( pIx!=0 );
      assert( pIx->pSchema==pTab->pSchema );
      assert( iIndexCur>=0 );
      if( op ){







>
>
>
>
>







6444
6445
6446
6447
6448
6449
6450
6451
6452
6453
6454
6455
6456
6457
6458
6459
6460
6461
6462
      }else if( iAuxArg && (wctrlFlags & WHERE_OR_SUBCLAUSE)!=0 ){
        iIndexCur = iAuxArg;
        op = OP_ReopenIdx;
      }else{
        iIndexCur = pParse->nTab++;
        if( pIx->bHasExpr && OptimizationEnabled(db, SQLITE_IndexedExpr) ){
          whereAddIndexedExpr(pParse, pIx, iIndexCur, pTabItem);
        }
        if( pIx->pPartIdxWhere && (pTabItem->fg.jointype & JT_RIGHT)==0 ){
          wherePartIdxExpr(
              pParse, pIx, pIx->pPartIdxWhere, 0, iIndexCur, pTabItem
          );
        }
      }
      pLevel->iIdxCur = iIndexCur;
      assert( pIx!=0 );
      assert( pIx->pSchema==pTab->pSchema );
      assert( iIndexCur>=0 );
      if( op ){
Added test/indexA.test.












































































































































































































































































































































































































































































































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
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
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
# 2023 September 23
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl
set testprefix indexA

do_execsql_test 1.0 {
  CREATE TABLE t1(a TEXT, b, c);
  CREATE INDEX i1 ON t1(b, c) WHERE a='abc';
  INSERT INTO t1 VALUES('abc', 1, 2);
}

do_execsql_test 1.1 {
  SELECT * FROM t1 WHERE a='abc'
} {abc 1 2}

do_eqp_test 1.2 {
  SELECT * FROM t1 WHERE a='abc'
} {USING COVERING INDEX i1}

do_execsql_test 1.3 {
  CREATE INDEX i2 ON t1(b, c) WHERE a=5;
  INSERT INTO t1 VALUES(5, 4, 3);

  SELECT a, typeof(a), b, c FROM t1 WHERE a=5;
} {5 text 4 3}

do_execsql_test 1.4 {
  CREATE TABLE t2(x);
  INSERT INTO t2 VALUES('v');
}

do_execsql_test 1.5 {
  SELECT x, a, b, c FROM t2 LEFT JOIN t1 ON (a=5 AND b=x)
} {v {} {} {}}

do_execsql_test 1.6 {
  SELECT x, a, b, c FROM t2 RIGHT JOIN t1 ON (t1.a=5 AND t1.b=t2.x)
} {{} abc 1 2   {} 5 4 3}

do_eqp_test 1.7 {
  SELECT x, a, b, c FROM t2 RIGHT JOIN t1 ON (t1.a=5 AND t1.b=t2.x)
} {USING INDEX i2}

#-------------------------------------------------------------------------
reset_db

do_execsql_test 2.0 {
  CREATE TABLE x1(a TEXT, b, c);
  INSERT INTO x1 VALUES('2', 'two', 'ii');
  INSERT INTO x1 VALUES('2.0', 'twopointoh', 'ii.0');

  CREATE TABLE x2(a NUMERIC, b, c);
  INSERT INTO x2 VALUES('2', 'two', 'ii');
  INSERT INTO x2 VALUES('2.0', 'twopointoh', 'ii.0');

  CREATE TABLE x3(a REAL, b, c);
  INSERT INTO x3 VALUES('2', 'two', 'ii');
  INSERT INTO x3 VALUES('2.0', 'twopointoh', 'ii.0');
}

foreach {tn idx} {
  0 {
  }
  1 {
    CREATE INDEX i1 ON x1(b, c) WHERE a=2;
    CREATE INDEX i2 ON x2(b, c) WHERE a=2;
    CREATE INDEX i3 ON x3(b, c) WHERE a=2;
  }
  2 {
    CREATE INDEX i1 ON x1(b, c) WHERE a=2.0;
    CREATE INDEX i2 ON x2(b, c) WHERE a=2.0;
    CREATE INDEX i3 ON x3(b, c) WHERE a=2.0;
  }
  3 {
    CREATE INDEX i1 ON x1(b, c) WHERE a='2.0';
    CREATE INDEX i2 ON x2(b, c) WHERE a='2.0';
    CREATE INDEX i3 ON x3(b, c) WHERE a='2.0';
  }
  4 {
    CREATE INDEX i1 ON x1(b, c) WHERE a='2';
    CREATE INDEX i2 ON x2(b, c) WHERE a='2';
    CREATE INDEX i3 ON x3(b, c) WHERE a='2';
  }
} {
  execsql { DROP INDEX IF EXISTS i1 }
  execsql { DROP INDEX IF EXISTS i2 }
  execsql { DROP INDEX IF EXISTS i3 }

  execsql $idx
  do_execsql_test 2.1.$tn.1 {
    SELECT *, typeof(a) FROM x1 WHERE a=2
  } {2 two ii text}
  do_execsql_test 2.1.$tn.2 {
    SELECT *, typeof(a) FROM x1 WHERE a=2.0
  } {2.0 twopointoh ii.0 text}
  do_execsql_test 2.1.$tn.3 {
    SELECT *, typeof(a) FROM x1 WHERE a='2'
  } {2 two ii text}
  do_execsql_test 2.1.$tn.4 {
    SELECT *, typeof(a) FROM x1 WHERE a='2.0'
  } {2.0 twopointoh ii.0 text}

  do_execsql_test 2.1.$tn.5 {
    SELECT *, typeof(a) FROM x2 WHERE a=2
  } {2 two ii integer 2 twopointoh ii.0 integer}
  do_execsql_test 2.1.$tn.6 {
    SELECT *, typeof(a) FROM x2 WHERE a=2.0
  } {2 two ii integer 2 twopointoh ii.0 integer}
  do_execsql_test 2.1.$tn.7 {
    SELECT *, typeof(a) FROM x2 WHERE a='2'
  } {2 two ii integer 2 twopointoh ii.0 integer}
  do_execsql_test 2.1.$tn.8 {
    SELECT *, typeof(a) FROM x2 WHERE a='2.0'
  } {2 two ii integer 2 twopointoh ii.0 integer}

  do_execsql_test 2.1.$tn.9 {
    SELECT *, typeof(a) FROM x3 WHERE a=2
  } {2.0 two ii real 2.0 twopointoh ii.0 real}
  do_execsql_test 2.1.$tn.10 {
    SELECT *, typeof(a) FROM x3 WHERE a=2.0
  } {2.0 two ii real 2.0 twopointoh ii.0 real}
  do_execsql_test 2.1.$tn.11 {
    SELECT *, typeof(a) FROM x3 WHERE a='2'
  } {2.0 two ii real 2.0 twopointoh ii.0 real}
  do_execsql_test 2.1.$tn.12 {
    SELECT *, typeof(a) FROM x3 WHERE a='2.0'
  } {2.0 two ii real 2.0 twopointoh ii.0 real}

}

reset_db
do_execsql_test 3.0 {
  CREATE TABLE x1(a TEXT, d PRIMARY KEY, b, c) WITHOUT ROWID;
  INSERT INTO x1 VALUES('2', 1, 'two', 'ii');
  INSERT INTO x1 VALUES('2.0', 2, 'twopointoh', 'ii.0');

  CREATE TABLE x2(a NUMERIC, b, c, d PRIMARY KEY) WITHOUT ROWID;
  INSERT INTO x2 VALUES('2', 'two', 'ii', 1);
  INSERT INTO x2 VALUES('2.0', 'twopointoh', 'ii.0', 2);

  CREATE TABLE x3(d PRIMARY KEY, a REAL, b, c) WITHOUT ROWID;
  INSERT INTO x3 VALUES(34, '2', 'two', 'ii');
  INSERT INTO x3 VALUES(35, '2.0', 'twopointoh', 'ii.0');
}

foreach {tn idx} {
  0 {
  }
  1 {
    CREATE INDEX i1 ON x1(b, c) WHERE a=2;
    CREATE INDEX i2 ON x2(b, c) WHERE a=2;
    CREATE INDEX i3 ON x3(b, c) WHERE a=2;
  }
  2 {
    CREATE INDEX i1 ON x1(b, c) WHERE a=2.0;
    CREATE INDEX i2 ON x2(b, c) WHERE a=2.0;
    CREATE INDEX i3 ON x3(b, c) WHERE a=2.0;
  }
  3 {
    CREATE INDEX i1 ON x1(b, c) WHERE a='2.0';
    CREATE INDEX i2 ON x2(b, c) WHERE a='2.0';
    CREATE INDEX i3 ON x3(b, c) WHERE a='2.0';
  }
  4 {
    CREATE INDEX i1 ON x1(b, c) WHERE a='2';
    CREATE INDEX i2 ON x2(b, c) WHERE a='2';
    CREATE INDEX i3 ON x3(b, c) WHERE a='2';
  }
} {
  execsql { DROP INDEX IF EXISTS i1 }
  execsql { DROP INDEX IF EXISTS i2 }
  execsql { DROP INDEX IF EXISTS i3 }

  execsql $idx
  do_execsql_test 3.1.$tn.1 {
    SELECT a, b, c, typeof(a) FROM x1 WHERE a=2
  } {2 two ii text}
  do_execsql_test 3.1.$tn.2 {
    SELECT a, b, c, typeof(a) FROM x1 WHERE a=2.0
  } {2.0 twopointoh ii.0 text}
  do_execsql_test 3.1.$tn.3 {
    SELECT a, b, c, typeof(a) FROM x1 WHERE a='2'
  } {2 two ii text}
  do_execsql_test 3.1.$tn.4 {
    SELECT a, b, c, typeof(a) FROM x1 WHERE a='2.0'
  } {2.0 twopointoh ii.0 text}

  do_execsql_test 3.1.$tn.5 {
    SELECT a, b, c, typeof(a) FROM x2 WHERE a=2
  } {2 two ii integer 2 twopointoh ii.0 integer}
  do_execsql_test 3.1.$tn.6 {
    SELECT a, b, c, typeof(a) FROM x2 WHERE a=2.0
  } {2 two ii integer 2 twopointoh ii.0 integer}
  do_execsql_test 3.1.$tn.7 {
    SELECT a, b, c, typeof(a) FROM x2 WHERE a='2'
  } {2 two ii integer 2 twopointoh ii.0 integer}
  do_execsql_test 3.1.$tn.8 {
    SELECT a, b, c, typeof(a) FROM x2 WHERE a='2.0'
  } {2 two ii integer 2 twopointoh ii.0 integer}

  do_execsql_test 3.1.$tn.9 {
    SELECT a, b, c, typeof(a) FROM x3 WHERE a=2
  } {2.0 two ii real 2.0 twopointoh ii.0 real}
  do_execsql_test 3.1.$tn.10 {
    SELECT a, b, c, typeof(a) FROM x3 WHERE a=2.0
  } {2.0 two ii real 2.0 twopointoh ii.0 real}
  do_execsql_test 3.1.$tn.11 {
    SELECT a, b, c, typeof(a) FROM x3 WHERE a='2'
  } {2.0 two ii real 2.0 twopointoh ii.0 real}
  do_execsql_test 3.1.$tn.12 {
    SELECT a, b, c, typeof(a) FROM x3 WHERE a='2.0'
  } {2.0 two ii real 2.0 twopointoh ii.0 real}
}

#-------------------------------------------------------------------------
reset_db
do_execsql_test 4.0 {
  CREATE TABLE t2(a INTEGER, b TEXT);
  INSERT INTO t2 VALUES(1, 'two');
  INSERT INTO t2 VALUES(2, 'two');
  INSERT INTO t2 VALUES(3, 'two');
  INSERT INTO t2 VALUES(1, 'three');
  INSERT INTO t2 VALUES(2, 'three');
  INSERT INTO t2 VALUES(3, 'three');

  CREATE INDEX t2a_two ON t2(a) WHERE b='two';
}

# explain_i { SELECT sum(a), b FROM t2 WHERE b='two' }
do_execsql_test 4.1.1 {
  SELECT sum(a), b FROM t2 WHERE b='two'
} {6 two}
do_eqp_test 4.1.2 {
  SELECT sum(a), b FROM t2 WHERE b='two'
} {USING COVERING INDEX t2a_two}

#-------------------------------------------------------------------------
reset_db
do_execsql_test 5.0 {
  CREATE TABLE t1(a INTEGER PRIMQRY KEY, b, c);
}
do_catchsql_test 5.1 {
  CREATE INDEX ex1 ON t1(c) WHERE b IS 'abc' COLLATE g;
} {1 {no such collation sequence: g}}

proc xyz {lhs rhs} {
  return [string compare $lhs $rhs]
}
db collate xyz xyz
do_execsql_test 5.2 {
  CREATE INDEX ex1 ON t1(c) WHERE b IS 'abc' COLLATE xyz;
}
db close
sqlite3 db test.db
do_execsql_test 5.3 {
  SELECT * FROM t1
}

#-------------------------------------------------------------------------
reset_db
do_execsql_test 6.0 {
  CREATE TABLE t1(a INTEGER PRIMARY KEY, b, c);
  CREATE TABLE t2(x INTEGER PRIMARY KEY, y INTEGER, z INTEGER);
  INSERT INTO t1 VALUES(1, 1, 1);
  INSERT INTO t1 VALUES(2, 1, 2);
  INSERT INTO t2 VALUES(1, 5, 1);
  INSERT INTO t2 VALUES(2, 5, 2);

  CREATE INDEX t2z ON t2(z) WHERE y=5;
}

do_execsql_test 6.1 {
  ANALYZE;
  UPDATE sqlite_stat1 SET stat = '50 1' WHERE idx='t2z';
  UPDATE sqlite_stat1 SET stat = '50' WHERE tbl='t2' AND idx IS NULL;
  UPDATE sqlite_stat1 SET stat = '5000' WHERE tbl='t1' AND idx IS NULL;
  ANALYZE sqlite_schema;
}

do_execsql_test 6.2 {
  SELECT * FROM t1, t2 WHERE b=1 AND z=c AND y=5;
} {
  1 1 1  1 5 1
  2 1 2  2 5 2
}

do_eqp_test 6.3 {
  SELECT * FROM t1, t2 WHERE b=1 AND z=c AND y=5;
} {BLOOM FILTER ON t2}

do_execsql_test 6.4 {
  SELECT * FROM t1 LEFT JOIN t2 ON (y=5) WHERE b=1 AND z IS c;
} {
  1 1 1  1 5 1
  2 1 2  2 5 2
}

do_eqp_test 6.5 {
  SELECT * FROM t1 LEFT JOIN t2 ON (y=5) WHERE b=1 AND z IS c;
} {BLOOM FILTER ON t2}

do_execsql_test 6.6 {
  CREATE INDEX t2yz ON t2(y, z) WHERE y=5;
}

do_execsql_test 6.7 {
  SELECT * FROM t1 LEFT JOIN t2 ON (y=5) WHERE b=1 AND z IS c;
} {
  1 1 1  1 5 1
  2 1 2  2 5 2
}

finish_test