com.bigdata.btree

Class TestLeafSplitShortestSeparatorKey

java.lang.Object

junit.framework.Assert

junit.framework.TestCase

junit.framework.TestCase2

com.bigdata.btree.TestLeafSplitShortestSeparatorKey

All Implemented Interfaces:

junit.framework.Test

public class TestLeafSplitShortestSeparatorKey
extends TestCase2

Version:

$Id$

Author:

Bryan Thompson

Nested Class Summary

Nested classes/interfaces inherited from class junit.framework.TestCase2

TestCase2.MyProperties, TestCase2.RandomType

Field Summary

Fields inherited from class junit.framework.TestCase2

_randomType, log

Constructor Summary

Constructors

Constructor and Description
TestLeafSplitShortestSeparatorKey()
TestLeafSplitShortestSeparatorKey(String name)

Method Summary

Methods

Modifier and Type	Method and Description
void	test_shortestSeparatorKey() On reflection, I suspect that this is an edge case which is simply not covered by the code.

Methods inherited from class junit.framework.TestCase2

assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEqualsWithinUlps, assertSameArray, assertSameArray, assertSameBigDecimal, assertSameBigDecimal, assertSameBigInteger, assertSameBigInteger, assertSameIterator, assertSameIterator, assertSameIteratorAnyOrder, assertSameIteratorAnyOrder, assertSameValue, assertSameValue, assertZeroUlps, assertZeroUlps, fail, getInnerCause, getNormalInt, getProjectBuildPath, getProperties, getRandomObject, getRandomObject, getRandomOrder, getRandomString, getTestInputStream, getTestResource, getTestResource, getUlps, getUlps, isDEBUG, isDEBUG, isINFO, isINFO, isInnerCause, logProperties

Methods inherited from class junit.framework.TestCase

assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertFalse, assertFalse, assertNotNull, assertNotNull, assertNotSame, assertNotSame, assertNull, assertNull, assertSame, assertSame, assertTrue, assertTrue, countTestCases, createResult, fail, fail, failNotEquals, failNotSame, failSame, format, getName, run, run, runBare, runTest, setName, setUp, tearDown, toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

TestLeafSplitShortestSeparatorKey

public TestLeafSplitShortestSeparatorKey()

TestLeafSplitShortestSeparatorKey

public TestLeafSplitShortestSeparatorKey(String name)

Parameters:

name -

Method Detail

test_shortestSeparatorKey

public void test_shortestSeparatorKey()

On reflection, I suspect that this is an edge case which is simply not covered by the code. I think that I can construct a unit test which will demonstrate the failure and then work out the logic for the edge case.

The exception is being thrown when a leaf is full. The leaf is in a temporary overflow condition. In order to split the leaf into a left sibling and a right sibling, the tuples in the leaf are divided into two by choosing the index of the first key which will enter the right sibling. A separator key is chosen which guides search into either the left sibling or the right sibling as appropriate and is then inserted into the parent. The assertion was tripped because the chosen separator key already existed in the parent. The code (Leaf#802) is attempting to choose the shortest separator key because that makes the keys in the nodes short, which reduces their on disk requirements. In fact, since we also use prefix compression (front-coding of the keys) there is less benefit to this than might otherwise be the case. Regardless, I believe that the source of the error is the failure to consider the existing separator key in the parent of the leaf which was directing search into the leaf. In this case, it appears that the shortest separator key when considering the last key in the left sibling and the first key in the right sibling is identical to the pre-existing separator key in the parent for the leaf before it is split. To fix this, I need to create a unit test with data in a tree which replicates the assertion as an existence proof of the problem and then change the logic to consider three keys when determining the shortest separator key -- the existing separator key in the parent node, the last key in the new left sibling, and the first key in the new right sibling. As a workaround, you can replace line 802:

 final byte[] separatorKey = BytesUtil.getSeparatorKey(//
         getKeys().get(splitIndex),//
         getKeys().get(splitIndex - 1)//
         );
 

with

 final byte[] separatorKey = getKeys().get(splitIndex);
 

This will use the first key in the new right sibling as the new separator key in the parent between the new left and right sibling. That should be correct, just a longer separator key.