/ Check-in [8f869ca7]
Login

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

Overview
Comment:Experiments in picking better query plans, especially when the usage of one index is a subset of another.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | query-plan-experiments
Files: files | file ages | folders
SHA1: 8f869ca7a6eaa9ca7a08102290e6c606735f9090
User & Date: drh 2014-03-29 21:16:07
Context
2014-03-31
18:24
Make sure that an index that covers a proper superset of the WHERE clause terms of some other index has a lower cost than the other index. check-in: ea8b0910 user: drh tags: query-plan-experiments
2014-03-29
21:16
Experiments in picking better query plans, especially when the usage of one index is a subset of another. check-in: 8f869ca7 user: drh tags: query-plan-experiments
2014-03-28
14:41
Disable the wal64k.test script for non-unix systems since it depends on unix-only features. check-in: 27deb6e4 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         -** Insert or replace a WhereLoop entry using the template supplied.
  3716         -**
  3717         -** An existing WhereLoop entry might be overwritten if the new template
  3718         -** is better and has fewer dependencies.  Or the template will be ignored
  3719         -** and no insert will occur if an existing WhereLoop is faster and has
  3720         -** fewer dependencies than the template.  Otherwise a new WhereLoop is
  3721         -** added based on the template.
  3722         -**
  3723         -** If pBuilder->pOrSet is not NULL then we only care about only the
  3724         -** prerequisites and rRun and nOut costs of the N best loops.  That
  3725         -** information is gathered in the pBuilder->pOrSet object.  This special
  3726         -** processing mode is used only for OR clause processing.
  3727         -**
  3728         -** When accumulating multiple loops (when pBuilder->pOrSet is NULL) we
  3729         -** still might overwrite similar loops with the new template if the
  3730         -** template is better.  Loops may be overwritten if the following 
  3731         -** conditions are met:
  3732         -**
  3733         -**    (1)  They have the same iTab.
  3734         -**    (2)  They have the same iSortIdx.
  3735         -**    (3)  The template has same or fewer dependencies than the current loop
  3736         -**    (4)  The template has the same or lower cost than the current loop
  3737         -**    (5)  The template uses more terms of the same index but has no additional
  3738         -**         dependencies          
  3739         -*/
  3740         -static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){
  3741         -  WhereLoop **ppPrev, *p, *pNext = 0;
  3742         -  WhereInfo *pWInfo = pBuilder->pWInfo;
  3743         -  sqlite3 *db = pWInfo->pParse->db;
  3744         -
  3745         -  /* If pBuilder->pOrSet is defined, then only keep track of the costs
  3746         -  ** and prereqs.
  3747         -  */
  3748         -  if( pBuilder->pOrSet!=0 ){
  3749         -#if WHERETRACE_ENABLED
  3750         -    u16 n = pBuilder->pOrSet->n;
  3751         -    int x =
  3752         -#endif
  3753         -    whereOrInsert(pBuilder->pOrSet, pTemplate->prereq, pTemplate->rRun,
  3754         -                                    pTemplate->nOut);
  3755         -#if WHERETRACE_ENABLED /* 0x8 */
  3756         -    if( sqlite3WhereTrace & 0x8 ){
  3757         -      sqlite3DebugPrintf(x?"   or-%d:  ":"   or-X:  ", n);
  3758         -      whereLoopPrint(pTemplate, pBuilder->pWC);
  3759         -    }
  3760         -#endif
  3761         -    return SQLITE_OK;
  3762         -  }
  3763         -
  3764         -  /* Search for an existing WhereLoop to overwrite, or which takes
  3765         -  ** priority over pTemplate.
  3766         -  */
  3767         -  for(ppPrev=&pWInfo->pLoops, p=*ppPrev; p; ppPrev=&p->pNextLoop, p=*ppPrev){
         3715  +** Search the list of WhereLoops in *ppPrev looking for one that can be
         3716  +** supplanted by pTemplate.
         3717  +**
         3718  +** Return NULL if the WhereLoop list contains an entry that can supplant
         3719  +** pTemplate, in other words if pTemplate does not belong on the list.
         3720  +**
         3721  +** If pX is a WhereLoop that pTemplate can supplant, then return the
         3722  +** link that points to pX.
         3723  +**
         3724  +** If pTemplate cannot supplant any existing element of the list but needs
         3725  +** to be added to the list, then return a pointer to the tail of the list.
         3726  +*/
         3727  +static WhereLoop **whereLoopFindLesser(
         3728  +  WhereLoop **ppPrev,
         3729  +  const WhereLoop *pTemplate
         3730  +){
         3731  +  WhereLoop *p;
         3732  +  for(p=(*ppPrev); p; ppPrev=&p->pNextLoop, p=*ppPrev){
  3768   3733       if( p->iTab!=pTemplate->iTab || p->iSortIdx!=pTemplate->iSortIdx ){
  3769   3734         /* If either the iTab or iSortIdx values for two WhereLoop are different
  3770   3735         ** then those WhereLoops need to be considered separately.  Neither is
  3771   3736         ** a candidate to replace the other. */
  3772   3737         continue;
  3773   3738       }
  3774   3739       /* In the current implementation, the rSetup value is either zero
................................................................................
  3795   3760          && p->nLTerm<pTemplate->nLTerm
  3796   3761          && (p->wsFlags & pTemplate->wsFlags & WHERE_INDEXED)!=0
  3797   3762          && (p->u.btree.pIndex==pTemplate->u.btree.pIndex
  3798   3763             || pTemplate->rRun+p->nLTerm<=p->rRun+pTemplate->nLTerm)
  3799   3764         ){
  3800   3765           /* Overwrite an existing WhereLoop with an similar one that uses
  3801   3766           ** more terms of the index */
  3802         -        pNext = p->pNextLoop;
  3803   3767           break;
  3804   3768         }else{
  3805         -        /* pTemplate is not helpful.
  3806         -        ** Return without changing or adding anything */
  3807         -        goto whereLoopInsert_noop;
         3769  +        /* There is an existing WhereLoop that is better than pTemplate */
         3770  +        return 0;
  3808   3771         }
  3809   3772       }
  3810   3773       if( (p->prereq & pTemplate->prereq)==pTemplate->prereq
  3811   3774        && p->rRun>=pTemplate->rRun
  3812   3775        && p->nOut>=pTemplate->nOut
  3813   3776       ){
  3814   3777         /* Overwrite an existing WhereLoop with a better one: one that is
  3815   3778         ** better at one of (1) dependencies, (2) setup-cost, (3) run-cost
  3816   3779         ** or (4) number of output rows, and is no worse in any of those
  3817   3780         ** categories. */
  3818   3781         assert( p->rSetup>=pTemplate->rSetup ); /* SETUP-INVARIANT above */
  3819         -      pNext = p->pNextLoop;
  3820   3782         break;
  3821   3783       }
         3784  +  }
         3785  +  return ppPrev;
         3786  +}
         3787  +
         3788  +/*
         3789  +** Insert or replace a WhereLoop entry using the template supplied.
         3790  +**
         3791  +** An existing WhereLoop entry might be overwritten if the new template
         3792  +** is better and has fewer dependencies.  Or the template will be ignored
         3793  +** and no insert will occur if an existing WhereLoop is faster and has
         3794  +** fewer dependencies than the template.  Otherwise a new WhereLoop is
         3795  +** added based on the template.
         3796  +**
         3797  +** If pBuilder->pOrSet is not NULL then we care about only the
         3798  +** prerequisites and rRun and nOut costs of the N best loops.  That
         3799  +** information is gathered in the pBuilder->pOrSet object.  This special
         3800  +** processing mode is used only for OR clause processing.
         3801  +**
         3802  +** When accumulating multiple loops (when pBuilder->pOrSet is NULL) we
         3803  +** still might overwrite similar loops with the new template if the
         3804  +** template is better.  Loops may be overwritten if the following 
         3805  +** conditions are met:
         3806  +**
         3807  +**    (1)  They have the same iTab.
         3808  +**    (2)  They have the same iSortIdx.
         3809  +**    (3)  The template has same or fewer dependencies than the current loop
         3810  +**    (4)  The template has the same or lower cost than the current loop
         3811  +**    (5)  The template uses more terms of the same index but has no additional
         3812  +**         dependencies          
         3813  +*/
         3814  +static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){
         3815  +  WhereLoop **ppPrev, *p;
         3816  +  WhereInfo *pWInfo = pBuilder->pWInfo;
         3817  +  sqlite3 *db = pWInfo->pParse->db;
         3818  +
         3819  +  /* If pBuilder->pOrSet is defined, then only keep track of the costs
         3820  +  ** and prereqs.
         3821  +  */
         3822  +  if( pBuilder->pOrSet!=0 ){
         3823  +#if WHERETRACE_ENABLED
         3824  +    u16 n = pBuilder->pOrSet->n;
         3825  +    int x =
         3826  +#endif
         3827  +    whereOrInsert(pBuilder->pOrSet, pTemplate->prereq, pTemplate->rRun,
         3828  +                                    pTemplate->nOut);
         3829  +#if WHERETRACE_ENABLED /* 0x8 */
         3830  +    if( sqlite3WhereTrace & 0x8 ){
         3831  +      sqlite3DebugPrintf(x?"   or-%d:  ":"   or-X:  ", n);
         3832  +      whereLoopPrint(pTemplate, pBuilder->pWC);
         3833  +    }
         3834  +#endif
         3835  +    return SQLITE_OK;
         3836  +  }
         3837  +
         3838  +  /* Look for an existing WhereLoop to replace with pTemplate
         3839  +  */
         3840  +  ppPrev = whereLoopFindLesser(&pWInfo->pLoops, pTemplate);
         3841  +
         3842  +  if( ppPrev==0 ){
         3843  +    /* There already exists a WhereLoop on the list that is better
         3844  +    ** than pTemplate, so just ignore pTemplate */
         3845  +#if WHERETRACE_ENABLED /* 0x8 */
         3846  +    if( sqlite3WhereTrace & 0x8 ){
         3847  +      sqlite3DebugPrintf("ins-noop: ");
         3848  +      whereLoopPrint(pTemplate, pBuilder->pWC);
         3849  +    }
         3850  +#endif
         3851  +    return SQLITE_OK;  
         3852  +  }else{
         3853  +    p = *ppPrev;
  3822   3854     }
  3823   3855   
  3824   3856     /* If we reach this point it means that either p[] should be overwritten
  3825   3857     ** with pTemplate[] if p[] exists, or if p==NULL then allocate a new
  3826   3858     ** WhereLoop and insert it.
  3827   3859     */
  3828   3860   #if WHERETRACE_ENABLED /* 0x8 */
................................................................................
  3832   3864         whereLoopPrint(p, pBuilder->pWC);
  3833   3865       }
  3834   3866       sqlite3DebugPrintf("ins-new:  ");
  3835   3867       whereLoopPrint(pTemplate, pBuilder->pWC);
  3836   3868     }
  3837   3869   #endif
  3838   3870     if( p==0 ){
  3839         -    p = sqlite3DbMallocRaw(db, sizeof(WhereLoop));
         3871  +    /* Allocate a new WhereLoop to add to the end of the list */
         3872  +    *ppPrev = p = sqlite3DbMallocRaw(db, sizeof(WhereLoop));
  3840   3873       if( p==0 ) return SQLITE_NOMEM;
  3841   3874       whereLoopInit(p);
         3875  +    p->pNextLoop = 0;
         3876  +  }else{
         3877  +    /* We will be overwriting WhereLoop p[].  But before we do, first
         3878  +    ** go through the rest of the list and delete any other entries besides
         3879  +    ** p[] that are also supplated by pTemplate */
         3880  +    WhereLoop **ppTail = &p->pNextLoop;
         3881  +    WhereLoop *pToDel;
         3882  +    while( *ppTail ){
         3883  +      ppTail = whereLoopFindLesser(ppTail, pTemplate);
         3884  +      if( NEVER(ppTail==0) ) break;
         3885  +      pToDel = *ppTail;
         3886  +      if( pToDel==0 ) break;
         3887  +      *ppTail = pToDel->pNextLoop;
         3888  +#if WHERETRACE_ENABLED /* 0x8 */
         3889  +      if( sqlite3WhereTrace & 0x8 ){
         3890  +        sqlite3DebugPrintf("ins-del: ");
         3891  +        whereLoopPrint(pToDel, pBuilder->pWC);
         3892  +      }
         3893  +#endif
         3894  +      whereLoopDelete(db, pToDel);
         3895  +    }
  3842   3896     }
  3843   3897     whereLoopXfer(db, p, pTemplate);
  3844         -  p->pNextLoop = pNext;
  3845         -  *ppPrev = p;
  3846   3898     if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){
  3847   3899       Index *pIndex = p->u.btree.pIndex;
  3848   3900       if( pIndex && pIndex->tnum==0 ){
  3849   3901         p->u.btree.pIndex = 0;
  3850   3902       }
  3851   3903     }
  3852   3904     return SQLITE_OK;
  3853         -
  3854         -  /* Jump here if the insert is a no-op */
  3855         -whereLoopInsert_noop:
  3856         -#if WHERETRACE_ENABLED /* 0x8 */
  3857         -  if( sqlite3WhereTrace & 0x8 ){
  3858         -    sqlite3DebugPrintf("ins-noop: ");
  3859         -    whereLoopPrint(pTemplate, pBuilder->pWC);
  3860         -  }
  3861         -#endif
  3862         -  return SQLITE_OK;  
  3863   3905   }
  3864   3906   
  3865   3907   /*
  3866   3908   ** Adjust the WhereLoop.nOut value downward to account for terms of the
  3867   3909   ** WHERE clause that reference the loop but which are not used by an
  3868   3910   ** index.
  3869   3911   **