/ 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 Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/where.c.

  3708   3708         whereLoopDelete(db, p);
  3709   3709       }
  3710   3710       sqlite3DbFree(db, pWInfo);
  3711   3711     }
  3712   3712   }
  3713   3713   
  3714   3714   /*
  3715         -** Return TRUE if the set of WHERE clause terms used by pA is a proper
  3716         -** subset of the WHERE clause terms used by pB.
         3715  +** Return TRUE if both of the following are true:
         3716  +**
         3717  +**   (1)  X has the same or lower cost that Y
         3718  +**   (2)  X is a proper subset of Y
         3719  +**
         3720  +** By "proper subset" we mean that X uses fewer WHERE clause terms
         3721  +** than Y and that every WHERE clause term used by X is also used
         3722  +** by Y.
         3723  +**
         3724  +** If X is a proper subset of Y then Y is a better choice and ought
         3725  +** to have a lower cost.  This routine returns TRUE when that cost 
         3726  +** relationship is inverted and needs to be adjusted.
  3717   3727   */
  3718         -static int whereLoopProperSubset(const WhereLoop *pA, const WhereLoop *pB){
         3728  +static int whereLoopCheaperProperSubset(
         3729  +  const WhereLoop *pX,       /* First WhereLoop to compare */
         3730  +  const WhereLoop *pY        /* Compare against this WhereLoop */
         3731  +){
  3719   3732     int i, j;
  3720         -  assert( pA->nLTerm<pB->nLTerm );  /* Checked by calling function */
  3721         -  for(j=0, i=pA->nLTerm-1; i>=0 && j>=0; i--){
  3722         -    for(j=pB->nLTerm-1; j>=0; j--){
  3723         -      if( pB->aLTerm[j]==pA->aLTerm[i] ) break;
         3733  +  if( pX->nLTerm >= pY->nLTerm ) return 0; /* X is not a subset of Y */
         3734  +  if( pX->rRun >= pY->rRun ){
         3735  +    if( pX->rRun > pY->rRun ) return 0;    /* X costs more than Y */
         3736  +    if( pX->nOut > pY->nOut ) return 0;    /* X costs more than Y */
         3737  +  }
         3738  +  for(j=0, i=pX->nLTerm-1; i>=0; i--){
         3739  +    for(j=pY->nLTerm-1; j>=0; j--){
         3740  +      if( pY->aLTerm[j]==pX->aLTerm[i] ) break;
  3724   3741       }
         3742  +    if( j<0 ) return 0;  /* X not a subset of Y since term X[i] not used by Y */
  3725   3743     }
  3726         -  return j>=0;
         3744  +  return 1;  /* All conditions meet */
  3727   3745   }
  3728   3746   
  3729   3747   /*
  3730   3748   ** Try to adjust the cost of WhereLoop pTemplate upwards or downwards so
  3731   3749   ** that:
  3732   3750   **
  3733   3751   **   (1) pTemplate costs less than any other WhereLoops that are a proper
................................................................................
  3741   3759   ** also used by Y.
  3742   3760   */
  3743   3761   static void whereLoopAdjustCost(const WhereLoop *p, WhereLoop *pTemplate){
  3744   3762     if( (pTemplate->wsFlags & WHERE_INDEXED)==0 ) return;
  3745   3763     for(; p; p=p->pNextLoop){
  3746   3764       if( p->iTab!=pTemplate->iTab ) continue;
  3747   3765       if( (p->wsFlags & WHERE_INDEXED)==0 ) continue;
  3748         -    if( p->nLTerm<pTemplate->nLTerm
  3749         -     && (p->rRun<pTemplate->rRun || (p->rRun==pTemplate->rRun &&
  3750         -                                     p->nOut<=pTemplate->nOut))
  3751         -     && whereLoopProperSubset(p, pTemplate)
  3752         -    ){
         3766  +    if( whereLoopCheaperProperSubset(p, pTemplate) ){
         3767  +      /* Adjust pTemplate cost downward so that it is cheaper than its 
         3768  +      ** subset p */
  3753   3769         pTemplate->rRun = p->rRun;
  3754   3770         pTemplate->nOut = p->nOut - 1;
  3755         -    }else
  3756         -    if( p->nLTerm>pTemplate->nLTerm
  3757         -     && (p->rRun>pTemplate->rRun || (p->rRun==pTemplate->rRun &&
  3758         -                                     p->nOut>=pTemplate->nOut))
  3759         -     && whereLoopProperSubset(pTemplate, p)
  3760         -    ){
         3771  +    }else if( whereLoopCheaperProperSubset(pTemplate, p) ){
         3772  +      /* Adjust pTemplate cost upward so that it is costlier than p since
         3773  +      ** pTemplate is a proper subset of p */
  3761   3774         pTemplate->rRun = p->rRun;
  3762   3775         pTemplate->nOut = p->nOut + 1;
  3763   3776       }
  3764   3777     }
  3765   3778   }
  3766   3779   
  3767   3780   /*