/ Check-in [9f932655]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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

Overview
Comment:Enhance the LIKE/GLOB query optimization so that it works as long as there is an index with the appropriate collating sequence and even if the default collating sequence of the column is different. Ticket [4711020446da7d93d99].
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 9f932655f9eb9fdab16d7deed98b7cad414e0ca6
User & Date: drh 2010-07-22 17:49:53
Context
2010-07-22
17:55
Make the sqlite3_db_status() routine threadsafe. check-in: 241f7bd1 user: dan tags: trunk
17:49
Enhance the LIKE/GLOB query optimization so that it works as long as there is an index with the appropriate collating sequence and even if the default collating sequence of the column is different. Ticket [4711020446da7d93d99]. check-in: 9f932655 user: drh tags: trunk
15:44
Add test/threadtest3.c, containing multi-thread tests implemented in C. check-in: aad88cf5 user: dan tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/expr.c.

    50     50       int j = pExpr->iColumn;
    51     51       if( j<0 ) return SQLITE_AFF_INTEGER;
    52     52       assert( pExpr->pTab && j<pExpr->pTab->nCol );
    53     53       return pExpr->pTab->aCol[j].affinity;
    54     54     }
    55     55     return pExpr->affinity;
    56     56   }
           57  +
           58  +/*
           59  +** Set the explicit collating sequence for an expression to the
           60  +** collating sequence supplied in the second argument.
           61  +*/
           62  +Expr *sqlite3ExprSetColl(Expr *pExpr, CollSeq *pColl){
           63  +  if( pExpr && pColl ){
           64  +    pExpr->pColl = pColl;
           65  +    pExpr->flags |= EP_ExpCollate;
           66  +  }
           67  +  return pExpr;
           68  +}
    57     69   
    58     70   /*
    59     71   ** Set the collating sequence for expression pExpr to be the collating
    60     72   ** sequence named by pToken.   Return a pointer to the revised expression.
    61     73   ** The collating sequence is marked as "explicit" using the EP_ExpCollate
    62     74   ** flag.  An explicit collating sequence will override implicit
    63     75   ** collating sequences.
    64     76   */
    65         -Expr *sqlite3ExprSetColl(Parse *pParse, Expr *pExpr, Token *pCollName){
           77  +Expr *sqlite3ExprSetCollByToken(Parse *pParse, Expr *pExpr, Token *pCollName){
    66     78     char *zColl = 0;            /* Dequoted name of collation sequence */
    67     79     CollSeq *pColl;
    68     80     sqlite3 *db = pParse->db;
    69     81     zColl = sqlite3NameFromToken(db, pCollName);
    70         -  if( pExpr && zColl ){
    71         -    pColl = sqlite3LocateCollSeq(pParse, zColl);
    72         -    if( pColl ){
    73         -      pExpr->pColl = pColl;
    74         -      pExpr->flags |= EP_ExpCollate;
    75         -    }
    76         -  }
           82  +  pColl = sqlite3LocateCollSeq(pParse, zColl);
           83  +  sqlite3ExprSetColl(pExpr, pColl);
    77     84     sqlite3DbFree(db, zColl);
    78     85     return pExpr;
    79     86   }
    80     87   
    81     88   /*
    82     89   ** Return the default collation sequence for the expression pExpr. If
    83     90   ** there is no default collation type, return 0.

Changes to src/parse.y.

   776    776   }
   777    777   expr(A) ::= VARIABLE(X).     {
   778    778     spanExpr(&A, pParse, TK_VARIABLE, &X);
   779    779     sqlite3ExprAssignVarNumber(pParse, A.pExpr);
   780    780     spanSet(&A, &X, &X);
   781    781   }
   782    782   expr(A) ::= expr(E) COLLATE ids(C). {
   783         -  A.pExpr = sqlite3ExprSetColl(pParse, E.pExpr, &C);
          783  +  A.pExpr = sqlite3ExprSetCollByToken(pParse, E.pExpr, &C);
   784    784     A.zStart = E.zStart;
   785    785     A.zEnd = &C.z[C.n];
   786    786   }
   787    787   %ifndef SQLITE_OMIT_CAST
   788    788   expr(A) ::= CAST(X) LP expr(E) AS typetoken(T) RP(Y). {
   789    789     A.pExpr = sqlite3PExpr(pParse, TK_CAST, E.pExpr, 0, &T);
   790    790     spanSet(&A,&X,&Y);
................................................................................
  1104   1104   
  1105   1105   idxlist_opt(A) ::= .                         {A = 0;}
  1106   1106   idxlist_opt(A) ::= LP idxlist(X) RP.         {A = X;}
  1107   1107   idxlist(A) ::= idxlist(X) COMMA nm(Y) collate(C) sortorder(Z).  {
  1108   1108     Expr *p = 0;
  1109   1109     if( C.n>0 ){
  1110   1110       p = sqlite3Expr(pParse->db, TK_COLUMN, 0);
  1111         -    sqlite3ExprSetColl(pParse, p, &C);
         1111  +    sqlite3ExprSetCollByToken(pParse, p, &C);
  1112   1112     }
  1113   1113     A = sqlite3ExprListAppend(pParse,X, p);
  1114   1114     sqlite3ExprListSetName(pParse,A,&Y,1);
  1115   1115     sqlite3ExprListCheckLength(pParse, A, "index");
  1116   1116     if( A ) A->a[A->nExpr-1].sortOrder = (u8)Z;
  1117   1117   }
  1118   1118   idxlist(A) ::= nm(Y) collate(C) sortorder(Z). {
  1119   1119     Expr *p = 0;
  1120   1120     if( C.n>0 ){
  1121   1121       p = sqlite3PExpr(pParse, TK_COLUMN, 0, 0, 0);
  1122         -    sqlite3ExprSetColl(pParse, p, &C);
         1122  +    sqlite3ExprSetCollByToken(pParse, p, &C);
  1123   1123     }
  1124   1124     A = sqlite3ExprListAppend(pParse,0, p);
  1125   1125     sqlite3ExprListSetName(pParse, A, &Y, 1);
  1126   1126     sqlite3ExprListCheckLength(pParse, A, "index");
  1127   1127     if( A ) A->a[A->nExpr-1].sortOrder = (u8)Z;
  1128   1128   }
  1129   1129   

Changes to src/sqliteInt.h.

  2865   2865   void *sqlite3HexToBlob(sqlite3*, const char *z, int n);
  2866   2866   int sqlite3TwoPartName(Parse *, Token *, Token *, Token **);
  2867   2867   const char *sqlite3ErrStr(int);
  2868   2868   int sqlite3ReadSchema(Parse *pParse);
  2869   2869   CollSeq *sqlite3FindCollSeq(sqlite3*,u8 enc, const char*,int);
  2870   2870   CollSeq *sqlite3LocateCollSeq(Parse *pParse, const char*zName);
  2871   2871   CollSeq *sqlite3ExprCollSeq(Parse *pParse, Expr *pExpr);
  2872         -Expr *sqlite3ExprSetColl(Parse *pParse, Expr *, Token *);
         2872  +Expr *sqlite3ExprSetColl(Expr*, CollSeq*);
         2873  +Expr *sqlite3ExprSetCollByToken(Parse *pParse, Expr*, Token*);
  2873   2874   int sqlite3CheckCollSeq(Parse *, CollSeq *);
  2874   2875   int sqlite3CheckObjectName(Parse *, const char *);
  2875   2876   void sqlite3VdbeSetChanges(sqlite3 *, int);
  2876   2877   
  2877   2878   const void *sqlite3ValueText(sqlite3_value*, u8);
  2878   2879   int sqlite3ValueBytes(sqlite3_value*, u8);
  2879   2880   void sqlite3ValueSetStr(sqlite3_value*, int, const void *,u8, 

Changes to src/where.c.

   631    631   ){
   632    632     const char *z = 0;         /* String on RHS of LIKE operator */
   633    633     Expr *pRight, *pLeft;      /* Right and left size of LIKE operator */
   634    634     ExprList *pList;           /* List of operands to the LIKE operator */
   635    635     int c;                     /* One character in z[] */
   636    636     int cnt;                   /* Number of non-wildcard prefix characters */
   637    637     char wc[3];                /* Wildcard characters */
   638         -  CollSeq *pColl;            /* Collating sequence for LHS */
   639    638     sqlite3 *db = pParse->db;  /* Database connection */
   640    639     sqlite3_value *pVal = 0;
   641    640     int op;                    /* Opcode of pRight */
   642    641   
   643    642     if( !sqlite3IsLikeFunction(db, pExpr, pnoCase, wc) ){
   644    643       return 0;
   645    644     }
................................................................................
   650    649     pLeft = pList->a[1].pExpr;
   651    650     if( pLeft->op!=TK_COLUMN || sqlite3ExprAffinity(pLeft)!=SQLITE_AFF_TEXT ){
   652    651       /* IMP: R-02065-49465 The left-hand side of the LIKE or GLOB operator must
   653    652       ** be the name of an indexed column with TEXT affinity. */
   654    653       return 0;
   655    654     }
   656    655     assert( pLeft->iColumn!=(-1) ); /* Because IPK never has AFF_TEXT */
   657         -  pColl = sqlite3ExprCollSeq(pParse, pLeft);
   658         -  if( pColl==0 ) return 0;  /* Happens when LHS has an undefined collation */
   659         -  if( (pColl->type!=SQLITE_COLL_BINARY || *pnoCase) &&
   660         -      (pColl->type!=SQLITE_COLL_NOCASE || !*pnoCase) ){
   661         -    /* IMP: R-09003-32046 For the GLOB operator, the column must use the
   662         -    ** default BINARY collating sequence.
   663         -    ** IMP: R-41408-28306 For the LIKE operator, if case_sensitive_like mode
   664         -    ** is enabled then the column must use the default BINARY collating
   665         -    ** sequence, or if case_sensitive_like mode is disabled then the column
   666         -    ** must use the built-in NOCASE collating sequence.
   667         -    */
   668         -    return 0;
   669         -  }
   670    656   
   671    657     pRight = pList->a[0].pExpr;
   672    658     op = pRight->op;
   673    659     if( op==TK_REGISTER ){
   674    660       op = pRight->op2;
   675    661     }
   676    662     if( op==TK_VARIABLE ){
................................................................................
  1242   1228     ){
  1243   1229       Expr *pLeft;       /* LHS of LIKE/GLOB operator */
  1244   1230       Expr *pStr2;       /* Copy of pStr1 - RHS of LIKE/GLOB operator */
  1245   1231       Expr *pNewExpr1;
  1246   1232       Expr *pNewExpr2;
  1247   1233       int idxNew1;
  1248   1234       int idxNew2;
         1235  +    CollSeq *pColl;    /* Collating sequence to use */
  1249   1236   
  1250   1237       pLeft = pExpr->x.pList->a[1].pExpr;
  1251   1238       pStr2 = sqlite3ExprDup(db, pStr1, 0);
  1252   1239       if( !db->mallocFailed ){
  1253   1240         u8 c, *pC;       /* Last character before the first wildcard */
  1254   1241         pC = (u8*)&pStr2->u.zToken[sqlite3Strlen30(pStr2->u.zToken)-1];
  1255   1242         c = *pC;
................................................................................
  1262   1249           */
  1263   1250           if( c=='A'-1 ) isComplete = 0;
  1264   1251   
  1265   1252           c = sqlite3UpperToLower[c];
  1266   1253         }
  1267   1254         *pC = c + 1;
  1268   1255       }
  1269         -    pNewExpr1 = sqlite3PExpr(pParse, TK_GE, sqlite3ExprDup(db,pLeft,0),pStr1,0);
         1256  +    pColl = sqlite3FindCollSeq(db, SQLITE_UTF8, noCase ? "NOCASE" : "BINARY",0);
         1257  +    pNewExpr1 = sqlite3PExpr(pParse, TK_GE, 
         1258  +                     sqlite3ExprSetColl(sqlite3ExprDup(db,pLeft,0), pColl),
         1259  +                     pStr1, 0);
  1270   1260       idxNew1 = whereClauseInsert(pWC, pNewExpr1, TERM_VIRTUAL|TERM_DYNAMIC);
  1271   1261       testcase( idxNew1==0 );
  1272   1262       exprAnalyze(pSrc, pWC, idxNew1);
  1273         -    pNewExpr2 = sqlite3PExpr(pParse, TK_LT, sqlite3ExprDup(db,pLeft,0),pStr2,0);
         1263  +    pNewExpr2 = sqlite3PExpr(pParse, TK_LT,
         1264  +                     sqlite3ExprSetColl(sqlite3ExprDup(db,pLeft,0), pColl),
         1265  +                     pStr2, 0);
  1274   1266       idxNew2 = whereClauseInsert(pWC, pNewExpr2, TERM_VIRTUAL|TERM_DYNAMIC);
  1275   1267       testcase( idxNew2==0 );
  1276   1268       exprAnalyze(pSrc, pWC, idxNew2);
  1277   1269       pTerm = &pWC->a[idxTerm];
  1278   1270       if( isComplete ){
  1279   1271         pWC->a[idxNew1].iParent = idxTerm;
  1280   1272         pWC->a[idxNew2].iParent = idxTerm;

Changes to test/like.test.

   773    773     }
   774    774   } {12 123 scan 3 like 0}
   775    775   do_test like-10.15 {
   776    776     count {
   777    777       SELECT a FROM t10b WHERE a GLOB '12*' ORDER BY a;
   778    778     }
   779    779   } {12 123 scan 5 like 6}
          780  +
          781  +# LIKE and GLOB where the default collating sequence is not appropriate
          782  +# but an index with the appropriate collating sequence exists.
          783  +#
          784  +do_test like-11.0 {
          785  +  execsql {
          786  +    CREATE TABLE t11(
          787  +      a INTEGER PRIMARY KEY,
          788  +      b TEXT COLLATE nocase,
          789  +      c TEXT COLLATE binary
          790  +    );
          791  +    INSERT INTO t11 VALUES(1, 'a','a');
          792  +    INSERT INTO t11 VALUES(2, 'ab','ab');
          793  +    INSERT INTO t11 VALUES(3, 'abc','abc');
          794  +    INSERT INTO t11 VALUES(4, 'abcd','abcd');
          795  +    INSERT INTO t11 VALUES(5, 'A','A');
          796  +    INSERT INTO t11 VALUES(6, 'AB','AB');
          797  +    INSERT INTO t11 VALUES(7, 'ABC','ABC');
          798  +    INSERT INTO t11 VALUES(8, 'ABCD','ABCD');
          799  +    INSERT INTO t11 VALUES(9, 'x','x');
          800  +    INSERT INTO t11 VALUES(10, 'yz','yz');
          801  +    INSERT INTO t11 VALUES(11, 'X','X');
          802  +    INSERT INTO t11 VALUES(12, 'YZ','YZ');
          803  +    SELECT count(*) FROM t11;
          804  +  }
          805  +} {12}
          806  +do_test like-11.1 {
          807  +  queryplan {
          808  +    PRAGMA case_sensitive_like=OFF;
          809  +    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY a;
          810  +  }
          811  +} {abc abcd ABC ABCD nosort t11 *}
          812  +do_test like-11.2 {
          813  +  queryplan {
          814  +    PRAGMA case_sensitive_like=ON;
          815  +    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY a;
          816  +  }
          817  +} {abc abcd nosort t11 *}
          818  +do_test like-11.3 {
          819  +  queryplan {
          820  +    PRAGMA case_sensitive_like=OFF;
          821  +    CREATE INDEX t11b ON t11(b);
          822  +    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY a;
          823  +  }
          824  +} {abc abcd ABC ABCD sort {} t11b}
          825  +do_test like-11.4 {
          826  +  queryplan {
          827  +    PRAGMA case_sensitive_like=ON;
          828  +    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY a;
          829  +  }
          830  +} {abc abcd nosort t11 *}
          831  +do_test like-11.5 {
          832  +  queryplan {
          833  +    PRAGMA case_sensitive_like=OFF;
          834  +    DROP INDEX t11b;
          835  +    CREATE INDEX t11bnc ON t11(b COLLATE nocase);
          836  +    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY a;
          837  +  }
          838  +} {abc abcd ABC ABCD sort {} t11bnc}
          839  +do_test like-11.6 {
          840  +  queryplan {
          841  +    CREATE INDEX t11bb ON t11(b COLLATE binary);
          842  +    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY a;
          843  +  }
          844  +} {abc abcd ABC ABCD sort {} t11bnc}
          845  +do_test like-11.7 {
          846  +  queryplan {
          847  +    PRAGMA case_sensitive_like=ON;
          848  +    SELECT b FROM t11 WHERE b LIKE 'abc%' ORDER BY a;
          849  +  }
          850  +} {abc abcd sort {} t11bb}
          851  +do_test like-11.8 {
          852  +  queryplan {
          853  +    PRAGMA case_sensitive_like=OFF;
          854  +    SELECT b FROM t11 WHERE b GLOB 'abc*' ORDER BY a;
          855  +  }
          856  +} {abc abcd sort {} t11bb}
          857  +do_test like-11.9 {
          858  +  queryplan {
          859  +    CREATE INDEX t11cnc ON t11(c COLLATE nocase);
          860  +    CREATE INDEX t11cb ON t11(c COLLATE binary);
          861  +    SELECT c FROM t11 WHERE c LIKE 'abc%' ORDER BY a;
          862  +  }
          863  +} {abc abcd ABC ABCD sort {} t11cnc}
          864  +do_test like-11.10 {
          865  +  queryplan {
          866  +    SELECT c FROM t11 WHERE c GLOB 'abc*' ORDER BY a;
          867  +  }
          868  +} {abc abcd sort {} t11cb}
   780    869   
   781    870   
   782    871   finish_test