/ Check-in [3edbe8d6]
Login

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

Overview
Comment:Optimize LIKE and GLOB operators in the WHERE clause. Code passes all regression tests but still needs additional tests. (CVS 2581)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 3edbe8d6217fd1180883e6b9f1e5b9011a39f80d
User & Date: drh 2005-08-12 22:56:09
Context
2005-08-12
22:58
Improved error message when a #NNN parameter appears on user input. Additional coverage testing. (CVS 2582) check-in: 3c00f598 user: drh tags: trunk
22:56
Optimize LIKE and GLOB operators in the WHERE clause. Code passes all regression tests but still needs additional tests. (CVS 2581) check-in: 3edbe8d6 user: drh tags: trunk
2005-08-11
02:10
Improve the error message associated with SQLITE_FULL. Ticket #1353. Also remove error messages for obsolete error codes SQLITE_INTERNAL, SQLITE_NOTFOUND, and SQLITE_TOOBIG. (CVS 2580) check-in: fa7403c7 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/expr.c.

     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** This file contains routines used for analyzing expressions and
    13     13   ** for generating VDBE code that evaluates expressions in SQLite.
    14     14   **
    15         -** $Id: expr.c,v 1.214 2005/07/29 15:10:18 drh Exp $
           15  +** $Id: expr.c,v 1.215 2005/08/12 22:56:09 drh Exp $
    16     16   */
    17     17   #include "sqliteInt.h"
    18     18   #include <ctype.h>
    19     19   
    20     20   /*
    21     21   ** Return the 'affinity' of the expression pExpr if any.
    22     22   **
................................................................................
   375    375     if( p->token.dyn ) sqliteFree((char*)p->token.z);
   376    376     sqlite3ExprDelete(p->pLeft);
   377    377     sqlite3ExprDelete(p->pRight);
   378    378     sqlite3ExprListDelete(p->pList);
   379    379     sqlite3SelectDelete(p->pSelect);
   380    380     sqliteFree(p);
   381    381   }
          382  +
          383  +/*
          384  +** The Expr.token field might be a string literal that is quoted.
          385  +** If so, remove the quotation marks.
          386  +*/
          387  +void sqlite3DequoteExpr(Expr *p){
          388  +  if( ExprHasAnyProperty(p, EP_Dequoted) ){
          389  +    return;
          390  +  }
          391  +  ExprSetProperty(p, EP_Dequoted);
          392  +  if( p->token.dyn==0 ){
          393  +    if( p->op==TK_BLOB ){
          394  +      p->token.n--;
          395  +      p->token.z++;
          396  +    }
          397  +    sqlite3TokenCopy(&p->token, &p->token);
          398  +  }
          399  +  sqlite3Dequote((char*)p->token.z);
          400  +}
   382    401   
   383    402   
   384    403   /*
   385    404   ** The following group of routines make deep copies of expressions,
   386    405   ** expression lists, ID lists, and select statements.  The copies can
   387    406   ** be deleted (by being passed to their respective ...Delete() routines)
   388    407   ** without effecting the originals.
................................................................................
  1438   1457         codeInteger(v, pExpr->token.z, pExpr->token.n);
  1439   1458         break;
  1440   1459       }
  1441   1460       case TK_FLOAT:
  1442   1461       case TK_STRING: {
  1443   1462         assert( TK_FLOAT==OP_Real );
  1444   1463         assert( TK_STRING==OP_String8 );
         1464  +      sqlite3DequoteExpr(pExpr);
  1445   1465         sqlite3VdbeOp3(v, op, 0, 0, pExpr->token.z, pExpr->token.n);
  1446         -      sqlite3VdbeDequoteP3(v, -1);
  1447   1466         break;
  1448   1467       }
  1449   1468       case TK_NULL: {
  1450   1469         sqlite3VdbeAddOp(v, OP_Null, 0, 0);
  1451   1470         break;
  1452   1471       }
  1453   1472   #ifndef SQLITE_OMIT_BLOB_LITERAL
  1454   1473       case TK_BLOB: {
  1455   1474         assert( TK_BLOB==OP_HexBlob );
  1456         -      sqlite3VdbeOp3(v, op, 0, 0, pExpr->token.z+1, pExpr->token.n-1);
  1457         -      sqlite3VdbeDequoteP3(v, -1);
         1475  +      sqlite3VdbeOp3(v, op, 0, 0, pExpr->token.z+2, pExpr->token.n-3);
  1458   1476         break;
  1459   1477       }
  1460   1478   #endif
  1461   1479       case TK_VARIABLE: {
  1462   1480         sqlite3VdbeAddOp(v, OP_Variable, pExpr->iTable, 0);
  1463   1481         if( pExpr->token.n>1 ){
  1464   1482           sqlite3VdbeChangeP3(v, -1, pExpr->token.z, pExpr->token.n);
................................................................................
  1712   1730                          "RAISE() may only be used within a trigger-program");
  1713   1731   	return;
  1714   1732         }
  1715   1733         if( pExpr->iColumn!=OE_Ignore ){
  1716   1734            assert( pExpr->iColumn==OE_Rollback ||
  1717   1735                    pExpr->iColumn == OE_Abort ||
  1718   1736                    pExpr->iColumn == OE_Fail );
         1737  +         sqlite3DequoteExpr(pExpr);
  1719   1738            sqlite3VdbeOp3(v, OP_Halt, SQLITE_CONSTRAINT, pExpr->iColumn,
  1720   1739                           pExpr->token.z, pExpr->token.n);
  1721         -         sqlite3VdbeDequoteP3(v, -1);
         1740  +//         sqlite3VdbeDequoteP3(v, -1);
  1722   1741         } else {
  1723   1742            assert( pExpr->iColumn == OE_Ignore );
  1724   1743            sqlite3VdbeAddOp(v, OP_ContextPop, 0, 0);
  1725   1744            sqlite3VdbeAddOp(v, OP_Goto, 0, pParse->trigStack->ignoreJump);
  1726   1745            VdbeComment((v, "# raise(IGNORE)"));
  1727   1746         }
  1728   1747       }

Changes to src/sqliteInt.h.

     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** Internal interface definitions for SQLite.
    13     13   **
    14         -** @(#) $Id: sqliteInt.h,v 1.400 2005/07/23 22:59:56 drh Exp $
           14  +** @(#) $Id: sqliteInt.h,v 1.401 2005/08/12 22:56:09 drh Exp $
    15     15   */
    16     16   #ifndef _SQLITEINT_H_
    17     17   #define _SQLITEINT_H_
    18     18   
    19     19   /*
    20     20   ** These #defines should enable >2GB file support on Posix if the
    21     21   ** underlying operating system supports it.  If the OS lacks
................................................................................
   842    842   */
   843    843   #define EP_FromJoin     0x01  /* Originated in ON or USING clause of a join */
   844    844   #define EP_Agg          0x02  /* Contains one or more aggregate functions */
   845    845   #define EP_Resolved     0x04  /* IDs have been resolved to COLUMNs */
   846    846   #define EP_Error        0x08  /* Expression contains one or more errors */
   847    847   #define EP_Not          0x10  /* Operator preceeded by NOT */
   848    848   #define EP_VarSelect    0x20  /* pSelect is correlated, not constant */
          849  +#define EP_Dequoted     0x40  /* True if the string has been dequoted */
   849    850   
   850    851   /*
   851    852   ** These macros can be used to test, set, or clear bits in the 
   852    853   ** Expr.flags field.
   853    854   */
   854    855   #define ExprHasProperty(E,P)     (((E)->flags&(P))==(P))
   855    856   #define ExprHasAnyProperty(E,P)  (((E)->flags&(P))!=0)
................................................................................
  1344   1345   char *sqlite3MPrintf(const char*, ...);
  1345   1346   char *sqlite3VMPrintf(const char*, va_list);
  1346   1347   void sqlite3DebugPrintf(const char*, ...);
  1347   1348   void *sqlite3TextToPtr(const char*);
  1348   1349   void sqlite3SetString(char **, ...);
  1349   1350   void sqlite3ErrorMsg(Parse*, const char*, ...);
  1350   1351   void sqlite3Dequote(char*);
         1352  +void sqlite3DequoteExpr(Expr*);
  1351   1353   int sqlite3KeywordCode(const char*, int);
  1352   1354   int sqlite3RunParser(Parse*, const char*, char **);
  1353   1355   void sqlite3FinishCoding(Parse*);
  1354   1356   Expr *sqlite3Expr(int, Expr*, Expr*, const Token*);
  1355   1357   Expr *sqlite3RegisterExpr(Parse*,Token*);
  1356   1358   Expr *sqlite3ExprAnd(Expr*, Expr*);
  1357   1359   void sqlite3ExprSpan(Expr*,Token*,Token*);

Changes to src/vdbe.h.

    11     11   *************************************************************************
    12     12   ** Header file for the Virtual DataBase Engine (VDBE)
    13     13   **
    14     14   ** This header defines the interface to the virtual database engine
    15     15   ** or VDBE.  The VDBE implements an abstract machine that runs a
    16     16   ** simple program to access and modify the underlying database.
    17     17   **
    18         -** $Id: vdbe.h,v 1.95 2005/05/19 08:43:00 danielk1977 Exp $
           18  +** $Id: vdbe.h,v 1.96 2005/08/12 22:56:09 drh Exp $
    19     19   */
    20     20   #ifndef _SQLITE_VDBE_H_
    21     21   #define _SQLITE_VDBE_H_
    22     22   #include <stdio.h>
    23     23   
    24     24   /*
    25     25   ** A single VDBE is an opaque structure named "Vdbe".  Only routines
................................................................................
   101    101   void sqlite3VdbeCreateCallback(Vdbe*, int*);
   102    102   int sqlite3VdbeAddOp(Vdbe*,int,int,int);
   103    103   int sqlite3VdbeOp3(Vdbe*,int,int,int,const char *zP3,int);
   104    104   int sqlite3VdbeAddOpList(Vdbe*, int nOp, VdbeOpList const *aOp);
   105    105   void sqlite3VdbeChangeP1(Vdbe*, int addr, int P1);
   106    106   void sqlite3VdbeChangeP2(Vdbe*, int addr, int P2);
   107    107   void sqlite3VdbeChangeP3(Vdbe*, int addr, const char *zP1, int N);
   108         -void sqlite3VdbeDequoteP3(Vdbe*, int addr);
   109    108   int sqlite3VdbeFindOp(Vdbe*, int, int, int);
   110    109   VdbeOp *sqlite3VdbeGetOp(Vdbe*, int);
   111    110   int sqlite3VdbeMakeLabel(Vdbe*);
   112    111   void sqlite3VdbeDelete(Vdbe*);
   113    112   void sqlite3VdbeMakeReady(Vdbe*,int,int,int,int,int);
   114    113   int sqlite3VdbeFinalize(Vdbe*);
   115    114   void sqlite3VdbeResolveLabel(Vdbe*, int);

Changes to src/vdbeaux.c.

   438    438     assert( p->aOp==0 || p->aOp[p->nOp-1].p3==0 );
   439    439     va_start(ap, zFormat);
   440    440     sqlite3VdbeChangeP3(p, -1, sqlite3VMPrintf(zFormat, ap), P3_DYNAMIC);
   441    441     va_end(ap);
   442    442   }
   443    443   #endif
   444    444   
   445         -/*
   446         -** If the P3 operand to the specified instruction appears
   447         -** to be a quoted string token, then this procedure removes 
   448         -** the quotes.
   449         -**
   450         -** The quoting operator can be either a grave ascent (ASCII 0x27)
   451         -** or a double quote character (ASCII 0x22).  Two quotes in a row
   452         -** resolve to be a single actual quote character within the string.
   453         -*/
   454         -void sqlite3VdbeDequoteP3(Vdbe *p, int addr){
   455         -  Op *pOp;
   456         -  assert( p->magic==VDBE_MAGIC_INIT );
   457         -  if( p->aOp==0 ) return;
   458         -  if( addr<0 || addr>=p->nOp ){
   459         -    addr = p->nOp - 1;
   460         -    if( addr<0 ) return;
   461         -  }
   462         -  pOp = &p->aOp[addr];
   463         -  if( pOp->p3==0 || pOp->p3[0]==0 ) return;
   464         -  if( pOp->p3type==P3_STATIC ){
   465         -    pOp->p3 = sqliteStrDup(pOp->p3);
   466         -    pOp->p3type = P3_DYNAMIC;
   467         -  }
   468         -  assert( pOp->p3type==P3_DYNAMIC );
   469         -  sqlite3Dequote(pOp->p3);
   470         -}
   471         -
   472    445   /*
   473    446   ** Search the current program starting at instruction addr for the given
   474    447   ** opcode and P2 value.  Return the address plus 1 if found and 0 if not
   475    448   ** found.
   476    449   */
   477    450   int sqlite3VdbeFindOp(Vdbe *p, int addr, int op, int p2){
   478    451     int i;

Changes to src/where.c.

    12     12   ** This module contains C code that generates VDBE code used to process
    13     13   ** the WHERE clause of SQL statements.  This module is reponsible for
    14     14   ** generating the code that loops through a table looking for applicable
    15     15   ** rows.  Indices are selected and used to speed the search when doing
    16     16   ** so is applicable.  Because this module is responsible for selecting
    17     17   ** indices, you might also think of this module as the "query optimizer".
    18     18   **
    19         -** $Id: where.c,v 1.159 2005/08/02 17:48:22 drh Exp $
           19  +** $Id: where.c,v 1.160 2005/08/12 22:56:09 drh Exp $
    20     20   */
    21     21   #include "sqliteInt.h"
    22     22   
    23     23   /*
    24     24   ** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
    25     25   */
    26     26   #define BMS  (sizeof(Bitmask)*8)
................................................................................
   453    453     WhereTerm *pTerm;
   454    454     int i;
   455    455     for(i=pWC->nTerm-1, pTerm=pWC->a; i>=0; i--, pTerm++){
   456    456       exprAnalyze(pTabList, pMaskSet, pTerm);
   457    457     }
   458    458   }
   459    459   
          460  +#ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
          461  +/*
          462  +** Check to see if the given expression is a LIKE or GLOB operator that
          463  +** can be optimized using inequality constraints.  Return TRUE if it is
          464  +** so and false if not.
          465  +**
          466  +** In order for the operator to be optimizible, the RHS must be a string
          467  +** literal that does not begin with a wildcard.  
          468  +*/
          469  +static int isLikeOrGlob(
          470  +  Expr *pExpr,      /* Test this expression */
          471  +  int *pnPattern,   /* Number of non-wildcard prefix characters */
          472  +  int *pisComplete  /* True if the only wildcard is % in the last character */
          473  +){
          474  +  const char *z;
          475  +  Expr *pRight, *pLeft;
          476  +  int c, cnt;
          477  +  char wc1, wc2, wc3;
          478  +  if( pExpr->op!=TK_FUNCTION ){
          479  +    return 0;
          480  +  }
          481  +  if( pExpr->pList->nExpr!=2 ){
          482  +    return 0;
          483  +  }
          484  +  if( pExpr->token.n!=4 ){
          485  +    return 0;
          486  +  }
          487  +  z = pExpr->token.z;
          488  +  if( sqlite3StrNICmp(z, "glob", 4)==0 ){
          489  +    wc1 = '*';
          490  +    wc2 = '?';
          491  +    wc3 = '[';
          492  +  }
          493  +#ifdef SQLITE_CASE_SENSITIVE_LIKE
          494  +  else if( sqlite3StrNICmp(z, "like", 4)==0 ){
          495  +    wc1 = '%';
          496  +    wc2 = '_';
          497  +    wc3 = '_';
          498  +  }
          499  +#endif
          500  +  else{
          501  +    return 0;
          502  +  }
          503  +  pRight = pExpr->pList->a[0].pExpr;
          504  +  if( pRight->op!=TK_STRING ){
          505  +    return 0;
          506  +  }
          507  +  pLeft = pExpr->pList->a[1].pExpr;
          508  +  if( pLeft->op!=TK_COLUMN ){
          509  +    return 0;
          510  +  }
          511  +  sqlite3DequoteExpr(pRight);
          512  +  z = pRight->token.z;
          513  +  for(cnt=0; (c=z[cnt])!=0 && c!=wc1 && c!=wc2 && c!=wc3; cnt++){}
          514  +  if( cnt==0 || 255==(u8)z[cnt] ){
          515  +    return 0;
          516  +  }
          517  +  *pisComplete = z[cnt]==wc1 && z[cnt+1]==0;
          518  +  *pnPattern = cnt;
          519  +  return 1;
          520  +}
          521  +#endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */
          522  +
   460    523   /*
   461    524   ** The input to this routine is an WhereTerm structure with only the
   462    525   ** "pExpr" field filled in.  The job of this routine is to analyze the
   463    526   ** subexpression and populate all the other fields of the WhereTerm
   464    527   ** structure.
   465    528   **
   466    529   ** If the expression is of the form "<expr> <op> X" it gets commuted
................................................................................
   474    537     ExprMaskSet *pMaskSet,    /* table masks */
   475    538     WhereTerm *pTerm          /* the WHERE clause term to be analyzed */
   476    539   ){
   477    540     Expr *pExpr = pTerm->pExpr;
   478    541     Bitmask prereqLeft;
   479    542     Bitmask prereqAll;
   480    543     int idxRight;
          544  +  int nPattern;
          545  +  int isComplete;
   481    546   
   482    547     prereqLeft = exprTableUsage(pMaskSet, pExpr->pLeft);
   483    548     pTerm->prereqRight = exprTableUsage(pMaskSet, pExpr->pRight);
   484    549     pTerm->prereqAll = prereqAll = exprTableUsage(pMaskSet, pExpr);
   485    550     pTerm->leftCursor = -1;
   486    551     pTerm->iParent = -1;
   487    552     pTerm->operator = 0;
................................................................................
   514    579         pNew->leftColumn = pLeft->iColumn;
   515    580         pNew->prereqRight = prereqLeft;
   516    581         pNew->prereqAll = prereqAll;
   517    582         pNew->operator = operatorMask(pDup->op);
   518    583       }
   519    584     }
   520    585   
          586  +#ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
   521    587     /* If a term is the BETWEEN operator, create two new virtual terms
   522    588     ** that define the range that the BETWEEN implements.
   523    589     */
   524    590     else if( pExpr->op==TK_BETWEEN ){
   525    591       ExprList *pList = pExpr->pList;
   526    592       int i;
   527    593       static const u8 ops[] = {TK_GE, TK_LE};
................................................................................
   535    601         pNewTerm = whereClauseInsert(pTerm->pWC, pNewExpr,
   536    602                                      TERM_VIRTUAL|TERM_DYNAMIC);
   537    603         exprAnalyze(pSrc, pMaskSet, pNewTerm);
   538    604         pNewTerm->iParent = pTerm->idx;
   539    605       }
   540    606       pTerm->nChild = 2;
   541    607     }
          608  +#endif /* SQLITE_OMIT_BETWEEN_OPTIMIZATION */
   542    609   
          610  +#ifndef SQLITE_OMIT_OR_OPTIMIZATION
   543    611     /* Attempt to convert OR-connected terms into an IN operator so that
   544    612     ** they can make use of indices.
   545    613     */
   546    614     else if( pExpr->op==TK_OR ){
   547    615       int ok;
   548    616       int i, j;
   549    617       int iColumn, iCursor;
................................................................................
   593    661         pTerm->pExpr = pNew;
   594    662         pTerm->flags |= TERM_DYNAMIC;
   595    663         exprAnalyze(pSrc, pMaskSet, pTerm);
   596    664       }
   597    665   or_not_possible:
   598    666       whereClauseClear(&sOr);
   599    667     }
          668  +#endif /* SQLITE_OMIT_OR_OPTIMIZATION */
          669  +
          670  +#ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
          671  +  /* Add constraints to reduce the search space on a LIKE or GLOB
          672  +  ** operator.
          673  +  */
          674  +  if( isLikeOrGlob(pExpr, &nPattern, &isComplete) ){
          675  +    Expr *pLeft, *pRight;
          676  +    Expr *pStr1, *pStr2;
          677  +    Expr *pNewExpr1, *pNewExpr2;
          678  +    WhereTerm *pNewTerm1, *pNewTerm2;
          679  +    pLeft = pExpr->pList->a[1].pExpr;
          680  +    pRight = pExpr->pList->a[0].pExpr;
          681  +    pStr1 = sqlite3Expr(TK_STRING, 0, 0, 0);
          682  +    if( pStr1 ){
          683  +      sqlite3TokenCopy(&pStr1->token, &pRight->token);
          684  +      pStr1->token.n = nPattern;
          685  +    }
          686  +    pStr2 = sqlite3ExprDup(pStr1);
          687  +    if( pStr2 ){
          688  +      assert( pStr2->token.dyn );
          689  +      ++*(u8*)&pStr2->token.z[nPattern-1];
          690  +    }
          691  +    pNewExpr1 = sqlite3Expr(TK_GE, sqlite3ExprDup(pLeft), pStr1, 0);
          692  +    pNewTerm1 = whereClauseInsert(pTerm->pWC, pNewExpr1,
          693  +                                  TERM_VIRTUAL|TERM_DYNAMIC);
          694  +    exprAnalyze(pSrc, pMaskSet, pNewTerm1);
          695  +    pNewExpr2 = sqlite3Expr(TK_LT, sqlite3ExprDup(pLeft), pStr2, 0);
          696  +    pNewTerm2 = whereClauseInsert(pTerm->pWC, pNewExpr2,
          697  +                                 TERM_VIRTUAL|TERM_DYNAMIC);
          698  +    exprAnalyze(pSrc, pMaskSet, pNewTerm2);
          699  +    if( isComplete ){
          700  +      pNewTerm2->iParent = pTerm->idx;
          701  +      pNewTerm1->iParent = pTerm->idx;
          702  +      pTerm->nChild = 2;
          703  +    }
          704  +  }
          705  +#endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */
   600    706   }
   601    707   
   602    708   
   603    709   /*
   604    710   ** This routine decides if pIdx can be used to satisfy the ORDER BY
   605    711   ** clause.  If it can, it returns 1.  If pIdx cannot satisfy the
   606    712   ** ORDER BY clause, this routine returns 0.