SQLite

Check-in [8f27f35f28]
Login

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

Overview
Comment:Simplify and add invariants to the WhereLoop merging logic inside of whereLoopInsert().
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1: 8f27f35f288434b9e7bc503c608f1e2b590ade4d
User & Date: drh 2013-06-19 12:34:13.186
Context
2013-06-19
13:32
Fix a harmless uninitialized variable warning. (check-in: 9d3ef3bd2c user: drh tags: nextgen-query-plan-exp)
12:34
Simplify and add invariants to the WhereLoop merging logic inside of whereLoopInsert(). (check-in: 8f27f35f28 user: drh tags: nextgen-query-plan-exp)
03:27
Fix compiler warnings. Fix a harmless off-by-one error in the solver. (check-in: 10021941d0 user: drh tags: nextgen-query-plan-exp)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/where.c.
4111
4112
4113
4114
4115
4116
4117
4118
















4119
4120
4121
4122
4123
4124
4125
4126
4127
4128
4129
4130
4131
4132
4133
4134
4135
4136
4137
4138
4139
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
    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){
    if( p->iTab!=pTemplate->iTab || p->iSortIdx!=pTemplate->iSortIdx ) continue;
















    if( (p->prereq & pTemplate->prereq)==p->prereq
     && p->rSetup<=pTemplate->rSetup
     && p->rRun<=pTemplate->rRun
    ){
      /* This branch taken when p is equal or better than pTemplate in 
      ** all of (1) dependences (2) setup-cost, and (3) run-cost. */
      testcase( p->rRun==pTemplate->rRun );
      if( p->nLTerm<pTemplate->nLTerm
       && (p->wsFlags & WHERE_INDEXED)!=0
       && (pTemplate->wsFlags & WHERE_INDEXED)!=0
       && p->u.btree.pIndex==pTemplate->u.btree.pIndex
       && p->prereq==pTemplate->prereq
      ){
        /* Overwrite an existing WhereLoop with an similar one that uses
        ** more terms of the index */
        pNext = p->pNextLoop;
        break;
      }else if( p->nOut>pTemplate->nOut
       && p->rSetup==pTemplate->rSetup
       && p->rRun==pTemplate->rRun
      ){
        /* Overwrite an existing WhereLoop with the same cost but more
        ** outputs */
        pNext = p->pNextLoop;
        break;
      }else{
        /* pTemplate is not helpful.
        ** Return without changing or adding anything */
        goto whereLoopInsert_noop;
      }
    }
    testcase( (p->prereq & pTemplate->prereq)==p->prereq
              && p->rSetup<=pTemplate->rSetup
              && p->rRun==pTemplate->rRun+1 );
    if( (p->prereq & pTemplate->prereq)==pTemplate->prereq
     && p->rSetup>=pTemplate->rSetup
     && p->rRun>=pTemplate->rRun

    ){
      /* Overwrite an existing WhereLoop with a better one: one that is
      ** better at one of (1) dependences, (2) setup-cost, or (3) run-cost
      ** and is no worse in any of those categories. */
      testcase( p->rSetup==pTemplate->rSetup );
      testcase( p->rRun==pTemplate->rRun );
      pNext = p->pNextLoop;
      break;
    }
    testcase( (p->prereq & pTemplate->prereq)==pTemplate->prereq
              && p->rSetup>=pTemplate->rSetup
              && p->rRun==pTemplate->rRun-1 );
  }

  /* If we reach this point it means that either p[] should be overwritten
  ** with pTemplate[] if p[] exists, or if p==NULL then allocate a new
  ** WhereLoop and insert it.
  */
#if WHERETRACE_ENABLED







|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>






|










<
<
<
<
<
<
<
<






<
<
<

<

>




<
<



<
<
<







4111
4112
4113
4114
4115
4116
4117
4118
4119
4120
4121
4122
4123
4124
4125
4126
4127
4128
4129
4130
4131
4132
4133
4134
4135
4136
4137
4138
4139
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
    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){
    if( p->iTab!=pTemplate->iTab || p->iSortIdx!=pTemplate->iSortIdx ){
      /* If either the iTab or iSortIdx values for two WhereLoop are different
      ** then those WhereLoops need to be considered separately.  Neither is
      ** a candidate to replace the other. */
      continue;
    }
    /* In the current implementation, the rSetup value is either zero
    ** or the cost of building an automatic index (NlogN) and the NlogN
    ** is the same for compatible WhereLoops. */
    assert( p->rSetup==0 || pTemplate->rSetup==0 
                 || p->rSetup==pTemplate->rSetup );

    /* whereLoopAddBtree() always generates and inserts the automatic index
    ** case first.  Hence compatible candidate WhereLoops never have a larger
    ** rSetup. Call this SETUP-INVARIANT */
    assert( p->rSetup>=pTemplate->rSetup );

    if( (p->prereq & pTemplate->prereq)==p->prereq
     && p->rSetup<=pTemplate->rSetup
     && p->rRun<=pTemplate->rRun
    ){
      /* This branch taken when p is equal or better than pTemplate in 
      ** all of (1) dependences (2) setup-cost, and (3) run-cost. */
      assert( p->rSetup==pTemplate->rSetup );
      if( p->nLTerm<pTemplate->nLTerm
       && (p->wsFlags & WHERE_INDEXED)!=0
       && (pTemplate->wsFlags & WHERE_INDEXED)!=0
       && p->u.btree.pIndex==pTemplate->u.btree.pIndex
       && p->prereq==pTemplate->prereq
      ){
        /* Overwrite an existing WhereLoop with an similar one that uses
        ** more terms of the index */
        pNext = p->pNextLoop;
        break;








      }else{
        /* pTemplate is not helpful.
        ** Return without changing or adding anything */
        goto whereLoopInsert_noop;
      }
    }



    if( (p->prereq & pTemplate->prereq)==pTemplate->prereq

     && p->rRun>=pTemplate->rRun
     && ALWAYS(p->rSetup>=pTemplate->rSetup) /* See SETUP-INVARIANT above */
    ){
      /* Overwrite an existing WhereLoop with a better one: one that is
      ** better at one of (1) dependences, (2) setup-cost, or (3) run-cost
      ** and is no worse in any of those categories. */


      pNext = p->pNextLoop;
      break;
    }



  }

  /* If we reach this point it means that either p[] should be overwritten
  ** with pTemplate[] if p[] exists, or if p==NULL then allocate a new
  ** WhereLoop and insert it.
  */
#if WHERETRACE_ENABLED