From d4187c716c534617d261fa198c5467bd57feb975 Mon Sep 17 00:00:00 2001 From: drh Date: Mon, 30 Aug 2010 22:15:45 +0000 Subject: [PATCH] Provide hints to the btree layer during the creation of transient tables when it is possible for those tables to use a hash rather than a binary tree. No use is current made of those hints, though assert() statement verify their accuracy. FossilOrigin-Name: 4fead8e714c7e50a9d246467e62bc846ef6180a0 --- manifest | 38 ++++++++++++++++++++++++-------------- manifest.uuid | 2 +- src/btree.c | 19 +++++++++++++++++-- src/btree.h | 21 +++++++++++++-------- src/btreeInt.h | 1 + src/expr.c | 13 +++++++------ src/select.c | 2 ++ src/update.c | 1 + src/vdbe.c | 19 ++++++++++++------- src/vdbeInt.h | 1 + 10 files changed, 79 insertions(+), 38 deletions(-) diff --git a/manifest b/manifest index f221784ea5..67c35cbe5c 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,8 @@ -C When\sgenerating\ssqlite3.h,\sappend\sthe\scontents\sof\ssqlite3rtree.h. -D 2010-08-30T18:39:50 +-----BEGIN PGP SIGNED MESSAGE----- +Hash: SHA1 + +C Provide\shints\sto\sthe\sbtree\slayer\sduring\sthe\screation\sof\stransient\stables\nwhen\sit\sis\spossible\sfor\sthose\stables\sto\suse\sa\shash\srather\sthan\sa\sbinary\stree.\nNo\suse\sis\scurrent\smade\sof\sthose\shints,\sthough\sassert()\sstatement\sverify\ntheir\saccuracy. +D 2010-08-30T22:15:45 F Makefile.arm-wince-mingw32ce-gcc d6df77f1f48d690bd73162294bbba7f59507c72f F Makefile.in c599a15d268b1db2aeadea19df2adc3bf2eb6bee F Makefile.linux-gcc 91d710bdc4998cb015f39edf3cb314ec4f4d7e23 @@ -116,16 +119,16 @@ F src/auth.c 523da7fb4979469955d822ff9298352d6b31de34 F src/backup.c 8ff0b7018df253c7f30d3f9702b0b16f19209d5c F src/bitvec.c af50f1c8c0ff54d6bdb7a80e2fceca5a93670bef F src/btmutex.c 96a12f50f7a17475155971a241d85ec5171573ff -F src/btree.c e601b88b59aa11a110b9a9b0017c3f816f421643 -F src/btree.h b4ba2fdf6b64c7c376bdfffa826af6b786b151d9 -F src/btreeInt.h 5b034ff54800046cc5870605d683ac1f9134bd99 +F src/btree.c 175495bf9a377a5526c82450dc2ce069a974e61c +F src/btree.h 2d1a83ad509047e8cc314fda7e054f99ff52414d +F src/btreeInt.h c424f2f131cc61ddf130f9bd736b3df12c8a51f0 F src/build.c 5acc8a7d79ca81102a5d020fbafb7a4162f96d1d F src/callback.c da3c38d0ef5d7f04fae371e519bda61aa9cb1704 F src/complete.c dc1d136c0feee03c2f7550bafc0d29075e36deac F src/ctime.c 4f3aadad62c6c9f0d4e5a96718516ac4e3c598df F src/date.c 5dd8448a0bfea8d31fb14cff487d0c06ff8c8b20 F src/delete.c 7ed8a8c8b5f748ece92df173d7e0f7810c899ebd -F src/expr.c 9ee507c3dc6eaa5657cbd1dad026cdeda89c559f +F src/expr.c 21ad2494bd7c0826072216ea0f20db86a0a4ac82 F src/fault.c 160a0c015b6c2629d3899ed2daf63d75754a32bb F src/fkey.c 58bbf52c6ddd3f64ca40a3230f9e548a83a5cb16 F src/func.c caa6c5134106d95cced4db80ce3fdcdde4f6c8d4 @@ -171,7 +174,7 @@ F src/printf.c 8ae5082dd38a1b5456030c3755ec3a392cd51506 F src/random.c cd4a67b3953b88019f8cd4ccd81394a8ddfaba50 F src/resolve.c 1c0f32b64f8e3f555fe1f732f9d6f501a7f05706 F src/rowset.c 69afa95a97c524ba6faf3805e717b5b7ae85a697 -F src/select.c 8add6cab889fc02e1492eda8dba462ccf11f51dd +F src/select.c fb7008115d9ccd85f6b6934c15c204b7fe6bfc38 F src/shell.c 8517fc1f9c59ae4007e6cc8b9af91ab231ea2056 F src/sqlite.h.in 55498e6664eecf9a1db722d473445dbd210fe5f7 F src/sqlite3ext.h 69dfb8116af51b84a029cddb3b35062354270c89 @@ -218,13 +221,13 @@ F src/test_vfs.c 702e52636113f6b9721da90ef1bf26e07fff414d F src/test_wsd.c 41cadfd9d97fe8e3e4e44f61a4a8ccd6f7ca8fe9 F src/tokenize.c 604607d6813e9551cf5189d899e0a25c12681080 F src/trigger.c b8bedb9c0084ceb51a40f54fcca2ce048c8de852 -F src/update.c 1521162d20c2994af1fdc8833e1a88dae09052c8 +F src/update.c 227e6cd512108b84f69421fc6c7aa1b83d60d6e0 F src/utf.c 1baeeac91707a4df97ccc6141ec0f808278af685 F src/util.c 32aebf04c10e51ad3977a928b7416bed671b620b F src/vacuum.c 241a8386727c1497eba4955933356dfba6ff8c9f -F src/vdbe.c 42b14547868f65b6d2d534287dc8cea56e3685f7 +F src/vdbe.c 36d9521bfc257bc068ad0bdee8f341d96d858ff7 F src/vdbe.h 4de0efb4b0fdaaa900cf419b35c458933ef1c6d2 -F src/vdbeInt.h ffd68c4d4229227a5089bec53a1c635146177abc +F src/vdbeInt.h a247bd5448039e83394bf4179975b2ae0092874c F src/vdbeapi.c d0f4407e465f261780ad725c1caece7d66a6aa35 F src/vdbeaux.c c73bcefcebfd3d2cf91bf6a41ef0fb0d884814c6 F src/vdbeblob.c 258a6010ba7a82b72b327fb24c55790655689256 @@ -851,7 +854,14 @@ F tool/speedtest2.tcl ee2149167303ba8e95af97873c575c3e0fab58ff F tool/speedtest8.c 2902c46588c40b55661e471d7a86e4dd71a18224 F tool/speedtest8inst1.c 293327bc76823f473684d589a8160bde1f52c14e F tool/vdbe-compress.tcl d70ea6d8a19e3571d7ab8c9b75cba86d1173ff0f -P b6719ce32892a38b9b3dff07decdd6e94c01b3e2 -R e20fba69bef0c45289549a99445b5f1f -U dan -Z 95b89ac5a9e9b52985b26a8b5f89fc31 +P fc4d75370bad9021d01b76dbb1b8dde9ff223d2c +R ad3bc7fe837e4387bdc8b7d527b6677e +U drh +Z a25a6ea6fddbc5fd583dc3a0bce7dfb5 +-----BEGIN PGP SIGNATURE----- +Version: GnuPG v1.4.6 (GNU/Linux) + +iD8DBQFMfC2VoxKgR168RlERAgsLAJ96exRcGb6HNQhqw763Wtb1qZt8OACeKV37 +W21WHOHvQuRsjF2J4rqfHKU= +=0DbL +-----END PGP SIGNATURE----- diff --git a/manifest.uuid b/manifest.uuid index 1c9b562c9f..f9b12aa422 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -fc4d75370bad9021d01b76dbb1b8dde9ff223d2c \ No newline at end of file +4fead8e714c7e50a9d246467e62bc846ef6180a0 \ No newline at end of file diff --git a/src/btree.c b/src/btree.c index 4fc3a5ec45..0b4b6c683d 100644 --- a/src/btree.c +++ b/src/btree.c @@ -1726,6 +1726,13 @@ int sqlite3BtreeOpen( assert( db!=0 ); assert( sqlite3_mutex_held(db->mutex) ); + assert( (flags&0xff)==flags ); /* flags fit in 8 bits */ + + /* Only a BTREE_SINGLE database can be BTREE_UNORDERED */ + assert( (flags & BTREE_UNORDERED)==0 || (flags & BTREE_SINGLE)!=0 ); + + /* A BTREE_SINGLE database is always a temporary and/or ephemeral */ + assert( (flags & BTREE_SINGLE)==0 || isTempDb ); if( db->flags & SQLITE_NoReadlock ){ flags |= BTREE_NO_READLOCK; @@ -1828,6 +1835,7 @@ int sqlite3BtreeOpen( if( rc!=SQLITE_OK ){ goto btree_open_out; } + pBt->openFlags = flags; pBt->db = db; sqlite3PagerSetBusyhandler(pBt->pPager, btreeInvokeBusyHandler, pBt); p->pBt = pBt; @@ -6890,11 +6898,12 @@ int sqlite3BtreeDelete(BtCursor *pCur){ ** BTREE_INTKEY|BTREE_LEAFDATA Used for SQL tables with rowid keys ** BTREE_ZERODATA Used for SQL indices */ -static int btreeCreateTable(Btree *p, int *piTable, int flags){ +static int btreeCreateTable(Btree *p, int *piTable, int createTabFlags){ BtShared *pBt = p->pBt; MemPage *pRoot; Pgno pgnoRoot; int rc; + int ptfFlags; /* Page-type flage for the root page of new table */ assert( sqlite3BtreeHoldsMutex(p) ); assert( pBt->inTransaction==TRANS_WRITE ); @@ -7013,8 +7022,14 @@ static int btreeCreateTable(Btree *p, int *piTable, int flags){ } #endif assert( sqlite3PagerIswriteable(pRoot->pDbPage) ); - zeroPage(pRoot, flags | PTF_LEAF); + if( createTabFlags & BTREE_INTKEY ){ + ptfFlags = PTF_INTKEY | PTF_LEAFDATA | PTF_LEAF; + }else{ + ptfFlags = PTF_ZERODATA | PTF_LEAF; + } + zeroPage(pRoot, ptfFlags); sqlite3PagerUnref(pRoot->pDbPage); + assert( (pBt->openFlags & BTREE_SINGLE)==0 || pgnoRoot==2 ); *piTable = (int)pgnoRoot; return SQLITE_OK; } diff --git a/src/btree.h b/src/btree.h index c989307aad..39af03f961 100644 --- a/src/btree.h +++ b/src/btree.h @@ -67,12 +67,11 @@ int sqlite3BtreeOpen( ** NOTE: These values must match the corresponding PAGER_ values in ** pager.h. */ -#define BTREE_OMIT_JOURNAL 1 /* Do not use journal. No argument */ +#define BTREE_OMIT_JOURNAL 1 /* Do not create or use a rollback journal */ #define BTREE_NO_READLOCK 2 /* Omit readlocks on readonly files */ -#define BTREE_MEMORY 4 /* In-memory DB. No argument */ -#define BTREE_READONLY 8 /* Open the database in read-only mode */ -#define BTREE_READWRITE 16 /* Open for both reading and writing */ -#define BTREE_CREATE 32 /* Create the database if it does not exist */ +#define BTREE_MEMORY 4 /* This is an in-memory DB */ +#define BTREE_SINGLE 8 /* The file contains at most 1 b-tree */ +#define BTREE_UNORDERED 16 /* Use of a hash implementation is OK */ int sqlite3BtreeClose(Btree*); int sqlite3BtreeSetCacheSize(Btree*,int); @@ -108,11 +107,17 @@ int sqlite3BtreeCopyFile(Btree *, Btree *); int sqlite3BtreeIncrVacuum(Btree *); /* The flags parameter to sqlite3BtreeCreateTable can be the bitwise OR -** of the following flags: +** of the flags shown below. +** +** Every SQLite table must have either BTREE_INTKEY or BTREE_BLOBKEY set. +** With BTREE_INTKEY, the table key is a 64-bit integer and arbitrary data +** is stored in the leaves. (BTREE_INTKEY is used for SQL tables.) With +** BTREE_BLOBKEY, the key is an arbitrary BLOB and no content is stored +** anywhere - the key is the content. (BTREE_BLOBKEY is used for SQL +** indices.) */ #define BTREE_INTKEY 1 /* Table has only 64-bit signed integer keys */ -#define BTREE_ZERODATA 2 /* Table has keys only - no data */ -#define BTREE_LEAFDATA 4 /* Data stored in leaves only. Implies INTKEY */ +#define BTREE_BLOBKEY 2 /* Table has keys only - no data */ int sqlite3BtreeDropTable(Btree*, int, int*); int sqlite3BtreeClearTable(Btree*, int, int*); diff --git a/src/btreeInt.h b/src/btreeInt.h index 7b46bcebbd..59597faecb 100644 --- a/src/btreeInt.h +++ b/src/btreeInt.h @@ -409,6 +409,7 @@ struct BtShared { u8 pageSizeFixed; /* True if the page size can no longer be changed */ u8 secureDelete; /* True if secure_delete is enabled */ u8 initiallyEmpty; /* Database is empty at start of transaction */ + u8 openFlags; /* Flags to sqlite3BtreeOpen() */ #ifndef SQLITE_OMIT_AUTOVACUUM u8 autoVacuum; /* True if auto-vacuum is enabled */ u8 incrVacuum; /* True if incr-vacuum is enabled */ diff --git a/src/expr.c b/src/expr.c index 33864b2dae..a23a7b197d 100644 --- a/src/expr.c +++ b/src/expr.c @@ -1535,8 +1535,8 @@ int sqlite3FindInIndex(Parse *pParse, Expr *pX, int *prNotFound){ #endif /* -** Generate code for scalar subqueries used as an expression -** and IN operators. Examples: +** Generate code for scalar subqueries used as a subquery expression, EXISTS, +** or IN operators. Examples: ** ** (SELECT a FROM b) -- subquery ** EXISTS (SELECT a FROM b) -- EXISTS subquery @@ -1599,10 +1599,10 @@ int sqlite3CodeSubselect( switch( pExpr->op ){ case TK_IN: { - char affinity; - KeyInfo keyInfo; - int addr; /* Address of OP_OpenEphemeral instruction */ - Expr *pLeft = pExpr->pLeft; + char affinity; /* Affinity of the LHS of the IN */ + KeyInfo keyInfo; /* Keyinfo for the generated table */ + int addr; /* Address of OP_OpenEphemeral instruction */ + Expr *pLeft = pExpr->pLeft; /* the LHS of the IN operator */ if( rMayHaveNull ){ sqlite3VdbeAddOp2(v, OP_Null, 0, rMayHaveNull); @@ -1625,6 +1625,7 @@ int sqlite3CodeSubselect( */ pExpr->iTable = pParse->nTab++; addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pExpr->iTable, !isRowid); + if( rMayHaveNull==0 ) sqlite3VdbeChangeP5(v, BTREE_UNORDERED); memset(&keyInfo, 0, sizeof(keyInfo)); keyInfo.nField = 1; diff --git a/src/select.c b/src/select.c index 17184b675a..55d771ecf4 100644 --- a/src/select.c +++ b/src/select.c @@ -1503,6 +1503,7 @@ static int multiSelect( if( dest.eDest==SRT_EphemTab ){ assert( p->pEList ); sqlite3VdbeAddOp2(v, OP_OpenEphemeral, dest.iParm, p->pEList->nExpr); + sqlite3VdbeChangeP5(v, BTREE_UNORDERED); dest.eDest = SRT_Table; } @@ -3769,6 +3770,7 @@ int sqlite3Select( pKeyInfo = keyInfoFromExprList(pParse, p->pEList); sqlite3VdbeAddOp4(v, OP_OpenEphemeral, distinct, 0, 0, (char*)pKeyInfo, P4_KEYINFO_HANDOFF); + sqlite3VdbeChangeP5(v, BTREE_UNORDERED); }else{ distinct = -1; } diff --git a/src/update.c b/src/update.c index 44f047b488..8bf58d7666 100644 --- a/src/update.c +++ b/src/update.c @@ -638,6 +638,7 @@ static void updateVirtualTable( assert( v ); ephemTab = pParse->nTab++; sqlite3VdbeAddOp2(v, OP_OpenEphemeral, ephemTab, pTab->nCol+1+(pRowid!=0)); + sqlite3VdbeChangeP5(v, BTREE_UNORDERED); /* fill the ephemeral table */ diff --git a/src/vdbe.c b/src/vdbe.c index dc9b2e2b50..90c1d784e2 100644 --- a/src/vdbe.c +++ b/src/vdbe.c @@ -3006,6 +3006,7 @@ case OP_OpenWrite: { pCur = allocateCursor(p, pOp->p1, nField, iDb, 1); if( pCur==0 ) goto no_mem; pCur->nullRow = 1; + pCur->isOrdered = 1; rc = sqlite3BtreeCursor(pX, p2, wrFlag, pKeyInfo, pCur->pCursor); pCur->pKeyInfo = pKeyInfo; @@ -3056,7 +3057,7 @@ case OP_OpenWrite: { case OP_OpenAutoindex: case OP_OpenEphemeral: { VdbeCursor *pCx; - static const int openFlags = + static const int vfsFlags = SQLITE_OPEN_READWRITE | SQLITE_OPEN_CREATE | SQLITE_OPEN_EXCLUSIVE | @@ -3067,20 +3068,21 @@ case OP_OpenEphemeral: { pCx = allocateCursor(p, pOp->p1, pOp->p2, -1, 1); if( pCx==0 ) goto no_mem; pCx->nullRow = 1; - rc = sqlite3BtreeOpen(0, db, &pCx->pBt, BTREE_OMIT_JOURNAL, openFlags); + rc = sqlite3BtreeOpen(0, db, &pCx->pBt, + BTREE_OMIT_JOURNAL | BTREE_SINGLE | pOp->p5, vfsFlags); if( rc==SQLITE_OK ){ rc = sqlite3BtreeBeginTrans(pCx->pBt, 1); } if( rc==SQLITE_OK ){ /* If a transient index is required, create it by calling - ** sqlite3BtreeCreateTable() with the BTREE_ZERODATA flag before + ** sqlite3BtreeCreateTable() with the BTREE_BLOBKEY flag before ** opening it. If a transient table is required, just use the - ** automatically created table with root-page 1 (an INTKEY table). + ** automatically created table with root-page 1 (an BLOB_INTKEY table). */ if( pOp->p4.pKeyInfo ){ int pgno; assert( pOp->p4type==P4_KEYINFO ); - rc = sqlite3BtreeCreateTable(pCx->pBt, &pgno, BTREE_ZERODATA); + rc = sqlite3BtreeCreateTable(pCx->pBt, &pgno, BTREE_BLOBKEY); if( rc==SQLITE_OK ){ assert( pgno==MASTER_ROOT+1 ); rc = sqlite3BtreeCursor(pCx->pBt, pgno, 1, @@ -3094,6 +3096,7 @@ case OP_OpenEphemeral: { pCx->isTable = 1; } } + pCx->isOrdered = (pOp->p5!=BTREE_UNORDERED); pCx->isIndex = !pCx->isTable; break; } @@ -3209,6 +3212,7 @@ case OP_SeekGt: { /* jump, in3 */ assert( OP_SeekLe == OP_SeekLt+1 ); assert( OP_SeekGe == OP_SeekLt+2 ); assert( OP_SeekGt == OP_SeekLt+3 ); + assert( pC->isOrdered ); if( pC->pCursor!=0 ){ oc = pOp->opcode; pC->nullRow = 0; @@ -4362,6 +4366,7 @@ case OP_IdxGE: { /* jump */ assert( pOp->p1>=0 && pOp->p1nCursor ); pC = p->apCsr[pOp->p1]; assert( pC!=0 ); + assert( pC->isOrdered ); if( ALWAYS(pC->pCursor!=0) ){ assert( pC->deferredMoveto==0 ); assert( pOp->p5==0 || pOp->p5==1 ); @@ -4514,9 +4519,9 @@ case OP_CreateTable: { /* out2-prerelease */ assert( pDb->pBt!=0 ); if( pOp->opcode==OP_CreateTable ){ /* flags = BTREE_INTKEY; */ - flags = BTREE_LEAFDATA|BTREE_INTKEY; + flags = BTREE_INTKEY; }else{ - flags = BTREE_ZERODATA; + flags = BTREE_BLOBKEY; } rc = sqlite3BtreeCreateTable(pDb->pBt, &pgno, flags); pOut->u.i = pgno; diff --git a/src/vdbeInt.h b/src/vdbeInt.h index 4a19f14c2d..c6096e1654 100644 --- a/src/vdbeInt.h +++ b/src/vdbeInt.h @@ -57,6 +57,7 @@ struct VdbeCursor { Bool deferredMoveto; /* A call to sqlite3BtreeMoveto() is needed */ Bool isTable; /* True if a table requiring integer keys */ Bool isIndex; /* True if an index containing keys only - no data */ + Bool isOrdered; /* True if the underlying table is BTREE_UNORDERED */ i64 movetoTarget; /* Argument to the deferred sqlite3BtreeMoveto() */ Btree *pBt; /* Separate file holding temporary table */ int pseudoTableReg; /* Register holding pseudotable content. */ -- 2.47.2