SQLite4
Check-in [3f4a1c7648]
Not logged in

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

Overview
Comment:Update where.c with patches from sqlite3. src4 where.c is now based on sqlite3 artifact 1a26c37b7b.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 3f4a1c7648f1240f611e4b3b084a8f3917291930
User & Date: dan 2013-07-26 20:04:29
References
2013-07-29
12:31
Fix an typo affecting virtual WHERE clause terms made in [3f4a1c7648]. check-in: 736b5e6a1a user: dan tags: trunk
Context
2013-07-26
21:13
Remove unused fields from KeyInfo. Enhancement the EXPLAIN output for KeyInfo P4 columns. check-in: 9eb585660b user: drh tags: trunk
20:04
Update where.c with patches from sqlite3. src4 where.c is now based on sqlite3 artifact 1a26c37b7b. check-in: 3f4a1c7648 user: dan tags: trunk
19:13
Fix some issues with assigning costs to loops in where.c. check-in: faac50a266 user: dan tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

43
44
45
46
47
48
49


50
51
52
53
54
55
56
...
149
150
151
152
153
154
155





















156
157
158
159
160
161
162
...
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
...
507
508
509
510
511
512
513

















































514
515
516
517
518
519
520
....
3865
3866
3867
3868
3869
3870
3871

3872
3873
3874
3875
3876
3877
3878
....
4198
4199
4200
4201
4202
4203
4204
4205
4206
4207
4208
4209
4210
4211
4212
4213
4214
4215
4216
4217
....
4222
4223
4224
4225
4226
4227
4228
4229
4230
4231
4232
4233


4234
4235
4236
4237
4238
4239
4240
4241
4242
4243
4244
4245
4246
4247
4248


4249
4250
4251
4252
4253
4254
4255
4256
4257
4258
4259
....
4339
4340
4341
4342
4343
4344
4345
4346
4347
4348
4349
4350
4351
4352
4353
....
4616
4617
4618
4619
4620
4621
4622
4623
4624
4625
4626
4627
4628
4629
4630
....
4696
4697
4698
4699
4700
4701
4702
4703
4704
4705
4706
4707
4708
4709
4710
....
4917
4918
4919
4920
4921
4922
4923
4924
4925
4926
4927
4928
4929
4930
4931
....
4932
4933
4934
4935
4936
4937
4938
4939
4940
4941
4942
4943
4944
4945
4946
4947
4948
4949
4950
4951
4952
4953
4954
4955
....
4956
4957
4958
4959
4960
4961
4962
4963
4964
4965
4966
4967
4968

4969
4970
4971
4972
4973
4974

4975
4976
4977
4978
4979
4980









4981
4982
4983



4984
4985
4986
4987



4988
4989

4990
4991
4992
4993
4994
4995
4996
4997
4998
4999

5000
5001
5002
5003
5004
5005
5006
....
5797
5798
5799
5800
5801
5802
5803
5804

5805
5806
5807
5808
5809
5810
5811
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.
................................................................................
  /**** 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(sqlite4*, WhereLoop*, int);

/*
** Each instance of this object holds a sequence of WhereLoop objects
** that implement some or all of a query plan.
................................................................................
** 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
................................................................................
** the rowids returned by a WHERE clause.  Return FALSE if doing an
** UPDATE or DELETE might change subsequent WHERE clause results.
*/
int sqlite4WhereOkOnePass(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 */
){
................................................................................
    ** 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 = sqlite4ExprDup(pParse->db, pExpr, 0);
        pAndExpr = sqlite4ExprAnd(pParse->db, pAndExpr, pExpr);
      }
      if( pAndExpr ){
................................................................................
**
** 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
................................................................................
static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){
  WhereLoop **ppPrev, *p, *pNext = 0;
  WhereInfo *pWInfo = pBuilder->pWInfo;
  sqlite4 *db = pWInfo->pParse->db;

  assert( pTemplate->u.btree.pIndex || !(pTemplate->wsFlags & WHERE_INDEXED) );

  /* 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( sqlite4WhereTrace & 0x8 ){
      sqlite4DebugPrintf(p->maskSelf==0 ? "ins-init: " : "ins-best: ");


      whereLoopPrint(pTemplate, pWInfo->pTabList);
    }
#endif
    whereLoopXfer(db, p, pTemplate);
    return SQLITE4_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){
................................................................................
  }
  return SQLITE4_OK;

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


................................................................................
  }

  rSize = whereCost(pSrc->pTab->nRowEst);
  rLogSize = estLog(rSize);

#ifndef SQLITE4_OMIT_AUTOMATIC_INDEX
  /* Automatic indexes */
  if( !pBuilder->pBest
   && (pWInfo->pParse->db->flags & SQLITE4_AutoIndex)!=0
   && pSrc->pIndex==0
#if 0
   && !pSrc->viaCoroutine
#endif
   && !pSrc->notIndexed
   && !pSrc->isCorrelated
................................................................................
    assert( (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || b==0 );
    pNew->iSortIdx = b ? iSortIdx : 0;

    if( pProbe==pPk || b || (bCover
     && pProbe->bUnordered==0
     && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
#if 0
     && sqlite3GlobalConfig.bUseCis
     && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan)
#endif
    )){
      if( pProbe==pPk ){
        /* TUNING: Cost of full table scan is 3*(N + log2(N)).
        **  +  The extra 3 factor is to encourage the use of indexed lookups
        **     over full scans.  A smaller constant 2 is used for covering
................................................................................
  WhereClause *pWC;
  WhereLoop *pNew;
  WhereTerm *pTerm, *pWCEnd;
  int rc = SQLITE4_OK;
  int iCur;
  WhereClause tempWC;
  WhereLoopBuilder sSubBuild;
  WhereLoop sBest;
  struct SrcListItem *pItem;
  
  pWC = pBuilder->pWC;
  if( pWInfo->wctrlFlags & WHERE_AND_ONLY ) return SQLITE4_OK;
  pWCEnd = pWC->a + pWC->nTerm;
  pNew = pBuilder->pNew;

................................................................................
  for(pTerm=pWC->a; pTerm<pWCEnd && rc==SQLITE4_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 SQLITE4_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==SQLITE4_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 
*/
static int whereLoopAddAll(WhereLoopBuilder *pBuilder){
  WhereInfo *pWInfo = pBuilder->pWInfo;
  Bitmask mExtra = 0;
................................................................................
  pWInfo->pResultSet = pResultSet;
  pWInfo->iBreak = sqlite4VdbeMakeLabel(v);
  pWInfo->wctrlFlags = wctrlFlags;
  pWInfo->savedNQueryLoop = pParse->nQueryLoop;
  pMaskSet = &pWInfo->sMaskSet;
  sWLB.pWInfo = pWInfo;
  sWLB.pWC = &pWInfo->sWC;
  sWLB.pNew = (WhereLoop*)&pWInfo->a[nTabList];

  whereLoopInit(sWLB.pNew);
#ifdef SQLITE4_DEBUG
  sWLB.pNew->cId = '*';
#endif

  /* Split the WHERE clause into separate subexpressions where each
  ** subexpression is separated by an AND operator.







>
>







 







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







 







|







 







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







 







>







 







|
|
|
|

|







 







|
|
<
<

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


<
>
>



<







 







|







 







|







 







|







 







|







 







|
|
<
|
<




|







 







|
|
<



>





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

<
>
|
|
<


<




>







 







|
>







43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
...
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
184
185
...
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
...
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
589
590
591
592
....
3937
3938
3939
3940
3941
3942
3943
3944
3945
3946
3947
3948
3949
3950
3951
....
4271
4272
4273
4274
4275
4276
4277
4278
4279
4280
4281
4282
4283
4284
4285
4286
4287
4288
4289
4290
....
4295
4296
4297
4298
4299
4300
4301
4302
4303


4304
4305
4306
4307
4308
4309
4310
4311







4312
4313

4314
4315
4316
4317
4318

4319
4320
4321
4322
4323
4324
4325
....
4405
4406
4407
4408
4409
4410
4411
4412
4413
4414
4415
4416
4417
4418
4419
....
4682
4683
4684
4685
4686
4687
4688
4689
4690
4691
4692
4693
4694
4695
4696
....
4762
4763
4764
4765
4766
4767
4768
4769
4770
4771
4772
4773
4774
4775
4776
....
4983
4984
4985
4986
4987
4988
4989
4990
4991
4992
4993
4994
4995
4996
4997
....
4998
4999
5000
5001
5002
5003
5004
5005
5006

5007

5008
5009
5010
5011
5012
5013
5014
5015
5016
5017
5018
5019
....
5020
5021
5022
5023
5024
5025
5026
5027
5028

5029
5030
5031
5032
5033
5034
5035
5036
5037

5038
5039
5040
5041
5042
5043
5044
5045
5046
5047
5048
5049
5050
5051
5052
5053
5054


5055
5056
5057
5058
5059
5060
5061
5062
5063
5064
5065

5066
5067
5068

5069
5070

5071
5072
5073
5074
5075
5076
5077
5078
5079
5080
5081
5082
....
5873
5874
5875
5876
5877
5878
5879
5880
5881
5882
5883
5884
5885
5886
5887
5888
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.
................................................................................
  /**** 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(sqlite4*, WhereLoop*, int);

/*
** Each instance of this object holds a sequence of WhereLoop objects
** that implement some or all of a query plan.
................................................................................
** 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
................................................................................
** the rowids returned by a WHERE clause.  Return FALSE if doing an
** UPDATE or DELETE might change subsequent WHERE clause results.
*/
int sqlite4WhereOkOnePass(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 */
){
................................................................................
    ** 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_VIRTUAL|TERM_ORINFO) ) continue;
        if( (pWC->a[iTerm].eOperator & WO_ALL)==0 ) continue;
        pExpr = sqlite4ExprDup(pParse->db, pExpr, 0);
        pAndExpr = sqlite4ExprAnd(pParse->db, pAndExpr, pExpr);
      }
      if( pAndExpr ){
................................................................................
**
** 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
................................................................................
static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){
  WhereLoop **ppPrev, *p, *pNext = 0;
  WhereInfo *pWInfo = pBuilder->pWInfo;
  sqlite4 *db = pWInfo->pParse->db;

  assert( pTemplate->u.btree.pIndex || !(pTemplate->wsFlags & WHERE_INDEXED) );

  /* 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( sqlite4WhereTrace & 0x8 ){


      sqlite4DebugPrintf(x?"   or-%d:  ":"   or-X:  ", n);
      whereLoopPrint(pTemplate, pWInfo->pTabList);
    }
#endif

    return SQLITE4_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){
................................................................................
  }
  return SQLITE4_OK;

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


................................................................................
  }

  rSize = whereCost(pSrc->pTab->nRowEst);
  rLogSize = estLog(rSize);

#ifndef SQLITE4_OMIT_AUTOMATIC_INDEX
  /* Automatic indexes */
  if( !pBuilder->pOrSet
   && (pWInfo->pParse->db->flags & SQLITE4_AutoIndex)!=0
   && pSrc->pIndex==0
#if 0
   && !pSrc->viaCoroutine
#endif
   && !pSrc->notIndexed
   && !pSrc->isCorrelated
................................................................................
    assert( (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || b==0 );
    pNew->iSortIdx = b ? iSortIdx : 0;

    if( pProbe==pPk || b || (bCover
     && pProbe->bUnordered==0
     && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
#if 0
     && sqlite4GlobalConfig.bUseCis
     && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan)
#endif
    )){
      if( pProbe==pPk ){
        /* TUNING: Cost of full table scan is 3*(N + log2(N)).
        **  +  The extra 3 factor is to encourage the use of indexed lookups
        **     over full scans.  A smaller constant 2 is used for covering
................................................................................
  WhereClause *pWC;
  WhereLoop *pNew;
  WhereTerm *pTerm, *pWCEnd;
  int rc = SQLITE4_OK;
  int iCur;
  WhereClause tempWC;
  WhereLoopBuilder sSubBuild;
  WhereOrSet sSum, sCur, sPrev;
  struct SrcListItem *pItem;
  
  pWC = pBuilder->pWC;
  if( pWInfo->wctrlFlags & WHERE_AND_ONLY ) return SQLITE4_OK;
  pWCEnd = pWC->a + pWC->nTerm;
  pNew = pBuilder->pNew;

................................................................................
  for(pTerm=pWC->a; pTerm<pWCEnd && rc==SQLITE4_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 SQLITE4_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==SQLITE4_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==SQLITE4_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 
*/
static int whereLoopAddAll(WhereLoopBuilder *pBuilder){
  WhereInfo *pWInfo = pBuilder->pWInfo;
  Bitmask mExtra = 0;
................................................................................
  pWInfo->pResultSet = pResultSet;
  pWInfo->iBreak = sqlite4VdbeMakeLabel(v);
  pWInfo->wctrlFlags = wctrlFlags;
  pWInfo->savedNQueryLoop = pParse->nQueryLoop;
  pMaskSet = &pWInfo->sMaskSet;
  sWLB.pWInfo = pWInfo;
  sWLB.pWC = &pWInfo->sWC;
  sWLB.pNew = (WhereLoop*)(((char*)pWInfo)+nByteWInfo);
  assert( EIGHT_BYTE_ALIGNMENT(sWLB.pNew) );
  whereLoopInit(sWLB.pNew);
#ifdef SQLITE4_DEBUG
  sWLB.pNew->cId = '*';
#endif

  /* Split the WHERE clause into separate subexpressions where each
  ** subexpression is separated by an AND operator.