/ Check-in [9a5d38c7]
Login

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

Overview
Comment:Clean up the proper-subset cost adjustment logic to make it more compact and easier to read and so that full branch test coverage is more easily obtained.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 9a5d38c79d2482a23bcfbc3ff35ca4fa269c768d
User & Date: drh 2014-04-18 22:20:31
Context
2014-04-21
13:21
Avoid discarding an ORDER BY clause in the case where an identical GROUP BY clauses uses an index to group, but not sort, the rows. Fix for [b75a9ca6b0]. check-in: de9a490f user: dan tags: trunk
2014-04-18
22:20
Clean up the proper-subset cost adjustment logic to make it more compact and easier to read and so that full branch test coverage is more easily obtained. check-in: 9a5d38c7 user: drh tags: trunk
00:49
Add the SQLITE_RUNTIME_BYTEORDER compile-time option to force SQLite to check the processor byte-order at run-time. Add additional compile-time byte order checks for ARM, PPC, and SPARC. check-in: 2c536387 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

3708
3709
3710
3711
3712
3713
3714
3715
3716










3717
3718




3719
3720





3721
3722
3723

3724

3725
3726

3727
3728
3729
3730
3731
3732
3733
....
3741
3742
3743
3744
3745
3746
3747
3748
3749
3750
3751
3752
3753
3754
3755
3756
3757
3758
3759
3760
3761
3762
3763
3764
3765
3766
3767
      whereLoopDelete(db, p);
    }
    sqlite3DbFree(db, pWInfo);
  }
}

/*
** Return TRUE if the set of WHERE clause terms used by pA is a proper
** subset of the WHERE clause terms used by pB.










*/
static int whereLoopProperSubset(const WhereLoop *pA, const WhereLoop *pB){




  int i, j;
  assert( pA->nLTerm<pB->nLTerm );  /* Checked by calling function */





  for(j=0, i=pA->nLTerm-1; i>=0 && j>=0; i--){
    for(j=pB->nLTerm-1; j>=0; j--){
      if( pB->aLTerm[j]==pA->aLTerm[i] ) break;

    }

  }
  return j>=0;

}

/*
** Try to adjust the cost of WhereLoop pTemplate upwards or downwards so
** that:
**
**   (1) pTemplate costs less than any other WhereLoops that are a proper
................................................................................
** also used by Y.
*/
static void whereLoopAdjustCost(const WhereLoop *p, WhereLoop *pTemplate){
  if( (pTemplate->wsFlags & WHERE_INDEXED)==0 ) return;
  for(; p; p=p->pNextLoop){
    if( p->iTab!=pTemplate->iTab ) continue;
    if( (p->wsFlags & WHERE_INDEXED)==0 ) continue;
    if( p->nLTerm<pTemplate->nLTerm
     && (p->rRun<pTemplate->rRun || (p->rRun==pTemplate->rRun &&
                                     p->nOut<=pTemplate->nOut))
     && whereLoopProperSubset(p, pTemplate)
    ){
      pTemplate->rRun = p->rRun;
      pTemplate->nOut = p->nOut - 1;
    }else
    if( p->nLTerm>pTemplate->nLTerm
     && (p->rRun>pTemplate->rRun || (p->rRun==pTemplate->rRun &&
                                     p->nOut>=pTemplate->nOut))
     && whereLoopProperSubset(pTemplate, p)
    ){
      pTemplate->rRun = p->rRun;
      pTemplate->nOut = p->nOut + 1;
    }
  }
}

/*







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

<
>
>
>
>

<
>
>
>
>
>
|
|
<
>

>

<
>







 







|
|
|
|
|
|
|
|
<
<
<
<
<







3708
3709
3710
3711
3712
3713
3714
3715
3716
3717
3718
3719
3720
3721
3722
3723
3724
3725
3726
3727

3728
3729
3730
3731
3732

3733
3734
3735
3736
3737
3738
3739

3740
3741
3742
3743

3744
3745
3746
3747
3748
3749
3750
3751
....
3759
3760
3761
3762
3763
3764
3765
3766
3767
3768
3769
3770
3771
3772
3773





3774
3775
3776
3777
3778
3779
3780
      whereLoopDelete(db, p);
    }
    sqlite3DbFree(db, pWInfo);
  }
}

/*
** Return TRUE if both of the following are true:
**
**   (1)  X has the same or lower cost that Y
**   (2)  X is a proper subset of Y
**
** By "proper subset" we mean that X uses fewer WHERE clause terms
** than Y and that every WHERE clause term used by X is also used
** by Y.
**
** If X is a proper subset of Y then Y is a better choice and ought
** to have a lower cost.  This routine returns TRUE when that cost 
** relationship is inverted and needs to be adjusted.
*/

static int whereLoopCheaperProperSubset(
  const WhereLoop *pX,       /* First WhereLoop to compare */
  const WhereLoop *pY        /* Compare against this WhereLoop */
){
  int i, j;

  if( pX->nLTerm >= pY->nLTerm ) return 0; /* X is not a subset of Y */
  if( pX->rRun >= pY->rRun ){
    if( pX->rRun > pY->rRun ) return 0;    /* X costs more than Y */
    if( pX->nOut > pY->nOut ) return 0;    /* X costs more than Y */
  }
  for(j=0, i=pX->nLTerm-1; i>=0; i--){
    for(j=pY->nLTerm-1; j>=0; j--){

      if( pY->aLTerm[j]==pX->aLTerm[i] ) break;
    }
    if( j<0 ) return 0;  /* X not a subset of Y since term X[i] not used by Y */
  }

  return 1;  /* All conditions meet */
}

/*
** Try to adjust the cost of WhereLoop pTemplate upwards or downwards so
** that:
**
**   (1) pTemplate costs less than any other WhereLoops that are a proper
................................................................................
** also used by Y.
*/
static void whereLoopAdjustCost(const WhereLoop *p, WhereLoop *pTemplate){
  if( (pTemplate->wsFlags & WHERE_INDEXED)==0 ) return;
  for(; p; p=p->pNextLoop){
    if( p->iTab!=pTemplate->iTab ) continue;
    if( (p->wsFlags & WHERE_INDEXED)==0 ) continue;
    if( whereLoopCheaperProperSubset(p, pTemplate) ){
      /* Adjust pTemplate cost downward so that it is cheaper than its 
      ** subset p */
      pTemplate->rRun = p->rRun;
      pTemplate->nOut = p->nOut - 1;
    }else if( whereLoopCheaperProperSubset(pTemplate, p) ){
      /* Adjust pTemplate cost upward so that it is costlier than p since
      ** pTemplate is a proper subset of p */





      pTemplate->rRun = p->rRun;
      pTemplate->nOut = p->nOut + 1;
    }
  }
}

/*