SQLite

Check-in [5e19d05410]
Login

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

Overview
Comment:Enhance the query planner so that it looks at multiple solutions to OR expressions in the WHERE clause.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 5e19d054105fb16ff52d265d48cc87a418603f6f
User & Date: drh 2013-07-16 21:31:23.453
Context
2013-07-16
23:26
Make sure the sqlite3_prepare16 and sqlite3_prepare16_v2 interfaces do not read past a zero-terminator if the nBytes parameter is too large. (check-in: 20dba3a7fb user: drh tags: trunk)
21:31
Enhance the query planner so that it looks at multiple solutions to OR expressions in the WHERE clause. (check-in: 5e19d05410 user: drh tags: trunk)
2013-07-15
17:02
Add the sqlite3_cancel_auto_extension(X) interface which will undo a prior call to sqlite3_auto_extension(X). (check-in: cdce87eb88 user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/where.c.
41
42
43
44
45
46
47


48
49
50
51
52
53
54
typedef struct WhereAndInfo WhereAndInfo;
typedef struct WhereLevel WhereLevel;
typedef struct WhereLoop WhereLoop;
typedef struct WherePath WherePath;
typedef struct WhereTerm WhereTerm;
typedef struct WhereLoopBuilder WhereLoopBuilder;
typedef struct WhereScan WhereScan;



/*
** Cost X is tracked as 10*log2(X) stored in a 16-bit integer.  The
** maximum cost for ordinary tables is 64*(2**63) which becomes 6900.
** (Virtual tables can return a larger cost, but let's assume they do not.)
** So all costs can be stored in a 16-bit unsigned integer without risk
** of overflow.







>
>







41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
typedef struct WhereAndInfo WhereAndInfo;
typedef struct WhereLevel WhereLevel;
typedef struct WhereLoop WhereLoop;
typedef struct WherePath WherePath;
typedef struct WhereTerm WhereTerm;
typedef struct WhereLoopBuilder WhereLoopBuilder;
typedef struct WhereScan WhereScan;
typedef struct WhereOrCost WhereOrCost;
typedef struct WhereOrSet WhereOrSet;

/*
** Cost X is tracked as 10*log2(X) stored in a 16-bit integer.  The
** maximum cost for ordinary tables is 64*(2**63) which becomes 6900.
** (Virtual tables can return a larger cost, but let's assume they do not.)
** So all costs can be stored in a 16-bit unsigned integer without risk
** of overflow.
147
148
149
150
151
152
153





















154
155
156
157
158
159
160
  /**** whereLoopXfer() copies fields above ***********************/
# define WHERE_LOOP_XFER_SZ offsetof(WhereLoop,nLSlot)
  u16 nLSlot;           /* Number of slots allocated for aLTerm[] */
  WhereTerm **aLTerm;   /* WhereTerms used */
  WhereLoop *pNextLoop; /* Next WhereLoop object in the WhereClause */
  WhereTerm *aLTermSpace[4];  /* Initial aLTerm[] space */
};






















/* Forward declaration of methods */
static int whereLoopResize(sqlite3*, WhereLoop*, int);

/*
** Each instance of this object holds a sequence of WhereLoop objects
** that implement some or all of a query plan.







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







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
  /**** whereLoopXfer() copies fields above ***********************/
# define WHERE_LOOP_XFER_SZ offsetof(WhereLoop,nLSlot)
  u16 nLSlot;           /* Number of slots allocated for aLTerm[] */
  WhereTerm **aLTerm;   /* WhereTerms used */
  WhereLoop *pNextLoop; /* Next WhereLoop object in the WhereClause */
  WhereTerm *aLTermSpace[4];  /* Initial aLTerm[] space */
};

/* This object holds the prerequisites and the cost of running a
** subquery on one operand of an OR operator in the WHERE clause.
** See WhereOrSet for additional information 
*/
struct WhereOrCost {
  Bitmask prereq;     /* Prerequisites */
  WhereCost rRun;     /* Cost of running this subquery */
  WhereCost nOut;     /* Number of outputs for this subquery */
};

/* The WhereOrSet object holds a set of possible WhereOrCosts that
** correspond to the subquery(s) of OR-clause processing.  At most
** favorable N_OR_COST elements are retained.
*/
#define N_OR_COST 3
struct WhereOrSet {
  u16 n;                      /* Number of valid a[] entries */
  WhereOrCost a[N_OR_COST];   /* Set of best costs */
};


/* Forward declaration of methods */
static int whereLoopResize(sqlite3*, WhereLoop*, int);

/*
** Each instance of this object holds a sequence of WhereLoop objects
** that implement some or all of a query plan.
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
** to construct WhereLoop objects for a particular query.
*/
struct WhereLoopBuilder {
  WhereInfo *pWInfo;        /* Information about this WHERE */
  WhereClause *pWC;         /* WHERE clause terms */
  ExprList *pOrderBy;       /* ORDER BY clause */
  WhereLoop *pNew;          /* Template WhereLoop */
  WhereLoop *pBest;         /* If non-NULL, store single best loop here */
};

/*
** The WHERE clause processing routine has two halves.  The
** first part does the start of the WHERE loop and the second
** half does the tail of the WHERE loop.  An instance of
** this structure is returned by the first half and passed







|







385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
** to construct WhereLoop objects for a particular query.
*/
struct WhereLoopBuilder {
  WhereInfo *pWInfo;        /* Information about this WHERE */
  WhereClause *pWC;         /* WHERE clause terms */
  ExprList *pOrderBy;       /* ORDER BY clause */
  WhereLoop *pNew;          /* Template WhereLoop */
  WhereOrSet *pOrSet;       /* Record best loops here, if not NULL */
};

/*
** The WHERE clause processing routine has two halves.  The
** first part does the start of the WHERE loop and the second
** half does the tail of the WHERE loop.  An instance of
** this structure is returned by the first half and passed
504
505
506
507
508
509
510
















































511
512
513
514
515
516
517
** Return TRUE if an UPDATE or DELETE statement can operate directly on
** the rowids returned by a WHERE clause.  Return FALSE if doing an
** UPDATE or DELETE might change subsequent WHERE clause results.
*/
int sqlite3WhereOkOnePass(WhereInfo *pWInfo){
  return pWInfo->okOnePass;
}

















































/*
** Initialize a preallocated WhereClause structure.
*/
static void whereClauseInit(
  WhereClause *pWC,        /* The WhereClause to be initialized */
  WhereInfo *pWInfo        /* The WHERE processing context */







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







527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
** Return TRUE if an UPDATE or DELETE statement can operate directly on
** the rowids returned by a WHERE clause.  Return FALSE if doing an
** UPDATE or DELETE might change subsequent WHERE clause results.
*/
int sqlite3WhereOkOnePass(WhereInfo *pWInfo){
  return pWInfo->okOnePass;
}

/*
** Move the content of pSrc into pDest
*/
static void whereOrMove(WhereOrSet *pDest, WhereOrSet *pSrc){
  pDest->n = pSrc->n;
  memcpy(pDest->a, pSrc->a, pDest->n*sizeof(pDest->a[0]));
}

/*
** Try to insert a new prerequisite/cost entry into the WhereOrSet pSet.
**
** The new entry might overwrite an existing entry, or it might be
** appended, or it might be discarded.  Do whatever is the right thing
** so that pSet keeps the N_OR_COST best entries seen so far.
*/
static int whereOrInsert(
  WhereOrSet *pSet,      /* The WhereOrSet to be updated */
  Bitmask prereq,        /* Prerequisites of the new entry */
  WhereCost rRun,        /* Run-cost of the new entry */
  WhereCost nOut         /* Number of outputs for the new entry */
){
  u16 i;
  WhereOrCost *p;
  for(i=pSet->n, p=pSet->a; i>0; i--, p++){
    if( rRun<=p->rRun && (prereq & p->prereq)==prereq ){
      goto whereOrInsert_done;
    }
    if( p->rRun<=rRun && (p->prereq & prereq)==p->prereq ){
      return 0;
    }
  }
  if( pSet->n<N_OR_COST ){
    p = &pSet->a[pSet->n++];
    p->nOut = nOut;
  }else{
    p = pSet->a;
    for(i=1; i<pSet->n; i++){
      if( p->rRun>pSet->a[i].rRun ) p = pSet->a + i;
    }
    if( p->rRun<=rRun ) return 0;
  }
whereOrInsert_done:
  p->prereq = prereq;
  p->rRun = rRun;
  if( p->nOut>nOut ) p->nOut = nOut;
  return 1;
}

/*
** Initialize a preallocated WhereClause structure.
*/
static void whereClauseInit(
  WhereClause *pWC,        /* The WhereClause to be initialized */
  WhereInfo *pWInfo        /* The WHERE processing context */
3739
3740
3741
3742
3743
3744
3745

3746
3747
3748
3749
3750
3751
3752
3753
3754
    ** is not contained in the ON clause of a LEFT JOIN.
    ** See ticket http://www.sqlite.org/src/info/f2369304e4
    */
    if( pWC->nTerm>1 ){
      int iTerm;
      for(iTerm=0; iTerm<pWC->nTerm; iTerm++){
        Expr *pExpr = pWC->a[iTerm].pExpr;

        if( ExprHasProperty(pExpr, EP_FromJoin) ) continue;
        if( pWC->a[iTerm].wtFlags & (TERM_VIRTUAL|TERM_ORINFO) ) continue;
        if( (pWC->a[iTerm].eOperator & WO_ALL)==0 ) continue;
        pExpr = sqlite3ExprDup(pParse->db, pExpr, 0);
        pAndExpr = sqlite3ExprAnd(pParse->db, pAndExpr, pExpr);
      }
      if( pAndExpr ){
        pAndExpr = sqlite3PExpr(pParse, TK_AND, 0, pAndExpr, 0);
      }







>

|







3810
3811
3812
3813
3814
3815
3816
3817
3818
3819
3820
3821
3822
3823
3824
3825
3826
    ** is not contained in the ON clause of a LEFT JOIN.
    ** See ticket http://www.sqlite.org/src/info/f2369304e4
    */
    if( pWC->nTerm>1 ){
      int iTerm;
      for(iTerm=0; iTerm<pWC->nTerm; iTerm++){
        Expr *pExpr = pWC->a[iTerm].pExpr;
        if( &pWC->a[iTerm] == pTerm ) continue;
        if( ExprHasProperty(pExpr, EP_FromJoin) ) continue;
        if( pWC->a[iTerm].wtFlags & (TERM_ORINFO) ) continue;
        if( (pWC->a[iTerm].eOperator & WO_ALL)==0 ) continue;
        pExpr = sqlite3ExprDup(pParse->db, pExpr, 0);
        pAndExpr = sqlite3ExprAnd(pParse->db, pAndExpr, pExpr);
      }
      if( pAndExpr ){
        pAndExpr = sqlite3PExpr(pParse, TK_AND, 0, pAndExpr, 0);
      }
4068
4069
4070
4071
4072
4073
4074
4075
4076
4077
4078
4079
4080
4081
4082
4083
4084
4085
4086
4087
4088
4089
4090
4091
4092
4093
4094
4095
4096
4097
4098
4099
4100
4101


4102

4103
4104
4105
4106
4107
4108
4109
4110
4111
4112
4113
4114
4115
4116
4117
4118
4119
4120
4121
4122
4123
4124
4125
4126
4127
**
** An existing WhereLoop entry might be overwritten if the new template
** is better and has fewer dependencies.  Or the template will be ignored
** and no insert will occur if an existing WhereLoop is faster and has
** fewer dependencies than the template.  Otherwise a new WhereLoop is
** added based on the template.
**
** If pBuilder->pBest is not NULL then we only care about the very
** best template and that template should be stored in pBuilder->pBest.
** If pBuilder->pBest is NULL then a list of the best templates are stored
** in pBuilder->pWInfo->pLoops.
**
** When accumulating multiple loops (when pBuilder->pBest is NULL) we
** still might overwrite similar loops with the new template if the
** template is better.  Loops may be overwritten if the following 
** conditions are met:
**
**    (1)  They have the same iTab.
**    (2)  They have the same iSortIdx.
**    (3)  The template has same or fewer dependencies than the current loop
**    (4)  The template has the same or lower cost than the current loop
**    (5)  The template uses more terms of the same index but has no additional
**         dependencies          
*/
static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){
  WhereLoop **ppPrev, *p, *pNext = 0;
  WhereInfo *pWInfo = pBuilder->pWInfo;
  sqlite3 *db = pWInfo->pParse->db;

  /* If pBuilder->pBest is defined, then only keep track of the single
  ** best WhereLoop.  pBuilder->pBest->maskSelf==0 indicates that no
  ** prior WhereLoops have been evaluated and that the current pTemplate
  ** is therefore the first and hence the best and should be retained.
  */


  if( (p = pBuilder->pBest)!=0 ){

    if( p->maskSelf!=0 ){
      WhereCost rCost = whereCostAdd(p->rRun,p->rSetup);
      WhereCost rTemplate = whereCostAdd(pTemplate->rRun,pTemplate->rSetup);
      if( rCost < rTemplate ){
        testcase( rCost==rTemplate-1 );
        goto whereLoopInsert_noop;
      }
      if( rCost==rTemplate && (p->prereq & pTemplate->prereq)==p->prereq ){
        goto whereLoopInsert_noop;
      }
    }
#if WHERETRACE_ENABLED
    if( sqlite3WhereTrace & 0x8 ){
      sqlite3DebugPrintf(p->maskSelf==0 ? "ins-init: " : "ins-best: ");
      whereLoopPrint(pTemplate, pWInfo->pTabList);
    }
#endif
    whereLoopXfer(db, p, pTemplate);
    return SQLITE_OK;
  }

  /* Search for an existing WhereLoop to overwrite, or which takes
  ** priority over pTemplate.
  */
  for(ppPrev=&pWInfo->pLoops, p=*ppPrev; p; ppPrev=&p->pNextLoop, p=*ppPrev){







|
|
|
|

|
















|
<
|
<

>
>
|
>
|
<
|
|
<
<
<
<
<
<
<


|



<







4140
4141
4142
4143
4144
4145
4146
4147
4148
4149
4150
4151
4152
4153
4154
4155
4156
4157
4158
4159
4160
4161
4162
4163
4164
4165
4166
4167
4168
4169

4170

4171
4172
4173
4174
4175
4176

4177
4178







4179
4180
4181
4182
4183
4184

4185
4186
4187
4188
4189
4190
4191
**
** An existing WhereLoop entry might be overwritten if the new template
** is better and has fewer dependencies.  Or the template will be ignored
** and no insert will occur if an existing WhereLoop is faster and has
** fewer dependencies than the template.  Otherwise a new WhereLoop is
** added based on the template.
**
** If pBuilder->pOrSet is not NULL then we only care about only the
** prerequisites and rRun and nOut costs of the N best loops.  That
** information is gathered in the pBuilder->pOrSet object.  This special
** processing mode is used only for OR clause processing.
**
** When accumulating multiple loops (when pBuilder->pOrSet is NULL) we
** still might overwrite similar loops with the new template if the
** template is better.  Loops may be overwritten if the following 
** conditions are met:
**
**    (1)  They have the same iTab.
**    (2)  They have the same iSortIdx.
**    (3)  The template has same or fewer dependencies than the current loop
**    (4)  The template has the same or lower cost than the current loop
**    (5)  The template uses more terms of the same index but has no additional
**         dependencies          
*/
static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){
  WhereLoop **ppPrev, *p, *pNext = 0;
  WhereInfo *pWInfo = pBuilder->pWInfo;
  sqlite3 *db = pWInfo->pParse->db;

  /* If pBuilder->pOrSet is defined, then only keep track of the costs

  ** and prereqs.

  */
  if( pBuilder->pOrSet!=0 ){
#if WHERETRACE_ENABLED
    u16 n = pBuilder->pOrSet->n;
    int x =
#endif

    whereOrInsert(pBuilder->pOrSet, pTemplate->prereq, pTemplate->rRun,
                                    pTemplate->nOut);







#if WHERETRACE_ENABLED
    if( sqlite3WhereTrace & 0x8 ){
      sqlite3DebugPrintf(x?"   or-%d:  ":"   or-X:  ", n);
      whereLoopPrint(pTemplate, pWInfo->pTabList);
    }
#endif

    return SQLITE_OK;
  }

  /* Search for an existing WhereLoop to overwrite, or which takes
  ** priority over pTemplate.
  */
  for(ppPrev=&pWInfo->pLoops, p=*ppPrev; p; ppPrev=&p->pNextLoop, p=*ppPrev){
4207
4208
4209
4210
4211
4212
4213
4214
4215
4216
4217
4218
4219
4220
4221
  }
  return SQLITE_OK;

  /* Jump here if the insert is a no-op */
whereLoopInsert_noop:
#if WHERETRACE_ENABLED
  if( sqlite3WhereTrace & 0x8 ){
    sqlite3DebugPrintf(pBuilder->pBest ? "ins-skip: " : "ins-noop: ");
    whereLoopPrint(pTemplate, pWInfo->pTabList);
  }
#endif
  return SQLITE_OK;  
}

/*







|







4271
4272
4273
4274
4275
4276
4277
4278
4279
4280
4281
4282
4283
4284
4285
  }
  return SQLITE_OK;

  /* Jump here if the insert is a no-op */
whereLoopInsert_noop:
#if WHERETRACE_ENABLED
  if( sqlite3WhereTrace & 0x8 ){
    sqlite3DebugPrintf("ins-noop: ");
    whereLoopPrint(pTemplate, pWInfo->pTabList);
  }
#endif
  return SQLITE_OK;  
}

/*
4489
4490
4491
4492
4493
4494
4495
4496
4497
4498
4499
4500
4501
4502
4503
    }
    pProbe = &sPk;
  }
  rSize = whereCost(pSrc->pTab->nRowEst);
  rLogSize = estLog(rSize);

  /* Automatic indexes */
  if( !pBuilder->pBest
   && (pWInfo->pParse->db->flags & SQLITE_AutoIndex)!=0
   && pSrc->pIndex==0
   && !pSrc->viaCoroutine
   && !pSrc->notIndexed
   && !pSrc->isCorrelated
  ){
    /* Generate auto-index WhereLoops */







|







4553
4554
4555
4556
4557
4558
4559
4560
4561
4562
4563
4564
4565
4566
4567
    }
    pProbe = &sPk;
  }
  rSize = whereCost(pSrc->pTab->nRowEst);
  rLogSize = estLog(rSize);

  /* Automatic indexes */
  if( !pBuilder->pOrSet
   && (pWInfo->pParse->db->flags & SQLITE_AutoIndex)!=0
   && pSrc->pIndex==0
   && !pSrc->viaCoroutine
   && !pSrc->notIndexed
   && !pSrc->isCorrelated
  ){
    /* Generate auto-index WhereLoops */
4775
4776
4777
4778
4779
4780
4781
4782
4783
4784
4785
4786
4787
4788
4789
4790
4791
4792
4793
4794
4795
4796
4797
4798
4799
4800
4801
4802
4803
4804
4805
4806
4807
4808
4809
4810
4811
4812
4813
4814
4815
4816
4817
4818
4819
4820
4821
4822
4823
4824
4825
4826

4827
4828
4829
4830
4831
4832
4833


4834



4835





4836
4837
4838
4839
4840
4841



4842
4843
4844
4845



4846
4847
4848
4849
4850
4851
4852
4853
4854
4855
4856
4857
4858
4859
4860
  WhereClause *pWC;
  WhereLoop *pNew;
  WhereTerm *pTerm, *pWCEnd;
  int rc = SQLITE_OK;
  int iCur;
  WhereClause tempWC;
  WhereLoopBuilder sSubBuild;
  WhereLoop sBest;
  struct SrcList_item *pItem;
  
  pWC = pBuilder->pWC;
  if( pWInfo->wctrlFlags & WHERE_AND_ONLY ) return SQLITE_OK;
  pWCEnd = pWC->a + pWC->nTerm;
  pNew = pBuilder->pNew;

  for(pTerm=pWC->a; pTerm<pWCEnd && rc==SQLITE_OK; pTerm++){
    if( (pTerm->eOperator & WO_OR)!=0
     && (pTerm->u.pOrInfo->indexable & pNew->maskSelf)!=0 
    ){
      WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
      WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
      WhereTerm *pOrTerm;
      WhereCost rTotal = 0;
      WhereCost nRow = 0;
      Bitmask prereq = mExtra;
    
      whereLoopInit(&sBest);
      pItem = pWInfo->pTabList->a + pNew->iTab;
      iCur = pItem->iCursor;
      sSubBuild = *pBuilder;
      sSubBuild.pOrderBy = 0;
      sSubBuild.pBest = &sBest;

      for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
        if( (pOrTerm->eOperator & WO_AND)!=0 ){
          sSubBuild.pWC = &pOrTerm->u.pAndInfo->wc;
        }else if( pOrTerm->leftCursor==iCur ){
          tempWC.pWInfo = pWC->pWInfo;
          tempWC.pOuter = pWC;
          tempWC.op = TK_AND;
          tempWC.nTerm = 1;
          tempWC.a = pOrTerm;
          sSubBuild.pWC = &tempWC;
        }else{
          continue;
        }
        sBest.maskSelf = 0;
        sBest.rSetup = 0;
        sBest.rRun = 0;
#ifndef SQLITE_OMIT_VIRTUALTABLE
        if( IsVirtual(pItem->pTab) ){
          rc = whereLoopAddVirtual(&sSubBuild);

        }else
#endif
        {
          rc = whereLoopAddBtree(&sSubBuild, mExtra);
        }
        /* sBest.maskSelf is always zero if an error occurs */
        assert( rc==SQLITE_OK || sBest.maskSelf==0 );


        if( sBest.maskSelf==0 ) break;



        assert( sBest.rSetup==0 );





        rTotal = whereCostAdd(rTotal, sBest.rRun);
        nRow = whereCostAdd(nRow, sBest.nOut);
        prereq |= sBest.prereq;
      }
      assert( pNew->nLSlot>=1 );
      if( sBest.maskSelf ){



        pNew->nLTerm = 1;
        pNew->aLTerm[0] = pTerm;
        pNew->wsFlags = WHERE_MULTI_OR;
        pNew->rSetup = 0;



        /* TUNING: Multiple by 3.5 for the secondary table lookup */
        pNew->rRun = rTotal + 18; assert( 18==whereCost(7)-whereCost(2) );
        pNew->nOut = nRow;
        pNew->prereq = prereq;
        memset(&pNew->u, 0, sizeof(pNew->u));
        rc = whereLoopInsert(pBuilder, pNew);
      }
      whereLoopClear(pWInfo->pParse->db, &sBest);
    }
  }
  return rc;
}

/*
** Add all WhereLoop objects for all tables 







|














|
|
<

<




|














<
<
|



>





<
|
>
>
|
>
>
>
|
>
>
>
>
>
|
|
<
|
<
<
>
>
>
|
|
|
|
>
>
>

|
|
|
<


<







4839
4840
4841
4842
4843
4844
4845
4846
4847
4848
4849
4850
4851
4852
4853
4854
4855
4856
4857
4858
4859
4860
4861
4862

4863

4864
4865
4866
4867
4868
4869
4870
4871
4872
4873
4874
4875
4876
4877
4878
4879
4880
4881
4882


4883
4884
4885
4886
4887
4888
4889
4890
4891
4892

4893
4894
4895
4896
4897
4898
4899
4900
4901
4902
4903
4904
4905
4906
4907

4908


4909
4910
4911
4912
4913
4914
4915
4916
4917
4918
4919
4920
4921
4922

4923
4924

4925
4926
4927
4928
4929
4930
4931
  WhereClause *pWC;
  WhereLoop *pNew;
  WhereTerm *pTerm, *pWCEnd;
  int rc = SQLITE_OK;
  int iCur;
  WhereClause tempWC;
  WhereLoopBuilder sSubBuild;
  WhereOrSet sSum, sCur, sPrev;
  struct SrcList_item *pItem;
  
  pWC = pBuilder->pWC;
  if( pWInfo->wctrlFlags & WHERE_AND_ONLY ) return SQLITE_OK;
  pWCEnd = pWC->a + pWC->nTerm;
  pNew = pBuilder->pNew;

  for(pTerm=pWC->a; pTerm<pWCEnd && rc==SQLITE_OK; pTerm++){
    if( (pTerm->eOperator & WO_OR)!=0
     && (pTerm->u.pOrInfo->indexable & pNew->maskSelf)!=0 
    ){
      WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
      WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
      WhereTerm *pOrTerm;
      int once = 1;
      int i, j;

    

      pItem = pWInfo->pTabList->a + pNew->iTab;
      iCur = pItem->iCursor;
      sSubBuild = *pBuilder;
      sSubBuild.pOrderBy = 0;
      sSubBuild.pOrSet = &sCur;

      for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
        if( (pOrTerm->eOperator & WO_AND)!=0 ){
          sSubBuild.pWC = &pOrTerm->u.pAndInfo->wc;
        }else if( pOrTerm->leftCursor==iCur ){
          tempWC.pWInfo = pWC->pWInfo;
          tempWC.pOuter = pWC;
          tempWC.op = TK_AND;
          tempWC.nTerm = 1;
          tempWC.a = pOrTerm;
          sSubBuild.pWC = &tempWC;
        }else{
          continue;
        }


        sCur.n = 0;
#ifndef SQLITE_OMIT_VIRTUALTABLE
        if( IsVirtual(pItem->pTab) ){
          rc = whereLoopAddVirtual(&sSubBuild);
          for(i=0; i<sCur.n; i++) sCur.a[i].prereq |= mExtra;
        }else
#endif
        {
          rc = whereLoopAddBtree(&sSubBuild, mExtra);
        }

        assert( rc==SQLITE_OK || sCur.n==0 );
        if( sCur.n==0 ){
          sSum.n = 0;
          break;
        }else if( once ){
          whereOrMove(&sSum, &sCur);
          once = 0;
        }else{
          whereOrMove(&sPrev, &sSum);
          sSum.n = 0;
          for(i=0; i<sPrev.n; i++){
            for(j=0; j<sCur.n; j++){
              whereOrInsert(&sSum, sPrev.a[i].prereq | sCur.a[j].prereq,
                            whereCostAdd(sPrev.a[i].rRun, sCur.a[j].rRun),
                            whereCostAdd(sPrev.a[i].nOut, sCur.a[j].nOut));

            }


          }
        }
      }
      pNew->nLTerm = 1;
      pNew->aLTerm[0] = pTerm;
      pNew->wsFlags = WHERE_MULTI_OR;
      pNew->rSetup = 0;
      pNew->iSortIdx = 0;
      memset(&pNew->u, 0, sizeof(pNew->u));
      for(i=0; rc==SQLITE_OK && i<sSum.n; i++){
        /* TUNING: Multiple by 3.5 for the secondary table lookup */
        pNew->rRun = sSum.a[i].rRun + 18;
        pNew->nOut = sSum.a[i].nOut;
        pNew->prereq = sSum.a[i].prereq;

        rc = whereLoopInsert(pBuilder, pNew);
      }

    }
  }
  return rc;
}

/*
** Add all WhereLoop objects for all tables 
Changes to test/where2.test.
694
695
696
697
698
699
700











701
702
703
  }
} {4}
do_test where2-11.4 {
  execsql {
    SELECT d FROM t11 WHERE c=7 OR (a=1 AND b=2) ORDER BY d;
  }
} {4 8 10}













finish_test







>
>
>
>
>
>
>
>
>
>
>



694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
  }
} {4}
do_test where2-11.4 {
  execsql {
    SELECT d FROM t11 WHERE c=7 OR (a=1 AND b=2) ORDER BY d;
  }
} {4 8 10}

# Verify that the OR clause is used in an outer loop even when
# the OR clause scores slightly better on an inner loop.
do_execsql_test where2-12.1 {
  CREATE TABLE t12(x INTEGER PRIMARY KEY, y);
  CREATE INDEX t12y ON t12(y);
  EXPLAIN QUERY PLAN
    SELECT a.x, b.x
      FROM t12 AS a JOIN t12 AS b ON a.y=b.x
     WHERE (b.x=$abc OR b.y=$abc);
} {/.*SEARCH TABLE t12 AS b .*SEARCH TABLE t12 AS b .*/}


finish_test
Changes to test/where8.test.
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
    SELECT a, d FROM t1, t2 WHERE (a = 2 OR a = 3) AND d = a
  }
} {2 2 3 3 0 0}

do_test where8-3.5 {
  execsql_status {
    SELECT a, d FROM t1, t2 WHERE (a = 2 OR a = 3) AND (d = a OR e = 'sixteen')

  }
} {2 2 2 4 3 3 3 4 0 0}

do_test where8-3.6 {
  # The first part of the WHERE clause in this query, (a=2 OR a=3) is
  # transformed into "a IN (2, 3)". This is why the sort is required.
  #
  execsql_status {
    SELECT a, d 
    FROM t1, t2 
    WHERE (a = 2 OR a = 3) AND (d = a OR e = 'sixteen')
    ORDER BY t1.rowid
  }
} {2 2 2 4 3 3 3 4 0 1}
do_test where8-3.7 {
  execsql_status {
    SELECT a, d 
    FROM t1, t2 
    WHERE a = 2 AND (d = a OR e = 'sixteen')
    ORDER BY t1.rowid
  }
} {2 2 2 4 0 0}
do_test where8-3.8 {
  execsql_status {
    SELECT a, d 
    FROM t1, t2 
    WHERE (a = 2 OR b = 'three') AND (d = a OR e = 'sixteen')
    ORDER BY t1.rowid
  }







>

|



















|







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
    SELECT a, d FROM t1, t2 WHERE (a = 2 OR a = 3) AND d = a
  }
} {2 2 3 3 0 0}

do_test where8-3.5 {
  execsql_status {
    SELECT a, d FROM t1, t2 WHERE (a = 2 OR a = 3) AND (d = a OR e = 'sixteen')
     ORDER BY +a, +d;
  }
} {2 2 2 4 3 3 3 4 0 1}

do_test where8-3.6 {
  # The first part of the WHERE clause in this query, (a=2 OR a=3) is
  # transformed into "a IN (2, 3)". This is why the sort is required.
  #
  execsql_status {
    SELECT a, d 
    FROM t1, t2 
    WHERE (a = 2 OR a = 3) AND (d = a OR e = 'sixteen')
    ORDER BY t1.rowid
  }
} {2 2 2 4 3 3 3 4 0 1}
do_test where8-3.7 {
  execsql_status {
    SELECT a, d 
    FROM t1, t2 
    WHERE a = 2 AND (d = a OR e = 'sixteen')
    ORDER BY t1.rowid
  }
} {/2 2 2 4 0 [01]/}
do_test where8-3.8 {
  execsql_status {
    SELECT a, d 
    FROM t1, t2 
    WHERE (a = 2 OR b = 'three') AND (d = a OR e = 'sixteen')
    ORDER BY t1.rowid
  }