The current implementation of page split in the BTree (and even the RTree),
distribute the records in half between the left and right pages as opposed to
distributing them based on their sizes. As a result, there is a chance that
after distributing the records, there is not enough space to insert the new
record in the designated page, still. One solution to the problem is to do a
double split. In other words, once we split the page, we should check if there
is enough space as opposed to blindingly inserting the record in either pages.
If there is not enough space, then we restart traversing the tree. There could
be possible optimization to avoid restarting the traversal but it could
complicate the traversal logic. So assuming this case should not occur many
often, restarting from root should be OK.
What steps will reproduce the problem?
1. Use the attached proof of concept example by copying the code and placing it
inside the file OrderedIndexExamplesTest.
2. Run the test case BTreeExamplesTest
What is the expected output? What do you see instead?
All the 6 records should be inserted sucessfuly since neither of them is larger
than the page size which is 256. Their sizes are even less than half of the
page size.
Instead we get the following exception:
java.lang.ArrayIndexOutOfBoundsException
at java.lang.System.arraycopy(Native Method)
at edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriter.writeTuple(TypeAwareTupleWriter.java:82)
at edu.uci.ics.hyracks.storage.am.btree.frames.BTreeNSMLeafFrame.insert(BTreeNSMLeafFrame.java:125)
at edu.uci.ics.hyracks.storage.am.btree.frames.BTreeNSMLeafFrame.split(BTreeNSMLeafFrame.java:182)
at edu.uci.ics.hyracks.storage.am.btree.impls.BTree.performLeafSplit(BTree.java:407)
at edu.uci.ics.hyracks.storage.am.btree.impls.BTree.insertLeaf(BTree.java:366)
at edu.uci.ics.hyracks.storage.am.btree.impls.BTree.performOp(BTree.java:698)
at edu.uci.ics.hyracks.storage.am.btree.impls.BTree.insertUpdateOrDelete(BTree.java:280)
at edu.uci.ics.hyracks.storage.am.btree.impls.BTree.insert(BTree.java:308)
at edu.uci.ics.hyracks.storage.am.btree.impls.BTree.access$2(BTree.java:306)
at edu.uci.ics.hyracks.storage.am.btree.impls.BTree$BTreeAccessor.insert(BTree.java:847)
at edu.uci.ics.hyracks.storage.am.btree.OrderedIndexExamplesTest.crashExample(OrderedIndexExamplesTest.java:363)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.lang.reflect.Method.invoke(Method.java:616)
at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:44)
at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:15)
at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:41)
at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:20)
at org.junit.internal.runners.statements.RunBefores.evaluate(RunBefores.java:28)
at org.junit.internal.runners.statements.RunAfters.evaluate(RunAfters.java:31)
at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:76)
at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:50)
at org.junit.runners.ParentRunner$3.run(ParentRunner.java:193)
at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:52)
at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:191)
at org.junit.runners.ParentRunner.access$000(ParentRunner.java:42)
at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:184)
at org.junit.runners.ParentRunner.run(ParentRunner.java:236)
at org.eclipse.jdt.internal.junit4.runner.JUnit4TestReference.run(JUnit4TestReference.java:50)
at org.eclipse.jdt.internal.junit.runner.TestExecution.run(TestExecution.java:38)
at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.runTests(RemoteTestRunner.java:467)
at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.runTests(RemoteTestRunner.java:683)
at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.run(RemoteTestRunner.java:390)
at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.main(RemoteTestRunner.java:197)
Please use labels and text to provide additional information.
Original issue reported on code.google.com by salsuba...@gmail.com on 4 Oct 2012 at 11:12
Original issue reported on code.google.com by
salsuba...@gmail.com
on 4 Oct 2012 at 11:12