SQLite

Check-in [54c63b3292]
Login

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

Overview
Comment:Improvements to the way the LIKE optimization is implemented, resulting in slightly smaller and faster code that is easier to test.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 54c63b329288729031f45b7778752552cd90e226
User & Date: drh 2016-05-02 10:25:42.392
Context
2016-05-02
12:18
Disable the multi-row one-pass DELETE optimization when the WHERE clause contains a subquery. Fix for ticket [dc6ebeda9396087]. (check-in: 3f221f592a user: drh tags: trunk)
10:25
Improvements to the way the LIKE optimization is implemented, resulting in slightly smaller and faster code that is easier to test. (check-in: 54c63b3292 user: drh tags: trunk)
2016-04-30
19:23
Change the way tester.tcl handes $argv so that in "permutations.test <permutation> <filename>" <filename> may be the name of any file in the test/ directory. (check-in: 820c57bb24 user: dan tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/vdbe.c.
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097


1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
}
  
/* Opcode: String P1 P2 P3 P4 P5
** Synopsis: r[P2]='P4' (len=P1)
**
** The string value P4 of length P1 (bytes) is stored in register P2.
**
** If P5!=0 and the content of register P3 is greater than zero, then
** the datatype of the register P2 is converted to BLOB.  The content is
** the same sequence of bytes, it is merely interpreted as a BLOB instead
** of a string, as if it had been CAST.


*/
case OP_String: {          /* out2 */
  assert( pOp->p4.z!=0 );
  pOut = out2Prerelease(p, pOp);
  pOut->flags = MEM_Str|MEM_Static|MEM_Term;
  pOut->z = pOp->p4.z;
  pOut->n = pOp->p1;
  pOut->enc = encoding;
  UPDATE_MAX_BLOBSIZE(pOut);
#ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
  if( pOp->p5 ){
    assert( pOp->p3>0 );
    assert( pOp->p3<=(p->nMem+1 - p->nCursor) );
    pIn3 = &aMem[pOp->p3];
    assert( pIn3->flags & MEM_Int );
    if( pIn3->u.i ) pOut->flags = MEM_Blob|MEM_Static|MEM_Term;
  }
#endif
  break;
}

/* Opcode: Null P1 P2 P3 * *
** Synopsis:  r[P2..P3]=NULL







|


|
>
>










|
<



|







1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110

1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
}
  
/* Opcode: String P1 P2 P3 P4 P5
** Synopsis: r[P2]='P4' (len=P1)
**
** The string value P4 of length P1 (bytes) is stored in register P2.
**
** If P3 is not zero and the content of register P3 is equal to P5, then
** the datatype of the register P2 is converted to BLOB.  The content is
** the same sequence of bytes, it is merely interpreted as a BLOB instead
** of a string, as if it had been CAST.  In other words:
**
** if( P3!=0 and reg[P3]==P5 ) reg[P2] := CAST(reg[P2] as BLOB)
*/
case OP_String: {          /* out2 */
  assert( pOp->p4.z!=0 );
  pOut = out2Prerelease(p, pOp);
  pOut->flags = MEM_Str|MEM_Static|MEM_Term;
  pOut->z = pOp->p4.z;
  pOut->n = pOp->p1;
  pOut->enc = encoding;
  UPDATE_MAX_BLOBSIZE(pOut);
#ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
  if( pOp->p3>0 ){

    assert( pOp->p3<=(p->nMem+1 - p->nCursor) );
    pIn3 = &aMem[pOp->p3];
    assert( pIn3->flags & MEM_Int );
    if( pIn3->u.i==pOp->p5 ) pOut->flags = MEM_Blob|MEM_Static|MEM_Term;
  }
#endif
  break;
}

/* Opcode: Null P1 P2 P3 * *
** Synopsis:  r[P2..P3]=NULL
5962
5963
5964
5965
5966
5967
5968
5969
5970
5971
5972
5973
5974
5975
5976
5977
5978
5979
5980
5981
5982
5983
5984
5985
5986
5987
5988
5989
5990
  pIn1->u.i--;
  VdbeBranchTaken(pIn1->u.i==0, 2);
  if( pIn1->u.i==0 ) goto jump_to_p2;
  break;
}


/* Opcode: JumpZeroIncr P1 P2 * * *
** Synopsis: if (r[P1]++)==0 ) goto P2
**
** The register P1 must contain an integer.  If register P1 is initially
** zero, then jump to P2.  Increment register P1 regardless of whether or
** not the jump is taken.
*/
case OP_JumpZeroIncr: {        /* jump, in1 */
  pIn1 = &aMem[pOp->p1];
  assert( pIn1->flags&MEM_Int );
  VdbeBranchTaken(pIn1->u.i==0, 2);
  if( (pIn1->u.i++)==0 ) goto jump_to_p2;
  break;
}

/* Opcode: AggStep0 * P2 P3 P4 P5
** Synopsis: accum=r[P3] step(r[P2@P5])
**
** Execute the step function for an aggregate.  The
** function has P5 arguments.   P4 is a pointer to the FuncDef
** structure that specifies the function.  Register P3 is the
** accumulator.







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







5963
5964
5965
5966
5967
5968
5969















5970
5971
5972
5973
5974
5975
5976
  pIn1->u.i--;
  VdbeBranchTaken(pIn1->u.i==0, 2);
  if( pIn1->u.i==0 ) goto jump_to_p2;
  break;
}

















/* Opcode: AggStep0 * P2 P3 P4 P5
** Synopsis: accum=r[P3] step(r[P2@P5])
**
** Execute the step function for an aggregate.  The
** function has P5 arguments.   P4 is a pointer to the FuncDef
** structure that specifies the function.  Register P3 is the
** accumulator.
Changes to src/where.c.
4603
4604
4605
4606
4607
4608
4609
4610
4611
4612
4613
4614
4615
4616
4617
4618
4619
4620
4621
4622
4623
      sqlite3VdbeGoto(v, pLevel->addrSkip);
      VdbeComment((v, "next skip-scan on %s", pLoop->u.btree.pIndex->zName));
      sqlite3VdbeJumpHere(v, pLevel->addrSkip);
      sqlite3VdbeJumpHere(v, pLevel->addrSkip-2);
    }
#ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
    if( pLevel->addrLikeRep ){
      int op;
      if( sqlite3VdbeGetOp(v, pLevel->addrLikeRep-1)->p1 ){
        op = OP_DecrJumpZero;
      }else{
        op = OP_JumpZeroIncr;
      }
      sqlite3VdbeAddOp2(v, op, pLevel->iLikeRepCntr, pLevel->addrLikeRep);
      VdbeCoverage(v);
    }
#endif
    if( pLevel->iLeftJoin ){
      addr = sqlite3VdbeAddOp1(v, OP_IfPos, pLevel->iLeftJoin); VdbeCoverage(v);
      assert( (pLoop->wsFlags & WHERE_IDX_ONLY)==0
           || (pLoop->wsFlags & WHERE_INDEXED)!=0 );







<
<
|
<
<
<
|







4603
4604
4605
4606
4607
4608
4609


4610



4611
4612
4613
4614
4615
4616
4617
4618
      sqlite3VdbeGoto(v, pLevel->addrSkip);
      VdbeComment((v, "next skip-scan on %s", pLoop->u.btree.pIndex->zName));
      sqlite3VdbeJumpHere(v, pLevel->addrSkip);
      sqlite3VdbeJumpHere(v, pLevel->addrSkip-2);
    }
#ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
    if( pLevel->addrLikeRep ){


      sqlite3VdbeAddOp2(v, OP_DecrJumpZero, (int)(pLevel->iLikeRepCntr>>1),



                        pLevel->addrLikeRep);
      VdbeCoverage(v);
    }
#endif
    if( pLevel->iLeftJoin ){
      addr = sqlite3VdbeAddOp1(v, OP_IfPos, pLevel->iLeftJoin); VdbeCoverage(v);
      assert( (pLoop->wsFlags & WHERE_IDX_ONLY)==0
           || (pLoop->wsFlags & WHERE_INDEXED)!=0 );
Changes to src/whereInt.h.
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
  int addrBrk;          /* Jump here to break out of the loop */
  int addrNxt;          /* Jump here to start the next IN combination */
  int addrSkip;         /* Jump here for next iteration of skip-scan */
  int addrCont;         /* Jump here to continue with the next loop cycle */
  int addrFirst;        /* First instruction of interior of the loop */
  int addrBody;         /* Beginning of the body of this loop */
#ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
  int iLikeRepCntr;     /* LIKE range processing counter register */
  int addrLikeRep;      /* LIKE range processing address */
#endif
  u8 iFrom;             /* Which entry in the FROM clause */
  u8 op, p3, p5;        /* Opcode, P3 & P5 of the opcode that ends the loop */
  int p1, p2;           /* Operands of the opcode used to ends the loop */
  union {               /* Information that depends on pWLoop->wsFlags */
    struct {







|







66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
  int addrBrk;          /* Jump here to break out of the loop */
  int addrNxt;          /* Jump here to start the next IN combination */
  int addrSkip;         /* Jump here for next iteration of skip-scan */
  int addrCont;         /* Jump here to continue with the next loop cycle */
  int addrFirst;        /* First instruction of interior of the loop */
  int addrBody;         /* Beginning of the body of this loop */
#ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
  u32 iLikeRepCntr;     /* LIKE range processing counter register (times 2) */
  int addrLikeRep;      /* LIKE range processing address */
#endif
  u8 iFrom;             /* Which entry in the FROM clause */
  u8 op, p3, p5;        /* Opcode, P3 & P5 of the opcode that ends the loop */
  int p1, p2;           /* Operands of the opcode used to ends the loop */
  union {               /* Information that depends on pWLoop->wsFlags */
    struct {
Changes to src/wherecode.c.
556
557
558
559
560
561
562
563
564
565

566
567
568
569
570
571
572
  }
  *pzAff = zAff;
  return regBase;
}

#ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
/*
** If the most recently coded instruction is a constant range contraint
** that originated from the LIKE optimization, then change the P3 to be
** pLoop->iLikeRepCntr and set P5.

**
** The LIKE optimization trys to evaluate "x LIKE 'abc%'" as a range
** expression: "x>='ABC' AND x<'abd'".  But this requires that the range
** scan loop run twice, once for strings and a second time for BLOBs.
** The OP_String opcodes on the second pass convert the upper and lower
** bound string contants to blobs.  This routine makes the necessary changes
** to the OP_String opcodes for that to happen.







|
|
|
>







556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
  }
  *pzAff = zAff;
  return regBase;
}

#ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
/*
** If the most recently coded instruction is a constant range constraint
** (a string literal) that originated from the LIKE optimization, then 
** set P3 and P5 on the OP_String opcode so that the string will be cast
** to a BLOB at appropriate times.
**
** The LIKE optimization trys to evaluate "x LIKE 'abc%'" as a range
** expression: "x>='ABC' AND x<'abd'".  But this requires that the range
** scan loop run twice, once for strings and a second time for BLOBs.
** The OP_String opcodes on the second pass convert the upper and lower
** bound string contants to blobs.  This routine makes the necessary changes
** to the OP_String opcodes for that to happen.
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
  if( pTerm->wtFlags & TERM_LIKEOPT ){
    VdbeOp *pOp;
    assert( pLevel->iLikeRepCntr>0 );
    pOp = sqlite3VdbeGetOp(v, -1);
    assert( pOp!=0 );
    assert( pOp->opcode==OP_String8 
            || pTerm->pWC->pWInfo->pParse->db->mallocFailed );
    pOp->p3 = pLevel->iLikeRepCntr;
    pOp->p5 = 1;
  }
}
#else
# define whereLikeOptimizationStringFixup(A,B,C)
#endif

#ifdef SQLITE_ENABLE_CURSOR_HINTS







|
|







584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
  if( pTerm->wtFlags & TERM_LIKEOPT ){
    VdbeOp *pOp;
    assert( pLevel->iLikeRepCntr>0 );
    pOp = sqlite3VdbeGetOp(v, -1);
    assert( pOp!=0 );
    assert( pOp->opcode==OP_String8 
            || pTerm->pWC->pWInfo->pParse->db->mallocFailed );
    pOp->p3 = (int)(pLevel->iLikeRepCntr>>1);  /* Register holding counter */
    pOp->p5 = (u8)(pLevel->iLikeRepCntr&1);    /* ASC or DESC */
  }
}
#else
# define whereLikeOptimizationStringFixup(A,B,C)
#endif

#ifdef SQLITE_ENABLE_CURSOR_HINTS
1171
1172
1173
1174
1175
1176
1177
1178





1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
    if( pLoop->wsFlags & WHERE_TOP_LIMIT ){
      pRangeEnd = pLoop->aLTerm[j++];
      nExtraReg = 1;
#ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
      if( (pRangeEnd->wtFlags & TERM_LIKEOPT)!=0 ){
        assert( pRangeStart!=0 );                     /* LIKE opt constraints */
        assert( pRangeStart->wtFlags & TERM_LIKEOPT );   /* occur in pairs */
        pLevel->iLikeRepCntr = ++pParse->nMem;





        testcase( bRev );
        testcase( pIdx->aSortOrder[nEq]==SQLITE_SO_DESC );
        sqlite3VdbeAddOp2(v, OP_Integer,
                          bRev ^ (pIdx->aSortOrder[nEq]==SQLITE_SO_DESC),
                          pLevel->iLikeRepCntr);
        VdbeComment((v, "LIKE loop counter"));
        pLevel->addrLikeRep = sqlite3VdbeCurrentAddr(v);
      }
#endif
      if( pRangeStart==0
       && (j = pIdx->aiColumn[nEq])>=0 
       && pIdx->pTable->aCol[j].notNull==0
      ){
        bSeekPastNull = 1;







|
>
>
>
>
>


<
|
|
<
|







1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186

1187
1188

1189
1190
1191
1192
1193
1194
1195
1196
    if( pLoop->wsFlags & WHERE_TOP_LIMIT ){
      pRangeEnd = pLoop->aLTerm[j++];
      nExtraReg = 1;
#ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
      if( (pRangeEnd->wtFlags & TERM_LIKEOPT)!=0 ){
        assert( pRangeStart!=0 );                     /* LIKE opt constraints */
        assert( pRangeStart->wtFlags & TERM_LIKEOPT );   /* occur in pairs */
        pLevel->iLikeRepCntr = (u32)++pParse->nMem;
        sqlite3VdbeAddOp2(v, OP_Integer, 1, (int)pLevel->iLikeRepCntr);
        VdbeComment((v, "LIKE loop counter"));
        pLevel->addrLikeRep = sqlite3VdbeCurrentAddr(v);
        /* iLikeRepCntr actually stores 2x the counter register number.  The
        ** bottom bit indicates whether the search order is ASC or DESC. */
        testcase( bRev );
        testcase( pIdx->aSortOrder[nEq]==SQLITE_SO_DESC );

        assert( (bRev & ~1)==0 );
        pLevel->iLikeRepCntr <<=1;

        pLevel->iLikeRepCntr |= bRev ^ (pIdx->aSortOrder[nEq]==SQLITE_SO_DESC);
      }
#endif
      if( pRangeStart==0
       && (j = pIdx->aiColumn[nEq])>=0 
       && pIdx->pTable->aCol[j].notNull==0
      ){
        bSeekPastNull = 1;
1692
1693
1694
1695
1696
1697
1698





1699
1700
1701
1702

1703
1704
1705
1706
1707
1708
1709
1710
    }
    pE = pTerm->pExpr;
    assert( pE!=0 );
    if( pLevel->iLeftJoin && !ExprHasProperty(pE, EP_FromJoin) ){
      continue;
    }
    if( pTerm->wtFlags & TERM_LIKECOND ){





#ifdef SQLITE_LIKE_DOESNT_MATCH_BLOBS
      continue;
#else
      assert( pLevel->iLikeRepCntr>0 );

      skipLikeAddr = sqlite3VdbeAddOp1(v, OP_IfNot, pLevel->iLikeRepCntr);
      VdbeCoverage(v);
#endif
    }
    sqlite3ExprIfFalse(pParse, pE, addrCont, SQLITE_JUMPIFNULL);
    if( skipLikeAddr ) sqlite3VdbeJumpHere(v, skipLikeAddr);
    pTerm->wtFlags |= TERM_CODED;
  }







>
>
>
>
>



|
>
|







1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
    }
    pE = pTerm->pExpr;
    assert( pE!=0 );
    if( pLevel->iLeftJoin && !ExprHasProperty(pE, EP_FromJoin) ){
      continue;
    }
    if( pTerm->wtFlags & TERM_LIKECOND ){
      /* If the TERM_LIKECOND flag is set, that means that the range search
      ** is sufficient to guarantee that the LIKE operator is true, so we
      ** can skip the call to the like(A,B) function.  But this only works
      ** for strings.  So do not skip the call to the function on the pass
      ** that compares BLOBs. */
#ifdef SQLITE_LIKE_DOESNT_MATCH_BLOBS
      continue;
#else
      u32 x = pLevel->iLikeRepCntr;
      assert( x>0 );
      skipLikeAddr = sqlite3VdbeAddOp1(v, (x&1)? OP_IfNot : OP_If, (int)(x>>1));
      VdbeCoverage(v);
#endif
    }
    sqlite3ExprIfFalse(pParse, pE, addrCont, SQLITE_JUMPIFNULL);
    if( skipLikeAddr ) sqlite3VdbeJumpHere(v, skipLikeAddr);
    pTerm->wtFlags |= TERM_CODED;
  }