Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Merge recent trunk changes with this branch. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | exp-window-functions |
Files: | files | file ages | folders |
SHA3-256: |
c71f23590c25b4cecd27722e6c0fc8e3 |
User & Date: | dan 2018-06-09 18:09:44.345 |
Context
2018-06-10
| ||
07:42 | Update Makefile.msc to include window.c in the build. (check-in: 16db73842a user: dan tags: exp-window-functions) | |
2018-06-09
| ||
18:09 | Merge recent trunk changes with this branch. (check-in: c71f23590c user: dan tags: exp-window-functions) | |
17:58 | Update the amalgamation build script to include window.c. (check-in: 21d2f4a62e user: dan tags: exp-window-functions) | |
16:49 | Slightly smaller and faster code by encapsulating wal-index hash table location information in a separate WalHashLoc object rather than passing around the various elements as separate variables. (check-in: 538a365b7a user: drh tags: trunk) | |
Changes
Changes to src/btree.c.
︙ | ︙ | |||
5592 5593 5594 5595 5596 5597 5598 | } pCur->skipNext = 0; } } pPage = pCur->pPage; idx = ++pCur->ix; | | > > > > > > > > > | 5592 5593 5594 5595 5596 5597 5598 5599 5600 5601 5602 5603 5604 5605 5606 5607 5608 5609 5610 5611 5612 5613 5614 5615 | } pCur->skipNext = 0; } } pPage = pCur->pPage; idx = ++pCur->ix; if( !pPage->isInit ){ /* The only known way for this to happen is for there to be a ** recursive SQL function that does a DELETE operation as part of a ** SELECT which deletes content out from under an active cursor ** in a corrupt database file where the table being DELETE-ed from ** has pages in common with the table being queried. See TH3 ** module cov1/btree78.test testcase 220 (2018-06-08) for an ** example. */ return SQLITE_CORRUPT_BKPT; } /* If the database file is corrupt, it is possible for the value of idx ** to be invalid here. This can only occur if a second cursor modifies ** the page while cursor pCur is holding a reference to it. Which can ** only happen if the database is corrupt in such a way as to link the ** page into more than one b-tree structure. */ testcase( idx>pPage->nCell ); |
︙ | ︙ |
Changes to src/build.c.
︙ | ︙ | |||
1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 | /* Return true if value x is found any of the first nCol entries of aiCol[] */ static int hasColumn(const i16 *aiCol, int nCol, int x){ while( nCol-- > 0 ) if( x==*(aiCol++) ) return 1; return 0; } /* ** This routine runs at the end of parsing a CREATE TABLE statement that ** has a WITHOUT ROWID clause. The job of this routine is to convert both ** internal schema data structures and the generated VDBE code so that they ** are appropriate for a WITHOUT ROWID table instead of a rowid table. ** Changes include: | > > > > > > > > > > > > > > > > > > > > > > > > > | 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 | /* Return true if value x is found any of the first nCol entries of aiCol[] */ static int hasColumn(const i16 *aiCol, int nCol, int x){ while( nCol-- > 0 ) if( x==*(aiCol++) ) return 1; return 0; } /* Recompute the colNotIdxed field of the Index. ** ** colNotIdxed is a bitmask that has a 0 bit representing each indexed ** columns that are within the first 63 columns of the table. The ** high-order bit of colNotIdxed is always 1. All unindexed columns ** of the table have a 1. ** ** The colNotIdxed mask is AND-ed with the SrcList.a[].colUsed mask ** to determine if the index is covering index. */ static void recomputeColumnsNotIndexed(Index *pIdx){ Bitmask m = 0; int j; for(j=pIdx->nColumn-1; j>=0; j--){ int x = pIdx->aiColumn[j]; if( x>=0 ){ testcase( x==BMS-1 ); testcase( x==BMS-2 ); if( x<BMS-1 ) m |= MASKBIT(x); } } pIdx->colNotIdxed = ~m; assert( (pIdx->colNotIdxed>>63)==1 ); } /* ** This routine runs at the end of parsing a CREATE TABLE statement that ** has a WITHOUT ROWID clause. The job of this routine is to convert both ** internal schema data structures and the generated VDBE code so that they ** are appropriate for a WITHOUT ROWID table instead of a rowid table. ** Changes include: |
︙ | ︙ | |||
1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 | } } assert( pPk->nColumn==j ); assert( pTab->nCol==j ); }else{ pPk->nColumn = pTab->nCol; } } /* ** This routine is called to report the final ")" that terminates ** a CREATE TABLE statement. ** ** The table structure that other action routines have been building | > | 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 | } } assert( pPk->nColumn==j ); assert( pTab->nCol==j ); }else{ pPk->nColumn = pTab->nCol; } recomputeColumnsNotIndexed(pPk); } /* ** This routine is called to report the final ")" that terminates ** a CREATE TABLE statement. ** ** The table structure that other action routines have been building |
︙ | ︙ | |||
3272 3273 3274 3275 3276 3277 3278 3279 3280 3281 3282 3283 3284 3285 | sqlite3DefaultRowEst(pIndex); if( pParse->pNewTable==0 ) estimateIndexWidth(pIndex); /* If this index contains every column of its table, then mark ** it as a covering index */ assert( HasRowid(pTab) || pTab->iPKey<0 || sqlite3ColumnOfIndex(pIndex, pTab->iPKey)>=0 ); if( pTblName!=0 && pIndex->nColumn>=pTab->nCol ){ pIndex->isCovering = 1; for(j=0; j<pTab->nCol; j++){ if( j==pTab->iPKey ) continue; if( sqlite3ColumnOfIndex(pIndex,j)>=0 ) continue; pIndex->isCovering = 0; break; | > | 3298 3299 3300 3301 3302 3303 3304 3305 3306 3307 3308 3309 3310 3311 3312 | sqlite3DefaultRowEst(pIndex); if( pParse->pNewTable==0 ) estimateIndexWidth(pIndex); /* If this index contains every column of its table, then mark ** it as a covering index */ assert( HasRowid(pTab) || pTab->iPKey<0 || sqlite3ColumnOfIndex(pIndex, pTab->iPKey)>=0 ); recomputeColumnsNotIndexed(pIndex); if( pTblName!=0 && pIndex->nColumn>=pTab->nCol ){ pIndex->isCovering = 1; for(j=0; j<pTab->nCol; j++){ if( j==pTab->iPKey ) continue; if( sqlite3ColumnOfIndex(pIndex,j)>=0 ) continue; pIndex->isCovering = 0; break; |
︙ | ︙ |
Changes to src/sqliteInt.h.
︙ | ︙ | |||
1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 | typedef struct VTable VTable; typedef struct VtabCtx VtabCtx; typedef struct Walker Walker; typedef struct WhereInfo WhereInfo; typedef struct Window Window; typedef struct With With; /* A VList object records a mapping between parameters/variables/wildcards ** in the SQL statement (such as $abc, @pqr, or :xyz) and the integer ** variable number associated with that parameter. See the format description ** on the sqlite3VListAdd() routine for more information. A VList is really ** just an array of integers. */ typedef int VList; | > > > > > > > > > > > > > > > > > > > > > > > > > > | 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 | typedef struct VTable VTable; typedef struct VtabCtx VtabCtx; typedef struct Walker Walker; typedef struct WhereInfo WhereInfo; typedef struct Window Window; typedef struct With With; /* ** The bitmask datatype defined below is used for various optimizations. ** ** Changing this from a 64-bit to a 32-bit type limits the number of ** tables in a join to 32 instead of 64. But it also reduces the size ** of the library by 738 bytes on ix86. */ #ifdef SQLITE_BITMASK_TYPE typedef SQLITE_BITMASK_TYPE Bitmask; #else typedef u64 Bitmask; #endif /* ** 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)) #define MASKBIT32(n) (((unsigned int)1)<<(n)) #define ALLBITS ((Bitmask)-1) /* A VList object records a mapping between parameters/variables/wildcards ** in the SQL statement (such as $abc, @pqr, or :xyz) and the integer ** variable number associated with that parameter. See the format description ** on the sqlite3VListAdd() routine for more information. A VList is really ** just an array of integers. */ typedef int VList; |
︙ | ︙ | |||
2209 2210 2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 | int nSample; /* Number of elements in aSample[] */ int nSampleCol; /* Size of IndexSample.anEq[] and so on */ tRowcnt *aAvgEq; /* Average nEq values for keys not in aSample */ IndexSample *aSample; /* Samples of the left-most key */ tRowcnt *aiRowEst; /* Non-logarithmic stat1 data for this index */ tRowcnt nRowEst0; /* Non-logarithmic number of rows in the index */ #endif }; /* ** Allowed values for Index.idxType */ #define SQLITE_IDXTYPE_APPDEF 0 /* Created using CREATE INDEX */ #define SQLITE_IDXTYPE_UNIQUE 1 /* Implements a UNIQUE constraint */ | > | 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 | int nSample; /* Number of elements in aSample[] */ int nSampleCol; /* Size of IndexSample.anEq[] and so on */ tRowcnt *aAvgEq; /* Average nEq values for keys not in aSample */ IndexSample *aSample; /* Samples of the left-most key */ tRowcnt *aiRowEst; /* Non-logarithmic stat1 data for this index */ tRowcnt nRowEst0; /* Non-logarithmic number of rows in the index */ #endif Bitmask colNotIdxed; /* 0 for unindexed columns in pTab */ }; /* ** Allowed values for Index.idxType */ #define SQLITE_IDXTYPE_APPDEF 0 /* Created using CREATE INDEX */ #define SQLITE_IDXTYPE_UNIQUE 1 /* Implements a UNIQUE constraint */ |
︙ | ︙ | |||
2555 2556 2557 2558 2559 2560 2561 | struct IdList_item { char *zName; /* Name of the identifier */ int idx; /* Index in some Table.aCol[] of a column named zName */ } *a; int nId; /* Number of identifiers on the list */ }; | < < < < < < < < < < < < < < < < < < < < < < < < < | 2582 2583 2584 2585 2586 2587 2588 2589 2590 2591 2592 2593 2594 2595 | struct IdList_item { char *zName; /* Name of the identifier */ int idx; /* Index in some Table.aCol[] of a column named zName */ } *a; int nId; /* Number of identifiers on the list */ }; /* ** 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/wal.c.
︙ | ︙ | |||
875 876 877 878 879 880 881 882 883 884 885 886 887 | assert( iPage>0 ); assert( (HASHTABLE_NSLOT & (HASHTABLE_NSLOT-1))==0 ); return (iPage*HASHTABLE_HASH_1) & (HASHTABLE_NSLOT-1); } static int walNextHash(int iPriorHash){ return (iPriorHash+1)&(HASHTABLE_NSLOT-1); } /* ** Return pointers to the hash table and page number array stored on ** page iHash of the wal-index. The wal-index is broken into 32KB pages ** numbered starting from 0. ** | > > > > > > > > > > > > | | | | | | < < < | < < < | | | | < | < < | 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 | assert( iPage>0 ); assert( (HASHTABLE_NSLOT & (HASHTABLE_NSLOT-1))==0 ); return (iPage*HASHTABLE_HASH_1) & (HASHTABLE_NSLOT-1); } static int walNextHash(int iPriorHash){ return (iPriorHash+1)&(HASHTABLE_NSLOT-1); } /* ** An instance of the WalHashLoc object is used to describe the location ** of a page hash table in the wal-index. This becomes the return value ** from walHashGet(). */ typedef struct WalHashLoc WalHashLoc; struct WalHashLoc { volatile ht_slot *aHash; /* Start of the wal-index hash table */ volatile u32 *aPgno; /* aPgno[1] is the page of first frame indexed */ u32 iZero; /* One less than the frame number of first indexed*/ }; /* ** Return pointers to the hash table and page number array stored on ** page iHash of the wal-index. The wal-index is broken into 32KB pages ** numbered starting from 0. ** ** Set output variable pLoc->aHash to point to the start of the hash table ** in the wal-index file. Set pLoc->iZero to one less than the frame ** number of the first frame indexed by this hash table. If a ** slot in the hash table is set to N, it refers to frame number ** (pLoc->iZero+N) in the log. ** ** Finally, set pLoc->aPgno so that pLoc->aPgno[1] is the page number of the ** first frame indexed by the hash table, frame (pLoc->iZero+1). */ static int walHashGet( Wal *pWal, /* WAL handle */ int iHash, /* Find the iHash'th table */ WalHashLoc *pLoc /* OUT: Hash table location */ ){ int rc; /* Return code */ rc = walIndexPage(pWal, iHash, &pLoc->aPgno); assert( rc==SQLITE_OK || iHash>0 ); if( rc==SQLITE_OK ){ pLoc->aHash = (volatile ht_slot *)&pLoc->aPgno[HASHTABLE_NPAGE]; if( iHash==0 ){ pLoc->aPgno = &pLoc->aPgno[WALINDEX_HDR_SIZE/sizeof(u32)]; pLoc->iZero = 0; }else{ pLoc->iZero = HASHTABLE_NPAGE_ONE + (iHash-1)*HASHTABLE_NPAGE; } pLoc->aPgno = &pLoc->aPgno[-1]; } return rc; } /* ** Return the number of the wal-index page that contains the hash-table ** and page-number array that contain entries corresponding to WAL frame |
︙ | ︙ | |||
963 964 965 966 967 968 969 | ** ** At most only the hash table containing pWal->hdr.mxFrame needs to be ** updated. Any later hash tables will be automatically cleared when ** pWal->hdr.mxFrame advances to the point where those hash tables are ** actually needed. */ static void walCleanupHash(Wal *pWal){ | < < | | | | | | | | | | | < < | | | > | | | | | | | > > | | | | 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 | ** ** At most only the hash table containing pWal->hdr.mxFrame needs to be ** updated. Any later hash tables will be automatically cleared when ** pWal->hdr.mxFrame advances to the point where those hash tables are ** actually needed. */ static void walCleanupHash(Wal *pWal){ WalHashLoc sLoc; /* Hash table location */ int iLimit = 0; /* Zero values greater than this */ int nByte; /* Number of bytes to zero in aPgno[] */ int i; /* Used to iterate through aHash[] */ assert( pWal->writeLock ); testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE_ONE-1 ); testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE_ONE ); testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE_ONE+1 ); if( pWal->hdr.mxFrame==0 ) return; /* Obtain pointers to the hash-table and page-number array containing ** the entry that corresponds to frame pWal->hdr.mxFrame. It is guaranteed ** that the page said hash-table and array reside on is already mapped. */ assert( pWal->nWiData>walFramePage(pWal->hdr.mxFrame) ); assert( pWal->apWiData[walFramePage(pWal->hdr.mxFrame)] ); walHashGet(pWal, walFramePage(pWal->hdr.mxFrame), &sLoc); /* Zero all hash-table entries that correspond to frame numbers greater ** than pWal->hdr.mxFrame. */ iLimit = pWal->hdr.mxFrame - sLoc.iZero; assert( iLimit>0 ); for(i=0; i<HASHTABLE_NSLOT; i++){ if( sLoc.aHash[i]>iLimit ){ sLoc.aHash[i] = 0; } } /* Zero the entries in the aPgno array that correspond to frames with ** frame numbers greater than pWal->hdr.mxFrame. */ nByte = (int)((char *)sLoc.aHash - (char *)&sLoc.aPgno[iLimit+1]); memset((void *)&sLoc.aPgno[iLimit+1], 0, nByte); #ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT /* Verify that the every entry in the mapping region is still reachable ** via the hash table even after the cleanup. */ if( iLimit ){ int j; /* Loop counter */ int iKey; /* Hash key */ for(j=1; j<=iLimit; j++){ for(iKey=walHash(sLoc.aPgno[j]);sLoc.aHash[iKey];iKey=walNextHash(iKey)){ if( sLoc.aHash[iKey]==j ) break; } assert( sLoc.aHash[iKey]==j ); } } #endif /* SQLITE_ENABLE_EXPENSIVE_ASSERT */ } /* ** Set an entry in the wal-index that will map database page number ** pPage into WAL frame iFrame. */ static int walIndexAppend(Wal *pWal, u32 iFrame, u32 iPage){ int rc; /* Return code */ WalHashLoc sLoc; /* Wal-index hash table location */ rc = walHashGet(pWal, walFramePage(iFrame), &sLoc); /* Assuming the wal-index file was successfully mapped, populate the ** page number array and hash table entry. */ if( rc==SQLITE_OK ){ int iKey; /* Hash table key */ int idx; /* Value to write to hash-table slot */ int nCollide; /* Number of hash collisions */ idx = iFrame - sLoc.iZero; assert( idx <= HASHTABLE_NSLOT/2 + 1 ); /* If this is the first entry to be added to this hash-table, zero the ** entire hash table and aPgno[] array before proceeding. */ if( idx==1 ){ int nByte = (int)((u8 *)&sLoc.aHash[HASHTABLE_NSLOT] - (u8 *)&sLoc.aPgno[1]); memset((void*)&sLoc.aPgno[1], 0, nByte); } /* If the entry in aPgno[] is already set, then the previous writer ** must have exited unexpectedly in the middle of a transaction (after ** writing one or more dirty pages to the WAL to free up memory). ** Remove the remnants of that writers uncommitted transaction from ** the hash-table before writing any new entries. */ if( sLoc.aPgno[idx] ){ walCleanupHash(pWal); assert( !sLoc.aPgno[idx] ); } /* Write the aPgno[] array entry and the hash-table slot. */ nCollide = idx; for(iKey=walHash(iPage); sLoc.aHash[iKey]; iKey=walNextHash(iKey)){ if( (nCollide--)==0 ) return SQLITE_CORRUPT_BKPT; } sLoc.aPgno[idx] = iPage; sLoc.aHash[iKey] = (ht_slot)idx; #ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT /* Verify that the number of entries in the hash table exactly equals ** the number of entries in the mapping region. */ { int i; /* Loop counter */ int nEntry = 0; /* Number of entries in the hash table */ for(i=0; i<HASHTABLE_NSLOT; i++){ if( sLoc.aHash[i] ) nEntry++; } assert( nEntry==idx ); } /* Verify that the every entry in the mapping region is reachable ** via the hash table. This turns out to be a really, really expensive ** thing to check, so only do this occasionally - not on every ** iteration. */ if( (idx&0x3ff)==0 ){ int i; /* Loop counter */ for(i=1; i<=idx; i++){ for(iKey=walHash(sLoc.aPgno[i]); sLoc.aHash[iKey]; iKey=walNextHash(iKey)){ if( sLoc.aHash[iKey]==i ) break; } assert( sLoc.aHash[iKey]==i ); } } #endif /* SQLITE_ENABLE_EXPENSIVE_ASSERT */ } return rc; |
︙ | ︙ | |||
1630 1631 1632 1633 1634 1635 1636 | sizeof(ht_slot) * (iLast>HASHTABLE_NPAGE?HASHTABLE_NPAGE:iLast) ); if( !aTmp ){ rc = SQLITE_NOMEM_BKPT; } for(i=walFramePage(nBackfill+1); rc==SQLITE_OK && i<nSegment; i++){ | | < < | | | | | | | | | | 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 | sizeof(ht_slot) * (iLast>HASHTABLE_NPAGE?HASHTABLE_NPAGE:iLast) ); if( !aTmp ){ rc = SQLITE_NOMEM_BKPT; } for(i=walFramePage(nBackfill+1); rc==SQLITE_OK && i<nSegment; i++){ WalHashLoc sLoc; rc = walHashGet(pWal, i, &sLoc); if( rc==SQLITE_OK ){ int j; /* Counter variable */ int nEntry; /* Number of entries in this segment */ ht_slot *aIndex; /* Sorted index for this segment */ sLoc.aPgno++; if( (i+1)==nSegment ){ nEntry = (int)(iLast - sLoc.iZero); }else{ nEntry = (int)((u32*)sLoc.aHash - (u32*)sLoc.aPgno); } aIndex = &((ht_slot *)&p->aSegment[p->nSegment])[sLoc.iZero]; sLoc.iZero++; for(j=0; j<nEntry; j++){ aIndex[j] = (ht_slot)j; } walMergesort((u32 *)sLoc.aPgno, aTmp, aIndex, &nEntry); p->aSegment[i].iZero = sLoc.iZero; p->aSegment[i].nEntry = nEntry; p->aSegment[i].aIndex = aIndex; p->aSegment[i].aPgno = (u32 *)sLoc.aPgno; } } sqlite3_free(aTmp); if( rc!=SQLITE_OK ){ walIteratorFree(p); p = 0; |
︙ | ︙ | |||
2669 2670 2671 2672 2673 2674 2675 | void *pBuf1 = sqlite3_malloc(szPage); void *pBuf2 = sqlite3_malloc(szPage); if( pBuf1==0 || pBuf2==0 ){ rc = SQLITE_NOMEM; }else{ u32 i = pInfo->nBackfillAttempted; for(i=pInfo->nBackfillAttempted; i>pInfo->nBackfill; i--){ | < < | | | | 2669 2670 2671 2672 2673 2674 2675 2676 2677 2678 2679 2680 2681 2682 2683 2684 2685 2686 2687 2688 2689 2690 | void *pBuf1 = sqlite3_malloc(szPage); void *pBuf2 = sqlite3_malloc(szPage); if( pBuf1==0 || pBuf2==0 ){ rc = SQLITE_NOMEM; }else{ u32 i = pInfo->nBackfillAttempted; for(i=pInfo->nBackfillAttempted; i>pInfo->nBackfill; i--){ WalHashLoc sLoc; /* Hash table location */ u32 pgno; /* Page number in db file */ i64 iDbOff; /* Offset of db file entry */ i64 iWalOff; /* Offset of wal file entry */ rc = walHashGet(pWal, walFramePage(i), &sLoc); if( rc!=SQLITE_OK ) break; pgno = sLoc.aPgno[i-sLoc.iZero]; iDbOff = (i64)(pgno-1) * szPage; if( iDbOff+szPage<=szDb ){ iWalOff = walFrameOffset(i, szPage) + WAL_FRAME_HDRSIZE; rc = sqlite3OsRead(pWal->pWalFd, pBuf1, szPage, iWalOff); if( rc==SQLITE_OK ){ |
︙ | ︙ | |||
2879 2880 2881 2882 2883 2884 2885 | ** ** (iFrame<=iLast): ** This condition filters out entries that were added to the hash ** table after the current read-transaction had started. */ iMinHash = walFramePage(pWal->minFrame); for(iHash=walFramePage(iLast); iHash>=iMinHash; iHash--){ | < < | | | | | > | 2877 2878 2879 2880 2881 2882 2883 2884 2885 2886 2887 2888 2889 2890 2891 2892 2893 2894 2895 2896 2897 2898 2899 2900 2901 2902 2903 2904 | ** ** (iFrame<=iLast): ** This condition filters out entries that were added to the hash ** table after the current read-transaction had started. */ iMinHash = walFramePage(pWal->minFrame); for(iHash=walFramePage(iLast); iHash>=iMinHash; iHash--){ WalHashLoc sLoc; /* Hash table location */ int iKey; /* Hash slot index */ int nCollide; /* Number of hash collisions remaining */ int rc; /* Error code */ rc = walHashGet(pWal, iHash, &sLoc); if( rc!=SQLITE_OK ){ return rc; } nCollide = HASHTABLE_NSLOT; for(iKey=walHash(pgno); sLoc.aHash[iKey]; iKey=walNextHash(iKey)){ u32 iFrame = sLoc.aHash[iKey] + sLoc.iZero; if( iFrame<=iLast && iFrame>=pWal->minFrame && sLoc.aPgno[sLoc.aHash[iKey]]==pgno ){ assert( iFrame>iRead || CORRUPT_DB ); iRead = iFrame; } if( (nCollide--)==0 ){ return SQLITE_CORRUPT_BKPT; } } |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
2447 2448 2449 2450 2451 2452 2453 | || (pNew->wsFlags & WHERE_COLUMN_NULL)!=0 || (pNew->wsFlags & WHERE_COLUMN_IN)!=0 || (pNew->wsFlags & WHERE_SKIPSCAN)!=0 ); if( eOp & WO_IN ){ Expr *pExpr = pTerm->pExpr; | < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 2447 2448 2449 2450 2451 2452 2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 2469 2470 2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 2515 | || (pNew->wsFlags & WHERE_COLUMN_NULL)!=0 || (pNew->wsFlags & WHERE_COLUMN_IN)!=0 || (pNew->wsFlags & WHERE_SKIPSCAN)!=0 ); if( eOp & WO_IN ){ Expr *pExpr = pTerm->pExpr; if( ExprHasProperty(pExpr, EP_xIsSelect) ){ /* "x IN (SELECT ...)": TUNING: the SELECT returns 25 rows */ int i; nIn = 46; assert( 46==sqlite3LogEst(25) ); /* The expression may actually be of the form (x, y) IN (SELECT...). ** In this case there is a separate term for each of (x) and (y). ** However, the nIn multiplier should only be applied once, not once ** for each such term. The following loop checks that pTerm is the ** first such term in use, and sets nIn back to 0 if it is not. */ for(i=0; i<pNew->nLTerm-1; i++){ if( pNew->aLTerm[i] && pNew->aLTerm[i]->pExpr==pExpr ) nIn = 0; } }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){ /* "x IN (value, value, ...)" */ nIn = sqlite3LogEst(pExpr->x.pList->nExpr); assert( nIn>0 ); /* RHS always has 2 or more terms... The parser ** changes "x IN (?)" into "x=?". */ } if( pProbe->hasStat1 ){ LogEst M, logK, safetyMargin; /* Let: ** N = the total number of rows in the table ** K = the number of entries on the RHS of the IN operator ** M = the number of rows in the table that match terms to the ** to the left in the same index. If the IN operator is on ** the left-most index column, M==N. ** ** Given the definitions above, it is better to omit the IN operator ** from the index lookup and instead do a scan of the M elements, ** testing each scanned row against the IN operator separately, if: ** ** M*log(K) < K*log(N) ** ** Our estimates for M, K, and N might be inaccurate, so we build in ** a safety margin of 2 (LogEst: 10) that favors using the IN operator ** with the index, as using an index has better worst-case behavior. ** If we do not have real sqlite_stat1 data, always prefer to use ** the index. */ M = pProbe->aiRowLogEst[saved_nEq]; logK = estLog(nIn); safetyMargin = 10; /* TUNING: extra weight for indexed IN */ if( M + logK + safetyMargin < nIn + rLogSize ){ WHERETRACE(0x40, ("Scan preferred over IN operator on column %d of \"%s\" (%d<%d)\n", saved_nEq, pProbe->zName, M+logK+10, nIn+rLogSize)); continue; }else{ WHERETRACE(0x40, ("IN operator preferred on column %d of \"%s\" (%d>=%d)\n", saved_nEq, pProbe->zName, M+logK+10, nIn+rLogSize)); } } pNew->wsFlags |= WHERE_COLUMN_IN; }else if( eOp & (WO_EQ|WO_IS) ){ int iCol = pProbe->aiColumn[saved_nEq]; pNew->wsFlags |= WHERE_COLUMN_EQ; assert( saved_nEq==pNew->u.btree.nEq ); if( iCol==XN_ROWID || (iCol>=0 && nInMul==0 && saved_nEq==pProbe->nKeyCol-1) ){ |
︙ | ︙ | |||
2696 2697 2698 2699 2700 2701 2702 | } } } } return 0; } | < < < < < < < < < < < < < < < < < < | 2731 2732 2733 2734 2735 2736 2737 2738 2739 2740 2741 2742 2743 2744 | } } } } return 0; } /* Check to see if a partial index with pPartIndexWhere can be used ** in the current query. Return true if it can be and false if not. */ static int whereUsablePartialIndex(int iTab, WhereClause *pWC, Expr *pWhere){ int i; WhereTerm *pTerm; Parse *pParse = pWC->pWInfo->pParse; |
︙ | ︙ | |||
2929 2930 2931 2932 2933 2934 2935 | if( rc ) break; }else{ Bitmask m; if( pProbe->isCovering ){ pNew->wsFlags = WHERE_IDX_ONLY | WHERE_INDEXED; m = 0; }else{ | | | 2946 2947 2948 2949 2950 2951 2952 2953 2954 2955 2956 2957 2958 2959 2960 | if( rc ) break; }else{ Bitmask m; if( pProbe->isCovering ){ pNew->wsFlags = WHERE_IDX_ONLY | WHERE_INDEXED; m = 0; }else{ m = pSrc->colUsed & pProbe->colNotIdxed; pNew->wsFlags = (m==0) ? (WHERE_IDX_ONLY|WHERE_INDEXED) : WHERE_INDEXED; } /* Full scan via index */ if( b || !HasRowid(pTab) || pProbe->pPartIdxWhere!=0 |
︙ | ︙ | |||
3496 3497 3498 3499 3500 3501 3502 | } rc = whereLoopAddVirtual(pBuilder, mPrereq, mUnusable); }else #endif /* SQLITE_OMIT_VIRTUALTABLE */ { rc = whereLoopAddBtree(pBuilder, mPrereq); } | | | 3513 3514 3515 3516 3517 3518 3519 3520 3521 3522 3523 3524 3525 3526 3527 | } rc = whereLoopAddVirtual(pBuilder, mPrereq, mUnusable); }else #endif /* SQLITE_OMIT_VIRTUALTABLE */ { rc = whereLoopAddBtree(pBuilder, mPrereq); } if( rc==SQLITE_OK && pBuilder->pWC->hasOr ){ rc = whereLoopAddOr(pBuilder, mPrereq, mUnusable); } mPrior |= pNew->maskSelf; if( rc || db->mallocFailed ) break; } whereLoopClear(db, pNew); |
︙ | ︙ | |||
4332 4333 4334 4335 4336 4337 4338 | pTerm = sqlite3WhereFindTerm(pWC, iCur, j, 0, opMask, pIdx); if( pTerm==0 ) break; testcase( pTerm->eOperator & WO_IS ); pLoop->aLTerm[j] = pTerm; } if( j!=pIdx->nKeyCol ) continue; pLoop->wsFlags = WHERE_COLUMN_EQ|WHERE_ONEROW|WHERE_INDEXED; | | | 4349 4350 4351 4352 4353 4354 4355 4356 4357 4358 4359 4360 4361 4362 4363 | pTerm = sqlite3WhereFindTerm(pWC, iCur, j, 0, opMask, pIdx); if( pTerm==0 ) break; testcase( pTerm->eOperator & WO_IS ); pLoop->aLTerm[j] = pTerm; } if( j!=pIdx->nKeyCol ) continue; pLoop->wsFlags = WHERE_COLUMN_EQ|WHERE_ONEROW|WHERE_INDEXED; if( pIdx->isCovering || (pItem->colUsed & pIdx->colNotIdxed)==0 ){ pLoop->wsFlags |= WHERE_IDX_ONLY; } pLoop->nLTerm = j; pLoop->u.btree.nEq = j; pLoop->u.btree.pIndex = pIdx; /* TUNING: Cost of a unique index lookup is 15 */ pLoop->rRun = 39; /* 39==sqlite3LogEst(15) */ |
︙ | ︙ |
Changes to src/whereInt.h.
︙ | ︙ | |||
318 319 320 321 322 323 324 325 326 327 328 329 330 331 | ** the subclauses "(b AND c)" and "(d AND e)". The pOuter field of the ** subclauses points to the WhereClause object for the whole clause. */ struct WhereClause { WhereInfo *pWInfo; /* WHERE clause processing context */ WhereClause *pOuter; /* Outer conjunction */ u8 op; /* Split operator. TK_AND or TK_OR */ int nTerm; /* Number of terms */ int nSlot; /* Number of entries in a[] */ WhereTerm *a; /* Each a[] describes a term of the WHERE cluase */ #if defined(SQLITE_SMALL_STACK) WhereTerm aStatic[1]; /* Initial static space for a[] */ #else WhereTerm aStatic[8]; /* Initial static space for a[] */ | > | 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 | ** the subclauses "(b AND c)" and "(d AND e)". The pOuter field of the ** subclauses points to the WhereClause object for the whole clause. */ struct WhereClause { WhereInfo *pWInfo; /* WHERE clause processing context */ WhereClause *pOuter; /* Outer conjunction */ u8 op; /* Split operator. TK_AND or TK_OR */ u8 hasOr; /* True if any a[].eOperator is WO_OR */ int nTerm; /* Number of terms */ int nSlot; /* Number of entries in a[] */ WhereTerm *a; /* Each a[] describes a term of the WHERE cluase */ #if defined(SQLITE_SMALL_STACK) WhereTerm aStatic[1]; /* Initial static space for a[] */ #else WhereTerm aStatic[8]; /* Initial static space for a[] */ |
︙ | ︙ | |||
491 492 493 494 495 496 497 498 499 500 501 502 503 504 | ); /* whereexpr.c: */ void sqlite3WhereClauseInit(WhereClause*,WhereInfo*); void sqlite3WhereClauseClear(WhereClause*); void sqlite3WhereSplit(WhereClause*,Expr*,u8); Bitmask sqlite3WhereExprUsage(WhereMaskSet*, Expr*); Bitmask sqlite3WhereExprListUsage(WhereMaskSet*, ExprList*); void sqlite3WhereExprAnalyze(SrcList*, WhereClause*); void sqlite3WhereTabFuncArgs(Parse*, struct SrcList_item*, WhereClause*); | > | 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 | ); /* whereexpr.c: */ void sqlite3WhereClauseInit(WhereClause*,WhereInfo*); void sqlite3WhereClauseClear(WhereClause*); void sqlite3WhereSplit(WhereClause*,Expr*,u8); Bitmask sqlite3WhereExprUsage(WhereMaskSet*, Expr*); Bitmask sqlite3WhereExprUsageNN(WhereMaskSet*, Expr*); Bitmask sqlite3WhereExprListUsage(WhereMaskSet*, ExprList*); void sqlite3WhereExprAnalyze(SrcList*, WhereClause*); void sqlite3WhereTabFuncArgs(Parse*, struct SrcList_item*, WhereClause*); |
︙ | ︙ |
Changes to src/whereexpr.c.
︙ | ︙ | |||
668 669 670 671 672 673 674 | } /* ** Record the set of tables that satisfy case 3. The set might be ** empty. */ pOrInfo->indexable = indexable; | > | > > > > | 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 | } /* ** Record the set of tables that satisfy case 3. The set might be ** empty. */ pOrInfo->indexable = indexable; if( indexable ){ pTerm->eOperator = WO_OR; pWC->hasOr = 1; }else{ pTerm->eOperator = WO_OR; } /* For a two-way OR, attempt to implementation case 2. */ if( indexable && pOrWc->nTerm==2 ){ int iOne = 0; WhereTerm *pOne; while( (pOne = whereNthSubterm(&pOrWc->a[0],iOne++))!=0 ){ |
︙ | ︙ | |||
1007 1008 1009 1010 1011 1012 1013 | } }else if( op==TK_ISNULL ){ pTerm->prereqRight = 0; }else{ pTerm->prereqRight = sqlite3WhereExprUsage(pMaskSet, pExpr->pRight); } pMaskSet->bVarSelect = 0; | | | 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 | } }else if( op==TK_ISNULL ){ pTerm->prereqRight = 0; }else{ pTerm->prereqRight = sqlite3WhereExprUsage(pMaskSet, pExpr->pRight); } pMaskSet->bVarSelect = 0; prereqAll = sqlite3WhereExprUsageNN(pMaskSet, pExpr); if( pMaskSet->bVarSelect ) pTerm->wtFlags |= TERM_VARSELECT; if( ExprHasProperty(pExpr, EP_FromJoin) ){ Bitmask x = sqlite3WhereGetMask(pMaskSet, pExpr->iRightJoinTable); prereqAll |= x; extraRight = x-1; /* ON clause terms may not be used with an index ** on left table of a LEFT JOIN. Ticket #3015 */ if( (prereqAll>>1)>=x ){ |
︙ | ︙ | |||
1436 1437 1438 1439 1440 1441 1442 | /* ** These routines walk (recursively) an expression tree and generate ** a bitmask indicating which tables are used in that expression ** tree. */ | | < > > > < | | > > > | 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 | /* ** These routines walk (recursively) an expression tree and generate ** a bitmask indicating which tables are used in that expression ** tree. */ Bitmask sqlite3WhereExprUsageNN(WhereMaskSet *pMaskSet, Expr *p){ Bitmask mask; if( p->op==TK_COLUMN ){ return sqlite3WhereGetMask(pMaskSet, p->iTable); }else if( ExprHasProperty(p, EP_TokenOnly|EP_Leaf) ){ assert( p->op!=TK_IF_NULL_ROW ); return 0; } mask = (p->op==TK_IF_NULL_ROW) ? sqlite3WhereGetMask(pMaskSet, p->iTable) : 0; if( p->pLeft ) mask |= sqlite3WhereExprUsageNN(pMaskSet, p->pLeft); if( p->pRight ){ mask |= sqlite3WhereExprUsageNN(pMaskSet, p->pRight); assert( p->x.pList==0 ); }else if( ExprHasProperty(p, EP_xIsSelect) ){ if( ExprHasProperty(p, EP_VarSelect) ) pMaskSet->bVarSelect = 1; mask |= exprSelectUsage(pMaskSet, p->x.pSelect); }else if( p->x.pList ){ mask |= sqlite3WhereExprListUsage(pMaskSet, p->x.pList); } return mask; } Bitmask sqlite3WhereExprUsage(WhereMaskSet *pMaskSet, Expr *p){ return p ? sqlite3WhereExprUsageNN(pMaskSet,p) : 0; } Bitmask sqlite3WhereExprListUsage(WhereMaskSet *pMaskSet, ExprList *pList){ int i; Bitmask mask = 0; if( pList ){ for(i=0; i<pList->nExpr; i++){ mask |= sqlite3WhereExprUsage(pMaskSet, pList->a[i].pExpr); |
︙ | ︙ |
Changes to test/in6.test.
︙ | ︙ | |||
24 25 26 27 28 29 30 31 32 33 34 35 36 37 | do_test in6-1.1 { db eval { CREATE TABLE t1(a,b,c,d); WITH RECURSIVE c(x) AS (VALUES(1) UNION ALL SELECT x+1 FROM c WHERE x<100) INSERT INTO t1(a,b,c,d) SELECT 100, 200+x/2, 300+x/5, x FROM c; CREATE INDEX t1abc ON t1(a,b,c); } set ::sqlite_search_count 0 db eval { SELECT d FROM t1 WHERE a=99 AND b IN (200,205,201,204) AND c IN (304,302,309,308); | > > > | 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | do_test in6-1.1 { db eval { CREATE TABLE t1(a,b,c,d); WITH RECURSIVE c(x) AS (VALUES(1) UNION ALL SELECT x+1 FROM c WHERE x<100) INSERT INTO t1(a,b,c,d) SELECT 100, 200+x/2, 300+x/5, x FROM c; CREATE INDEX t1abc ON t1(a,b,c); ANALYZE; UPDATE sqlite_stat1 SET stat='1000000 500000 500 50'; ANALYZE sqlite_master; } set ::sqlite_search_count 0 db eval { SELECT d FROM t1 WHERE a=99 AND b IN (200,205,201,204) AND c IN (304,302,309,308); |
︙ | ︙ |
Changes to test/rowvalue4.test.
︙ | ︙ | |||
220 221 222 223 224 225 226 | CREATE TABLE d2(a, b, c); CREATE INDEX d2ab ON d2(a, b); CREATE INDEX d2c ON d2(c); WITH i(i) AS ( VALUES(1) UNION ALL SELECT i+1 FROM i WHERE i<1000 ) | | | 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 | CREATE TABLE d2(a, b, c); CREATE INDEX d2ab ON d2(a, b); CREATE INDEX d2c ON d2(c); WITH i(i) AS ( VALUES(1) UNION ALL SELECT i+1 FROM i WHERE i<1000 ) INSERT INTO d2 SELECT i/100, i%100, i/100 FROM i; ANALYZE; } do_eqp_test 5.1 { SELECT * FROM d2 WHERE (a, b) IN (SELECT x, y FROM d1) AND (c) IN (SELECT y FROM d1) |
︙ | ︙ |