/ Check-in [76cd611d]
Login

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

Overview
Comment:Smaller and faster implementation of exprMightBeIndexed().
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: 76cd611d41465fcec61c21520d55172cb236530f38386b7d4a5544ba87de2353
User & Date: drh 2017-04-11 18:06:48
Context
2017-04-11
19:00
Update this branch with latest trunk changes. check-in: 0f66a093 user: dan tags: schemalint
18:55
Limit the depth of recursion for valid JSON in the JSON1 extension in order to avoid using excess stack space in the recursive descent parser. Fix for ticket [981329adeef51011052667a9]. check-in: 1f68c184 user: drh tags: trunk
18:06
Smaller and faster implementation of exprMightBeIndexed(). check-in: 76cd611d user: drh tags: trunk
16:44
Very slight smaller and faster sqlite3SelectNew() check-in: 4143650c user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/whereexpr.c.

   826    826     return mask;
   827    827   }
   828    828   
   829    829   /*
   830    830   ** Expression pExpr is one operand of a comparison operator that might
   831    831   ** be useful for indexing.  This routine checks to see if pExpr appears
   832    832   ** in any index.  Return TRUE (1) if pExpr is an indexed term and return
   833         -** FALSE (0) if not.  If TRUE is returned, also set *piCur to the cursor
   834         -** number of the table that is indexed and *piColumn to the column number
          833  +** FALSE (0) if not.  If TRUE is returned, also set aiCurCol[0] to the cursor
          834  +** number of the table that is indexed and aiCurCol[1] to the column number
   835    835   ** of the column that is indexed, or XN_EXPR (-2) if an expression is being
   836    836   ** indexed.
   837    837   **
   838    838   ** If pExpr is a TK_COLUMN column reference, then this routine always returns
   839    839   ** true even if that particular column is not indexed, because the column
   840    840   ** might be added to an automatic index later.
   841    841   */
   842         -static int exprMightBeIndexed(
          842  +static SQLITE_NOINLINE int exprMightBeIndexed2(
   843    843     SrcList *pFrom,        /* The FROM clause */
   844         -  int op,                /* The specific comparison operator */
   845    844     Bitmask mPrereq,       /* Bitmask of FROM clause terms referenced by pExpr */
   846         -  Expr *pExpr,           /* An operand of a comparison operator */
   847         -  int *piCur,            /* Write the referenced table cursor number here */
   848         -  int *piColumn          /* Write the referenced table column number here */
          845  +  int *aiCurCol,         /* Write the referenced table cursor and column here */
          846  +  Expr *pExpr            /* An operand of a comparison operator */
   849    847   ){
   850    848     Index *pIdx;
   851    849     int i;
   852    850     int iCur;
   853         -
          851  +  for(i=0; mPrereq>1; i++, mPrereq>>=1){}
          852  +  iCur = pFrom->a[i].iCursor;
          853  +  for(pIdx=pFrom->a[i].pTab->pIndex; pIdx; pIdx=pIdx->pNext){
          854  +    if( pIdx->aColExpr==0 ) continue;
          855  +    for(i=0; i<pIdx->nKeyCol; i++){
          856  +      if( pIdx->aiColumn[i]!=XN_EXPR ) continue;
          857  +      if( sqlite3ExprCompareSkip(pExpr, pIdx->aColExpr->a[i].pExpr, iCur)==0 ){
          858  +        aiCurCol[0] = iCur;
          859  +        aiCurCol[1] = XN_EXPR;
          860  +        return 1;
          861  +      }
          862  +    }
          863  +  }
          864  +  return 0;
          865  +}
          866  +static int exprMightBeIndexed(
          867  +  SrcList *pFrom,        /* The FROM clause */
          868  +  Bitmask mPrereq,       /* Bitmask of FROM clause terms referenced by pExpr */
          869  +  int *aiCurCol,         /* Write the referenced table cursor & column here */
          870  +  Expr *pExpr,           /* An operand of a comparison operator */
          871  +  int op                 /* The specific comparison operator */
          872  +){
   854    873     /* If this expression is a vector to the left or right of a 
   855    874     ** inequality constraint (>, <, >= or <=), perform the processing 
   856    875     ** on the first element of the vector.  */
   857    876     assert( TK_GT+1==TK_LE && TK_GT+2==TK_LT && TK_GT+3==TK_GE );
   858    877     assert( TK_IS<TK_GE && TK_ISNULL<TK_GE && TK_IN<TK_GE );
   859    878     assert( op<=TK_GE );
   860    879     if( pExpr->op==TK_VECTOR && (op>=TK_GT && ALWAYS(op<=TK_GE)) ){
   861    880       pExpr = pExpr->x.pList->a[0].pExpr;
   862    881     }
   863    882   
   864    883     if( pExpr->op==TK_COLUMN ){
   865         -    *piCur = pExpr->iTable;
   866         -    *piColumn = pExpr->iColumn;
          884  +    aiCurCol[0] = pExpr->iTable;
          885  +    aiCurCol[1] = pExpr->iColumn;
   867    886       return 1;
   868    887     }
   869    888     if( mPrereq==0 ) return 0;                 /* No table references */
   870    889     if( (mPrereq&(mPrereq-1))!=0 ) return 0;   /* Refs more than one table */
   871         -  for(i=0; mPrereq>1; i++, mPrereq>>=1){}
   872         -  iCur = pFrom->a[i].iCursor;
   873         -  for(pIdx=pFrom->a[i].pTab->pIndex; pIdx; pIdx=pIdx->pNext){
   874         -    if( pIdx->aColExpr==0 ) continue;
   875         -    for(i=0; i<pIdx->nKeyCol; i++){
   876         -      if( pIdx->aiColumn[i]!=XN_EXPR ) continue;
   877         -      if( sqlite3ExprCompareSkip(pExpr, pIdx->aColExpr->a[i].pExpr, iCur)==0 ){
   878         -        *piCur = iCur;
   879         -        *piColumn = XN_EXPR;
   880         -        return 1;
   881         -      }
   882         -    }
   883         -  }
   884         -  return 0;
          890  +  return exprMightBeIndexed2(pFrom,mPrereq,aiCurCol,pExpr);
   885    891   }
   886    892   
   887    893   /*
   888    894   ** The input to this routine is an WhereTerm structure with only the
   889    895   ** "pExpr" field filled in.  The job of this routine is to analyze the
   890    896   ** subexpression and populate all the other fields of the WhereTerm
   891    897   ** structure.
................................................................................
   957    963       }
   958    964     }
   959    965     pTerm->prereqAll = prereqAll;
   960    966     pTerm->leftCursor = -1;
   961    967     pTerm->iParent = -1;
   962    968     pTerm->eOperator = 0;
   963    969     if( allowedOp(op) ){
   964         -    int iCur, iColumn;
          970  +    int aiCurCol[2];
   965    971       Expr *pLeft = sqlite3ExprSkipCollate(pExpr->pLeft);
   966    972       Expr *pRight = sqlite3ExprSkipCollate(pExpr->pRight);
   967    973       u16 opMask = (pTerm->prereqRight & prereqLeft)==0 ? WO_ALL : WO_EQUIV;
   968    974   
   969    975       if( pTerm->iField>0 ){
   970    976         assert( op==TK_IN );
   971    977         assert( pLeft->op==TK_VECTOR );
   972    978         pLeft = pLeft->x.pList->a[pTerm->iField-1].pExpr;
   973    979       }
   974    980   
   975         -    if( exprMightBeIndexed(pSrc, op, prereqLeft, pLeft, &iCur, &iColumn) ){
   976         -      pTerm->leftCursor = iCur;
   977         -      pTerm->u.leftColumn = iColumn;
          981  +    if( exprMightBeIndexed(pSrc, prereqLeft, aiCurCol, pLeft, op) ){
          982  +      pTerm->leftCursor = aiCurCol[0];
          983  +      pTerm->u.leftColumn = aiCurCol[1];
   978    984         pTerm->eOperator = operatorMask(op) & opMask;
   979    985       }
   980    986       if( op==TK_IS ) pTerm->wtFlags |= TERM_IS;
   981    987       if( pRight 
   982         -     && exprMightBeIndexed(pSrc, op, pTerm->prereqRight, pRight, &iCur,&iColumn)
          988  +     && exprMightBeIndexed(pSrc, pTerm->prereqRight, aiCurCol, pRight, op)
   983    989       ){
   984    990         WhereTerm *pNew;
   985    991         Expr *pDup;
   986    992         u16 eExtraOp = 0;        /* Extra bits for pNew->eOperator */
   987    993         assert( pTerm->iField==0 );
   988    994         if( pTerm->leftCursor>=0 ){
   989    995           int idxNew;
................................................................................
  1005   1011             eExtraOp = WO_EQUIV;
  1006   1012           }
  1007   1013         }else{
  1008   1014           pDup = pExpr;
  1009   1015           pNew = pTerm;
  1010   1016         }
  1011   1017         exprCommute(pParse, pDup);
  1012         -      pNew->leftCursor = iCur;
  1013         -      pNew->u.leftColumn = iColumn;
         1018  +      pNew->leftCursor = aiCurCol[0];
         1019  +      pNew->u.leftColumn = aiCurCol[1];
  1014   1020         testcase( (prereqLeft | extraRight) != prereqLeft );
  1015   1021         pNew->prereqRight = prereqLeft | extraRight;
  1016   1022         pNew->prereqAll = prereqAll;
  1017   1023         pNew->eOperator = (operatorMask(pDup->op) + eExtraOp) & opMask;
  1018   1024       }
  1019   1025     }
  1020   1026