/ Check-in [ea8b0910]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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

Overview
Comment: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.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | query-plan-experiments
Files: files | file ages | folders
SHA1: ea8b0910040198751551b0b960e6b783913607df
User & Date: drh 2014-03-31 18:24:18
Context
2014-03-31
19:49
Also make sure an index that is a proper subset of some other index has a higher cost than that other index. Add test cases. check-in: b7830d23 user: drh tags: query-plan-experiments
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
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/where.c.

  3706   3706         WhereLoop *p = pWInfo->pLoops;
  3707   3707         pWInfo->pLoops = p->pNextLoop;
  3708   3708         whereLoopDelete(db, p);
  3709   3709       }
  3710   3710       sqlite3DbFree(db, pWInfo);
  3711   3711     }
  3712   3712   }
         3713  +
         3714  +/*
         3715  +** Compare every WhereLoop X on the list p against pTemplate.  If:
         3716  +**
         3717  +**    (1) both X and pTemplate refer to the same table, and
         3718  +**    (2) both X and pTemplate use a single index, and
         3719  +**    (3) pTemplate uses all the same WHERE clause terms as X plus
         3720  +**        at least one more term,
         3721  +**
         3722  +** then make sure the cost pTemplate is less than the cost of X, adjusting
         3723  +** the cost of pTemplate downward if necessary.
         3724  +**
         3725  +** Example: When computing the query plan for the SELECT below:
         3726  +**
         3727  +**     CREATE TABLE t1(a,b,c,d);
         3728  +**     CREATE INDEX t1abc ON t1(a,b,c);
         3729  +**     CREATE INDEX t1bc ON t1(b,c);
         3730  +**     SELECT d FROM t1 WHERE a=? AND b=? AND c>=? ORDER BY c;
         3731  +** 
         3732  +** Make sure the cost of using three three columns of index t1abc is less
         3733  +** than the cost of using both columns of t1bc.
         3734  +*/
         3735  +static void whereLoopAdjustCost(const WhereLoop *p, WhereLoop *pTemplate){
         3736  +  if( (pTemplate->wsFlags & WHERE_INDEXED)==0 ) return;
         3737  +  if( pTemplate->nLTerm==0 ) return;
         3738  +  for(; p; p=p->pNextLoop){
         3739  +    if( p->iTab==pTemplate->iTab
         3740  +     && (p->wsFlags & WHERE_INDEXED)!=0
         3741  +     && p->nLTerm<pTemplate->nLTerm
         3742  +     && (p->rRun<pTemplate->rRun || (p->rRun==pTemplate->rRun &&
         3743  +                                     p->nOut<=pTemplate->nOut))
         3744  +    ){
         3745  +      int i, j;
         3746  +      for(j=0, i=p->nLTerm-1; i>=0 && j>=0; i--){
         3747  +        for(j=pTemplate->nLTerm-1; j>=0; j--){
         3748  +          if( pTemplate->aLTerm[j]==p->aLTerm[i] ) break;
         3749  +        }
         3750  +      }
         3751  +      if( j>=0 ){
         3752  +        pTemplate->rRun = p->rRun;
         3753  +        pTemplate->nOut = p->nOut - 1;
         3754  +      }
         3755  +    }
         3756  +  }
         3757  +}
  3713   3758   
  3714   3759   /*
  3715   3760   ** Search the list of WhereLoops in *ppPrev looking for one that can be
  3716   3761   ** supplanted by pTemplate.
  3717   3762   **
  3718   3763   ** Return NULL if the WhereLoop list contains an entry that can supplant
  3719   3764   ** pTemplate, in other words if pTemplate does not belong on the list.
................................................................................
  3743   3788                    || p->rSetup==pTemplate->rSetup );
  3744   3789   
  3745   3790       /* whereLoopAddBtree() always generates and inserts the automatic index
  3746   3791       ** case first.  Hence compatible candidate WhereLoops never have a larger
  3747   3792       ** rSetup. Call this SETUP-INVARIANT */
  3748   3793       assert( p->rSetup>=pTemplate->rSetup );
  3749   3794   
  3750         -    if( (p->prereq & pTemplate->prereq)==p->prereq
  3751         -     && p->rSetup<=pTemplate->rSetup
  3752         -     && p->rRun<=pTemplate->rRun
  3753         -     && p->nOut<=pTemplate->nOut
         3795  +    /* If existing WhereLoop p is better than pTemplate, pTemplate can be
         3796  +    ** discarded.  WhereLoop p is better if:
         3797  +    **   (1)  p has no more dependencies than pTemplate, and
         3798  +    **   (2)  p has an equal or lower cost than pTemplate
         3799  +    */
         3800  +    if( (p->prereq & pTemplate->prereq)==p->prereq    /* (1)  */
         3801  +     && p->rSetup<=pTemplate->rSetup                  /* (2a) */
         3802  +     && p->rRun<=pTemplate->rRun                      /* (2b) */
         3803  +     && p->nOut<=pTemplate->nOut                      /* (2c) */
  3754   3804       ){
  3755         -      /* This branch taken when p is equal or better than pTemplate in 
  3756         -      ** all of (1) dependencies (2) setup-cost, (3) run-cost, and
  3757         -      ** (4) number of output rows. */
  3758         -      assert( p->rSetup==pTemplate->rSetup );
  3759         -      if( p->prereq==pTemplate->prereq
  3760         -       && p->nLTerm<pTemplate->nLTerm
  3761         -       && (p->wsFlags & pTemplate->wsFlags & WHERE_INDEXED)!=0
  3762         -       && (p->u.btree.pIndex==pTemplate->u.btree.pIndex
  3763         -          || pTemplate->rRun+p->nLTerm<=p->rRun+pTemplate->nLTerm)
  3764         -      ){
  3765         -        /* Overwrite an existing WhereLoop with an similar one that uses
  3766         -        ** more terms of the index */
  3767         -        break;
  3768         -      }else{
  3769         -        /* There is an existing WhereLoop that is better than pTemplate */
  3770         -        return 0;
  3771         -      }
         3805  +      return 0;  /* Discard pTemplate */
  3772   3806       }
  3773         -    if( (p->prereq & pTemplate->prereq)==pTemplate->prereq
  3774         -     && p->rRun>=pTemplate->rRun
  3775         -     && p->nOut>=pTemplate->nOut
         3807  +
         3808  +    /* If pTemplate is always better than p, then cause p to be overwritten
         3809  +    ** with pTemplate.  pTemplate is better than p if:
         3810  +    **   (1)  pTemplate has no more dependences than p, and
         3811  +    **   (2)  pTemplate has an equal or lower cost than p.
         3812  +    */
         3813  +    if( (p->prereq & pTemplate->prereq)==pTemplate->prereq   /* (1)  */
         3814  +     && p->rRun>=pTemplate->rRun                             /* (2a) */
         3815  +     && p->nOut>=pTemplate->nOut                             /* (2b) */
  3776   3816       ){
  3777         -      /* Overwrite an existing WhereLoop with a better one: one that is
  3778         -      ** better at one of (1) dependencies, (2) setup-cost, (3) run-cost
  3779         -      ** or (4) number of output rows, and is no worse in any of those
  3780         -      ** categories. */
  3781   3817         assert( p->rSetup>=pTemplate->rSetup ); /* SETUP-INVARIANT above */
  3782         -      break;
         3818  +      break;   /* Cause p to be overwritten by pTemplate */
  3783   3819       }
  3784   3820     }
  3785   3821     return ppPrev;
  3786   3822   }
  3787   3823   
  3788   3824   /*
  3789   3825   ** Insert or replace a WhereLoop entry using the template supplied.
................................................................................
  3797   3833   ** If pBuilder->pOrSet is not NULL then we care about only the
  3798   3834   ** prerequisites and rRun and nOut costs of the N best loops.  That
  3799   3835   ** information is gathered in the pBuilder->pOrSet object.  This special
  3800   3836   ** processing mode is used only for OR clause processing.
  3801   3837   **
  3802   3838   ** When accumulating multiple loops (when pBuilder->pOrSet is NULL) we
  3803   3839   ** still might overwrite similar loops with the new template if the
  3804         -** template is better.  Loops may be overwritten if the following 
         3840  +** new template is better.  Loops may be overwritten if the following 
  3805   3841   ** conditions are met:
  3806   3842   **
  3807   3843   **    (1)  They have the same iTab.
  3808   3844   **    (2)  They have the same iSortIdx.
  3809   3845   **    (3)  The template has same or fewer dependencies than the current loop
  3810   3846   **    (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   3847   */
  3814   3848   static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){
  3815   3849     WhereLoop **ppPrev, *p;
  3816   3850     WhereInfo *pWInfo = pBuilder->pWInfo;
  3817   3851     sqlite3 *db = pWInfo->pParse->db;
  3818   3852   
  3819   3853     /* If pBuilder->pOrSet is defined, then only keep track of the costs
................................................................................
  3833   3867       }
  3834   3868   #endif
  3835   3869       return SQLITE_OK;
  3836   3870     }
  3837   3871   
  3838   3872     /* Look for an existing WhereLoop to replace with pTemplate
  3839   3873     */
         3874  +  whereLoopAdjustCost(pWInfo->pLoops, pTemplate);
  3840   3875     ppPrev = whereLoopFindLesser(&pWInfo->pLoops, pTemplate);
  3841   3876   
  3842   3877     if( ppPrev==0 ){
  3843   3878       /* There already exists a WhereLoop on the list that is better
  3844   3879       ** than pTemplate, so just ignore pTemplate */
  3845   3880   #if WHERETRACE_ENABLED /* 0x8 */
  3846   3881       if( sqlite3WhereTrace & 0x8 ){