Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Refactor the ORDER BY optimizer in the NGQP so that it is easier to maintain and so that it can support optimizing out GROUP BY and DISTINCT clauses. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | nextgen-query-plan-exp |
Files: | files | file ages | folders |
SHA1: |
e605c468e3a1163167831c4a6220825c |
User & Date: | drh 2013-06-04 12:42:29.293 |
Context
2013-06-04
| ||
12:58 | Fix a display issue with EXPLAIN QUERY PLAN. (check-in: ff2fa40755 user: drh tags: nextgen-query-plan-exp) | |
12:42 | Refactor the ORDER BY optimizer in the NGQP so that it is easier to maintain and so that it can support optimizing out GROUP BY and DISTINCT clauses. (check-in: e605c468e3 user: drh tags: nextgen-query-plan-exp) | |
2013-06-03
| ||
22:08 | Remove more vestiges of sqlite_query_plan from the test cases. (check-in: eb27086e8a user: drh tags: nextgen-query-plan-exp) | |
Changes
Changes to src/build.c.
︙ | ︙ | |||
2691 2692 2693 2694 2695 2696 2697 2698 2699 2700 2701 2702 2703 2704 | pIndex->aSortOrder = (u8 *)(&pIndex->aiColumn[nCol]); pIndex->zName = (char *)(&pIndex->aSortOrder[nCol]); zExtra = (char *)(&pIndex->zName[nName+1]); memcpy(pIndex->zName, zName, nName+1); pIndex->pTable = pTab; pIndex->nColumn = pList->nExpr; pIndex->onError = (u8)onError; pIndex->autoIndex = (u8)(pName==0); pIndex->pSchema = db->aDb[iDb].pSchema; assert( sqlite3SchemaMutexHeld(db, iDb, 0) ); /* Check to see if we should honor DESC requests on index columns */ if( pDb->pSchema->file_format>=4 ){ | > | 2691 2692 2693 2694 2695 2696 2697 2698 2699 2700 2701 2702 2703 2704 2705 | pIndex->aSortOrder = (u8 *)(&pIndex->aiColumn[nCol]); pIndex->zName = (char *)(&pIndex->aSortOrder[nCol]); zExtra = (char *)(&pIndex->zName[nName+1]); memcpy(pIndex->zName, zName, nName+1); pIndex->pTable = pTab; pIndex->nColumn = pList->nExpr; pIndex->onError = (u8)onError; pIndex->uniqNotNull = onError==OE_Abort; pIndex->autoIndex = (u8)(pName==0); pIndex->pSchema = db->aDb[iDb].pSchema; assert( sqlite3SchemaMutexHeld(db, iDb, 0) ); /* Check to see if we should honor DESC requests on index columns */ if( pDb->pSchema->file_format>=4 ){ |
︙ | ︙ | |||
2749 2750 2751 2752 2753 2754 2755 2756 2757 2758 2759 2760 2761 2762 | } if( !db->init.busy && !sqlite3LocateCollSeq(pParse, zColl) ){ goto exit_create_index; } pIndex->azColl[i] = zColl; requestedSortOrder = pListItem->sortOrder & sortOrderMask; pIndex->aSortOrder[i] = (u8)requestedSortOrder; } sqlite3DefaultRowEst(pIndex); if( pTab==pParse->pNewTable ){ /* This routine has been called to create an automatic index as a ** result of a PRIMARY KEY or UNIQUE clause on a column definition, or ** a PRIMARY KEY or UNIQUE clause following the column definitions. | > | 2750 2751 2752 2753 2754 2755 2756 2757 2758 2759 2760 2761 2762 2763 2764 | } if( !db->init.busy && !sqlite3LocateCollSeq(pParse, zColl) ){ goto exit_create_index; } pIndex->azColl[i] = zColl; requestedSortOrder = pListItem->sortOrder & sortOrderMask; pIndex->aSortOrder[i] = (u8)requestedSortOrder; if( pTab->aCol[j].notNull==0 ) pIndex->uniqNotNull = 0; } sqlite3DefaultRowEst(pIndex); if( pTab==pParse->pNewTable ){ /* This routine has been called to create an automatic index as a ** result of a PRIMARY KEY or UNIQUE clause on a column definition, or ** a PRIMARY KEY or UNIQUE clause following the column definitions. |
︙ | ︙ |
Changes to src/sqliteInt.h.
︙ | ︙ | |||
1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 | u8 *aSortOrder; /* for each column: True==DESC, False==ASC */ char **azColl; /* Array of collation sequence names for index */ int tnum; /* DB Page containing root of this index */ u16 nColumn; /* Number of columns in table used by this index */ u8 onError; /* OE_Abort, OE_Ignore, OE_Replace, or OE_None */ unsigned autoIndex:2; /* 1==UNIQUE, 2==PRIMARY KEY, 0==CREATE INDEX */ unsigned bUnordered:1; /* Use this index for == or IN queries only */ #ifdef SQLITE_ENABLE_STAT3 int nSample; /* Number of elements in aSample[] */ tRowcnt avgEq; /* Average nEq value for key values not in aSample */ IndexSample *aSample; /* Samples of the left-most key */ #endif }; | > | 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 | u8 *aSortOrder; /* for each column: True==DESC, False==ASC */ char **azColl; /* Array of collation sequence names for index */ int tnum; /* DB Page containing root of this index */ u16 nColumn; /* Number of columns in table used by this index */ u8 onError; /* OE_Abort, OE_Ignore, OE_Replace, or OE_None */ unsigned autoIndex:2; /* 1==UNIQUE, 2==PRIMARY KEY, 0==CREATE INDEX */ unsigned bUnordered:1; /* Use this index for == or IN queries only */ unsigned uniqNotNull:1; /* True if UNIQUE and NOT NULL for all columns */ #ifdef SQLITE_ENABLE_STAT3 int nSample; /* Number of elements in aSample[] */ tRowcnt avgEq; /* Average nEq value for key values not in aSample */ IndexSample *aSample; /* Samples of the left-most key */ #endif }; |
︙ | ︙ | |||
1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 | typedef u64 Bitmask; /* ** The number of bits in a Bitmask. "BMS" means "BitMask Size". */ #define BMS ((int)(sizeof(Bitmask)*8)) /* ** The following structure describes the FROM clause of a SELECT statement. ** Each table or subquery in the FROM clause is a separate element of ** the SrcList.a[] array. ** ** With the addition of multiple database support, the following structure ** can also be used to describe a particular table such as the table that | > > > > > | 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 | typedef u64 Bitmask; /* ** The number of bits in a Bitmask. "BMS" means "BitMask Size". */ #define BMS ((int)(sizeof(Bitmask)*8)) /* ** A bit in a Bitmask */ #define MASKBIT(n) (((Bitmask)1)<<(n)) /* ** The following structure describes the FROM clause of a SELECT statement. ** Each table or subquery in the FROM clause is a separate element of ** the SrcList.a[] array. ** ** With the addition of multiple database support, the following structure ** can also be used to describe a particular table such as the table that |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
323 324 325 326 327 328 329 | #define WHERE_BTM_LIMIT 0x00000020 /* x>EXPR or x>=EXPR constraint */ #define WHERE_BOTH_LIMIT 0x00000030 /* Both x>EXPR and x<EXPR */ #define WHERE_IDX_ONLY 0x00000040 /* Use index only - omit table */ #define WHERE_IPK 0x00000100 /* x is the INTEGER PRIMARY KEY */ #define WHERE_INDEXED 0x00000200 /* WhereLoop.u.btree.pIndex is valid */ #define WHERE_VIRTUALTABLE 0x00000400 /* WhereLoop.u.vtab is valid */ #define WHERE_IN_ABLE 0x00000800 /* Able to support an IN operator */ | | | 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 | #define WHERE_BTM_LIMIT 0x00000020 /* x>EXPR or x>=EXPR constraint */ #define WHERE_BOTH_LIMIT 0x00000030 /* Both x>EXPR and x<EXPR */ #define WHERE_IDX_ONLY 0x00000040 /* Use index only - omit table */ #define WHERE_IPK 0x00000100 /* x is the INTEGER PRIMARY KEY */ #define WHERE_INDEXED 0x00000200 /* WhereLoop.u.btree.pIndex is valid */ #define WHERE_VIRTUALTABLE 0x00000400 /* WhereLoop.u.vtab is valid */ #define WHERE_IN_ABLE 0x00000800 /* Able to support an IN operator */ #define WHERE_ONEROW 0x00001000 /* Selects no more than one row */ #define WHERE_MULTI_OR 0x00002000 /* OR using multiple indices */ #define WHERE_TEMP_INDEX 0x00004000 /* Uses an ephemeral index */ #define WHERE_COVER_SCAN 0x00008000 /* Full scan of a covering index */ /* ** Initialize a preallocated WhereClause structure. */ |
︙ | ︙ | |||
478 479 480 481 482 483 484 | ** iCursor is not in the set. */ static Bitmask getMask(WhereMaskSet *pMaskSet, int iCursor){ int i; assert( pMaskSet->n<=(int)sizeof(Bitmask)*8 ); for(i=0; i<pMaskSet->n; i++){ if( pMaskSet->ix[i]==iCursor ){ | | | 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 | ** iCursor is not in the set. */ static Bitmask getMask(WhereMaskSet *pMaskSet, int iCursor){ int i; assert( pMaskSet->n<=(int)sizeof(Bitmask)*8 ); for(i=0; i<pMaskSet->n; i++){ if( pMaskSet->ix[i]==iCursor ){ return MASKBIT(i); } } return 0; } /* ** Create a new mask for cursor iCursor. |
︙ | ︙ | |||
1834 1835 1836 1837 1838 1839 1840 | idxCols = 0; pLoop->aTerm = sqlite3DbRealloc(pParse->db, pLoop->aTerm, mxConstraint*sizeof(pLoop->aTerm[0])); if( pLoop->aTerm==0 ) return; for(pTerm=pWC->a; pTerm<pWCEnd && pLoop->nTerm<mxConstraint; pTerm++){ if( termCanDriveIndex(pTerm, pSrc, notReady) ){ int iCol = pTerm->u.leftColumn; | | | 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 | idxCols = 0; pLoop->aTerm = sqlite3DbRealloc(pParse->db, pLoop->aTerm, mxConstraint*sizeof(pLoop->aTerm[0])); if( pLoop->aTerm==0 ) return; for(pTerm=pWC->a; pTerm<pWCEnd && pLoop->nTerm<mxConstraint; pTerm++){ if( termCanDriveIndex(pTerm, pSrc, notReady) ){ int iCol = pTerm->u.leftColumn; Bitmask cMask = iCol>=BMS ? MASKBIT(BMS-1) : MASKBIT(iCol); testcase( iCol==BMS ); testcase( iCol==BMS-1 ); if( (idxCols & cMask)==0 ){ pLoop->aTerm[nColumn++] = pTerm; idxCols |= cMask; } } |
︙ | ︙ | |||
1856 1857 1858 1859 1860 1861 1862 | ** covering index. A "covering index" is an index that contains all ** columns that are needed by the query. With a covering index, the ** original table never needs to be accessed. Automatic indices must ** be a covering index because the index will not be updated if the ** original table changes and the index and table cannot both be used ** if they go out of sync. */ | | | | | 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 | ** covering index. A "covering index" is an index that contains all ** columns that are needed by the query. With a covering index, the ** original table never needs to be accessed. Automatic indices must ** be a covering index because the index will not be updated if the ** original table changes and the index and table cannot both be used ** if they go out of sync. */ extraCols = pSrc->colUsed & (~idxCols | MASKBIT(BMS-1)); mxBitCol = (pTable->nCol >= BMS-1) ? BMS-1 : pTable->nCol; testcase( pTable->nCol==BMS-1 ); testcase( pTable->nCol==BMS-2 ); for(i=0; i<mxBitCol; i++){ if( extraCols & MASKBIT(i) ) nColumn++; } if( pSrc->colUsed & MASKBIT(BMS-1) ){ nColumn += pTable->nCol - BMS + 1; } pLoop->wsFlags |= WHERE_COLUMN_EQ | WHERE_IDX_ONLY; /* Construct the Index object to describe this index */ nByte = sizeof(Index); nByte += nColumn*sizeof(int); /* Index.aiColumn */ |
︙ | ︙ | |||
1887 1888 1889 1890 1891 1892 1893 | pIdx->nColumn = nColumn; pIdx->pTable = pTable; n = 0; idxCols = 0; for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){ if( termCanDriveIndex(pTerm, pSrc, notReady) ){ int iCol = pTerm->u.leftColumn; | | | | | 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 | pIdx->nColumn = nColumn; pIdx->pTable = pTable; n = 0; idxCols = 0; for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){ if( termCanDriveIndex(pTerm, pSrc, notReady) ){ int iCol = pTerm->u.leftColumn; Bitmask cMask = iCol>=BMS ? MASKBIT(BMS-1) : MASKBIT(iCol); if( (idxCols & cMask)==0 ){ Expr *pX = pTerm->pExpr; idxCols |= cMask; pIdx->aiColumn[n] = pTerm->u.leftColumn; pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight); pIdx->azColl[n] = ALWAYS(pColl) ? pColl->zName : "BINARY"; n++; } } } assert( (u32)n==pLoop->u.btree.nEq ); /* Add additional columns needed to make the automatic index into ** a covering index */ for(i=0; i<mxBitCol; i++){ if( extraCols & MASKBIT(i) ){ pIdx->aiColumn[n] = i; pIdx->azColl[n] = "BINARY"; n++; } } if( pSrc->colUsed & MASKBIT(BMS-1) ){ for(i=BMS-1; i<pTable->nCol; i++){ pIdx->aiColumn[n] = i; pIdx->azColl[n] = "BINARY"; n++; } } assert( n==nColumn ); |
︙ | ︙ | |||
3386 3387 3388 3389 3390 3391 3392 | sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg); sqlite3VdbeAddOp2(v, OP_Seek, iCur, iRowidReg); /* Deferred seek */ } /* Record the instruction used to terminate the loop. Disable ** WHERE clause terms made redundant by the index range scan. */ | | | 3386 3387 3388 3389 3390 3391 3392 3393 3394 3395 3396 3397 3398 3399 3400 | sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg); sqlite3VdbeAddOp2(v, OP_Seek, iCur, iRowidReg); /* Deferred seek */ } /* Record the instruction used to terminate the loop. Disable ** WHERE clause terms made redundant by the index range scan. */ if( pLoop->wsFlags & WHERE_ONEROW ){ pLevel->op = OP_Noop; }else if( bRev ){ pLevel->op = OP_Prev; }else{ pLevel->op = OP_Next; } pLevel->p1 = iIdxCur; |
︙ | ︙ | |||
4000 4001 4002 4003 4004 4005 4006 4007 4008 4009 4010 4011 4012 4013 4014 4015 4016 4017 4018 4019 4020 | if( pTerm->prereqRight & pNew->maskSelf ) continue; pNew->wsFlags = savedLoop.wsFlags; pNew->u.btree.nEq = savedLoop.u.btree.nEq; pNew->nTerm = savedLoop.nTerm; if( pNew->nTerm>=pBuilder->mxTerm ) break; /* Repeated column in index */ pNew->aTerm[pNew->nTerm++] = pTerm; pNew->prereq = (savedLoop.prereq | pTerm->prereqRight) & ~pNew->maskSelf; if( pTerm->eOperator & WO_IN ){ Expr *pExpr = pTerm->pExpr; pNew->wsFlags |= WHERE_COLUMN_IN; if( ExprHasProperty(pExpr, EP_xIsSelect) ){ /* "x IN (SELECT ...)": Assume the SELECT returns 25 rows */ nIn = 25; }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){ /* "x IN (value, value, ...)" */ nIn = pExpr->x.pList->nExpr; } pNew->u.btree.nEq++; pNew->nOut = (double)iRowEst * nInMul * nIn; }else if( pTerm->eOperator & (WO_EQ) ){ pNew->wsFlags |= WHERE_COLUMN_EQ; | > > > > | > | > | < | 4000 4001 4002 4003 4004 4005 4006 4007 4008 4009 4010 4011 4012 4013 4014 4015 4016 4017 4018 4019 4020 4021 4022 4023 4024 4025 4026 4027 4028 4029 4030 4031 4032 4033 4034 4035 4036 4037 4038 4039 4040 4041 4042 4043 4044 4045 4046 4047 4048 4049 4050 4051 4052 4053 4054 4055 | if( pTerm->prereqRight & pNew->maskSelf ) continue; pNew->wsFlags = savedLoop.wsFlags; pNew->u.btree.nEq = savedLoop.u.btree.nEq; pNew->nTerm = savedLoop.nTerm; if( pNew->nTerm>=pBuilder->mxTerm ) break; /* Repeated column in index */ pNew->aTerm[pNew->nTerm++] = pTerm; pNew->prereq = (savedLoop.prereq | pTerm->prereqRight) & ~pNew->maskSelf; pNew->rRun = rLogSize; if( pTerm->eOperator & WO_IN ){ Expr *pExpr = pTerm->pExpr; pNew->wsFlags |= WHERE_COLUMN_IN; if( ExprHasProperty(pExpr, EP_xIsSelect) ){ /* "x IN (SELECT ...)": Assume the SELECT returns 25 rows */ nIn = 25; }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){ /* "x IN (value, value, ...)" */ nIn = pExpr->x.pList->nExpr; } pNew->rRun *= nIn; pNew->u.btree.nEq++; pNew->nOut = (double)iRowEst * nInMul * nIn; }else if( pTerm->eOperator & (WO_EQ) ){ assert( (pNew->wsFlags & (WHERE_COLUMN_NULL|WHERE_COLUMN_IN))!=0 || nInMul==1 ); pNew->wsFlags |= WHERE_COLUMN_EQ; if( iCol<0 || (pProbe->onError==OE_Abort && nInMul==1 && pNew->u.btree.nEq==pProbe->nColumn-1) ){ testcase( pNew->wsFlags & WHERE_COLUMN_IN ); pNew->wsFlags |= WHERE_ONEROW; } pNew->u.btree.nEq++; pNew->nOut = (double)iRowEst * nInMul; }else if( pTerm->eOperator & (WO_ISNULL) ){ pNew->wsFlags |= WHERE_COLUMN_NULL; pNew->u.btree.nEq++; nIn = 2; /* Assume IS NULL matches two rows */ pNew->nOut = (double)iRowEst * nInMul * nIn; }else if( pTerm->eOperator & (WO_GT|WO_GE) ){ pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_BTM_LIMIT; pBtm = pTerm; pTop = 0; }else if( pTerm->eOperator & (WO_LT|WO_LE) ){ pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_TOP_LIMIT; pTop = pTerm; pBtm = (pNew->wsFlags & WHERE_BTM_LIMIT)!=0 ? pNew->aTerm[pNew->nTerm-2] : 0; } if( pNew->wsFlags & WHERE_COLUMN_RANGE ){ /* Adjust nOut and rRun for STAT3 range values */ double rDiv; whereRangeScanEst(pBuilder->pParse, pProbe, pNew->u.btree.nEq, pBtm, pTop, &rDiv); pNew->nOut = savedLoop.nOut/rDiv; } |
︙ | ︙ | |||
4214 4215 4216 4217 4218 4219 4220 | if( rc ) break; }else{ Bitmask m = pSrc->colUsed; int j; for(j=pProbe->nColumn-1; j>=0; j--){ int x = pProbe->aiColumn[j]; if( x<BMS-1 ){ | | | 4219 4220 4221 4222 4223 4224 4225 4226 4227 4228 4229 4230 4231 4232 4233 | if( rc ) break; }else{ Bitmask m = pSrc->colUsed; int j; for(j=pProbe->nColumn-1; j>=0; j--){ int x = pProbe->aiColumn[j]; if( x<BMS-1 ){ m &= ~MASKBIT(x); } } pNew->wsFlags = (m==0) ? (WHERE_IDX_ONLY|WHERE_INDEXED) : WHERE_INDEXED; /* Full scan via index */ if( (m==0 || b) && pProbe->bUnordered==0 |
︙ | ︙ | |||
4525 4526 4527 4528 4529 4530 4531 | whereLoopAddAll_end: whereLoopDelete(db, pBuilder->pNew); pBuilder->pNew = 0; return rc; } /* | | | | < < | | > | < | | | | > | | | | > > > > | | > | | | | > | < | | | | < < < < | < < | > > < < < | | < < < | | > > | < < < < < < < < < < < < < < < < < < < < < > > | | > > > | > | > > > > > > > > > > | | | > > > > > > > > > > | > > > > > > > > > > > > > > > > | | | | | | | | | | | > > > | > | > | | > > > > > > > > > > > > | | | | < | > > | | | < < < | < < > > | | | > > > | | | > > > > > | | > > | > > | > | > > > > | > > > > > > | 4530 4531 4532 4533 4534 4535 4536 4537 4538 4539 4540 4541 4542 4543 4544 4545 4546 4547 4548 4549 4550 4551 4552 4553 4554 4555 4556 4557 4558 4559 4560 4561 4562 4563 4564 4565 4566 4567 4568 4569 4570 4571 4572 4573 4574 4575 4576 4577 4578 4579 4580 4581 4582 4583 4584 4585 4586 4587 4588 4589 4590 4591 4592 4593 4594 4595 4596 4597 4598 4599 4600 4601 4602 4603 4604 4605 4606 4607 4608 4609 4610 4611 4612 4613 4614 4615 4616 4617 4618 4619 4620 4621 4622 4623 4624 4625 4626 4627 4628 4629 4630 4631 4632 4633 4634 4635 4636 4637 4638 4639 4640 4641 4642 4643 4644 4645 4646 4647 4648 4649 4650 4651 4652 4653 4654 4655 4656 4657 4658 4659 4660 4661 4662 4663 4664 4665 4666 4667 4668 4669 4670 4671 4672 4673 4674 4675 4676 4677 4678 4679 4680 4681 4682 4683 4684 4685 4686 4687 4688 4689 4690 4691 4692 4693 4694 4695 4696 4697 4698 4699 4700 4701 4702 4703 4704 4705 4706 4707 4708 4709 4710 4711 4712 4713 4714 4715 4716 4717 4718 4719 4720 4721 4722 4723 4724 4725 4726 4727 4728 4729 4730 4731 4732 4733 4734 4735 4736 4737 4738 4739 4740 4741 4742 4743 4744 4745 4746 4747 4748 4749 4750 4751 4752 4753 | whereLoopAddAll_end: whereLoopDelete(db, pBuilder->pNew); pBuilder->pNew = 0; return rc; } /* ** Examine a WherePath (with the addition of the extra WhereLoop of the 5th ** parameters) to see if it outputs rows in the requested ORDER BY ** (or GROUP BY) without requiring a separate source operation. Return: ** ** 0: ORDER BY is not satisfied. Sorting required ** 1: ORDER BY is satisfied. Omit sorting ** -1: Unknown at this time ** */ static int wherePathSatisfiesOrderBy( WhereInfo *pWInfo, /* The WHERE clause */ WherePath *pPath, /* The WherePath to check */ int nLoop, /* Number of entries in pPath->aLoop[] */ int isLastLoop, /* True if pLast is the inner-most loop */ WhereLoop *pLast, /* Add this WhereLoop to the end of pPath->aLoop[] */ Bitmask *pRevMask /* Mask of WhereLoops to run in reverse order */ ){ u8 revSet; /* True if rev is known */ u8 rev; /* Composite sort order */ u8 revIdx; /* Index sort order */ u8 isWellOrdered; /* All WhereLoops are well-ordered so far */ u16 nColumn; /* Number of columns in pIndex */ u16 nOrderBy; /* Number terms in the ORDER BY clause */ int iLoop; /* Index of WhereLoop in pPath being processed */ int i, j; /* Loop counters */ int iCur; /* Cursor number for current WhereLoop */ int iColumn; /* A column number within table iCur */ WhereLoop *pLoop; /* Current WhereLoop being processed. */ ExprList *pOrderBy = pWInfo->pOrderBy; /* the ORDER BY clause */ WhereTerm *pTerm; /* A single term of the WHERE clause */ Expr *pOBExpr; /* An expression from the ORDER BY clause */ CollSeq *pColl; /* COLLATE function from an ORDER BY clause term */ Index *pIndex; /* The index associated with pLoop */ sqlite3 *db = pWInfo->pParse->db; /* Database connection */ Bitmask obSat = 0; /* Mask of ORDER BY terms satisfied so far */ Bitmask obDone; /* Mask of all ORDER BY terms */ Bitmask orderedMask; /* Mask of all well-ordered loops */ WhereMaskSet *pMaskSet; /* WhereMaskSet object for this where clause */ /* ** We say the WhereLoop is "one-row" if it generates no more than one ** row of output. A WhereLoop is one-row if all of the following are true: ** (a) All index columns match with WHERE_COLUMN_EQ. ** (b) The index is unique ** Any WhereLoop with an WHERE_COLUMN_EQ constraint on the rowid is one-row. ** Every one-row WhereLoop will have the WHERE_ONEROW bit set in wsFlags. ** ** We say the WhereLoop is "well-ordered" if ** (i) it satisfies at least one term of the ORDER BY clause, and ** (ii) every row output is distinct over the terms that match the ** ORDER BY clause. ** Every one-row WhereLoop is automatically well-ordered, even if it ** does not match any terms of the ORDER BY clause. ** For condition (ii), be mindful that a UNIQUE column can have multiple ** rows that are NULL and so it not necessarily distinct. The column ** must be UNIQUE and NOT NULL. in order to be well-ordered. */ assert( pOrderBy!=0 ); /* Sortability of virtual tables is determined by the xBestIndex method ** of the virtual table itself */ if( pLast->wsFlags & WHERE_VIRTUALTABLE ){ testcase( nLoop>0 ); /* True when outer loops are one-row and match ** no ORDER BY terms */ return pLast->u.vtab.isOrdered; } if( nLoop && OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ) return 0; nOrderBy = pOrderBy->nExpr; if( nOrderBy>60 ) return 0; isWellOrdered = 1; obDone = MASKBIT(nOrderBy)-1; orderedMask = 0; pMaskSet = pWInfo->pWC->pMaskSet; for(iLoop=0; isWellOrdered && obSat<obDone && iLoop<=nLoop; iLoop++){ pLoop = iLoop<nLoop ? pPath->aLoop[iLoop] : pLast; assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 ); iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor; if( (pLoop->wsFlags & WHERE_ONEROW)==0 ){ if( pLoop->wsFlags & WHERE_IPK ){ pIndex = 0; nColumn = 0; }else if( (pIndex = pLoop->u.btree.pIndex)==0 || pIndex->bUnordered ){ return 0; }else{ nColumn = pIndex->nColumn; } /* For every term of the index that is constrained by == or IS NULL ** mark off corresponding ORDER BY terms wherever they occur ** in the ORDER BY clause. */ for(i=0; i<pLoop->u.btree.nEq; i++){ pTerm = pLoop->aTerm[i]; if( (pTerm->eOperator & (WO_EQ|WO_ISNULL))==0 ) continue; iColumn = pTerm->u.leftColumn; for(j=0; j<nOrderBy; j++){ if( MASKBIT(j) & obSat ) continue; pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[j].pExpr); if( pOBExpr->op!=TK_COLUMN ) continue; if( pOBExpr->iTable!=iCur ) continue; if( pOBExpr->iColumn!=iColumn ) continue; if( iColumn>=0 ){ pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[j].pExpr); if( !pColl ) pColl = db->pDfltColl; if( sqlite3StrICmp(pColl->zName, pIndex->azColl[i])!=0 ) continue; } obSat |= MASKBIT(j); } if( obSat==obDone ) return 1; } /* Loop through all columns of the index and deal with the ones ** that are not constrained by == or IN. */ rev = revSet = 0; for(j=0; j<=nColumn; j++){ u8 bOnce; /* True to run the ORDER BY search loop */ if( j<pLoop->u.btree.nEq && (pLoop->aTerm[j]->eOperator & (WO_EQ|WO_ISNULL))!=0 ){ continue; /* Skip == and IS NULL terms already processed */ } /* Get the column number in the table and sort order for the ** j-th column of the index for this WhereLoop */ if( j<nColumn ){ /* Normal index columns */ iColumn = pIndex->aiColumn[j]; revIdx = pIndex->aSortOrder[j]; if( iColumn==pIndex->pTable->iPKey ) iColumn = -1; }else{ /* The ROWID column at the end */ iColumn = -1; revIdx = 0; } /* An unconstrained column that might be NULL means that this ** WhereLoop is not well-ordered */ if( iColumn>=0 && j>=pLoop->u.btree.nEq && pIndex->pTable->aCol[iColumn].notNull==0 ){ isWellOrdered = 0; } /* Find the ORDER BY term that corresponds to the j-th column ** of the index and and mark that ORDER BY term off */ bOnce = 1; for(i=0; bOnce && i<nOrderBy; i++){ if( MASKBIT(i) & obSat ) continue; pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr); if( pOBExpr->op!=TK_COLUMN ) continue; if( (pWInfo->wctrlFlags & WHERE_GROUPBY)==0 ) bOnce = 0; if( pOBExpr->iTable!=iCur ) continue; if( pOBExpr->iColumn!=iColumn ) continue; if( iColumn>=0 ){ pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[i].pExpr); if( !pColl ) pColl = db->pDfltColl; if( sqlite3StrICmp(pColl->zName, pIndex->azColl[j])!=0 ) continue; } bOnce = 1; break; } if( bOnce && i<nOrderBy ){ if( iColumn<0 ) isWellOrdered = 1; obSat |= MASKBIT(i); if( (pWInfo->wctrlFlags & WHERE_GROUPBY)==0 ){ /* If we have an ORDER BY clause, we must match the next available ** column of the ORDER BY */ if( revSet ){ if( (rev ^ revIdx)!=pOrderBy->a[i].sortOrder ) return 0; }else{ rev = revIdx ^ pOrderBy->a[i].sortOrder; if( rev ) *pRevMask |= MASKBIT(iLoop); revSet = 1; } } }else{ /* No match found */ if( j<nColumn || pIndex==0 || pIndex->onError!=OE_Abort ){ isWellOrdered = 0; } break; } } /* end Loop over all index columns */ } /* end-if not one-row */ /* Mark off any other ORDER BY terms that reference pLoop */ if( isWellOrdered ){ orderedMask |= pLoop->maskSelf; for(i=0; i<nOrderBy; i++){ Expr *p; if( MASKBIT(i) & obSat ) continue; p = pOrderBy->a[i].pExpr; if( (exprTableUsage(pMaskSet, p)&~orderedMask)==0 ){ obSat |= MASKBIT(i); } } } } if( obSat==obDone ) return 1; if( !isWellOrdered ) return 0; if( isLastLoop ) return 1; return -1; } #ifdef WHERETRACE_ENABLED /* For debugging use only: */ static const char *wherePathName(WherePath *pPath, int nLoop, WhereLoop *pLast){ static char zName[65]; |
︙ | ︙ | |||
5212 5213 5214 5215 5216 5217 5218 | #if 0 /* FIXME: Add this back in? */ /* If the caller is an UPDATE or DELETE statement that is requesting ** to use a one-pass algorithm, determine if this is appropriate. ** The one-pass algorithm only works if the WHERE clause constraints ** the statement to update a single row. */ assert( (wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || pWInfo->nLevel==1 ); | | | 5272 5273 5274 5275 5276 5277 5278 5279 5280 5281 5282 5283 5284 5285 5286 | #if 0 /* FIXME: Add this back in? */ /* If the caller is an UPDATE or DELETE statement that is requesting ** to use a one-pass algorithm, determine if this is appropriate. ** The one-pass algorithm only works if the WHERE clause constraints ** the statement to update a single row. */ assert( (wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || pWInfo->nLevel==1 ); if( (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 && (andFlags & WHERE_ONEROW)!=0 ){ pWInfo->okOnePass = 1; pWInfo->a[0].plan.wsFlags &= ~WHERE_IDX_ONLY; } #endif /* Open all tables in the pTabList and any indices selected for ** searching those tables. |
︙ | ︙ |
Changes to test/tkt-2a5629202f.test.
︙ | ︙ | |||
42 43 44 45 46 47 48 49 50 51 52 53 54 55 | } {null/four null/three a/one b/two} do_execsql_test 1.3 { CREATE UNIQUE INDEX i1 ON t8(b); SELECT coalesce(b, 'null') || '/' || c FROM t8 x ORDER BY x.b, x.c } {null/four null/three a/one b/two} #------------------------------------------------------------------------- # do_execsql_test 2.1 { CREATE TABLE t2(a, b NOT NULL, c); CREATE UNIQUE INDEX t2ab ON t2(a, b); CREATE UNIQUE INDEX t2ba ON t2(b, a); | > > > > > > | 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | } {null/four null/three a/one b/two} do_execsql_test 1.3 { CREATE UNIQUE INDEX i1 ON t8(b); SELECT coalesce(b, 'null') || '/' || c FROM t8 x ORDER BY x.b, x.c } {null/four null/three a/one b/two} do_execsql_test 1.4 { DROP INDEX t8; CREATE UNIQUE INDEX i1 ON t8(b, c); SELECT coalesce(b, 'null') || '/' || c FROM t8 x ORDER BY x.b, x.c } {null/four null/three a/one b/two} #------------------------------------------------------------------------- # do_execsql_test 2.1 { CREATE TABLE t2(a, b NOT NULL, c); CREATE UNIQUE INDEX t2ab ON t2(a, b); CREATE UNIQUE INDEX t2ba ON t2(b, a); |
︙ | ︙ | |||
64 65 66 67 68 69 70 | } {sort} do_test 2.4 { cksort { SELECT * FROM t2 WHERE a IS NULL ORDER BY a, b, c } } {sort} finish_test | < | 70 71 72 73 74 75 76 | } {sort} do_test 2.4 { cksort { SELECT * FROM t2 WHERE a IS NULL ORDER BY a, b, c } } {sort} finish_test |