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-20 00:46:04+01:00, vvaintroub@wva. +3 -0
WL#3763 - Falcon supernodes
- Performance tweaking : replaces linear search in findSupernode by
binary search (measured 50% performance gain, even though the array
has only 16 elements)
- Corrected crash in split supernodes, if page being split has no
supernodes at all.
- Introduced #ifdef SUPERNODE_ON_DUPLICATE_KEYS on places that can be
enabled in the future, if/when supernodes works with
non-first occurence of duplicate key.
storage/falcon/IndexPage.cpp@stripped, 2008-03-20 00:45:59+01:00, vvaintroub@wva. +111 -45
- Use binary search in supernodes array. Can speed up performance to
of findSupernode ~50 percent and different findNode()'s to 15%
- Corrected crash in split supernodes, if no page being split contains
no supernodes at all.
- things that shall be corrected if supernodes on non-first occurence
of duplicate index key are allows are marked with
#ifdef SUPERNODES_ON_DUPLICATE_KEYS
storage/falcon/IndexPage.h@stripped, 2008-03-20 00:46:00+01:00, vvaintroub@wva. +1 -1
new output parameter in findSuperNode - tells if key was exactly matched
storage/falcon/IndexRootPage.cpp@stripped, 2008-03-20 00:46:00+01:00, vvaintroub@wva. +1 -2
Replaced unused output parameter for findNodeInLeaf with NULL pointer-
(findNodeInLeaf will do a lot more then necessary to fill this
structure,if it is not NULL)
diff -Nrup a/storage/falcon/IndexPage.cpp b/storage/falcon/IndexPage.cpp
--- a/storage/falcon/IndexPage.cpp 2008-03-17 19:38:49 +01:00
+++ b/storage/falcon/IndexPage.cpp 2008-03-20 00:45:59 +01:00
@@ -204,10 +204,14 @@ Btn* IndexPage::findNodeInLeaf(IndexKey
return nodes;
}
- super = findSupernode(level, indexKey, 0, 0);
+ bool hitSupernode;
+ super = findSupernode(level, indexKey, 0, 0, &hitSupernode);
IndexNode node(super);
+ if (hitSupernode)
+ goto exit;
+
for (;; node.getNext(bucketEnd))
{
if (node.node >= bucketEnd)
@@ -267,12 +271,11 @@ Btn* IndexPage::findNodeInLeaf(IndexKey
exit:
if (foundKey)
- foundKey->keyLength = priorLength;
-
- if (foundKey && foundKey->keyLength==0 && node.node == super && node.node != nodes)
{
- /* hit on left supernode, find prior key*/
- findPriorNodeForSupernode(node.node,foundKey);
+ if (hitSupernode) /* hit on left supernode, find prior key*/
+ findPriorNodeForSupernode(node.node,foundKey);
+ else
+ foundKey->keyLength = priorLength;
}
return node.node;
@@ -388,18 +391,20 @@ Bdb* IndexPage::splitIndexPageMiddle(Dbb
// Split supernodes
memset(split->superNodes,0, sizeof(split->superNodes));
int i = 0;
- for (i = 0; nodes + superNodes[i] < node.node; i++) ;
+ for (i = 0; i < SUPERNODES && superNodes[i]; i++)
+ if(nodes + superNodes[i] >= node.node)
+ break;
int j = 0;
for (; i < SUPERNODES && superNodes[i]; i++)
- {
+ {
short newVal = superNodes[i] - delta + newNodeSize;
ASSERT(newVal >=0);
if(newVal == 0)
continue;
split->superNodes[j++] = newVal;
superNodes[i] = 0;
- }
+ }
//validate(NULL);
//split->validate(NULL);
@@ -428,7 +433,12 @@ Btn* IndexPage::findNodeInBranch(IndexKe
Btn *bucketEnd = (Btn*) ((UCHAR*) this + length);
UCHAR *key = searchKey->key;
- Btn *super = findSupernode(level, searchKey, searchRecordNumber, 0);
+ bool hitSupernode;
+ Btn *super = findSupernode(level, searchKey, searchRecordNumber, 0, &hitSupernode);
+
+ if(hitSupernode)
+ return super;
+
Btn *prior = super;
for (IndexNode node(super) ; node.node < bucketEnd ; prior = node.node, node.getNext(bucketEnd))
@@ -489,7 +499,6 @@ void IndexPage::validate(void *before)
int supernodeCount = 0;
-
for (int i=0; i< SUPERNODES; i++)
{
if(superNodes[i] ==0)
@@ -595,8 +604,10 @@ 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;
@@ -779,6 +790,8 @@ int IndexPage::deleteNode(Dbb * dbb, Ind
return 0;
}
+
+
void IndexPage::printPage(IndexPage * page, int32 pageNumber, bool inversion)
{
LogLock logLock;
@@ -1264,18 +1277,23 @@ Btn* IndexPage::findInsertionPoint(int l
const UCHAR *keyEnd = key + indexKey->keyLength;
uint matchedOffset = 0;
uint priorLength = 0;
+ IndexNode node;
+ bool hitSupernode;
if (level && indexKey->recordNumber)
keyEnd -= indexKey->getAppendedRecordNumberLength();
+ Btn *super = findSupernode(level, indexKey,(level > 0)?indexKey->recordNumber:recordNumber ,from, &hitSupernode);
+ if (hitSupernode)
+ {
+ node.parseNode(super);
+ goto exit;
+ }
- Btn *super = findSupernode(level, indexKey,(level > 0)?indexKey->recordNumber:recordNumber ,from);
- IndexNode node;
if (super > from)
node.parseNode(super);
else
node.parseNode(from);
-
if (node.node != nodes)
{
@@ -1375,7 +1393,7 @@ Btn* IndexPage::findInsertionPoint(int l
expandedKey->keyLength = priorLength;
- if (expandedKey && expandedKey->keyLength==0 && node.node == super && node.node != nodes)
+ if (expandedKey && hitSupernode)
{
/* hit on start supernode, find prior key */
findPriorNodeForSupernode(node.node,expandedKey);
@@ -1389,6 +1407,7 @@ Btn* IndexPage::getEnd(void)
return (Btn*) ((UCHAR*) this + length);
}
+
/* 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)
{
@@ -1403,18 +1422,21 @@ bool IndexPage::checkAddSuperNode(int pa
if (superNodes[SUPERNODES-1]) // supernode array is full
return false;
-
int keyLen = indexKey->keyLength;
if (level)
keyLen -= indexKey->getAppendedRecordNumberLength();
+ 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;
// Find superNodes corresponding to insertion point
for(i = 0; i< SUPERNODES;i++)
@@ -1433,7 +1455,7 @@ bool IndexPage::checkAddSuperNode(int pa
IndexNode::nodeLength(offset, indexKey->keyLength - offset, recordNumber);
/* Ideal distance between supernodes , assume page will get 90% full*/
- int idealDistance = pageSize/(SUPERNODES+1)*9/10;
+ int idealDistance = pageSize/(SUPERNODES+1);
int distLeft, distRight;
@@ -1556,51 +1578,95 @@ bool IndexPage::deleteSupernode(Btn *whe
}
-// Given a key, find the maximum supernode smaller or equal to the search key
-// Optional parameter "after" tells to skip supernodes smaller than its value
+/* compare supernode to given key. Helper function, used for binary search in findSupernode*/
-Btn * IndexPage::findSupernode(int level, IndexKey *searchKey, int32 recordNumber, Btn *after)
+static int compareSuper(IndexNode *node, UCHAR *key, int keylen, int recordNumber, int level)
{
+ int result;
- int keylen = searchKey->keyLength;
- UCHAR* key = searchKey->key;
-
- Btn *retval = nodes;
+ int len = node->keyLength();
- for(int i=0; i< SUPERNODES && superNodes[i];i++)
- {
- Btn *pos = nodes +superNodes[i];
+ if (level)
+ len =- node->getAppendedRecordNumberLength();
- if (after && (pos < after))
- continue;
+ result = memcmp(node->key, key, MIN(keylen,len));
- IndexNode node(pos);
- int len = node.keyLength();
+ if (result == 0)
+ result = len - keylen;
- if (level)
- len =- node.getAppendedRecordNumberLength();
+ if (result == 0)
+ {
+ int number= (level == 0)? node->number : node->getAppendedRecordNumber();
+ if ( number < 0 || recordNumber == 0)
+ result = 1;
+ else
+ result = number - recordNumber;
+ }
+ return result;
+}
- int result = memcmp(key, node.key, MIN(keylen,len));
+// Given a key, find the maximum supernode smaller or equal to the search key
+// Optional parameter "after" tells to skip supernodes smaller than its value
+// Binary search is used for better speed
+Btn * IndexPage::findSupernode(int level, IndexKey *searchKey, int32 recordNumber, Btn *after, bool *found)
+{
- if (result == 0)
- result = keylen - len;
+ *found = false;
+ if (superNodes[0] == 0)
+ return nodes;
+ int keylen = searchKey->keyLength;
+ UCHAR* key = searchKey->key;
- if (result == 0)
+ int low = 0;
+ int high = SUPERNODES;
+ while (low < high)
+ {
+ int mid = (low + high)/2;
+
+ int result;
+ if (superNodes[mid] == 0)
+ result = 1; // after last supernode
+ else
{
- int number= (level == 0)? node.number : node.getAppendedRecordNumber();
- if ( (level > 0 && recordNumber == 0) || number == END_BUCKET)
+ Btn *pos = nodes +superNodes[mid];
+ if (after && (pos < after))
result = -1;
- else
- result = recordNumber - number;
+ else
+ {
+ IndexNode node(pos);
+ result = compareSuper(&node, key, keylen, recordNumber, level);
+ }
}
- if (result < 0)
+ if (result == 0)
+ {
+ low = mid;
+ *found = true;
break;
+ }
+ else if (result < 0)
+ low = mid + 1;
+ else
+ high = mid;
+ }
+
+ if (low == SUPERNODES)
+ return nodes + superNodes[SUPERNODES-1];
- retval = node.node;
+ if (!(*found))
+ {
+ IndexNode node(nodes + superNodes[low]);
+ *found = (compareSuper(&node, key, keylen, recordNumber, level) == 0);
}
- return retval;
+
+ if (*found)
+ return nodes + superNodes[low];
+
+ if (low == 0)
+ return nodes;
+
+ return nodes + superNodes[low-1];
}
diff -Nrup a/storage/falcon/IndexPage.h b/storage/falcon/IndexPage.h
--- a/storage/falcon/IndexPage.h 2008-03-17 19:38:50 +01:00
+++ b/storage/falcon/IndexPage.h 2008-03-20 00:46:00 +01:00
@@ -61,7 +61,7 @@ public:
void moveMemory(void *dst,void *src);
void addSupernode(Btn *where);
bool deleteSupernode(Btn *where);
- Btn* findSupernode(int level, IndexKey *searchKey, int32 recordNumber, Btn *after);
+ Btn* findSupernode(int level, IndexKey *searchKey, int32 recordNumber, Btn *after, bool *match);
Btn* findPriorNodeForSupernode(Btn *where,IndexKey *priorKey);
diff -Nrup a/storage/falcon/IndexRootPage.cpp b/storage/falcon/IndexRootPage.cpp
--- a/storage/falcon/IndexRootPage.cpp 2008-03-17 19:38:50 +01:00
+++ b/storage/falcon/IndexRootPage.cpp 2008-03-20 00:46:00 +01:00
@@ -138,9 +138,8 @@ bool IndexRootPage::addIndexEntry(Dbb *
for (;;)
{
- IndexKey priorKey;
page = (IndexPage*) bdb->buffer;
- Btn *node = page->findNodeInLeaf(key, &priorKey);
+ Btn *node = page->findNodeInLeaf(key, NULL);
Btn *bucketEnd = (Btn*) ((char*) page + page->length);
if (node < bucketEnd || page->nextPage == 0)
| Thread |
|---|
| • bk commit into 6.0 tree (vvaintroub:1.2600) WL#3763 | vvaintroub | 20 Mar |
