Below is the list of changes that have just been committed into a local
6.0 repository of vvaintroub. When vvaintroub does a push these changes
will be propagated to the main repository and, within 24 hours after the
push, to the public repository.
For information on how to access the public repository
see http://dev.mysql.com/doc/mysql/en/installing-source-tree.html
ChangeSet@stripped, 2008-03-28 07:40:07+01:00, vvaintroub@wva. +2 -0
WL#3763: Supernodes
- If insert is done in decreasing order of values, no supernodes were
created. Now fixed - if index node is inserted at the start
of the page, next node can become supernode, if the gap between the
start of the page and first supernode is too large.
- Allow supernode on duplicate keys.
- Do not always delete supernode if previous node is deleted, but check
whether saving it makes sense.
storage/falcon/IndexPage.cpp@stripped, 2008-03-28 07:40:03+01:00, vvaintroub@wva. +76 -40
- If insert is done in decreasing order of values, no supernodes were
created. Now fixed - if index node is inserted at the start
of the page, next node can become supernode, if the gap between the
start of the page and first supernode is too large.
- Allow supernode on duplicate keys.
- Do not always delete supernode if previous node is deleted, but check
whether saving it makes sense.
storage/falcon/IndexPage.h@stripped, 2008-03-28 07:40:03+01:00, vvaintroub@wva. +1 -1
checkAddSuperNode got an additional parameter, to indicate that node
*after* insertion point shall be made supernode.
diff -Nrup a/storage/falcon/IndexPage.cpp b/storage/falcon/IndexPage.cpp
--- a/storage/falcon/IndexPage.cpp 2008-03-22 15:52:15 +01:00
+++ b/storage/falcon/IndexPage.cpp 2008-03-28 07:40:03 +01:00
@@ -41,6 +41,9 @@
static const char THIS_FILE[]=__FILE__;
#endif
+// Do not make supernode, if there is too much loss for prefix compression
+#define SUPERNODE_COMPRESSION_LOSS_LIMIT(pageSize) (pageSize)/(SUPERNODES+1)/2
+
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
@@ -87,8 +90,9 @@ AddNodeResult IndexPage::addNode (Dbb *d
int offset1 = computePrefix (priorKey, indexKey);
// Check whether inserted node shall be supernode. If yes, does not compress the prefix.
- bool addSuper = checkAddSuperNode(dbb->pageSize, node, indexKey, recordNumber, offset1);
- if (addSuper)
+ bool makeNextSuper;
+ bool makeSuper = checkAddSuperNode(dbb->pageSize, node, indexKey, recordNumber, offset1, &makeNextSuper);
+ if (makeSuper)
offset1 = 0;
int length1 = indexKey->keyLength - offset1;
@@ -105,6 +109,12 @@ AddNodeResult IndexPage::addNode (Dbb *d
{
node->expandKey (nextKey);
offset2 = computePrefix(indexKey, nextKey);
+
+ if (offset2 > SUPERNODE_COMPRESSION_LOSS_LIMIT(dbb->pageSize))
+ makeNextSuper = false; // compresses well, no supenode
+ else if (makeNextSuper)
+ offset2 = 0; // we'll make supernode, so don't prefix compress
+
int deltaOffset = offset2 - node->offset;
if (node->length >= 128 && (node->length - deltaOffset) < 128)
@@ -138,10 +148,9 @@ AddNodeResult IndexPage::addNode (Dbb *d
index, recordNumber, (CHAR*) node - (CHAR*) page);
***/
- // Check whether there was a supernode at the insertion point
- // If yes, delete it fow now. Supernode will be reinstalled at another position later,
- // unless it gets prefix-compressed.
- bool wasSuper = deleteSupernode(node->node);
+ // Delete supernode at the insertion point, if there was one
+ // It might be reinstalled later
+ deleteSupernode(node->node);
// Slide tail of bucket forward to make room
@@ -158,17 +167,19 @@ AddNodeResult IndexPage::addNode (Dbb *d
// Insert new node
IndexNode newNode;
+
+ if (makeSuper)
+ addSupernode(node->node);
+
newNode.insert (node->node, offset1, length1, key, recordNumber);
// If necessary, rebuild next node
- if (wasSuper && (offset2 == 0))
+ if (makeNextSuper)
addSupernode(newNode.nextNode);
if (offset2 >= 0)
newNode.insert (newNode.nextNode, offset2, nextKey->keyLength - offset2, nextKey->key, nextNumber);
- if (addSuper)
- addSupernode(node->node);
@@ -585,14 +596,10 @@ void IndexPage::validate(void *before)
FATAL ("Index validate: record numbers out of order");
- bool equalKeys = (priorKeyLength == keyLength);
for (UCHAR *p = node.key, *q = key + node.offset, *end = key + l; q < end; p++, q++)
{
if (*p > *q) // current > previous, good
- {
- equalKeys = false;
break;
- }
else if (*p == *q) // current == previous, good so far
continue;
else if (*p < *q) // current < previous, bad
@@ -604,10 +611,7 @@ void IndexPage::validate(void *before)
FATAL("Mal-formed index page");
}
}
-#ifndef SUPERNODES_ON_DUPLICATE_KEYS
- if( isSuper && equalKeys)
- FATAL("supernode key equal to previous node");
-#endif
+
node.expandKey(key);
priorKeyLength = keyLength;
priorRecordNumber = recordNumber;
@@ -754,12 +758,19 @@ int IndexPage::deleteNode(Dbb * dbb, Ind
int prefix = computePrefix(&priorKey, &nextKey);
// Check whether next node is a supernode.
- // If yes, delete it for now. Supernode will be reinstalled later,
- // if it does not get prefix-compressed.
+ // If yes, delete it for now. Supernode will be reinstalled
+ // at current position, if it makes sense.
+
+ Btn *supernodePosition = 0;
- Btn *nextSuper = 0;
- if(deleteSupernode(node.nextNode) && (prefix == 0) && node.node != nodes)
- nextSuper = node.node;
+ if(deleteSupernode(node.nextNode))
+ {
+ if (checkAddSuperNode(dbb->pageSize, &node, &nextKey, next.getNumber(), prefix, 0))
+ {
+ prefix = 0;
+ supernodePosition = node.node;
+ }
+ }
int32 num = next.getNumber();
node.insert(node.node, prefix, nextKey.keyLength - prefix, nextKey.key, num);
@@ -771,8 +782,8 @@ int IndexPage::deleteNode(Dbb * dbb, Ind
if (tailLength > 0)
moveMemory(newTail, tail);
- if (nextSuper)
- addSupernode(nextSuper);
+ if (supernodePosition)
+ addSupernode(supernodePosition);
length = (int) ((char*) newTail + tailLength - (char*) this);
//validate(NULL);
@@ -809,11 +820,24 @@ void IndexPage::printPage(IndexPage * pa
Btn *end = (Btn*) ((UCHAR*) page + page->length);
IndexNode node (page);
+ Log::debug("Supernodes:");
+ for (int i=0; i < SUPERNODES && page->superNodes[i]; i++)
+ Log::debug("%d ",page->superNodes[i]);
+ Log::debug("\n");
+
+ int superIdx = 0;
+
for (; node.node < end; node.getNext(end))
{
- Log::debug (" %d. offset %d, length %d, %d: ",
- (char*) node.node - (char*) page,
- node.offset, node.length, node.getNumber());
+ bool isSuper = false;
+ if (superIdx < SUPERNODES && (node.node - page->nodes == page->superNodes[superIdx]) )
+ {
+ superIdx++;
+ isSuper = true;
+ }
+ Log::debug (" %d%s. offset %d, length %d, %d: ",
+ (char*) node.node - (char*) page, (isSuper ? "(super)" : ""),
+ node.offset, node.length, node.getNumber());
node.expandKey (key);
node.printKey ("", key, inversion);
}
@@ -1172,9 +1196,7 @@ Bdb* IndexPage::splitIndexPageEnd(Dbb *d
split->appendNode(insertKey, recordNumber, dbb->pageSize);
split->appendNode(&rolloverKey, rolloverNumber, dbb->pageSize);
//split->validate(NULL);
- //printf ("splitIndexPage: level %d, %d -> %d\n", level, bdb->pageNumber, nextPage);
- //validate( splitBdb->buffer);
-
+
if (dbb->debug & (DEBUG_PAGES | DEBUG_SPLIT_PAGE))
{
printPage (this, 0, false);
@@ -1411,14 +1433,28 @@ Btn* IndexPage::getEnd(void)
/* During node insertion, check whether supernode should be added at insertion point */
-bool IndexPage::checkAddSuperNode(int pageSize, IndexNode* node, IndexKey *indexKey, int recordNumber, int offset)
+bool IndexPage::checkAddSuperNode(int pageSize, IndexNode* node, IndexKey *indexKey,
+ int recordNumber, int offset, bool *makeNextSuper)
{
+
+
Btn *insertionPoint = node->node;
- if (insertionPoint == nodes) // no supernode at the start of the page
- return false;
+ if (makeNextSuper)
+ *makeNextSuper = false;
- if (offset >= pageSize/SUPERNODES/2) //compression is too good, no super
+ if (insertionPoint == nodes)
+ {
+
+ // Make supernode at the following node, if the
+ // gap from the start of the page to the first supernode is too large.
+ if (makeNextSuper && superNodes[0] > pageSize/(SUPERNODES+1) && !superNodes[SUPERNODES-1])
+ *makeNextSuper = true;
+
+ return false; // no supernode at the start of the page
+ }
+
+ if (offset >= SUPERNODE_COMPRESSION_LOSS_LIMIT(pageSize)) //compression is too good, no super
return false;
if (superNodes[SUPERNODES-1]) // supernode array is full
@@ -1432,11 +1468,6 @@ bool IndexPage::checkAddSuperNode(int pa
if (keyLen == 0)
return false;
-#ifndef SUPERNODES_ON_DUPLICATE_KEYS
- if (keyLen == offset) // no supernode on duplicate entry (yet)
- return false;
-#endif
-
int position = (int)(insertionPoint - nodes);
int i;
@@ -1451,12 +1482,17 @@ bool IndexPage::checkAddSuperNode(int pa
// Avoid 2 superNodes adjacent to each other
if (nodes + superNodes[i] == insertionPoint)
+ {
+ // Retain existing supernode
+ if (makeNextSuper)
+ *makeNextSuper = true;
return false;
+ }
int nodeLen =
IndexNode::nodeLength(offset, indexKey->keyLength - offset, recordNumber);
- /* Ideal distance between supernodes , assume page will get 90% full*/
+ /* Ideal distance between supernodes*/
int idealDistance = pageSize/(SUPERNODES+1);
diff -Nrup a/storage/falcon/IndexPage.h b/storage/falcon/IndexPage.h
--- a/storage/falcon/IndexPage.h 2008-03-20 21:56:50 +01:00
+++ b/storage/falcon/IndexPage.h 2008-03-28 07:40:03 +01:00
@@ -57,7 +57,7 @@ public:
void validateNodes (Dbb *dbb, Validation *validation, Bitmap *children, int32 parentPageNumber);
void validate (Dbb *dbb, Validation *validation, Bitmap *pages, int32 parentPageNumber);
void validate(void *before);
- bool checkAddSuperNode(int pageSize, IndexNode* node, IndexKey *indexKey, int recordNumber, int offset);
+ bool checkAddSuperNode(int pageSize, IndexNode* node, IndexKey *indexKey, int recordNumber, int offset, bool *makeNextSuper);
void moveMemory(void *dst,void *src);
void addSupernode(Btn *where);
bool deleteSupernode(Btn *where);
| Thread |
|---|
| • bk commit into 6.0 tree (vvaintroub:1.2608) WL#3763 | vvaintroub | 28 Mar |
