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 |
Timelines: | family | ancestors | descendants | both | query-plan-experiments |
Files: | files | file ages | folders |
SHA1: |
8f869ca7a6eaa9ca7a08102290e6c606 |
User & Date: | drh 2014-03-29 21:16:07.103 |
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: ea8b091004 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: 8f869ca7a6 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: 27deb6e49b user: drh tags: trunk) | |
Changes
Changes to src/where.c.
︙ | ︙ | |||
3708 3709 3710 3711 3712 3713 3714 | whereLoopDelete(db, p); } sqlite3DbFree(db, pWInfo); } } /* | | > | < < < | | < < < | < < < < < < | < < < > | | < < < < < < < < < < < < | < < < < < < < < | | < < | | 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 | whereLoopDelete(db, p); } sqlite3DbFree(db, pWInfo); } } /* ** Search the list of WhereLoops in *ppPrev looking for one that can be ** supplanted by pTemplate. ** ** Return NULL if the WhereLoop list contains an entry that can supplant ** pTemplate, in other words if pTemplate does not belong on the list. ** ** If pX is a WhereLoop that pTemplate can supplant, then return the ** link that points to pX. ** ** If pTemplate cannot supplant any existing element of the list but needs ** to be added to the list, then return a pointer to the tail of the list. */ static WhereLoop **whereLoopFindLesser( WhereLoop **ppPrev, const WhereLoop *pTemplate ){ WhereLoop *p; for(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 |
︙ | ︙ | |||
3795 3796 3797 3798 3799 3800 3801 | && p->nLTerm<pTemplate->nLTerm && (p->wsFlags & pTemplate->wsFlags & WHERE_INDEXED)!=0 && (p->u.btree.pIndex==pTemplate->u.btree.pIndex || pTemplate->rRun+p->nLTerm<=p->rRun+pTemplate->nLTerm) ){ /* Overwrite an existing WhereLoop with an similar one that uses ** more terms of the index */ | < | | < < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | > > > > > > > > > > > > > > > > > | > > > > < < < < < < < < < < < < | 3760 3761 3762 3763 3764 3765 3766 3767 3768 3769 3770 3771 3772 3773 3774 3775 3776 3777 3778 3779 3780 3781 3782 3783 3784 3785 3786 3787 3788 3789 3790 3791 3792 3793 3794 3795 3796 3797 3798 3799 3800 3801 3802 3803 3804 3805 3806 3807 3808 3809 3810 3811 3812 3813 3814 3815 3816 3817 3818 3819 3820 3821 3822 3823 3824 3825 3826 3827 3828 3829 3830 3831 3832 3833 3834 3835 3836 3837 3838 3839 3840 3841 3842 3843 3844 3845 3846 3847 3848 3849 3850 3851 3852 3853 3854 3855 3856 3857 3858 3859 3860 3861 3862 3863 3864 3865 3866 3867 3868 3869 3870 3871 3872 3873 3874 3875 3876 3877 3878 3879 3880 3881 3882 3883 3884 3885 3886 3887 3888 3889 3890 3891 3892 3893 3894 3895 3896 3897 3898 3899 3900 3901 3902 3903 3904 3905 3906 3907 3908 3909 3910 3911 | && p->nLTerm<pTemplate->nLTerm && (p->wsFlags & pTemplate->wsFlags & WHERE_INDEXED)!=0 && (p->u.btree.pIndex==pTemplate->u.btree.pIndex || pTemplate->rRun+p->nLTerm<=p->rRun+pTemplate->nLTerm) ){ /* Overwrite an existing WhereLoop with an similar one that uses ** more terms of the index */ break; }else{ /* There is an existing WhereLoop that is better than pTemplate */ return 0; } } if( (p->prereq & pTemplate->prereq)==pTemplate->prereq && p->rRun>=pTemplate->rRun && p->nOut>=pTemplate->nOut ){ /* Overwrite an existing WhereLoop with a better one: one that is ** better at one of (1) dependencies, (2) setup-cost, (3) run-cost ** or (4) number of output rows, and is no worse in any of those ** categories. */ assert( p->rSetup>=pTemplate->rSetup ); /* SETUP-INVARIANT above */ break; } } return ppPrev; } /* ** Insert or replace a WhereLoop entry using the template supplied. ** ** An existing WhereLoop entry might be overwritten if the new template ** is better and has fewer dependencies. Or the template will be ignored ** and no insert will occur if an existing WhereLoop is faster and has ** fewer dependencies than the template. Otherwise a new WhereLoop is ** added based on the template. ** ** If pBuilder->pOrSet is not NULL then we care about only the ** prerequisites and rRun and nOut costs of the N best loops. That ** information is gathered in the pBuilder->pOrSet object. This special ** processing mode is used only for OR clause processing. ** ** When accumulating multiple loops (when pBuilder->pOrSet is NULL) we ** still might overwrite similar loops with the new template if the ** template is better. Loops may be overwritten if the following ** conditions are met: ** ** (1) They have the same iTab. ** (2) They have the same iSortIdx. ** (3) The template has same or fewer dependencies than the current loop ** (4) The template has the same or lower cost than the current loop ** (5) The template uses more terms of the same index but has no additional ** dependencies */ static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){ WhereLoop **ppPrev, *p; WhereInfo *pWInfo = pBuilder->pWInfo; sqlite3 *db = pWInfo->pParse->db; /* If pBuilder->pOrSet is defined, then only keep track of the costs ** and prereqs. */ if( pBuilder->pOrSet!=0 ){ #if WHERETRACE_ENABLED u16 n = pBuilder->pOrSet->n; int x = #endif whereOrInsert(pBuilder->pOrSet, pTemplate->prereq, pTemplate->rRun, pTemplate->nOut); #if WHERETRACE_ENABLED /* 0x8 */ if( sqlite3WhereTrace & 0x8 ){ sqlite3DebugPrintf(x?" or-%d: ":" or-X: ", n); whereLoopPrint(pTemplate, pBuilder->pWC); } #endif return SQLITE_OK; } /* Look for an existing WhereLoop to replace with pTemplate */ ppPrev = whereLoopFindLesser(&pWInfo->pLoops, pTemplate); if( ppPrev==0 ){ /* There already exists a WhereLoop on the list that is better ** than pTemplate, so just ignore pTemplate */ #if WHERETRACE_ENABLED /* 0x8 */ if( sqlite3WhereTrace & 0x8 ){ sqlite3DebugPrintf("ins-noop: "); whereLoopPrint(pTemplate, pBuilder->pWC); } #endif return SQLITE_OK; }else{ p = *ppPrev; } /* 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 /* 0x8 */ if( sqlite3WhereTrace & 0x8 ){ if( p!=0 ){ sqlite3DebugPrintf("ins-del: "); whereLoopPrint(p, pBuilder->pWC); } sqlite3DebugPrintf("ins-new: "); whereLoopPrint(pTemplate, pBuilder->pWC); } #endif if( p==0 ){ /* Allocate a new WhereLoop to add to the end of the list */ *ppPrev = p = sqlite3DbMallocRaw(db, sizeof(WhereLoop)); if( p==0 ) return SQLITE_NOMEM; whereLoopInit(p); p->pNextLoop = 0; }else{ /* We will be overwriting WhereLoop p[]. But before we do, first ** go through the rest of the list and delete any other entries besides ** p[] that are also supplated by pTemplate */ WhereLoop **ppTail = &p->pNextLoop; WhereLoop *pToDel; while( *ppTail ){ ppTail = whereLoopFindLesser(ppTail, pTemplate); if( NEVER(ppTail==0) ) break; pToDel = *ppTail; if( pToDel==0 ) break; *ppTail = pToDel->pNextLoop; #if WHERETRACE_ENABLED /* 0x8 */ if( sqlite3WhereTrace & 0x8 ){ sqlite3DebugPrintf("ins-del: "); whereLoopPrint(pToDel, pBuilder->pWC); } #endif whereLoopDelete(db, pToDel); } } whereLoopXfer(db, p, pTemplate); if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){ Index *pIndex = p->u.btree.pIndex; if( pIndex && pIndex->tnum==0 ){ p->u.btree.pIndex = 0; } } return SQLITE_OK; } /* ** Adjust the WhereLoop.nOut value downward to account for terms of the ** WHERE clause that reference the loop but which are not used by an ** index. ** |
︙ | ︙ |