asterixdb-notifications mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Preston Carman (Code Review)" <do-not-re...@asterixdb.incubator.apache.org>
Subject Change in asterixdb[master]: Updated DeletableFrameTupleAppender to support reusing index...
Date Mon, 26 Sep 2016 17:23:19 GMT
Preston Carman has uploaded a new change for review.

  https://asterix-gerrit.ics.uci.edu/1214

Change subject: Updated DeletableFrameTupleAppender to support reusing index slots.
......................................................................

Updated DeletableFrameTupleAppender to support reusing index slots.

The new appender uses a eight bytes per tuple, but allows the frame to
reuse tuple index slots after a tuple as been deleted. When the use case
has many tuples added and removed from a frame, the new appender better
utilizes the tuple index slots. Where the old method would continue to
take more slot for each new tuple, the new model will reuse delete tuple
index slots.

commit 05a1040cccbcb1e2bc996a91a10df26b43674171
Author: Preston Carman <prestonc@apache.org>
Date:   Sun Sep 25 23:53:00 2016 -0700

Change-Id: I05cda3360cc503bf847aeca5998be06f1f7d3c15
---
M hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/sort/util/DeletableFrameTupleAppender.java
A hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/sort/util/IntegerPair.java
A hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/sort/util/IntegerPairPool.java
M hyracks-fullstack/hyracks/hyracks-dataflow-std/src/test/java/org/apache/hyracks/dataflow/std/buffermanager/VariableTupleMemoryManagerTest.java
M hyracks-fullstack/hyracks/hyracks-dataflow-std/src/test/java/org/apache/hyracks/dataflow/std/sort/util/DeletableFrameTupleAppenderTest.java
5 files changed, 381 insertions(+), 109 deletions(-)


  git pull ssh://asterix-gerrit.ics.uci.edu:29418/asterixdb refs/changes/14/1214/1

diff --git a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/sort/util/DeletableFrameTupleAppender.java
b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/sort/util/DeletableFrameTupleAppender.java
index 7d4db64..79ed7b6 100644
--- a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/sort/util/DeletableFrameTupleAppender.java
+++ b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/sort/util/DeletableFrameTupleAppender.java
@@ -20,8 +20,8 @@
 package org.apache.hyracks.dataflow.std.sort.util;
 
 import java.nio.ByteBuffer;
+import java.util.PriorityQueue;
 
-import org.apache.hyracks.api.comm.FrameHelper;
 import org.apache.hyracks.api.comm.IFrameTupleAccessor;
 import org.apache.hyracks.api.dataflow.value.RecordDescriptor;
 import org.apache.hyracks.api.exceptions.HyracksDataException;
@@ -30,60 +30,134 @@
 /**
  * This is a special frame which is used in TupleMemoryBuffer.
  * This frame has a special structure to organize the deleted spaces.
- * Specifically, the endOffset of the deleted tuple will be set as negative number.
- * And we add a special <code>deleted_space</code> field at the last 4 bytes
to remember how many bytes has been deleted.
+ * Specifically, the <code>end_offset</code> of the deleted tuple will be set
as negative number.
+ * The offsets also store both the start and end values because tuples may be out of
+ * after several add, remove and reorganize operations.
+ * <ul>
+ * <li>A frame is formatted with tuple data concatenated starting at offset 0, one
tuple after another.</li>
+ * <li>Each tuple has its <code>start_offset</code> and <code>end_offset</code>
stored in tuple index
+ * slots used for looking up a tuple.
+ * <li>
+ * <li><code>tuple_append</code> holds an int indicating the offset used
to append the next tuple.</li>
+ * <li><code>next_index</code> holds an int indicating the next slot id
to be used.</li>
+ * <li><code>deleted_space</code> holds an int indicating how many bytes
has been deleted.</li>
+ * <li><code>index_count</code> holds an int indicating the number of slot
indexes (N) being used in the frame.</li>
+ * </ul>
+ *
+ * <pre>
+ * [ *tuple_1_bytes*,
+ *   *tuple_2_bytes*,
+ *   ...
+ *   int end_offset, int start_offset, # tuple 2
+ *   int end_offset, int start_offset, # tuple 1
+ *   int tuple_append,
+ *   int next_index,
+ *   int deleted_space,
+ *   int index_count,
+ * ]
+ * </pre>
  */
 public class DeletableFrameTupleAppender implements IAppendDeletableFrameTupleAccessor {
 
+    private static final int SIZE_INDEX_COUNT = 4;
     private static final int SIZE_DELETED_SPACE = 4;
+    private static final int SIZE_NEXT_INDEX = 4;
+    private static final int SIZE_TUPLE_APPEND = 4;
+
+    private static final int SIZE_START_OFFSET = 4;
+    private static final int SIZE_END_OFFSET = 4;
+    private static final int SIZE_OFFSET_GROUP = SIZE_END_OFFSET + SIZE_START_OFFSET;
+
     private final RecordDescriptor recordDescriptor;
     private ByteBuffer buffer;
-    private int tupleCountOffset;
-    private int tupleCount;
-    private int freeDataEndOffset;
+    private int indexSlotsOffset;
+    private int indexCount;
+    private int tupleAppend;
     private int deletedSpace;
-    private byte[] array;   // to speed up the array visit a little
+    private int nextIndex;
+    private byte[] array; // to speed up the array visit a little
+    private IntegerPairPool ipp = new IntegerPairPool();
+
+    private final PriorityQueue<IntegerPair> reorganizeQueue;
 
     public DeletableFrameTupleAppender(RecordDescriptor recordDescriptor) {
         this.recordDescriptor = recordDescriptor;
+        reorganizeQueue = new PriorityQueue<>(16, IntegerPair.RIGHT_ASC_COMPARATOR);
     }
 
-    private int getTupleCountOffset() {
-        return FrameHelper.getTupleCountOffset(buffer.capacity()) - SIZE_DELETED_SPACE;
+    private int getIndexCount() {
+        return IntSerDeUtils.getInt(array, getIndexCountOffset());
     }
 
-    private int getFreeDataEndOffset() {
-        return tupleCount == 0 ? 0 : Math.abs(IntSerDeUtils.getInt(array, tupleCountOffset
- tupleCount * 4));
+    private void setIndexCount(int count) {
+        IntSerDeUtils.putInt(array, getIndexCountOffset(), count);
     }
 
-    private void setFreeDataEndOffset(int offset) {
-        assert (offset >= 0);
-        IntSerDeUtils.putInt(array, tupleCountOffset - tupleCount * 4, offset);
-    }
-
-    private void setTupleCount(int count) {
-        IntSerDeUtils.putInt(array, tupleCountOffset, count);
-    }
-
-    private void setDeleteSpace(int count) {
-        IntSerDeUtils.putInt(array, buffer.capacity() - SIZE_DELETED_SPACE, count);
-    }
-
-    private int getPhysicalTupleCount() {
-        return IntSerDeUtils.getInt(array, tupleCountOffset);
+    private int getIndexCountOffset() {
+        return buffer.capacity() - SIZE_INDEX_COUNT;
     }
 
     private int getDeletedSpace() {
-        return IntSerDeUtils.getInt(array, buffer.capacity() - SIZE_DELETED_SPACE);
+        return IntSerDeUtils.getInt(array, getDeletedSpaceOffset());
+    }
+
+    private void setDeletedSpace(int space) {
+        IntSerDeUtils.putInt(array, getDeletedSpaceOffset(), space);
+    }
+
+    private int getDeletedSpaceOffset() {
+        return getIndexCountOffset() - SIZE_DELETED_SPACE;
+    }
+
+    private int getNextIndex() {
+        return IntSerDeUtils.getInt(array, getNextIndexOffset());
+    }
+
+    private void setNextIndex(int index) {
+        IntSerDeUtils.putInt(array, getNextIndexOffset(), index);
+    }
+
+    private int getNextIndexOffset() {
+        return getDeletedSpaceOffset() - SIZE_NEXT_INDEX;
+    }
+
+    private int getAndUpdateNextIndex() {
+        int index = nextIndex;
+        nextIndex = index + 1;
+        while (nextIndex < indexCount) {
+            if (getTupleEndOffset(nextIndex) <= 0) {
+                break;
+            }
+            nextIndex++;
+        }
+        setNextIndex(nextIndex);
+        return index;
+    }
+
+    private int getTupleAppend() {
+        return IntSerDeUtils.getInt(array, getTupleAppendOffset());
+    }
+
+    private void setTupleAppend(int offset) {
+        IntSerDeUtils.putInt(array, getTupleAppendOffset(), offset);
+    }
+
+    private int getTupleAppendOffset() {
+        return getNextIndexOffset() - SIZE_TUPLE_APPEND;
+    }
+
+    private int getIndexSlotOffset() {
+        return getTupleAppendOffset();
     }
 
     @Override
     public void clear(ByteBuffer buffer) throws HyracksDataException {
         this.buffer = buffer;
         this.array = buffer.array();
-        tupleCountOffset = getTupleCountOffset();
-        setTupleCount(0);
-        setDeleteSpace(0);
+        setIndexCount(0);
+        setDeletedSpace(0);
+        setNextIndex(0);
+        setTupleAppend(0);
         resetCounts();
     }
 
@@ -91,14 +165,15 @@
     public void reset(ByteBuffer buffer) {
         this.buffer = buffer;
         this.array = buffer.array();
-        tupleCountOffset = getTupleCountOffset();
         resetCounts();
     }
 
     private void resetCounts() {
+        indexSlotsOffset = getIndexSlotOffset();
         deletedSpace = getDeletedSpace();
-        tupleCount = getPhysicalTupleCount();
-        freeDataEndOffset = getFreeDataEndOffset();
+        indexCount = getIndexCount();
+        tupleAppend = getTupleAppend();
+        nextIndex = getNextIndex();
     }
 
     /**
@@ -115,11 +190,18 @@
         byte[] src = tupleAccessor.getBuffer().array();
         int tStartOffset = tupleAccessor.getTupleStartOffset(tIndex);
         int length = tupleAccessor.getTupleLength(tIndex);
-        System.arraycopy(src, tStartOffset, array, freeDataEndOffset, length);
-        setTupleCount(++tupleCount);
-        freeDataEndOffset += length;
-        setFreeDataEndOffset(freeDataEndOffset);
-        return tupleCount - 1;
+        System.arraycopy(src, tStartOffset, array, tupleAppend, length);
+        int index = getAndUpdateNextIndex();
+        if (index < indexCount) {
+            // Don't change index count
+        } else {
+            // Increment count
+            setIndexCount(++indexCount);
+        }
+        setTupleOffsets(index, tupleAppend, length);
+        tupleAppend += length;
+        setTupleAppend(tupleAppend);
+        return index;
     }
 
     @Override
@@ -128,7 +210,11 @@
         if (endOffset > 0) {
             setTupleEndOffset(tupleIndex, -endOffset);
             deletedSpace += endOffset - getTupleStartOffset(tupleIndex);
-            setDeleteSpace(deletedSpace);
+            setDeletedSpace(deletedSpace);
+            if (nextIndex > tupleIndex) {
+                nextIndex = tupleIndex;
+                setNextIndex(nextIndex);
+            }
         }
     }
 
@@ -139,36 +225,58 @@
         }
         reclaimDeletedEnding();
 
-        freeDataEndOffset = 0;
-        int endOffset = 0;
-        for (int i = 0; i < tupleCount; i++) {
-            int startOffset = Math.abs(endOffset);
+        // Build reorganize queue
+        IntegerPair ip;
+        int endOffset;
+        int startOffset;
+        for (int i = 0; i < indexCount; i++) {
             endOffset = getTupleEndOffset(i);
+            if (endOffset > 0) {
+                ip = ipp.takeOne();
+                ip.reset(i, getTupleStartOffset(i));
+                reorganizeQueue.add(ip);
+            }
+        }
+
+        int index;
+        tupleAppend = 0;
+        while (!reorganizeQueue.isEmpty()) {
+            ip = reorganizeQueue.remove();
+            index = ip.getLeft();
+            startOffset = getTupleStartOffset(index);
+            endOffset = getTupleEndOffset(index);
             if (endOffset >= 0) {
                 int length = endOffset - startOffset;
-                assert ( length >= 0);
-                if (freeDataEndOffset != startOffset) {
-                    System.arraycopy(array, startOffset, array, freeDataEndOffset, length);
+                assert length >= 0;
+                if (tupleAppend != startOffset) {
+                    System.arraycopy(array, startOffset, array, tupleAppend, length);
                 }
-                freeDataEndOffset += length;
+                setTupleOffsets(index, tupleAppend, length);
+                tupleAppend += length;
             }
-            setTupleEndOffset(i, freeDataEndOffset);
+            ipp.giveBack(ip);
         }
-        setFreeDataEndOffset(freeDataEndOffset);
+        setTupleAppend(tupleAppend);
         deletedSpace = 0;
-        setDeleteSpace(0);
+        setDeletedSpace(0);
+
+        // Clean up
+        reorganizeQueue.clear();
     }
 
     private void reclaimDeletedEnding() {
-        for (int i = tupleCount - 1; i >= 0; i--) {
+        for (int i = indexCount - 1; i >= 0; i--) {
             int endOffset = getTupleEndOffset(i);
-            if (endOffset < 0) {
-                tupleCount--;
+            if (endOffset <= 0) {
+                indexCount--;
             } else {
                 break;
             }
         }
-        setTupleCount(tupleCount);
+        setIndexCount(indexCount);
+        if (nextIndex > indexCount) {
+            setNextIndex(indexCount);
+        }
     }
 
     @Override
@@ -178,7 +286,8 @@
 
     @Override
     public int getContiguousFreeSpace() {
-        return getTupleCountOffset() - tupleCount * 4 - freeDataEndOffset;
+        int slotSpace = indexCount * SIZE_OFFSET_GROUP;
+        return indexSlotsOffset - tupleAppend - slotSpace;
     }
 
     @Override
@@ -202,6 +311,11 @@
     }
 
     @Override
+    public int getAbsoluteFieldStartOffset(int tupleIndex, int fIdx) {
+        return getTupleStartOffset(tupleIndex) + getFieldSlotsLength() + getFieldStartOffset(tupleIndex,
fIdx);
+    }
+
+    @Override
     public int getFieldLength(int tupleIndex, int fIdx) {
         return getFieldEndOffset(tupleIndex, fIdx) - getFieldStartOffset(tupleIndex, fIdx);
     }
@@ -215,29 +329,40 @@
         return endOffset - getTupleStartOffset(tupleIndex);
     }
 
+    private void setTupleOffsets(int tupleIndex, int start, int length) {
+        setTupleStartOffset(tupleIndex, start);
+        setTupleEndOffset(tupleIndex, start + length);
+    }
+
     @Override
     public int getTupleEndOffset(int tupleIndex) {
-        return IntSerDeUtils.getInt(array, tupleCountOffset - 4 * (tupleIndex + 1));
+        return IntSerDeUtils.getInt(array, getTupleEndSlotOffset(tupleIndex));
     }
 
     private void setTupleEndOffset(int tupleIndex, int offset) {
-        IntSerDeUtils.putInt(array, tupleCountOffset - 4 * (tupleIndex + 1), offset);
+        IntSerDeUtils.putInt(array, getTupleEndSlotOffset(tupleIndex), offset);
     }
 
     @Override
     public int getTupleStartOffset(int tupleIndex) {
-        int offset = tupleIndex == 0 ? 0 : IntSerDeUtils.getInt(array, tupleCountOffset -
4 * tupleIndex);
-        return Math.abs(offset);
+        return IntSerDeUtils.getInt(array, getTupleStartSlotOffset(tupleIndex));
     }
 
-    @Override
-    public int getAbsoluteFieldStartOffset(int tupleIndex, int fIdx) {
-        return getTupleStartOffset(tupleIndex) + getFieldSlotsLength() + getFieldStartOffset(tupleIndex,
fIdx);
+    public void setTupleStartOffset(int tupleIndex, int offset) {
+        IntSerDeUtils.putInt(array, getTupleStartSlotOffset(tupleIndex), offset);
+    }
+
+    public int getTupleStartSlotOffset(int tupleIndex) {
+        return indexSlotsOffset - SIZE_OFFSET_GROUP * tupleIndex - SIZE_START_OFFSET;
+    }
+
+    public int getTupleEndSlotOffset(int tupleIndex) {
+        return getTupleStartSlotOffset(tupleIndex) - SIZE_END_OFFSET;
     }
 
     @Override
     public int getTupleCount() {
-        return tupleCount;
+        return indexCount;
     }
 
     @Override
diff --git a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/sort/util/IntegerPair.java
b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/sort/util/IntegerPair.java
new file mode 100644
index 0000000..99f327b
--- /dev/null
+++ b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/sort/util/IntegerPair.java
@@ -0,0 +1,87 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.hyracks.dataflow.std.sort.util;
+
+import java.io.Serializable;
+import java.util.Comparator;
+
+public class IntegerPair implements Serializable {
+    private static final long serialVersionUID = 1L;
+
+    public static final Comparator<IntegerPair> LEFT_ASC_COMPARATOR = new Comparator<IntegerPair>()
{
+        @Override
+        public int compare(IntegerPair p1, IntegerPair p2) {
+            return p1.getLeft() - p2.getLeft();
+        }
+
+    };
+
+    public static final Comparator<IntegerPair> RIGHT_ASC_COMPARATOR = new Comparator<IntegerPair>()
{
+        @Override
+        public int compare(IntegerPair p1, IntegerPair p2) {
+            return p1.getRight() - p2.getRight();
+        }
+
+    };
+
+    private int left;
+    private int right;
+
+    public IntegerPair() {
+        reset(Integer.MIN_VALUE, Integer.MIN_VALUE);
+    }
+
+    public IntegerPair(int l, int r) {
+        reset(l, r);
+    }
+
+    public int getLeft() {
+        return left;
+    }
+
+    public int getRight() {
+        return right;
+    }
+
+    public void reset(int l, int r) {
+        left = l;
+        right = r;
+    }
+
+    @Override
+    public String toString() {
+        return left + "," + right;
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        if (!(obj instanceof IntegerPair)) {
+            return false;
+        } else {
+            IntegerPair p = (IntegerPair) obj;
+            return this.left == p.getLeft() && this.right == p.getRight();
+        }
+    }
+
+    @Override
+    public int hashCode() {
+        return left * 31 + right;
+    }
+
+}
diff --git a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/sort/util/IntegerPairPool.java
b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/sort/util/IntegerPairPool.java
new file mode 100644
index 0000000..330e822
--- /dev/null
+++ b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/sort/util/IntegerPairPool.java
@@ -0,0 +1,39 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hyracks.dataflow.std.sort.util;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class IntegerPairPool {
+    private final List<IntegerPair> list;
+
+    public IntegerPairPool() {
+        list = new ArrayList<>();
+    }
+
+    public IntegerPair takeOne() {
+        if (list.isEmpty()) {
+            return new IntegerPair();
+        }
+        return list.remove(list.size() - 1);
+    }
+
+    public void giveBack(IntegerPair pair) {
+        list.add(pair);
+    }
+}
diff --git a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/test/java/org/apache/hyracks/dataflow/std/buffermanager/VariableTupleMemoryManagerTest.java
b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/test/java/org/apache/hyracks/dataflow/std/buffermanager/VariableTupleMemoryManagerTest.java
index e2a231f..b7d3c7d 100644
--- a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/test/java/org/apache/hyracks/dataflow/std/buffermanager/VariableTupleMemoryManagerTest.java
+++ b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/test/java/org/apache/hyracks/dataflow/std/buffermanager/VariableTupleMemoryManagerTest.java
@@ -36,7 +36,8 @@
 
 public class VariableTupleMemoryManagerTest extends AbstractTupleMemoryManagerTest {
     VariableDeletableTupleMemoryManager tupleMemoryManager;
-    final int EXTRA_BYTES_FOR_DELETABLE_FRAME = 4;
+    private static final int EXTRA_BYTES_FOR_DELETABLE_FRAME = 16;
+    private static final int EXTRA_BYTES_FOR_DELETABLE_RECORD = 4;
 
     @Before
     public void setup() {
@@ -47,7 +48,7 @@
     @Test
     public void testInsertTupleToMemoryManager() throws HyracksDataException {
         int iTuplePerFrame = 3;
-        Map<Integer, Integer> mapPrepare = prepareFixedSizeTuples(iTuplePerFrame, EXTRA_BYTES_FOR_DELETABLE_FRAME,
0);
+        Map<Integer, Integer> mapPrepare = prepareFixedSizeTuples(iTuplePerFrame, EXTRA_BYTES_FOR_DELETABLE_FRAME,
EXTRA_BYTES_FOR_DELETABLE_RECORD);
         Map<TuplePointer, Integer> mapInserted = insertInFTAToBufferShouldAllSuccess();
         assertEachTupleInFTAIsInBuffer(mapPrepare, mapInserted);
     }
@@ -64,7 +65,7 @@
     @Test
     public void testDeleteTupleInMemoryManager() throws HyracksDataException {
         int iTuplePerFrame = 3;
-        Map<Integer, Integer> mapPrepare = prepareFixedSizeTuples(iTuplePerFrame, EXTRA_BYTES_FOR_DELETABLE_FRAME,
0);
+        Map<Integer, Integer> mapPrepare = prepareFixedSizeTuples(iTuplePerFrame, EXTRA_BYTES_FOR_DELETABLE_FRAME,
EXTRA_BYTES_FOR_DELETABLE_RECORD);
         Map<TuplePointer, Integer> mapInserted = insertInFTAToBufferShouldAllSuccess();
         deleteRandomSelectedTuples(mapPrepare, mapInserted, 1);
         assertEachTupleInFTAIsInBuffer(mapPrepare, mapInserted);
@@ -73,7 +74,7 @@
     @Test
     public void testReOrganizeSpace() throws HyracksDataException {
         int iTuplePerFrame = 3;
-        Map<Integer, Integer> mapPrepare = prepareFixedSizeTuples(iTuplePerFrame, EXTRA_BYTES_FOR_DELETABLE_FRAME,
0);
+        Map<Integer, Integer> mapPrepare = prepareFixedSizeTuples(iTuplePerFrame, EXTRA_BYTES_FOR_DELETABLE_FRAME,
EXTRA_BYTES_FOR_DELETABLE_RECORD);
         Map<Integer, Integer> copyMap = new HashMap<>(mapPrepare);
         Map<TuplePointer, Integer> mapInserted = insertInFTAToBufferShouldAllSuccess();
         ByteBuffer buffer = deleteRandomSelectedTuples(mapPrepare, mapInserted, mapPrepare.size()
/ 2);
diff --git a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/test/java/org/apache/hyracks/dataflow/std/sort/util/DeletableFrameTupleAppenderTest.java
b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/test/java/org/apache/hyracks/dataflow/std/sort/util/DeletableFrameTupleAppenderTest.java
index 7686540..35348af 100644
--- a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/test/java/org/apache/hyracks/dataflow/std/sort/util/DeletableFrameTupleAppenderTest.java
+++ b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/test/java/org/apache/hyracks/dataflow/std/sort/util/DeletableFrameTupleAppenderTest.java
@@ -24,30 +24,33 @@
 
 import java.nio.ByteBuffer;
 
-import org.apache.commons.lang3.ArrayUtils;
 import org.apache.hyracks.api.dataflow.value.ISerializerDeserializer;
 import org.apache.hyracks.api.dataflow.value.RecordDescriptor;
 import org.apache.hyracks.api.exceptions.HyracksDataException;
 import org.apache.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
 import org.apache.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
 import org.apache.hyracks.dataflow.common.data.marshalling.UTF8StringSerializerDeserializer;
-import org.apache.hyracks.util.IntSerDeUtils;
 import org.apache.hyracks.dataflow.std.sort.Utility;
+import org.apache.hyracks.util.IntSerDeUtils;
 import org.apache.hyracks.util.string.UTF8StringUtil;
 import org.junit.Before;
 import org.junit.Test;
 
+/**
+ * @see org.apache.hyracks.dataflow.std.sort.util.DeletableFrameTupleAppender
+ */
 public class DeletableFrameTupleAppenderTest {
+    private static final int META_DATA_SIZE = 4 + 4 + 4 + 4;
+    private static final int SLOT_SIZE = 4 + 4;
+    private static final char TEST_CH = 'x';
+    private static final int TEST_TUPLE_COUNT = 8;
+    private static final int TEST_FRAME_SIZE = 256;
+
     DeletableFrameTupleAppender appender;
-    ISerializerDeserializer[] fields = new ISerializerDeserializer[] {
-            IntegerSerializerDeserializer.INSTANCE,
-            new UTF8StringSerializerDeserializer(),
-    };
+    ISerializerDeserializer[] fields = new ISerializerDeserializer[] { IntegerSerializerDeserializer.INSTANCE,
+            new UTF8StringSerializerDeserializer(), };
     RecordDescriptor recordDescriptor = new RecordDescriptor(fields);
     ArrayTupleBuilder builder = new ArrayTupleBuilder(recordDescriptor.getFieldCount());
-    static final char TEST_CH = 'x';
-
-    int cap = 256;
 
     @Before
     public void initial() throws HyracksDataException {
@@ -56,30 +59,46 @@
 
     @Test
     public void testClear() throws Exception {
-        ByteBuffer buffer = ByteBuffer.allocate(cap);
+        ByteBuffer buffer = ByteBuffer.allocate(TEST_FRAME_SIZE);
         appender.clear(buffer);
         assertTrue(appender.getBuffer() == buffer);
         assertTrue(appender.getTupleCount() == 0);
-        assertTrue(appender.getContiguousFreeSpace() == cap - 4 - 4);
+        assertTrue(appender.getTotalFreeSpace() == TEST_FRAME_SIZE - META_DATA_SIZE);
+        assertTrue(appender.getContiguousFreeSpace() == TEST_FRAME_SIZE - META_DATA_SIZE);
     }
 
     ByteBuffer makeAFrame(int capacity, int count, int deletedBytes) throws HyracksDataException
{
         ByteBuffer buffer = ByteBuffer.allocate(capacity);
         int metaOffset = capacity - 4;
-        buffer.putInt(metaOffset, deletedBytes);
-        metaOffset -= 4;
         buffer.putInt(metaOffset, count);
         metaOffset -= 4;
+        buffer.putInt(metaOffset, deletedBytes);
+        // next index
+        metaOffset -= 4;
+        buffer.putInt(metaOffset, count);
+        // append slot
+        metaOffset -= 4;
+        int appendOffset = metaOffset;
+        buffer.putInt(metaOffset, 0);
+        metaOffset -= 4;
+
+        int start = 0;
         for (int i = 0; i < count; i++, metaOffset -= 4) {
             makeARecord(builder, i);
             for (int x = 0; x < builder.getFieldEndOffsets().length; x++) {
                 buffer.putInt(builder.getFieldEndOffsets()[x]);
             }
             buffer.put(builder.getByteArray(), 0, builder.getSize());
-            assert (metaOffset > buffer.position());
+
+            // Add slot information
+            buffer.putInt(metaOffset, start);
+            metaOffset -= 4;
             buffer.putInt(metaOffset, buffer.position());
 
+            start = buffer.position();
+            assert (metaOffset > buffer.position());
         }
+        buffer.putInt(appendOffset, start);
         return buffer;
     }
 
@@ -89,52 +108,52 @@
         builder.addField(fields[1], Utility.repeatString(TEST_CH, i + 1));
     }
 
-    int assertTupleIsExpected(int i, int dataOffset) {
-        int lenStrMeta = UTF8StringUtil.getNumBytesToStoreLength(i);
-        int tupleLength = 2 * 4 + 4 + lenStrMeta + i + 1;
+    int assertTupleIsExpected(int i, int dataOffset, int testString) {
+        int lenStrMeta = UTF8StringUtil.getNumBytesToStoreLength(testString);
+        int tupleLength = 2 * 4 + 4 + lenStrMeta + testString + 1;
         assertEquals(dataOffset, appender.getTupleStartOffset(i));
         assertEquals(tupleLength, appender.getTupleLength(i));
 
         assertEquals(dataOffset + 2 * 4, appender.getAbsoluteFieldStartOffset(i, 0));
         assertEquals(4, appender.getFieldLength(i, 0));
-        assertEquals(i + 1,
+        assertEquals(testString + 1,
                 IntSerDeUtils.getInt(appender.getBuffer().array(), appender.getAbsoluteFieldStartOffset(i,
0)));
         assertEquals(dataOffset + 2 * 4 + 4, appender.getAbsoluteFieldStartOffset(i, 1));
-        assertEquals(lenStrMeta + i + 1, appender.getFieldLength(i, 1));
+        assertEquals(lenStrMeta + testString + 1, appender.getFieldLength(i, 1));
         return tupleLength;
     }
 
     @Test
     public void testReset() throws Exception {
-        ByteBuffer buffer = ByteBuffer.allocate(cap);
+        ByteBuffer buffer = ByteBuffer.allocate(TEST_FRAME_SIZE);
         appender.reset(buffer);
         assertTrue(appender.getBuffer() == buffer);
         assertTrue(appender.getTupleCount() == 0);
-        assertTrue(appender.getContiguousFreeSpace() == cap - 4 - 4);
+        assertTrue(appender.getContiguousFreeSpace() == TEST_FRAME_SIZE - META_DATA_SIZE);
 
-        int count = 10;
+        int count = TEST_TUPLE_COUNT;
         int deleted = 7;
-        buffer = makeAFrame(cap, count, deleted);
+        buffer = makeAFrame(TEST_FRAME_SIZE, count, deleted);
         int pos = buffer.position();
         appender.reset(buffer);
         assertTrue(appender.getBuffer() == buffer);
         assertTrue(appender.getTupleCount() == count);
-        assertTrue(appender.getContiguousFreeSpace() == cap - 4 - 4 - count * 4 - pos);
+        assertTrue(appender.getContiguousFreeSpace() == TEST_FRAME_SIZE - META_DATA_SIZE
- count * SLOT_SIZE - pos);
         assertTrue(appender.getTotalFreeSpace() == appender.getContiguousFreeSpace() + deleted);
 
         int dataOffset = 0;
         for (int i = 0; i < count; i++) {
-            dataOffset += assertTupleIsExpected(i, dataOffset);
+            dataOffset += assertTupleIsExpected(i, dataOffset, i);
         }
     }
 
     @Test
     public void testAppend() throws Exception {
-        int count = 10;
-        ByteBuffer bufferRead = makeAFrame(cap, count, 0);
+        int count = TEST_TUPLE_COUNT;
+        ByteBuffer bufferRead = makeAFrame(TEST_FRAME_SIZE, count, 0);
         DeletableFrameTupleAppender accessor = new DeletableFrameTupleAppender(recordDescriptor);
         accessor.reset(bufferRead);
-        ByteBuffer bufferWrite = ByteBuffer.allocate(cap);
+        ByteBuffer bufferWrite = ByteBuffer.allocate(TEST_FRAME_SIZE);
         appender.clear(bufferWrite);
         for (int i = 0; i < accessor.getTupleCount(); i++) {
             appender.append(accessor, i);
@@ -146,9 +165,9 @@
 
     @Test
     public void testDelete() throws Exception {
-        int count = 10;
+        int count = TEST_TUPLE_COUNT;
         int deleteSpace = 0;
-        ByteBuffer buffer = makeAFrame(cap, count, deleteSpace);
+        ByteBuffer buffer = makeAFrame(TEST_FRAME_SIZE, count, deleteSpace);
         appender.reset(buffer);
 
         int freeSpace = appender.getContiguousFreeSpace();
@@ -156,7 +175,7 @@
             deleteSpace += assertDeleteSucceed(i, freeSpace, deleteSpace);
             int innerOffset = deleteSpace;
             for (int j = i + 1; j < appender.getTupleCount(); j++) {
-                innerOffset += assertTupleIsExpected(j, innerOffset);
+                innerOffset += assertTupleIsExpected(j, innerOffset, j);
             }
         }
     }
@@ -165,7 +184,8 @@
     public void testResetAfterDelete() throws Exception {
         testDelete();
         appender.reset(appender.getBuffer());
-        assertEquals(cap - appender.getTupleCount() * 4 - 4 - 4, appender.getTotalFreeSpace());
+        assertEquals(TEST_FRAME_SIZE - appender.getTupleCount() * SLOT_SIZE - META_DATA_SIZE,
+                appender.getTotalFreeSpace());
 
     }
 
@@ -187,14 +207,14 @@
     @Test
     public void testAppendAndDelete() throws Exception {
         int cap = 1024;
-        int count = 10;
+        int count = TEST_TUPLE_COUNT;
         int deleteSpace = 0;
         ByteBuffer buffer = makeAFrame(cap, count, deleteSpace);
         int dataOffset = buffer.position();
         appender.reset(buffer);
 
         int freeSpace = appender.getContiguousFreeSpace();
-        int[] deleteSet = new int[] { 1, 3, 5 };
+        int[] deleteSet = new int[] { 1, 3, 5, 7 };
         for (int i = 0; i < deleteSet.length; i++) {
             deleteSpace += assertDeleteSucceed(deleteSet[i], freeSpace, deleteSpace);
         }
@@ -203,28 +223,28 @@
         DeletableFrameTupleAppender accessor = new DeletableFrameTupleAppender(recordDescriptor);
         accessor.reset(bufferRead);
 
+        int[] appendSet = new int[] { 1, 3, 5, 7, 8, 9, 10, 11 };
         for (int i = count; i < accessor.getTupleCount(); i++) {
             int id = appender.append(accessor, i);
-            dataOffset += assertTupleIsExpected(i, dataOffset);
-            assertEquals(i, id);
+            dataOffset += assertTupleIsExpected(id, dataOffset, i);
+            assertEquals(appendSet[i - count], id);
         }
 
         appender.reOrganizeBuffer();
         dataOffset = 0;
+        int[] appendOrder = new int[] { 0, 2, 4, 6, 1, 3, 5, 7, 8, 9, 10, 11 };
+        int[] stringSize = new int[] { 0, 2, 4, 6, 8, 9, 10, 11, 12, 13, 14, 15 };
         for (int i = 0; i < appender.getTupleCount(); i++) {
-            if (ArrayUtils.contains(deleteSet, i)) {
-                continue;
-            }
-            dataOffset += assertTupleIsExpected(i, dataOffset);
+            dataOffset += assertTupleIsExpected(appendOrder[i], dataOffset, stringSize[i]);
         }
     }
 
     @Test
     public void testReOrganizeBuffer() throws Exception {
-        int count = 10;
+        int count = TEST_TUPLE_COUNT;
         testDelete();
         appender.reOrganizeBuffer();
-        ByteBuffer bufferRead = makeAFrame(cap, count, 0);
+        ByteBuffer bufferRead = makeAFrame(TEST_FRAME_SIZE, count, 0);
         DeletableFrameTupleAppender accessor = new DeletableFrameTupleAppender(recordDescriptor);
         accessor.reset(bufferRead);
         for (int i = 0; i < accessor.getTupleCount(); i++) {

-- 
To view, visit https://asterix-gerrit.ics.uci.edu/1214
To unsubscribe, visit https://asterix-gerrit.ics.uci.edu/settings

Gerrit-MessageType: newchange
Gerrit-Change-Id: I05cda3360cc503bf847aeca5998be06f1f7d3c15
Gerrit-PatchSet: 1
Gerrit-Project: asterixdb
Gerrit-Branch: master
Gerrit-Owner: Preston Carman <prestonc@apache.org>

Mime
View raw message