Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Experimental attempt to make better use of covering indexes within OR queries. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | covering-or |
Files: | files | file ages | folders |
SHA1: |
a323ac3a9d42bd5cb38d724c7e118058 |
User & Date: | dan 2016-01-29 19:29:45.658 |
Context
2016-01-29
| ||
20:58 | Different comment on the alternative cursor fields of VdbeCursor. (check-in: 6e3dcb6d7d user: drh tags: covering-or) | |
19:29 | Experimental attempt to make better use of covering indexes within OR queries. (check-in: a323ac3a9d user: dan tags: covering-or) | |
18:11 | Avoid unnecessary WHERE clause term tests when coding a join where one of the tables contains a OR constraint. (check-in: 512caa1ad3 user: drh tags: trunk) | |
Changes
Changes to src/vdbe.c.
︙ | ︙ | |||
2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 | const u8 *zEndHdr; /* Pointer to first byte after the header */ u32 offset; /* Offset into the data */ u64 offset64; /* 64-bit offset */ u32 avail; /* Number of bytes of available data */ u32 t; /* A type code from the record header */ Mem *pReg; /* PseudoTable input register */ p2 = pOp->p2; assert( pOp->p3>0 && pOp->p3<=(p->nMem-p->nCursor) ); pDest = &aMem[pOp->p3]; memAboutToChange(p, pDest); assert( pOp->p1>=0 && pOp->p1<p->nCursor ); | > > > > > < < < | 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392 2393 2394 2395 2396 2397 2398 2399 2400 2401 2402 2403 | const u8 *zEndHdr; /* Pointer to first byte after the header */ u32 offset; /* Offset into the data */ u64 offset64; /* 64-bit offset */ u32 avail; /* Number of bytes of available data */ u32 t; /* A type code from the record header */ Mem *pReg; /* PseudoTable input register */ pC = p->apCsr[pOp->p1]; p2 = pOp->p2; /* If the cursor cache is stale, bring it up-to-date */ rc = sqlite3VdbeCursorMoveto(&pC, &p2); assert( pOp->p3>0 && pOp->p3<=(p->nMem-p->nCursor) ); pDest = &aMem[pOp->p3]; memAboutToChange(p, pDest); assert( pOp->p1>=0 && pOp->p1<p->nCursor ); assert( pC!=0 ); assert( p2<pC->nField ); aOffset = pC->aOffset; assert( pC->eCurType!=CURTYPE_VTAB ); assert( pC->eCurType!=CURTYPE_PSEUDO || pC->nullRow ); assert( pC->eCurType!=CURTYPE_SORTER ); pCrsr = pC->uc.pCursor; if( rc ) goto abort_due_to_error; if( pC->cacheStatus!=p->cacheCtr ){ if( pC->nullRow ){ if( pC->eCurType==CURTYPE_PSEUDO ){ assert( pC->uc.pseudoTableReg>0 ); pReg = &aMem[pC->uc.pseudoTableReg]; assert( pReg->flags & MEM_Blob ); |
︙ | ︙ | |||
3842 3843 3844 3845 3846 3847 3848 | }else if( eqOnly ){ assert( pOp[1].opcode==OP_IdxLT || pOp[1].opcode==OP_IdxGT ); pOp++; /* Skip the OP_IdxLt or OP_IdxGT that follows */ } break; } | | > > > > > > > > > > | 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 | }else if( eqOnly ){ assert( pOp[1].opcode==OP_IdxLT || pOp[1].opcode==OP_IdxGT ); pOp++; /* Skip the OP_IdxLt or OP_IdxGT that follows */ } break; } /* Opcode: Seek P1 P2 P3 P4 * ** Synopsis: intkey=r[P2] ** ** P1 is an open table cursor and P2 is a rowid integer. Arrange ** for P1 to move so that it points to the rowid given by P2. ** ** This is actually a deferred seek. Nothing actually happens until ** the cursor is used to read a record. That way, if no reads ** occur, no unnecessary I/O happens. ** ** P4 may contain an array of integers (type P4_INTARRAY) containing ** one entry for each column in the table P1 is open on. If so, then ** parameter P3 is a cursor open on a database index. If array entry ** a[i] is non-zero, then reading column (a[i]-1) from cursor P3 is ** equivalent to performing the deferred seek and then reading column i ** from P1. */ case OP_Seek: { /* in2 */ VdbeCursor *pC; assert( pOp->p1>=0 && pOp->p1<p->nCursor ); pC = p->apCsr[pOp->p1]; assert( pC!=0 ); assert( pC->eCurType==CURTYPE_BTREE ); assert( pC->uc.pCursor!=0 ); assert( pC->isTable ); pC->nullRow = 0; pIn2 = &aMem[pOp->p2]; pC->movetoTarget = sqlite3VdbeIntValue(pIn2); pC->deferredMoveto = 1; assert( pOp->p4type==P4_INTARRAY || pOp->p4.ai==0 ); pC->aAltMap = pOp->p4.ai; pC->pAltCursor = p->apCsr[pOp->p3]; break; } /* Opcode: Found P1 P2 P3 P4 * ** Synopsis: key=r[P3@P4] ** |
︙ | ︙ |
Changes to src/vdbeInt.h.
︙ | ︙ | |||
70 71 72 73 74 75 76 77 78 79 80 81 82 83 | ** * A b-tree cursor ** - In the main database or in an ephemeral database ** - On either an index or a table ** * A sorter ** * A virtual table ** * A one-row "pseudotable" stored in a single register */ struct VdbeCursor { u8 eCurType; /* One of the CURTYPE_* values above */ i8 iDb; /* Index of cursor database in db->aDb[] (or -1) */ u8 nullRow; /* True if pointing to a row with no data */ u8 deferredMoveto; /* A call to sqlite3BtreeMoveto() is needed */ u8 isTable; /* True for rowid tables. False for indexes */ #ifdef SQLITE_DEBUG | > | 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 | ** * A b-tree cursor ** - In the main database or in an ephemeral database ** - On either an index or a table ** * A sorter ** * A virtual table ** * A one-row "pseudotable" stored in a single register */ typedef struct VdbeCursor VdbeCursor; struct VdbeCursor { u8 eCurType; /* One of the CURTYPE_* values above */ i8 iDb; /* Index of cursor database in db->aDb[] (or -1) */ u8 nullRow; /* True if pointing to a row with no data */ u8 deferredMoveto; /* A call to sqlite3BtreeMoveto() is needed */ u8 isTable; /* True for rowid tables. False for indexes */ #ifdef SQLITE_DEBUG |
︙ | ︙ | |||
96 97 98 99 100 101 102 103 104 105 106 107 108 109 | VdbeSorter *pSorter; /* CURTYPE_SORTER. Sorter object */ } uc; Btree *pBt; /* Separate file holding temporary table */ KeyInfo *pKeyInfo; /* Info about index keys needed by index cursors */ int seekResult; /* Result of previous sqlite3BtreeMoveto() */ i64 seqCount; /* Sequence counter */ i64 movetoTarget; /* Argument to the deferred sqlite3BtreeMoveto() */ #ifdef SQLITE_ENABLE_COLUMN_USED_MASK u64 maskUsed; /* Mask of columns used by this cursor */ #endif /* Cached information about the header for the data record that the ** cursor is currently pointing to. Only valid if cacheStatus matches ** Vdbe.cacheCtr. Vdbe.cacheCtr will never take on the value of | > > | 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 | VdbeSorter *pSorter; /* CURTYPE_SORTER. Sorter object */ } uc; Btree *pBt; /* Separate file holding temporary table */ KeyInfo *pKeyInfo; /* Info about index keys needed by index cursors */ int seekResult; /* Result of previous sqlite3BtreeMoveto() */ i64 seqCount; /* Sequence counter */ i64 movetoTarget; /* Argument to the deferred sqlite3BtreeMoveto() */ VdbeCursor *pAltCursor; /* Set by OP_Seek */ int *aAltMap; /* Set by OP_Seek */ #ifdef SQLITE_ENABLE_COLUMN_USED_MASK u64 maskUsed; /* Mask of columns used by this cursor */ #endif /* Cached information about the header for the data record that the ** cursor is currently pointing to. Only valid if cacheStatus matches ** Vdbe.cacheCtr. Vdbe.cacheCtr will never take on the value of |
︙ | ︙ | |||
120 121 122 123 124 125 126 | const u8 *aRow; /* Data for the current row, if all on one page */ u32 *aOffset; /* Pointer to aType[nField] */ u32 aType[1]; /* Type values for all entries in the record */ /* 2*nField extra array elements allocated for aType[], beyond the one ** static element declared in the structure. nField total array slots for ** aType[] and nField+1 array slots for aOffset[] */ }; | < | 123 124 125 126 127 128 129 130 131 132 133 134 135 136 | const u8 *aRow; /* Data for the current row, if all on one page */ u32 *aOffset; /* Pointer to aType[nField] */ u32 aType[1]; /* Type values for all entries in the record */ /* 2*nField extra array elements allocated for aType[], beyond the one ** static element declared in the structure. nField total array slots for ** aType[] and nField+1 array slots for aOffset[] */ }; /* ** When a sub-program is executed (OP_Program), a structure of this type ** is allocated to store the current value of the program counter, as ** well as the current memory cell array and various other frame specific ** values stored in the Vdbe struct. When the sub-program is finished, ** these values are copied back to the Vdbe from the VdbeFrame structure, |
︙ | ︙ | |||
419 420 421 422 423 424 425 | /* ** Function prototypes */ void sqlite3VdbeError(Vdbe*, const char *, ...); void sqlite3VdbeFreeCursor(Vdbe *, VdbeCursor*); void sqliteVdbePopStack(Vdbe*,int); | | | 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 | /* ** Function prototypes */ void sqlite3VdbeError(Vdbe*, const char *, ...); void sqlite3VdbeFreeCursor(Vdbe *, VdbeCursor*); void sqliteVdbePopStack(Vdbe*,int); int sqlite3VdbeCursorMoveto(VdbeCursor**, int*); int sqlite3VdbeCursorRestore(VdbeCursor*); #if defined(SQLITE_DEBUG) || defined(VDBE_PROFILE) void sqlite3VdbePrintOp(FILE*, int, Op*); #endif u32 sqlite3VdbeSerialTypeLen(u32); u8 sqlite3VdbeOneByteSerialTypeLen(u8); u32 sqlite3VdbeSerialType(Mem*, int, u32*); |
︙ | ︙ |
Changes to src/vdbeaux.c.
︙ | ︙ | |||
3004 3005 3006 3007 3008 3009 3010 | ** MoveTo now. If no move is pending, check to see if the row has been ** deleted out from under the cursor and if it has, mark the row as ** a NULL row. ** ** If the cursor is already pointing to the correct row and that row has ** not been deleted out from under the cursor, then this routine is a no-op. */ | | > > > > > > | 3004 3005 3006 3007 3008 3009 3010 3011 3012 3013 3014 3015 3016 3017 3018 3019 3020 3021 3022 3023 3024 3025 3026 | ** MoveTo now. If no move is pending, check to see if the row has been ** deleted out from under the cursor and if it has, mark the row as ** a NULL row. ** ** If the cursor is already pointing to the correct row and that row has ** not been deleted out from under the cursor, then this routine is a no-op. */ int sqlite3VdbeCursorMoveto(VdbeCursor **pp, int *piCol){ VdbeCursor *p = *pp; if( p->eCurType==CURTYPE_BTREE ){ if( p->deferredMoveto ){ if( p->aAltMap && p->aAltMap[*piCol] ){ *pp = p->pAltCursor; *piCol = p->aAltMap[*piCol] - 1; return SQLITE_OK; } return handleDeferredMoveto(p); } if( sqlite3BtreeCursorHasMoved(p->uc.pCursor) ){ return handleMovedCursor(p); } } return SQLITE_OK; |
︙ | ︙ |
Changes to src/wherecode.c.
︙ | ︙ | |||
741 742 743 744 745 746 747 748 749 750 751 752 753 754 | (sHint.pIdx ? sHint.iIdxCur : sHint.iTabCur), 0, 0, (const char*)pExpr, P4_EXPR); } } #else # define codeCursorHint(A,B,C) /* No-op */ #endif /* SQLITE_ENABLE_CURSOR_HINTS */ /* ** Generate code for the start of the iLevel-th loop in the WHERE clause ** implementation described by pWInfo. */ Bitmask sqlite3WhereCodeOneLoopStart( WhereInfo *pWInfo, /* Complete information about the WHERE clause */ | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 | (sHint.pIdx ? sHint.iIdxCur : sHint.iTabCur), 0, 0, (const char*)pExpr, P4_EXPR); } } #else # define codeCursorHint(A,B,C) /* No-op */ #endif /* SQLITE_ENABLE_CURSOR_HINTS */ /* ** Cursor iCur is open on an intkey b-tree (a table). Register iRowid contains ** a rowid value just read from cursor iIdxCur, open on index pIdx. This ** function generates code to do a deferred seek of cursor iCur to the ** rowid stored in register iRowid. ** ** Normally, this is just: ** ** OP_Seek $iCur $iRowid ** ** However, if the scan currently being coded is a branch of an OR-loop and ** the statement currently being coded is a SELECT, then P3 of the OP_Seek ** is set to iIdxCur and P4 is set to point to an array of integers ** containing one entry for each column of the table cursor iCur is open ** on. For each table column, if the column is the i'th column of the ** index, then the corresponding array entry is set to (i+1). If the column ** does not appear in the index at all, the array entry is set to 0. */ static void codeDeferredSeek( WhereInfo *pWInfo, /* Where clause context */ Index *pIdx, /* Index scan is using */ int iCur, /* Cursor for IPK b-tree */ int iRowid, /* Register containing rowid to seek to */ int iIdxCur /* Index cursor */ ){ Parse *pParse = pWInfo->pParse; /* Parse context */ Vdbe *v = pParse->pVdbe; /* Vdbe to generate code within */ assert( iIdxCur>0 ); assert( pIdx->aiColumn[pIdx->nColumn-1]==-1 ); sqlite3VdbeAddOp3(v, OP_Seek, iCur, iRowid, iIdxCur); if( (pWInfo->wctrlFlags & WHERE_FORCE_TABLE) && sqlite3ParseToplevel(pParse)->writeMask==0 ){ int i; Table *pTab = pIdx->pTable; int *ai = (int*)sqlite3DbMallocZero(pParse->db, sizeof(int) * pTab->nCol); if( ai ){ for(i=0; i<pIdx->nColumn-1; i++){ assert( pIdx->aiColumn[i]<pTab->nCol ); if( pIdx->aiColumn[i]>=0 ) ai[pIdx->aiColumn[i]] = i+1; } sqlite3VdbeChangeP4(v, -1, (char*)ai, P4_INTARRAY); } } } /* ** Generate code for the start of the iLevel-th loop in the WHERE clause ** implementation described by pWInfo. */ Bitmask sqlite3WhereCodeOneLoopStart( WhereInfo *pWInfo, /* Complete information about the WHERE clause */ |
︙ | ︙ | |||
1228 1229 1230 1231 1232 1233 1234 | iRowidReg = ++pParse->nMem; sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, iRowidReg); sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg); if( pWInfo->eOnePass!=ONEPASS_OFF ){ sqlite3VdbeAddOp3(v, OP_NotExists, iCur, 0, iRowidReg); VdbeCoverage(v); }else{ | | | 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 | iRowidReg = ++pParse->nMem; sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, iRowidReg); sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg); if( pWInfo->eOnePass!=ONEPASS_OFF ){ sqlite3VdbeAddOp3(v, OP_NotExists, iCur, 0, iRowidReg); VdbeCoverage(v); }else{ codeDeferredSeek(pWInfo, pIdx, iCur, iRowidReg, iIdxCur); } }else if( iCur!=iIdxCur ){ Index *pPk = sqlite3PrimaryKeyIndex(pIdx->pTable); iRowidReg = sqlite3GetTempRange(pParse, pPk->nKeyCol); for(j=0; j<pPk->nKeyCol; j++){ k = sqlite3ColumnOfIndex(pIdx, pPk->aiColumn[j]); sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, k, iRowidReg+j); |
︙ | ︙ |
Changes to test/whereD.test.
︙ | ︙ | |||
152 153 154 155 156 157 158 | SELECT a, b FROM t3 WHERE (a=2 AND b=(SELECT y FROM t4 WHERE x='b')) OR (a=1 AND b=(SELECT y FROM t4 WHERE x='a')) } {2 two 1 one search 8} do_searchcount_test 3.5.1 { SELECT a, b FROM t3 WHERE (a=1 AND b='one') OR rowid=4 | | | 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 | SELECT a, b FROM t3 WHERE (a=2 AND b=(SELECT y FROM t4 WHERE x='b')) OR (a=1 AND b=(SELECT y FROM t4 WHERE x='a')) } {2 two 1 one search 8} do_searchcount_test 3.5.1 { SELECT a, b FROM t3 WHERE (a=1 AND b='one') OR rowid=4 } {1 one 2 two search 2} do_searchcount_test 3.5.2 { SELECT a, c FROM t3 WHERE (a=1 AND b='one') OR rowid=4 } {1 i 2 ii search 3} # Ticket [d02e1406a58ea02d] (2012-10-04) # LEFT JOIN with an OR in the ON clause causes segfault # |
︙ | ︙ | |||
267 268 269 270 271 272 273 274 275 | c0=1 or c1=1 or c2=1 or c3=1 or c4=1 or c5=1 or c6=1 or c7=1 or c8=1 or c9=1 or c10=1 or c11=1 or c12=1 or c13=1 or c14=1 or c15=1 or c16=1 or c17=1; } {1 {} {} {} {} {} {} {} {} {} {} {} {} {} {} 1 {} {}} finish_test | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 | c0=1 or c1=1 or c2=1 or c3=1 or c4=1 or c5=1 or c6=1 or c7=1 or c8=1 or c9=1 or c10=1 or c11=1 or c12=1 or c13=1 or c14=1 or c15=1 or c16=1 or c17=1; } {1 {} {} {} {} {} {} {} {} {} {} {} {} {} {} 1 {} {}} #------------------------------------------------------------------------- do_execsql_test 6.1 { CREATE TABLE x1(a, b, c, d, e); CREATE INDEX x1a ON x1(a); CREATE INDEX x1bc ON x1(b, c); CREATE INDEX x1cd ON x1(c, d); INSERT INTO x1 VALUES(1, 2, 3, 4, 'A'); INSERT INTO x1 VALUES(5, 6, 7, 8, 'B'); INSERT INTO x1 VALUES(9, 10, 11, 12, 'C'); INSERT INTO x1 VALUES(13, 14, 15, 16, 'D'); } do_searchcount_test 6.2.1 { SELECT e FROM x1 WHERE b=2 OR c=7; } {A B search 6} do_searchcount_test 6.2.2 { SELECT c FROM x1 WHERE b=2 OR c=7; } {3 7 search 4} do_searchcount_test 6.3.1 { SELECT e FROM x1 WHERE a=1 OR b=10; } {A C search 6} do_searchcount_test 6.3.2 { SELECT c FROM x1 WHERE a=1 OR b=10; } {3 11 search 5} do_searchcount_test 6.3.3 { SELECT rowid FROM x1 WHERE a=1 OR b=10; } {1 3 search 4} finish_test |