Closed kawasin73 closed 10 months ago
it uses OP_NewRowid
to generate a new rowid.
sqlite> explain insert into example(col1, col2) values (1, 2);
addr opcode p1 p2 p3 p4 p5 comment
---- ------------- ---- ---- ---- ------------- -- -------------
0 Init 0 8 0 0 Start at 8
1 OpenWrite 0 2 0 2 0 root=2 iDb=0; example
2 Integer 1 2 0 0 r[2]=1
3 Integer 2 3 0 0 r[3]=2
4 NewRowid 0 1 0 0 r[1]=rowid
5 MakeRecord 2 2 4 0 r[4]=mkrec(r[2..3])
6 Insert 0 4 1 example 57 intkey=r[1] data=r[4]
7 Halt 0 0 0 0
8 Transaction 0 1 1 0 1 usesStmtJournal=0
9 Goto 0 1 0 0
vdbe.c
/* Opcode: NewRowid P1 P2 P3 * *
** Synopsis: r[P2]=rowid
**
** Get a new integer record number (a.k.a "rowid") used as the key to a table.
** The record number is not previously used as a key in the database
** table that cursor P1 points to. The new record number is written
** written to register P2.
**
** If P3>0 then P3 is a register in the root frame of this VDBE that holds
** the largest previously generated record number. No new record numbers are
** allowed to be less than this value. When this value reaches its maximum,
** an SQLITE_FULL error is generated. The P3 register is updated with the '
** generated record number. This P3 mechanism is used to help implement the
** AUTOINCREMENT feature.
*/
case OP_NewRowid: { /* out2 */
/* The next rowid or record number (different terms for the same
** thing) is obtained in a two-step algorithm.
**
** First we attempt to find the largest existing rowid and add one
** to that. But if the largest existing rowid is already the maximum
** positive integer, we have to fall through to the second
** probabilistic algorithm
**
** The second algorithm is to select a rowid at random and see if
** it already exists in the table. If it does not exist, we have
** succeeded. If the random rowid does exist, we select a new one
** and try again, up to 100 times.
*/
if( !pC->useRandomRowid ){
rc = sqlite3BtreeLast(pC->uc.pCursor, &res);
if( rc!=SQLITE_OK ){
goto abort_due_to_error;
}
if( res ){
v = 1; /* IMP: R-61914-48074 */
}else{
assert( sqlite3BtreeCursorIsValid(pC->uc.pCursor) );
v = sqlite3BtreeIntegerKey(pC->uc.pCursor);
if( v>=MAX_ROWID ){
pC->useRandomRowid = 1;
}else{
v++; /* IMP: R-29538-34987 */
}
}
}
If the table is empty, use 1
as the new rowid.
rowid collision is checked by NotExists
vdbe operation.
sqlite> explain insert into example(rowid, col1, col2) values (1, 3, 4);
addr opcode p1 p2 p3 p4 p5 comment
---- ------------- ---- ---- ---- ------------- -- -------------
0 Init 0 14 0 0 Start at 14
1 OpenWrite 0 2 0 2 0 root=2 iDb=0; example
2 Integer 3 2 0 0 r[2]=3
3 Integer 4 3 0 0 r[3]=4
4 Integer 1 1 0 0 r[1]=1
5 NotNull 1 7 0 0 if r[1]!=NULL goto 7
6 NewRowid 0 1 0 0 r[1]=rowid
7 MustBeInt 1 0 0 0
8 Noop 0 0 0 0 uniqueness check for ROWID
9 NotExists 0 11 1 0 intkey=r[1]
10 Halt 2579 2 0 example.rowid 2
11 MakeRecord 2 2 4 0 r[4]=mkrec(r[2..3])
12 Insert 0 4 1 example 49 intkey=r[1] data=r[4]
13 Halt 0 0 0 0
14 Transaction 0 1 1 0 1 usesStmtJournal=0
15 Goto 0 1 0 0
OP_Insert
calls sqlite3BtreeInsert()
.
rc = sqlite3BtreeInsert(pC->uc.pCursor, &x,
(pOp->p5 & (OPFLAG_APPEND|OPFLAG_SAVEPOSITION|OPFLAG_PREFORMAT)),
seekResult
);
sqlite3BtreeInsert()
/*
** Insert a new record into the BTree. The content of the new record
** is described by the pX object. The pCur cursor is used only to
** define what table the record should be inserted into, and is left
** pointing at a random location.
**
** For a table btree (used for rowid tables), only the pX.nKey value of
** the key is used. The pX.pKey value must be NULL. The pX.nKey is the
** rowid or INTEGER PRIMARY KEY of the row. The pX.nData,pData,nZero fields
** hold the content of the row.
**
** For an index btree (used for indexes and WITHOUT ROWID tables), the
** key is an arbitrary byte sequence stored in pX.pKey,nKey. The
** pX.pData,nData,nZero fields must be zero.
**
** If the seekResult parameter is non-zero, then a successful call to
** sqlite3BtreeIndexMoveto() to seek cursor pCur to (pKey,nKey) has already
** been performed. In other words, if seekResult!=0 then the cursor
** is currently pointing to a cell that will be adjacent to the cell
** to be inserted. If seekResult<0 then pCur points to a cell that is
** smaller then (pKey,nKey). If seekResult>0 then pCur points to a cell
** that is larger than (pKey,nKey).
**
** If seekResult==0, that means pCur is pointing at some unknown location.
** In that case, this routine must seek the cursor to the correct insertion
** point for (pKey,nKey) before doing the insertion. For index btrees,
** if pX->nMem is non-zero, then pX->aMem contains pointers to the unpacked
** key values and pX->aMem can be used instead of pX->pKey to avoid having
** to decode the key.
*/
int sqlite3BtreeInsert(
BtCursor *pCur, /* Insert data into the table of this cursor */
const BtreePayload *pX, /* Content of the row to be inserted */
int flags, /* True if this is likely an append */
int seekResult /* Result of prior IndexMoveto() call */
){
sqlite3BtreeInsert()
inserts if entry for the nKey does not exist in the btree, overwrites the entry if exists.
TRACE(("INSERT: table=%d nkey=%lld ndata=%d page=%d %s\n",
pCur->pgnoRoot, pX->nKey, pX->nData, pPage->pgno,
loc==0 ? "overwrite" : "new entry"));
newCell = p->pBt->pTmpSpace;
rc = insertCell(pPage, idx, newCell, szNew, 0, 0);
insertCell() puts a content as overflow if the content does not fit in the page but in a new page.
The content exceeds overflow criteria should be trimmed into overflow pages before insertCell()
(e.g. fillInCell()
)
/*
** Insert a new cell on pPage at cell index "i". pCell points to the
** content of the cell.
**
** If the cell content will fit on the page, then put it there. If it
** will not fit, then make a copy of the cell content into pTemp if
** pTemp is not null. Regardless of pTemp, allocate a new entry
** in pPage->apOvfl[] and make it point to the cell content (either
** in pTemp or the original pCell) and also record its index.
** Allocating a new entry in pPage->aCell[] implies that
** pPage->nOverflow is incremented.
*/
static int insertCell(
The thresholds for overflow are calculated at lockBtree()
and stored into BtShared
.
/* maxLocal is the maximum amount of payload to store locally for
** a cell. Make sure it is small enough so that at least minFanout
** cells can will fit on one page. We assume a 10-byte page header.
** Besides the payload, the cell must store:
** 2-byte pointer to the cell
** 4-byte child pointer
** 9-byte nKey value
** 4-byte nData value
** 4-byte overflow page pointer
** So a cell consists of a 2-byte pointer, a header which is as much as
** 17 bytes long, 0 to N bytes of payload, and an optional 4 byte overflow
** page pointer.
*/
pBt->maxLocal = (u16)((pBt->usableSize-12)*64/255 - 23);
pBt->minLocal = (u16)((pBt->usableSize-12)*32/255 - 23);
pBt->maxLeaf = (u16)(pBt->usableSize - 35);
pBt->minLeaf = (u16)((pBt->usableSize-12)*32/255 - 23);
if( pBt->maxLocal>127 ){
pBt->max1bytePayload = 127;
}else{
pBt->max1bytePayload = (u8)pBt->maxLocal;
}
fillInCell()
looks doing the work.
/*
** Create the byte sequence used to represent a cell on page pPage
** and write that byte sequence into pCell[]. Overflow pages are
** allocated and filled in as necessary. The calling procedure
** is responsible for making sure sufficient space has been allocated
** for pCell[].
**
** Note that pCell does not necessary need to point to the pPage->aData
** area. pCell might point to some temporary storage. The cell will
** be constructed in this temporary area then copied into pPage->aData
** later.
*/
static int fillInCell(
Each cell is at least 4 bytes.
git blame -L 6850,6855 -- src/btree.c
Blaming lines: 100% (6/6), done.
6200c88123 (drh 2014-09-23 22:36:25 +0000 6850) testcase( n==3 );
6200c88123 (drh 2014-09-23 22:36:25 +0000 6851) testcase( n==4 );
6200c88123 (drh 2014-09-23 22:36:25 +0000 6852) if( n<4 ) n = 4;
6200c88123 (drh 2014-09-23 22:36:25 +0000 6853) *pnSize = n;
5e27e1dc49 (drh 2017-08-23 14:45:59 +0000 6854) assert( nSrc<=nPayload );
5e27e1dc49 (drh 2017-08-23 14:45:59 +0000 6855) testcase( nSrc<nPayload );
This was introduced by this commit which copy the logic from btreeParseCellPtr().
commit 6200c88123e5933dc81ec132d0c03f8bff86a07b
Author: drh <drh@noemail.net>
Date: Tue Sep 23 22:36:25 2014 +0000
Avoid calling btreeParseCellPtr() from within fillInCell() since most of
what btreeParseCellPtr() computes is ignored by fillInCell(). Instead, have
fillInCell() compute the values it needs inline. Performance improvement.
FossilOrigin-Name: 4147f6671e3faa8ddffab8387a6c7d9b5b962fc8
The original one looks to be introduced by this commit.
commit 9e572e608fd19ca7b173808061282304d16dd8b0
Author: drh <drh@noemail.net>
Date: Fri Apr 23 23:43:10 2004 +0000
Begin modifying the BTree code for the new version-3 file format.
This is a work-in-progress.
As of this check-in, SQLite will not build. (CVS 1306)
FossilOrigin-Name: ce0bbd3a7159e12c86c5cde6571d6668b234827b
https://github.com/sqlite/sqlite/commit/9e572e608fd19ca7b173808061282304d16dd8b0
According to the commit difference, the cells in pages were 4 byte aligned before.
/*
** All structures on a database page are aligned to 4-byte boundries.
** This routine rounds up a number of bytes to the next multiple of 4.
**
** This might need to change for computer architectures that require
** and 8-byte alignment boundry for structures.
*/
#define ROUNDUP(X) ((X+3) & ~3)
But from the version 3, There is no longer 4 byte alignment. But instead, minimal size allocation is 4 bytes because freeblock requires at least 4 bytes. freeSpace()
expect each space to freed was allocated by allocateSpace()
and has at least 4 bytes.
Cells in table pages must be at least 4 bytes ([payload length varint] [key varint] [record header size varint] [header of a column varint]). But index cells can be 3 bytes: ([payload length varint] [record header size varint] [header of a column varint (NULL, 1, 0)]).
There can be fragmented space which is less than 3 bytes when a freeblock is used for a new cell which has 1~3 bytes less than the freeblock. Those are counted as fragmented bytes and saved in the page header.
** Unused space within a btree page is collected into a linked list of
** freeblocks. Each freeblock is at least 4 bytes in size. The byte offset
** to the first freeblock is given in the header. Freeblocks occur in
** increasing order. Because a freeblock is 4 bytes in size, the minimum
** size allocation on a btree page is 4 bytes. Because a freeblock must be
** at least 4 bytes in size, any group of 3 or fewer unused bytes cannot
** exist on the freeblock chain. The total number of such fragmented bytes
** is recorded in the page header at offset 5.
The main logic is in balance()
called from sqlite3BtreeInsert()
.
/* If no error has occurred and pPage has an overflow cell, call balance()
** to redistribute the cells within the tree. Since balance() may move
** the cursor, zero the BtCursor.info.nSize and BTCF_ValidNKey
** variables.
**
** Previous versions of SQLite called moveToRoot() to move the cursor
** back to the root page as balance() used to invalidate the contents
** of BtCursor.apPage[] and BtCursor.aiIdx[]. Instead of doing that,
** set the cursor state to "invalid". This makes common insert operations
** slightly faster.
**
** There is a subtle but important optimization here too. When inserting
** multiple records into an intkey b-tree using a single cursor (as can
** happen while processing an "INSERT INTO ... SELECT" statement), it
** is advantageous to leave the cursor pointing to the last entry in
** the b-tree if possible. If the cursor is left pointing to the last
** entry in the table, and the next row inserted has an integer key
** larger than the largest existing key, it is possible to insert the
** row without seeking the cursor. This can be a big performance boost.
*/
pCur->info.nSize = 0;
if( pPage->nOverflow ){
assert( rc==SQLITE_OK );
pCur->curFlags &= ~(BTCF_ValidNKey);
rc = balance(pCur);
/* Must make sure nOverflow is reset to zero even if the balance()
** fails. Internal data structure corruption will result otherwise.
** Also, set the cursor state to invalid. This stops saveCursorPosition()
** from trying to save the current position of the cursor. */
pCur->pPage->nOverflow = 0;
pCur->eState = CURSOR_INVALID;
if( (flags & BTREE_SAVEPOSITION) && rc==SQLITE_OK ){
btreeReleaseAllCursorPages(pCur);
if( pCur->pKeyInfo ){
assert( pCur->pKey==0 );
pCur->pKey = sqlite3Malloc( pX->nKey );
if( pCur->pKey==0 ){
rc = SQLITE_NOMEM;
}else{
memcpy(pCur->pKey, pX->pKey, pX->nKey);
}
}
pCur->eState = CURSOR_REQUIRESEEK;
pCur->nKey = pX->nKey;
}
}
/*
** The page that pCur currently points to has just been modified in
** some way. This function figures out if this modification means the
** tree needs to be balanced, and if so calls the appropriate balancing
** routine. Balancing routines are:
**
** balance_quick()
** balance_deeper()
** balance_nonroot()
*/
static int balance(BtCursor *pCur){
{
/* In this case, call balance_nonroot() to redistribute cells
** between pPage and up to 2 of its sibling pages. This involves
** modifying the contents of pParent, which may cause pParent to
** become overfull or underfull. The next iteration of the do-loop
** will balance the parent page to correct this.
**
** If the parent page becomes overfull, the overflow cell or cells
** are stored in the pSpace buffer allocated immediately below.
** A subsequent iteration of the do-loop will deal with this by
** calling balance_nonroot() (balance_deeper() may be called first,
** but it doesn't deal with overflow cells - just moves them to a
** different page). Once this subsequent call to balance_nonroot()
** has completed, it is safe to release the pSpace buffer used by
** the previous call, as the overflow cell data will have been
** copied either into the body of a database page or into the new
** pSpace buffer passed to the latter call to balance_nonroot().
*/
u8 *pSpace = sqlite3PageMalloc(pCur->pBt->pageSize);
rc = balance_nonroot(pParent, iIdx, pSpace, iPage==1,
pCur->hints&BTREE_BULKLOAD);
if( pFree ){
/* If pFree is not NULL, it points to the pSpace buffer used
** by a previous call to balance_nonroot(). Its contents are
** now stored either on real database pages or within the
** new pSpace buffer, so it may be safely freed here. */
sqlite3PageFree(pFree);
}
/* The pSpace buffer will be freed after the next call to
** balance_nonroot(), or just before this function returns, whichever
** comes first. */
pFree = pSpace;
}
and
/*
** This routine redistributes cells on the iParentIdx'th child of pParent
** (hereafter "the page") and up to 2 siblings so that all pages have about the
** same amount of free space. Usually a single sibling on either side of the
** page are used in the balancing, though both siblings might come from one
** side if the page is the first or last child of its parent. If the page
** has fewer than 2 siblings (something which can only happen if the page
** is a root page or a child of a root page) then all available siblings
** participate in the balancing.
**
** The number of siblings of the page might be increased or decreased by
** one or two in an effort to keep pages nearly full but not over full.
**
** Note that when this routine is called, some of the cells on the page
** might not actually be stored in MemPage.aData[]. This can happen
** if the page is overfull. This routine ensures that all cells allocated
** to the page and its siblings fit into MemPage.aData[] before returning.
**
** In the course of balancing the page and its siblings, cells may be
** inserted into or removed from the parent page (pParent). Doing so
** may cause the parent page to become overfull or underfull. If this
** happens, it is the responsibility of the caller to invoke the correct
** balancing routine to fix this problem (see the balance() routine).
**
** If this routine fails for any reason, it might leave the database
** in a corrupted state. So if this routine fails, the database should
** be rolled back.
**
** The third argument to this function, aOvflSpace, is a pointer to a
** buffer big enough to hold one page. If while inserting cells into the parent
** page (pParent) the parent page becomes overfull, this buffer is
** used to store the parent's overflow cells. Because this function inserts
** a maximum of four divider cells into the parent page, and the maximum
** size of a cell stored within an internal node is always less than 1/4
** of the page-size, the aOvflSpace[] buffer is guaranteed to be large
** enough for all overflow cells.
**
** If aOvflSpace is set to a null pointer, this function returns
** SQLITE_NOMEM.
*/
static int balance_nonroot(
balance_nonroot() is a long function...
In this following block, it packs cells from the left-most sibling page.
/*
** Figure out the number of pages needed to hold all b.nCell cells.
** Store this number in "k". Also compute szNew[] which is the total
** size of all cells on the i-th page and cntNew[] which is the index
** in b.apCell[] of the cell that divides page i from page i+1.
** cntNew[k] should equal b.nCell.
**
** Values computed by this block:
**
** k: The total number of sibling pages
** szNew[i]: Spaced used on the i-th sibling page.
** cntNew[i]: Index in b.apCell[] and b.szCell[] for the first cell to
** the right of the i-th sibling page.
** usableSpace: Number of bytes of space available on each sibling.
**
*/
This is to make all pages have at least one cell.
/*
** The packing computed by the previous block is biased toward the siblings
** on the left side (siblings with smaller keys). The left siblings are
** always nearly full, while the right-most sibling might be nearly empty.
** The next block of code attempts to adjust the packing of siblings to
** get a better balance.
**
** This adjustment is more than an optimization. The packing above might
** be so out of balance as to be illegal. For example, the right-most
** sibling might be completely empty. This adjustment is not optional.
*/
pages are sorted in page id order so that sequential search of btree become faster.
/*
** Reassign page numbers so that the new pages are in ascending order.
** This helps to keep entries in the disk file in order so that a scan
** of the table is closer to a linear scan through the file. That in turn
** helps the operating system to deliver pages from the disk more rapidly.
**
** An O(N*N) sort algorithm is used, but since N is never more than NB+2
** (5), that is not a performance concern.
**
** When NB==3, this one optimization makes the database about 25% faster
** for large insertions and deletions.
*/
/* Now update the actual sibling pages. The order in which they are updated
** is important, as this code needs to avoid disrupting any page from which
** cells may still to be read. In practice, this means:
**
** (1) If cells are moving left (from apNew[iPg] to apNew[iPg-1])
** then it is not safe to update page apNew[iPg] until after
** the left-hand sibling apNew[iPg-1] has been updated.
**
** (2) If cells are moving right (from apNew[iPg] to apNew[iPg+1])
** then it is not safe to update page apNew[iPg] until after
** the right-hand sibling apNew[iPg+1] has been updated.
**
** If neither of the above apply, the page is safe to update.
**
** The iPg value in the following loop starts at nNew-1 goes down
** to 0, then back up to nNew-1 again, thus making two passes over
** the pages. On the initial downward pass, only condition (1) above
** needs to be tested because (2) will always be true from the previous
** step. On the upward pass, both conditions are always true, so the
** upwards pass simply processes pages that were missed on the downward
** pass.
*/
As a first step, insert an entry to a table without using free pages.
without swap buffers