You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@carbondata.apache.org by ja...@apache.org on 2018/09/05 06:58:04 UTC
carbondata git commit: [CARBONDATA-2911] Remove unused BTree related
code
Repository: carbondata
Updated Branches:
refs/heads/master 70fe5144d -> cf74c88cc
[CARBONDATA-2911] Remove unused BTree related code
This closes #2688
Project: http://git-wip-us.apache.org/repos/asf/carbondata/repo
Commit: http://git-wip-us.apache.org/repos/asf/carbondata/commit/cf74c88c
Tree: http://git-wip-us.apache.org/repos/asf/carbondata/tree/cf74c88c
Diff: http://git-wip-us.apache.org/repos/asf/carbondata/diff/cf74c88c
Branch: refs/heads/master
Commit: cf74c88cc2e450c0fc92bc1d2691edede289a85b
Parents: 70fe514
Author: Manhua <ke...@qq.com>
Authored: Tue Sep 4 10:20:07 2018 +0800
Committer: Jacky Li <ja...@qq.com>
Committed: Wed Sep 5 14:56:41 2018 +0800
----------------------------------------------------------------------
.../core/datastore/BTreeBuilderInfo.java | 53 ---
.../carbondata/core/datastore/BtreeBuilder.java | 36 --
.../core/datastore/DataRefNodeFinder.java | 41 ---
.../impl/btree/AbstractBTreeBuilder.java | 162 ---------
.../impl/btree/AbstractBTreeLeafNode.java | 230 ------------
.../impl/btree/BTreeDataRefNodeFinder.java | 265 --------------
.../core/datastore/impl/btree/BTreeNode.java | 69 ----
.../datastore/impl/btree/BTreeNonLeafNode.java | 249 -------------
.../datastore/impl/btree/BlockBTreeBuilder.java | 114 ------
.../impl/btree/BlockBTreeLeafNode.java | 79 ----
.../AbstractDetailQueryResultIterator.java | 33 +-
.../impl/btree/BTreeBlockFinderTest.java | 364 -------------------
12 files changed, 4 insertions(+), 1691 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/carbondata/blob/cf74c88c/core/src/main/java/org/apache/carbondata/core/datastore/BTreeBuilderInfo.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/carbondata/core/datastore/BTreeBuilderInfo.java b/core/src/main/java/org/apache/carbondata/core/datastore/BTreeBuilderInfo.java
deleted file mode 100644
index 381e764..0000000
--- a/core/src/main/java/org/apache/carbondata/core/datastore/BTreeBuilderInfo.java
+++ /dev/null
@@ -1,53 +0,0 @@
-/*
- * 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.carbondata.core.datastore;
-
-import java.util.List;
-
-import org.apache.carbondata.core.metadata.blocklet.DataFileFooter;
-
-/**
- * below class holds the meta data requires to build the blocks
- */
-public class BTreeBuilderInfo {
-
- /**
- * holds all the information about data
- * file meta data
- */
- private List<DataFileFooter> footerList;
-
- /**
- * size of the each column value size
- * this will be useful for reading
- */
- private int[] dimensionColumnValueSize;
-
- public BTreeBuilderInfo(List<DataFileFooter> footerList,
- int[] dimensionColumnValueSize) {
- this.dimensionColumnValueSize = dimensionColumnValueSize;
- this.footerList = footerList;
- }
-
- public int[] getDimensionColumnValueSize() {
- return dimensionColumnValueSize;
- }
-
- public List<DataFileFooter> getFooterList() {
- return footerList;
- }
-}
http://git-wip-us.apache.org/repos/asf/carbondata/blob/cf74c88c/core/src/main/java/org/apache/carbondata/core/datastore/BtreeBuilder.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/carbondata/core/datastore/BtreeBuilder.java b/core/src/main/java/org/apache/carbondata/core/datastore/BtreeBuilder.java
deleted file mode 100644
index 135f736..0000000
--- a/core/src/main/java/org/apache/carbondata/core/datastore/BtreeBuilder.java
+++ /dev/null
@@ -1,36 +0,0 @@
-/*
- * 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.carbondata.core.datastore;
-
-/**
- * Below interface will be used to build the index
- * in some data structure
- */
-public interface BtreeBuilder {
-
- /**
- * Below method will be used to store the leaf collection in some data structure
- */
- void build(BTreeBuilderInfo blocksBuilderInfos);
-
- /**
- * below method to get the first data block
- *
- * @return data block
- */
- DataRefNode get();
-}
http://git-wip-us.apache.org/repos/asf/carbondata/blob/cf74c88c/core/src/main/java/org/apache/carbondata/core/datastore/DataRefNodeFinder.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/carbondata/core/datastore/DataRefNodeFinder.java b/core/src/main/java/org/apache/carbondata/core/datastore/DataRefNodeFinder.java
deleted file mode 100644
index 8e09abb..0000000
--- a/core/src/main/java/org/apache/carbondata/core/datastore/DataRefNodeFinder.java
+++ /dev/null
@@ -1,41 +0,0 @@
-/*
- * 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.carbondata.core.datastore;
-
-/**
- * Below Interface is to search a block
- */
-public interface DataRefNodeFinder {
-
- /**
- * Below method will be used to get the first tentative block which matches with
- * the search key
- *
- * @param dataBlocks complete data blocks present
- * @return data block
- */
- DataRefNode findFirstDataBlock(DataRefNode dataBlocks, IndexKey searchKey);
-
- /**
- * Below method will be used to get the last tentative block which matches with
- * the search key
- *
- * @param dataBlocks complete data blocks present
- * @return data block
- */
- DataRefNode findLastDataBlock(DataRefNode dataBlocks, IndexKey searchKey);
-}
http://git-wip-us.apache.org/repos/asf/carbondata/blob/cf74c88c/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/AbstractBTreeBuilder.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/AbstractBTreeBuilder.java b/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/AbstractBTreeBuilder.java
deleted file mode 100644
index 4e9f4b1..0000000
--- a/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/AbstractBTreeBuilder.java
+++ /dev/null
@@ -1,162 +0,0 @@
-/*
- * 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.carbondata.core.datastore.impl.btree;
-
-import java.nio.ByteBuffer;
-import java.util.ArrayList;
-import java.util.List;
-
-import org.apache.carbondata.core.constants.CarbonCommonConstants;
-import org.apache.carbondata.core.datastore.BtreeBuilder;
-import org.apache.carbondata.core.datastore.IndexKey;
-import org.apache.carbondata.core.util.CarbonProperties;
-
-/**
- * Abstract Btree based builder
- */
-public abstract class AbstractBTreeBuilder implements BtreeBuilder {
-
- /**
- * default Number of keys per page
- */
- private static final int DEFAULT_NUMBER_OF_ENTRIES_NONLEAF = 32;
-
- /**
- * Maximum number of entries in intermediate nodes
- */
- protected int maxNumberOfEntriesInNonLeafNodes;
-
- /**
- * Number of leaf nodes
- */
- protected int nLeaf;
-
- /**
- * root node of a btree
- */
- protected BTreeNode root;
-
- public AbstractBTreeBuilder() {
- maxNumberOfEntriesInNonLeafNodes = Integer.parseInt(CarbonProperties.getInstance()
- .getProperty("org.apache.carbondata.core.datastore.internalnodesize",
- DEFAULT_NUMBER_OF_ENTRIES_NONLEAF + ""));
- }
-
- /**
- * Below method is to build the intermediate node of the btree
- *
- * @param curNode current node
- * @param childNodeGroups children group which will have all the children for
- * particular intermediate node
- * @param currentGroup current group
- * @param interNSKeyList list if keys
- * @param numberOfInternalNode number of internal node
- */
- protected void addIntermediateNode(BTreeNode curNode, List<BTreeNode[]> childNodeGroups,
- BTreeNode[] currentGroup, List<List<IndexKey>> interNSKeyList, int numberOfInternalNode) {
-
- int groupCounter;
- // Build internal nodes level by level. Each upper node can have
- // upperMaxEntry keys and upperMaxEntry+1 children
- int remainder;
- int nHigh = numberOfInternalNode;
- boolean bRootBuilt = false;
- remainder = nLeaf % (maxNumberOfEntriesInNonLeafNodes);
- List<IndexKey> interNSKeys = null;
- while (nHigh > 1 || !bRootBuilt) {
- List<BTreeNode[]> internalNodeGroups =
- new ArrayList<BTreeNode[]>(CarbonCommonConstants.CONSTANT_SIZE_TEN);
- List<List<IndexKey>> interNSKeyTmpList =
- new ArrayList<List<IndexKey>>(CarbonCommonConstants.CONSTANT_SIZE_TEN);
- numberOfInternalNode = 0;
- for (int i = 0; i < nHigh; i++) {
- // Create a new internal node
- curNode = new BTreeNonLeafNode();
- // Allocate a new node group if current node group is full
- groupCounter = i % (maxNumberOfEntriesInNonLeafNodes);
- if (groupCounter == 0) {
- // Create new node group
- currentGroup = new BTreeNonLeafNode[maxNumberOfEntriesInNonLeafNodes];
- internalNodeGroups.add(currentGroup);
- numberOfInternalNode++;
- interNSKeys = new ArrayList<IndexKey>(CarbonCommonConstants.CONSTANT_SIZE_TEN);
- interNSKeyTmpList.add(interNSKeys);
- }
-
- // Add the new internal node to current group
- if (null != currentGroup) {
- currentGroup[groupCounter] = curNode;
- }
- int nNodes;
-
- if (i == nHigh - 1 && remainder != 0) {
- nNodes = remainder;
- } else {
- nNodes = maxNumberOfEntriesInNonLeafNodes;
- }
- // Point the internal node to its children node group
- curNode.setChildren(childNodeGroups.get(i));
- // Fill the internal node with keys based on its child nodes
- for (int j = 0; j < nNodes; j++) {
- curNode.setKey(interNSKeyList.get(i).get(j));
- if (j == 0 && null != interNSKeys) {
- interNSKeys.add(interNSKeyList.get(i).get(j));
-
- }
- }
- }
- // If nHigh is 1, we have the root node
- if (nHigh == 1) {
- bRootBuilt = true;
- }
-
- remainder = nHigh % (maxNumberOfEntriesInNonLeafNodes);
- nHigh = numberOfInternalNode;
- childNodeGroups = internalNodeGroups;
- interNSKeyList = interNSKeyTmpList;
- }
- root = curNode;
- }
-
- /**
- * Below method is to convert the start key
- * into fixed and variable length key.
- * data format<lenght><fixed length key><length><variable length key>
- *
- * @param startKey
- * @return Index key
- */
- protected IndexKey convertStartKeyToNodeEntry(byte[] startKey) {
- ByteBuffer buffer = ByteBuffer.wrap(startKey);
- buffer.rewind();
- int dictonaryKeySize = buffer.getInt();
- int nonDictonaryKeySize = buffer.getInt();
- byte[] dictionaryKey = new byte[dictonaryKeySize];
- buffer.get(dictionaryKey);
- byte[] nonDictionaryKey = new byte[nonDictonaryKeySize];
- buffer.get(nonDictionaryKey);
- return new IndexKey(dictionaryKey, nonDictionaryKey);
- }
-
- /**
- * Below method will be used to get the first data block
- * in Btree case it will be root node
- */
- @Override public BTreeNode get() {
- return root;
- }
-}
http://git-wip-us.apache.org/repos/asf/carbondata/blob/cf74c88c/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/AbstractBTreeLeafNode.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/AbstractBTreeLeafNode.java b/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/AbstractBTreeLeafNode.java
deleted file mode 100644
index 9477dff..0000000
--- a/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/AbstractBTreeLeafNode.java
+++ /dev/null
@@ -1,230 +0,0 @@
-/*
- * 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.carbondata.core.datastore.impl.btree;
-
-import java.io.IOException;
-
-import org.apache.carbondata.core.datastore.DataRefNode;
-import org.apache.carbondata.core.datastore.FileReader;
-import org.apache.carbondata.core.datastore.IndexKey;
-import org.apache.carbondata.core.datastore.chunk.impl.DimensionRawColumnChunk;
-import org.apache.carbondata.core.datastore.chunk.impl.MeasureRawColumnChunk;
-import org.apache.carbondata.core.util.BitSetGroup;
-
-/**
- * Non leaf node abstract class
- */
-public abstract class AbstractBTreeLeafNode implements BTreeNode {
-
- /**
- * number of keys in a btree
- */
- int numberOfKeys;
-
- /**
- * node number
- */
- long nodeNumber;
-
- /**
- * Next node of the leaf
- */
- private BTreeNode nextNode;
-
- /**
- * max key of the column this will be used to check whether this leaf will
- * be used for scanning or not
- */
- byte[][] maxKeyOfColumns;
-
- /**
- * min key of the column this will be used to check whether this leaf will
- * be used for scanning or not
- */
- byte[][] minKeyOfColumns;
-
- /**
- * Method to get the next block this can be used while scanning when
- * iterator of this class can be used iterate over blocks
- *
- * @return next block
- */
- @Override public int numRows() {
- return this.numberOfKeys;
- }
-
- /**
- * below method will used to set the next node
- *
- * @param nextNode
- */
- @Override public void setNextNode(BTreeNode nextNode) {
- this.nextNode = nextNode;
- }
-
- /**
- * Below method is to get the children based on index
- *
- * @param index children index
- * @return btree node
- */
- @Override public BTreeNode getChild(int index) {
- throw new UnsupportedOperationException("Operation not supported in case of leaf node");
- }
-
- /**
- * below method to set the node entry
- *
- * @param key node entry
- */
- @Override public void setKey(IndexKey key) {
- throw new UnsupportedOperationException("Operation not supported in case of leaf node");
- }
-
- /**
- * Method can be used to get the block index .This can be used when multiple
- * thread can be used scan group of blocks in that can we can assign the
- * some of the blocks to one thread and some to other
- *
- * @return block number
- */
- @Override public long nodeIndex() {
- return nodeNumber;
- }
-
- /**
- * This method will be used to get the max value of all the columns this can
- * be used in case of filter query
- *
- */
- @Override public byte[][] getColumnsMaxValue() {
- return maxKeyOfColumns;
- }
-
- /**
- * This method will be used to get the max value of all the columns this can
- * be used in case of filter query
- *
- */
- @Override public byte[][] getColumnsMinValue() {
- return minKeyOfColumns;
- }
-
- /**
- * to check whether node in a btree is a leaf node or not
- *
- * @return leaf node or not
- */
- @Override public boolean isLeafNode() {
- return true;
- }
-
- /**
- * Method to get the next block this can be used while scanning when
- * iterator of this class can be used iterate over blocks
- *
- * @return next block
- */
- @Override public DataRefNode getNextDataRefNode() {
- return nextNode;
- }
-
- /**
- * below method will return the one node indexes
- *
- * @return node entry array
- */
- @Override public IndexKey[] getNodeKeys() {
- // as this is a leaf node so this method implementation is not required
- throw new UnsupportedOperationException("Operation not supported in case of leaf node");
- }
-
- /**
- * below method will be used to set the children of intermediate node
- *
- * @param children array
- */
- @Override public void setChildren(BTreeNode[] children) {
- // no required in case of leaf node as leaf node will not have any children
- throw new UnsupportedOperationException("Operation not supported in case of leaf node");
- }
-
- /**
- * Below method will be used to get the dimension chunks
- *
- * @param fileReader file reader to read the chunks from file
- * @param columnIndexRange indexes of the blocks need to be read
- * @return dimension data chunks
- */
- @Override public DimensionRawColumnChunk[] readDimensionChunks(FileReader fileReader,
- int[][] columnIndexRange) throws IOException {
- // No required here as leaf which will will be use this class will implement its own get
- // dimension chunks
- return null;
- }
-
- /**
- * Below method will be used to get the dimension chunk
- *
- * @param fileReader file reader to read the chunk from file
- * @param columnIndex block index to be read
- * @return dimension data chunk
- */
- @Override public DimensionRawColumnChunk readDimensionChunk(FileReader fileReader,
- int columnIndex) throws IOException {
- // No required here as leaf which will will be use this class will implement
- // its own get dimension chunks
- return null;
- }
-
- /**
- * Below method will be used to get the measure chunk
- *
- * @param fileReader file reader to read the chunk from file
- * @param columnIndexRange block indexes to be read from file
- * @return measure column data chunk
- */
- @Override public MeasureRawColumnChunk[] readMeasureChunks(FileReader fileReader,
- int[][] columnIndexRange) throws IOException {
- // No required here as leaf which will will be use this class will implement its own get
- // measure chunks
- throw new UnsupportedOperationException("Unsupported operation");
- }
-
- /**
- * Below method will be used to read the measure chunk
- *
- * @param fileReader file read to read the file chunk
- * @param columnIndex block index to be read from file
- * @return measure data chunk
- */
- @Override public MeasureRawColumnChunk readMeasureChunk(FileReader fileReader, int columnIndex)
- throws IOException {
- // No required here as leaf which will will be use this class will implement its own get
- // measure chunks
- return null;
- }
-
- @Override
- public int getPageRowCount(int pageNumber) {
- throw new UnsupportedOperationException("Unsupported operation");
- }
-
- @Override public BitSetGroup getIndexedData() {
- return null;
- }
-}
http://git-wip-us.apache.org/repos/asf/carbondata/blob/cf74c88c/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/BTreeDataRefNodeFinder.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/BTreeDataRefNodeFinder.java b/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/BTreeDataRefNodeFinder.java
deleted file mode 100644
index 688d56a..0000000
--- a/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/BTreeDataRefNodeFinder.java
+++ /dev/null
@@ -1,265 +0,0 @@
-/*
- * 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.carbondata.core.datastore.impl.btree;
-
-import java.nio.ByteBuffer;
-
-import org.apache.carbondata.core.datastore.DataRefNode;
-import org.apache.carbondata.core.datastore.DataRefNodeFinder;
-import org.apache.carbondata.core.datastore.IndexKey;
-import org.apache.carbondata.core.util.ByteUtil;
-
-/**
- * Below class will be used to find a block in a btree
- */
-public class BTreeDataRefNodeFinder implements DataRefNodeFinder {
-
- /**
- * no dictionary column value is of variable length so in each column value
- * it will -1
- */
- private static final int NO_DCITIONARY_COLUMN_VALUE = -1;
-
- /**
- * sized of the short value in bytes
- */
- private static final short SHORT_SIZE_IN_BYTES = 2;
- /**
- * this will holds the information about the size of each value of a column,
- * this will be used during Comparison of the btree node value and the
- * search value if value is more than zero then its a fixed length column
- * else its variable length column. So as data of both type of column store
- * separately so this value size array will be used for both purpose
- * comparison and jumping(which type value we need to compare)
- */
- private int[] eachColumnValueSize;
-
- /**
- * the number of no dictionary columns in SORT_COLUMNS
- */
- private int numberOfNoDictSortColumns;
-
- /**
- * the number of columns in SORT_COLUMNS
- */
- private int numberOfSortColumns;
-
- public BTreeDataRefNodeFinder(int[] eachColumnValueSize, int numberOfSortColumns,
- int numberOfNoDictSortColumns) {
- this.eachColumnValueSize = eachColumnValueSize;
- this.numberOfNoDictSortColumns = numberOfNoDictSortColumns;
- this.numberOfSortColumns = numberOfSortColumns;
- }
-
- /**
- * Below method will be used to get the first tentative data block based on
- * search key
- *
- * @return data block
- */
- @Override public DataRefNode findFirstDataBlock(DataRefNode dataRefBlock, IndexKey searchKey) {
- // as its for btree type cast it to btree interface
- BTreeNode rootNode = (BTreeNode) dataRefBlock;
- while (!rootNode.isLeafNode()) {
- rootNode = findFirstLeafNode(searchKey, rootNode);
- }
- return rootNode;
- }
-
- /**
- * Below method will be used to get the last data tentative block based on
- * search key
- *
- * @return data block
- */
- @Override public DataRefNode findLastDataBlock(DataRefNode dataRefBlock, IndexKey searchKey) {
- // as its for btree type cast it to btree interface
- BTreeNode rootNode = (BTreeNode) dataRefBlock;
- while (!rootNode.isLeafNode()) {
- rootNode = findLastLeafNode(searchKey, rootNode);
- }
- return rootNode;
- }
-
- /**
- * Binary search used to get the first tentative block of the btree based on
- * search key
- *
- * @param key search key
- * @param node root node of btree
- * @return first tentative block
- */
- private BTreeNode findFirstLeafNode(IndexKey key, BTreeNode node) {
- int childNodeIndex;
- int low = 0;
- int high = node.numRows() - 1;
- int mid = 0;
- int compareRes = -1;
- IndexKey[] nodeKeys = node.getNodeKeys();
- //
- while (low <= high) {
- mid = (low + high) >>> 1;
- // compare the entries
- compareRes = compareIndexes(key, nodeKeys[mid]);
- if (compareRes < 0) {
- high = mid - 1;
- } else if (compareRes > 0) {
- low = mid + 1;
- } else {
- // if key is matched then get the first entry
- int currentPos = mid;
- while (currentPos - 1 >= 0 && compareIndexes(key, nodeKeys[currentPos - 1]) == 0) {
- currentPos--;
- }
- mid = currentPos;
- break;
- }
- }
- // if compare result is less than zero then we
- // and mid is more than 0 then we need to previous block as duplicates
- // record can be present
- if (compareRes < 0) {
- if (mid > 0) {
- mid--;
- }
- childNodeIndex = mid;
- } else {
- childNodeIndex = mid;
- }
- // get the leaf child
- node = node.getChild(childNodeIndex);
- return node;
- }
-
- /**
- * Binary search used to get the last tentative block of the btree based on
- * search key
- *
- * @param key search key
- * @param node root node of btree
- * @return first tentative block
- */
- private BTreeNode findLastLeafNode(IndexKey key, BTreeNode node) {
- int childNodeIndex;
- int low = 0;
- int high = node.numRows() - 1;
- int mid = 0;
- int compareRes = -1;
- IndexKey[] nodeKeys = node.getNodeKeys();
- //
- while (low <= high) {
- mid = (low + high) >>> 1;
- // compare the entries
- compareRes = compareIndexes(key, nodeKeys[mid]);
- if (compareRes < 0) {
- high = mid - 1;
- } else if (compareRes > 0) {
- low = mid + 1;
- } else {
- int currentPos = mid;
- // if key is matched then get the first entry
- while (currentPos + 1 < node.numRows()
- && compareIndexes(key, nodeKeys[currentPos + 1]) == 0) {
- currentPos++;
- }
- mid = currentPos;
- break;
- }
- }
- // if compare result is less than zero then we
- // and mid is more than 0 then we need to previous block as duplicates
- // record can be present
- if (compareRes < 0) {
- if (mid > 0) {
- mid--;
- }
- childNodeIndex = mid;
- } else {
- childNodeIndex = mid;
- }
- node = node.getChild(childNodeIndex);
- return node;
- }
-
- /**
- * Comparison of index key will be following format of key <Dictionary> key
- * will be in byte array No dictionary key Index of FirstKey (2
- * bytes)><Index of SecondKey (2 bytes)><Index of NKey (2 bytes)> <First Key
- * ByteArray><2nd Key ByteArray><N Key ByteArray> in each column value size
- * of no dictionary column will be -1 if in each column value is not -1 then
- * compare the byte array based on size and increment the offset to
- * dictionary column size if size is -1 then its a no dictionary key so to
- * get the length subtract the size of current with next key offset it will
- * give the actual length if it is at last position or only one key is
- * present then subtract with length
- *
- * @param first key
- * @param second key
- * @return comparison value
- */
- private int compareIndexes(IndexKey first, IndexKey second) {
- int dictionaryKeyOffset = 0;
- int nonDictionaryKeyOffset = 0;
- int compareResult = 0;
- int processedNoDictionaryColumn = numberOfNoDictSortColumns;
- ByteBuffer firstNoDictionaryKeyBuffer = ByteBuffer.wrap(first.getNoDictionaryKeys());
- ByteBuffer secondNoDictionaryKeyBuffer = ByteBuffer.wrap(second.getNoDictionaryKeys());
- int actualOffset = 0;
- int actualOffset1 = 0;
- int firstNoDcitionaryLength = 0;
- int secondNodeDictionaryLength = 0;
-
- for (int i = 0; i < numberOfSortColumns; i++) {
-
- if (eachColumnValueSize[i] != NO_DCITIONARY_COLUMN_VALUE) {
- compareResult = ByteUtil.UnsafeComparer.INSTANCE
- .compareTo(first.getDictionaryKeys(), dictionaryKeyOffset, eachColumnValueSize[i],
- second.getDictionaryKeys(), dictionaryKeyOffset, eachColumnValueSize[i]);
- dictionaryKeyOffset += eachColumnValueSize[i];
- } else {
- if (processedNoDictionaryColumn > 1) {
- actualOffset = firstNoDictionaryKeyBuffer.getShort(nonDictionaryKeyOffset);
- firstNoDcitionaryLength =
- firstNoDictionaryKeyBuffer.getShort(nonDictionaryKeyOffset + SHORT_SIZE_IN_BYTES)
- - actualOffset;
- actualOffset1 = secondNoDictionaryKeyBuffer.getShort(nonDictionaryKeyOffset);
- secondNodeDictionaryLength =
- secondNoDictionaryKeyBuffer.getShort(nonDictionaryKeyOffset + SHORT_SIZE_IN_BYTES)
- - actualOffset1;
- compareResult = ByteUtil.UnsafeComparer.INSTANCE
- .compareTo(first.getNoDictionaryKeys(), actualOffset, firstNoDcitionaryLength,
- second.getNoDictionaryKeys(), actualOffset1, secondNodeDictionaryLength);
- nonDictionaryKeyOffset += SHORT_SIZE_IN_BYTES;
- processedNoDictionaryColumn--;
- } else {
- actualOffset = firstNoDictionaryKeyBuffer.getShort(nonDictionaryKeyOffset);
- actualOffset1 = secondNoDictionaryKeyBuffer.getShort(nonDictionaryKeyOffset);
- firstNoDcitionaryLength = first.getNoDictionaryKeys().length - actualOffset;
- secondNodeDictionaryLength = second.getNoDictionaryKeys().length - actualOffset1;
- compareResult = ByteUtil.UnsafeComparer.INSTANCE
- .compareTo(first.getNoDictionaryKeys(), actualOffset, firstNoDcitionaryLength,
- second.getNoDictionaryKeys(), actualOffset1, secondNodeDictionaryLength);
- }
- }
- if (compareResult != 0) {
- return compareResult;
- }
- }
-
- return 0;
- }
-}
http://git-wip-us.apache.org/repos/asf/carbondata/blob/cf74c88c/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/BTreeNode.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/BTreeNode.java b/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/BTreeNode.java
deleted file mode 100644
index 3bb6527..0000000
--- a/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/BTreeNode.java
+++ /dev/null
@@ -1,69 +0,0 @@
-/*
- * 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.carbondata.core.datastore.impl.btree;
-
-import org.apache.carbondata.core.datastore.DataRefNode;
-import org.apache.carbondata.core.datastore.IndexKey;
-
-/**
- * Interface for btree node
- */
-public interface BTreeNode extends DataRefNode {
-
- /**
- * below method will return the one node indexes
- *
- * @return node entry array
- */
- IndexKey[] getNodeKeys();
-
- /**
- * to check whether node in a btree is a leaf node or not
- *
- * @return leaf node or not
- */
- boolean isLeafNode();
-
- /**
- * below method will be used to set the children of intermediate node
- *
- * @param children array
- */
- void setChildren(BTreeNode[] children);
-
- /**
- * below method will used to set the next node
- *
- * @param nextNode
- */
- void setNextNode(BTreeNode nextNode);
-
- /**
- * Below method is to get the children based on index
- *
- * @param index children index
- * @return btree node
- */
- BTreeNode getChild(int index);
-
- /**
- * below method to set the node entry
- *
- * @param key node entry
- */
- void setKey(IndexKey key);
-}
http://git-wip-us.apache.org/repos/asf/carbondata/blob/cf74c88c/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/BTreeNonLeafNode.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/BTreeNonLeafNode.java b/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/BTreeNonLeafNode.java
deleted file mode 100644
index a6eb695..0000000
--- a/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/BTreeNonLeafNode.java
+++ /dev/null
@@ -1,249 +0,0 @@
-/*
- * 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.carbondata.core.datastore.impl.btree;
-
-import java.util.ArrayList;
-import java.util.List;
-
-import org.apache.carbondata.core.constants.CarbonCommonConstants;
-import org.apache.carbondata.core.datastore.DataRefNode;
-import org.apache.carbondata.core.datastore.FileReader;
-import org.apache.carbondata.core.datastore.IndexKey;
-import org.apache.carbondata.core.datastore.chunk.impl.DimensionRawColumnChunk;
-import org.apache.carbondata.core.datastore.chunk.impl.MeasureRawColumnChunk;
-import org.apache.carbondata.core.util.BitSetGroup;
-
-/**
- * No leaf node of a b+tree class which will keep the matadata(start key) of the
- * leaf node
- */
-public class BTreeNonLeafNode implements BTreeNode {
-
- /**
- * Child nodes
- */
- private BTreeNode[] children;
-
- /**
- * list of keys in non leaf
- */
- private List<IndexKey> listOfKeys;
-
- BTreeNonLeafNode() {
- // creating a list which will store all the indexes
- listOfKeys = new ArrayList<IndexKey>(CarbonCommonConstants.DEFAULT_COLLECTION_SIZE);
- }
-
- /**
- * below method will return the one node indexes
- *
- * @return getting a complete leaf ]node keys
- */
- @Override public IndexKey[] getNodeKeys() {
- return listOfKeys.toArray(new IndexKey[listOfKeys.size()]);
- }
-
- /**
- * as it is a non leaf node it will have the reference of all the leaf node
- * under it, setting all the children
- *
- */
- @Override public void setChildren(BTreeNode[] children) {
- this.children = children;
- }
-
- /**
- * setting the next node
- */
- @Override public void setNextNode(BTreeNode nextNode) {
- // no required in case of non leaf node
- }
-
- /**
- * get the leaf node based on children
- *
- * @return leaf node
- */
- @Override public BTreeNode getChild(int index) {
- return this.children[index];
- }
-
- /**
- * add a key of a leaf node
- *
- */
- @Override public void setKey(IndexKey key) {
- listOfKeys.add(key);
-
- }
-
- /**
- * @return whether its a leaf node or not
- */
- @Override public boolean isLeafNode() {
- return false;
- }
-
- /**
- * Method to get the next block this can be used while scanning when
- * iterator of this class can be used iterate over blocks
- *
- * @return next block
- */
- @Override public DataRefNode getNextDataRefNode() {
- throw new UnsupportedOperationException("Unsupported operation");
- }
-
- /**
- * to get the number of keys tuples present in the block
- *
- * @return number of keys in the block
- */
- @Override public int numRows() {
- return listOfKeys.size();
- }
-
- /**
- * Method can be used to get the block index .This can be used when multiple
- * thread can be used scan group of blocks in that can we can assign the
- * some of the blocks to one thread and some to other
- *
- * @return block number
- */
- @Override public long nodeIndex() {
- throw new UnsupportedOperationException("Unsupported operation");
- }
-
- @Override public short blockletIndex() {
- throw new UnsupportedOperationException("Unsupported operation");
- }
-
- /**
- * This method will be used to get the max value of all the columns this can
- * be used in case of filter query
- *
- */
- @Override public byte[][] getColumnsMaxValue() {
- // operation of getting the max value is not supported as its a non leaf
- // node
- // and in case of B+Tree data will be stored only in leaf node and
- // intermediate
- // node will be used only for searching the leaf node
- throw new UnsupportedOperationException("Unsupported operation");
- }
-
- /**
- * This method will be used to get the max value of all the columns this can
- * be used in case of filter query
- *
- */
- @Override public byte[][] getColumnsMinValue() {
- // operation of getting the min value is not supported as its a non leaf
- // node
- // and in case of B+Tree data will be stored only in leaf node and
- // intermediate
- // node will be used only for searching the leaf node
- throw new UnsupportedOperationException("Unsupported operation");
- }
-
- /**
- * Below method will be used to get the dimension chunks
- *
- * @param fileReader file reader to read the chunks from file
- * @param columnIndexRange indexes of the blocks need to be read
- * @return dimension data chunks
- */
- @Override public DimensionRawColumnChunk[] readDimensionChunks(FileReader fileReader,
- int[][] columnIndexRange) {
-
- // operation of getting the dimension chunks is not supported as its a
- // non leaf node
- // and in case of B+Tree data will be stored only in leaf node and
- // intermediate
- // node will be used only for searching the leaf node
- throw new UnsupportedOperationException("Unsupported operation");
- }
-
- /**
- * Below method will be used to get the dimension chunk
- *
- * @param fileReader file reader to read the chunk from file
- * @return dimension data chunk
- */
- @Override public DimensionRawColumnChunk readDimensionChunk(FileReader fileReader,
- int columnIndex) {
- // operation of getting the dimension chunk is not supported as its a
- // non leaf node
- // and in case of B+Tree data will be stored only in leaf node and
- // intermediate
- // node will be used only for searching the leaf node
- throw new UnsupportedOperationException("Unsupported operation");
- }
-
- /**
- * Below method will be used to get the measure chunk
- *
- * @param fileReader file reader to read the chunk from file
- * @param columnIndexRange block indexes to be read from file
- * @return measure column data chunk
- */
- @Override public MeasureRawColumnChunk[] readMeasureChunks(FileReader fileReader,
- int[][] columnIndexRange) {
- // operation of getting the measure chunk is not supported as its a non
- // leaf node
- // and in case of B+Tree data will be stored only in leaf node and
- // intermediate
- // node will be used only for searching the leaf node
- throw new UnsupportedOperationException("Unsupported operation");
- }
-
- /**
- * Below method will be used to read the measure chunk
- *
- * @param fileReader file read to read the file chunk
- * @param columnIndex block index to be read from file
- * @return measure data chunk
- */
-
- @Override public MeasureRawColumnChunk readMeasureChunk(FileReader fileReader, int columnIndex) {
- // operation of getting the measure chunk is not supported as its a non
- // leaf node
- // and in case of B+Tree data will be stored only in leaf node and
- // intermediate
- // node will be used only for searching the leaf node
- throw new UnsupportedOperationException("Unsupported operation");
- }
-
- public BitSetGroup getIndexedData() {
- return null;
- }
-
- /**
- * number of pages in blocklet
- * @return
- */
- @Override
- public int numberOfPages() {
- // TODO Auto-generated method stub
- throw new UnsupportedOperationException("Unsupported operation");
- }
-
- @Override
- public int getPageRowCount(int pageNumber) {
- throw new UnsupportedOperationException("Unsupported operation");
- }
-}
http://git-wip-us.apache.org/repos/asf/carbondata/blob/cf74c88c/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/BlockBTreeBuilder.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/BlockBTreeBuilder.java b/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/BlockBTreeBuilder.java
deleted file mode 100644
index 5436345..0000000
--- a/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/BlockBTreeBuilder.java
+++ /dev/null
@@ -1,114 +0,0 @@
-/*
- * 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.carbondata.core.datastore.impl.btree;
-/*
- * 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.
- */
-
-import java.util.ArrayList;
-import java.util.List;
-
-import org.apache.carbondata.common.logging.LogService;
-import org.apache.carbondata.common.logging.LogServiceFactory;
-import org.apache.carbondata.core.constants.CarbonCommonConstants;
-import org.apache.carbondata.core.datastore.BTreeBuilderInfo;
-import org.apache.carbondata.core.datastore.IndexKey;
-
-/**
- * Below class will be used to build the btree BTree will be built for all the
- * blocks of a segment
- */
-public class BlockBTreeBuilder extends AbstractBTreeBuilder {
-
- /**
- * Attribute for Carbon LOGGER
- */
- private static final LogService LOGGER =
- LogServiceFactory.getLogService(BlockBTreeBuilder.class.getName());
-
- /**
- * Below method will be used to build the segment info bplus tree format
- * Tree will be a read only tree, and it will be build on Bottoms up
- * approach first all the leaf node will be built and then intermediate node
- * in our case one leaf node will have not only one entry it will have group
- * of entries
- */
- @Override public void build(BTreeBuilderInfo btreeBuilderInfo) {
- int groupCounter;
- int nInternal = 0;
- BTreeNode curNode = null;
- BTreeNode prevNode = null;
- List<BTreeNode[]> nodeGroups =
- new ArrayList<BTreeNode[]>(CarbonCommonConstants.CONSTANT_SIZE_TEN);
- BTreeNode[] currentGroup = null;
- List<List<IndexKey>> interNSKeyList =
- new ArrayList<List<IndexKey>>(CarbonCommonConstants.CONSTANT_SIZE_TEN);
- List<IndexKey> leafNSKeyList = null;
- long nodeNumber = 0;
- for (int metadataIndex = 0;
- metadataIndex < btreeBuilderInfo.getFooterList().size(); metadataIndex++) {
- // creating a leaf node
- curNode = new BlockBTreeLeafNode(btreeBuilderInfo, metadataIndex, nodeNumber++);
- nLeaf++;
- // setting a next node as its a b+tree
- // so all the leaf node will be chained
- // will be stored in linked list
- if (prevNode != null) {
- prevNode.setNextNode(curNode);
- }
- prevNode = curNode;
- // as intermediate node will have more than one leaf
- // in cerating a group
- groupCounter = (nLeaf - 1) % (maxNumberOfEntriesInNonLeafNodes);
- if (groupCounter == 0) {
- // Create new node group if current group is full
- leafNSKeyList = new ArrayList<IndexKey>(CarbonCommonConstants.CONSTANT_SIZE_TEN);
- currentGroup = new BTreeNode[maxNumberOfEntriesInNonLeafNodes];
- nodeGroups.add(currentGroup);
- nInternal++;
- interNSKeyList.add(leafNSKeyList);
- }
- if (null != leafNSKeyList) {
- leafNSKeyList.add(convertStartKeyToNodeEntry(
- btreeBuilderInfo.getFooterList().get(metadataIndex).getBlockletIndex()
- .getBtreeIndex().getStartKey()));
- }
- if (null != currentGroup) {
- currentGroup[groupCounter] = curNode;
- }
- }
- if (nLeaf == 0) {
- return;
- }
- // adding a intermediate node
- addIntermediateNode(curNode, nodeGroups, currentGroup, interNSKeyList, nInternal);
- LOGGER.info("************************Total Number Rows In BTREE: " + nLeaf);
- }
-}
http://git-wip-us.apache.org/repos/asf/carbondata/blob/cf74c88c/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/BlockBTreeLeafNode.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/BlockBTreeLeafNode.java b/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/BlockBTreeLeafNode.java
deleted file mode 100644
index 8af7eae..0000000
--- a/core/src/main/java/org/apache/carbondata/core/datastore/impl/btree/BlockBTreeLeafNode.java
+++ /dev/null
@@ -1,79 +0,0 @@
-/*
- * 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.carbondata.core.datastore.impl.btree;
-
-import org.apache.carbondata.core.datastore.BTreeBuilderInfo;
-import org.apache.carbondata.core.datastore.block.BlockInfo;
-import org.apache.carbondata.core.datastore.block.TableBlockInfo;
-import org.apache.carbondata.core.metadata.blocklet.DataFileFooter;
-import org.apache.carbondata.core.metadata.blocklet.index.BlockletMinMaxIndex;
-
-/**
- * Leaf node for btree where only min max will be store this can be used from
- * driver when only we need to find whether particular block be selected for
- * query execution
- */
-public class BlockBTreeLeafNode extends AbstractBTreeLeafNode {
-
- private BlockInfo blockInfo;
-
- /**
- * Create a leaf node
- *
- * @param builderInfos builder infos which have required metadata to create a leaf
- * node
- * @param metadataIndex metadata index
- */
- BlockBTreeLeafNode(BTreeBuilderInfo builderInfos, int metadataIndex, long nodeNumber) {
- DataFileFooter footer = builderInfos.getFooterList().get(metadataIndex);
- BlockletMinMaxIndex minMaxIndex = footer.getBlockletIndex().getMinMaxIndex();
- maxKeyOfColumns = minMaxIndex.getMaxValues();
- minKeyOfColumns = minMaxIndex.getMinValues();
- numberOfKeys = (int)footer.getNumberOfRows();
- this.nodeNumber = nodeNumber;
- this.blockInfo = footer.getBlockInfo();
- }
-
- /**
- * Below method is to get the table block info
- * This will be used only in case of BlockBtree leaf node which will
- * be used to from driver
- *
- * @return TableBlockInfo
- */
- public TableBlockInfo getTableBlockInfo() {
- return blockInfo.getTableBlockInfo();
- }
-
- /**
- * Below method is suppose to return the Blocklet ID.
- * @return
- */
- @Override public short blockletIndex() {
- return blockInfo.getTableBlockInfo().getDetailInfo().getBlockletId();
- }
-
- /**
- * number of pages in blocklet
- * @return
- */
- @Override
- public int numberOfPages() {
- throw new UnsupportedOperationException("Unsupported operation");
- }
-
-}
http://git-wip-us.apache.org/repos/asf/carbondata/blob/cf74c88c/core/src/main/java/org/apache/carbondata/core/scan/result/iterator/AbstractDetailQueryResultIterator.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/carbondata/core/scan/result/iterator/AbstractDetailQueryResultIterator.java b/core/src/main/java/org/apache/carbondata/core/scan/result/iterator/AbstractDetailQueryResultIterator.java
index 26925d3..5d430de 100644
--- a/core/src/main/java/org/apache/carbondata/core/scan/result/iterator/AbstractDetailQueryResultIterator.java
+++ b/core/src/main/java/org/apache/carbondata/core/scan/result/iterator/AbstractDetailQueryResultIterator.java
@@ -27,11 +27,9 @@ import org.apache.carbondata.common.logging.LogService;
import org.apache.carbondata.common.logging.LogServiceFactory;
import org.apache.carbondata.core.constants.CarbonCommonConstants;
import org.apache.carbondata.core.datastore.DataRefNode;
-import org.apache.carbondata.core.datastore.DataRefNodeFinder;
import org.apache.carbondata.core.datastore.FileReader;
import org.apache.carbondata.core.datastore.block.AbstractIndex;
import org.apache.carbondata.core.datastore.impl.FileFactory;
-import org.apache.carbondata.core.datastore.impl.btree.BTreeDataRefNodeFinder;
import org.apache.carbondata.core.indexstore.blockletindex.BlockletDataRefNode;
import org.apache.carbondata.core.mutate.DeleteDeltaVo;
import org.apache.carbondata.core.reader.CarbonDeleteFilesDataReader;
@@ -115,9 +113,6 @@ public abstract class AbstractDetailQueryResultIterator<E> extends CarbonIterato
private void intialiseInfos() {
for (BlockExecutionInfo blockInfo : blockExecutionInfos) {
Map<String, DeleteDeltaVo> deletedRowsMap = null;
- DataRefNodeFinder finder = new BTreeDataRefNodeFinder(blockInfo.getEachColumnValueSize(),
- blockInfo.getDataBlock().getSegmentProperties().getNumberOfSortColumns(),
- blockInfo.getDataBlock().getSegmentProperties().getNumberOfNoDictSortColumns());
// if delete delta file is present
if (null != blockInfo.getDeleteDeltaFilePath() && 0 != blockInfo
.getDeleteDeltaFilePath().length) {
@@ -128,30 +123,10 @@ public abstract class AbstractDetailQueryResultIterator<E> extends CarbonIterato
blockInfo.setDeletedRecordsMap(deletedRowsMap);
}
DataRefNode dataRefNode = blockInfo.getDataBlock().getDataRefNode();
- if (dataRefNode instanceof BlockletDataRefNode) {
- BlockletDataRefNode node = (BlockletDataRefNode) dataRefNode;
- blockInfo.setFirstDataBlock(node);
- blockInfo.setNumberOfBlockToScan(node.numberOfNodes());
- } else {
- DataRefNode startDataBlock =
- finder.findFirstDataBlock(dataRefNode, blockInfo.getStartKey());
- while ((null != startDataBlock) && (startDataBlock.nodeIndex() < blockInfo
- .getStartBlockletIndex())) {
- startDataBlock = startDataBlock.getNextDataRefNode();
- }
- long numberOfBlockToScan = blockInfo.getNumberOfBlockletToScan();
- //if number of block is less than 0 then take end block.
- if (numberOfBlockToScan <= 0) {
- DataRefNode endDataBlock = finder.findLastDataBlock(dataRefNode, blockInfo.getEndKey());
- if (null != startDataBlock) {
- numberOfBlockToScan = endDataBlock.nodeIndex() - startDataBlock.nodeIndex() + 1;
- } else {
- numberOfBlockToScan = endDataBlock.nodeIndex() + 1;
- }
- }
- blockInfo.setFirstDataBlock(startDataBlock);
- blockInfo.setNumberOfBlockToScan(numberOfBlockToScan);
- }
+ assert (dataRefNode instanceof BlockletDataRefNode);
+ BlockletDataRefNode node = (BlockletDataRefNode) dataRefNode;
+ blockInfo.setFirstDataBlock(node);
+ blockInfo.setNumberOfBlockToScan(node.numberOfNodes());
}
}
http://git-wip-us.apache.org/repos/asf/carbondata/blob/cf74c88c/core/src/test/java/org/apache/carbondata/core/datastore/impl/btree/BTreeBlockFinderTest.java
----------------------------------------------------------------------
diff --git a/core/src/test/java/org/apache/carbondata/core/datastore/impl/btree/BTreeBlockFinderTest.java b/core/src/test/java/org/apache/carbondata/core/datastore/impl/btree/BTreeBlockFinderTest.java
deleted file mode 100644
index 7f7719c..0000000
--- a/core/src/test/java/org/apache/carbondata/core/datastore/impl/btree/BTreeBlockFinderTest.java
+++ /dev/null
@@ -1,364 +0,0 @@
-/*
- * 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.carbondata.core.datastore.impl.btree;
-
-import java.nio.ByteBuffer;
-import java.util.ArrayList;
-import java.util.List;
-
-import org.apache.carbondata.common.logging.LogService;
-import org.apache.carbondata.common.logging.LogServiceFactory;
-import org.apache.carbondata.core.datastore.BTreeBuilderInfo;
-import org.apache.carbondata.core.datastore.BtreeBuilder;
-import org.apache.carbondata.core.datastore.DataRefNode;
-import org.apache.carbondata.core.datastore.DataRefNodeFinder;
-import org.apache.carbondata.core.datastore.IndexKey;
-import org.apache.carbondata.core.metadata.blocklet.DataFileFooter;
-import org.apache.carbondata.core.metadata.blocklet.index.BlockletBTreeIndex;
-import org.apache.carbondata.core.metadata.blocklet.index.BlockletIndex;
-import org.apache.carbondata.core.metadata.blocklet.index.BlockletMinMaxIndex;
-import org.apache.carbondata.core.keygenerator.KeyGenException;
-import org.apache.carbondata.core.keygenerator.KeyGenerator;
-import org.apache.carbondata.core.keygenerator.mdkey.MultiDimKeyVarLengthGenerator;
-import org.apache.carbondata.core.util.CarbonUtil;
-
-import junit.framework.TestCase;
-import org.junit.Test;
-
-public class BTreeBlockFinderTest extends TestCase {
-
- private static final LogService LOGGER =
- LogServiceFactory.getLogService(BTreeBlockFinderTest.class.getName());
-
- @Test public void testBtreeBuldingIsPorper() {
- BtreeBuilder builder = new BlockBTreeBuilder();
- List<DataFileFooter> footerList = getDataFileFooterList();
- BTreeBuilderInfo infos = new BTreeBuilderInfo(footerList, null);
- builder.build(infos);
-
- }
-
- @Test public void testBtreeBuilderGetMethodIsGivingNotNullRootNode() {
- BtreeBuilder builder = new BlockBTreeBuilder();
- List<DataFileFooter> footerList = getDataFileFooterList();
- BTreeBuilderInfo infos = new BTreeBuilderInfo(footerList, null);
- builder.build(infos);
- DataRefNode dataBlock = builder.get();
- assertTrue(dataBlock != null);
- }
-
- @Test public void testBtreeSearchIsWorkingAndGivingPorperBlockletWithNoDictionary1() {
- BtreeBuilder builder = new BlockBTreeBuilder();
- List<DataFileFooter> footerList = getFileFooterListWithOnlyNoDictionaryKey();
- BTreeBuilderInfo infos = new BTreeBuilderInfo(footerList, null);
- builder.build(infos);
- DataRefNode dataBlock = builder.get();
- assertTrue(dataBlock != null);
- DataRefNodeFinder finder = new BTreeDataRefNodeFinder(new int[] { -1 }, 1, 1);
- ByteBuffer buffer = ByteBuffer.allocate(4 + 2);
- buffer.rewind();
- buffer.putShort((short) 1);
- buffer.putInt(12);
- buffer.array();
- IndexKey key = new IndexKey(null, buffer.array());
- DataRefNode findFirstBlock = finder.findFirstDataBlock(dataBlock, key);
- assertEquals(1, findFirstBlock.nodeIndex());
- DataRefNode findLastBlock = finder.findLastDataBlock(dataBlock, key);
- assertEquals(1, findLastBlock.nodeIndex());
- }
-
- @Test public void testBtreeSearchIsWorkingAndGivingPorperBlockletWithNoDictionary() {
- BtreeBuilder builder = new BlockBTreeBuilder();
- List<DataFileFooter> footerList = getFileFooterListWithOnlyNoDictionaryKey();
- BTreeBuilderInfo infos = new BTreeBuilderInfo(footerList, null);
- builder.build(infos);
- DataRefNode dataBlock = builder.get();
- assertTrue(dataBlock != null);
- DataRefNodeFinder finder = new BTreeDataRefNodeFinder(new int[] { -1 }, 1, 1);
- ByteBuffer buffer = ByteBuffer.allocate(4 + 1);
- buffer.rewind();
- buffer.put((byte) 1);
- buffer.putInt(0);
- buffer.array();
- IndexKey key = new IndexKey(null, buffer.array());
- DataRefNode findFirstBlock = finder.findFirstDataBlock(dataBlock, key);
- assertEquals(0, findFirstBlock.nodeIndex());
- DataRefNode findLastBlock = finder.findLastDataBlock(dataBlock, key);
- assertEquals(0, findLastBlock.nodeIndex());
- }
-
- @Test public void testBtreeSearchIsWorkingAndGivingPorperBlockletWithDictionaryKey1()
- throws KeyGenException {
- BtreeBuilder builder = new BlockBTreeBuilder();
- List<DataFileFooter> footerList = getFileFooterListWithOnlyDictionaryKey();
- BTreeBuilderInfo infos = new BTreeBuilderInfo(footerList, null);
- builder.build(infos);
- DataRefNode dataBlock = builder.get();
- assertTrue(dataBlock != null);
- DataRefNodeFinder finder = new BTreeDataRefNodeFinder(new int[] { 2, 2 }, 2, 0);
- int[] dimensionBitLength =
- CarbonUtil.getDimensionBitLength(new int[] { 10000, 10000 }, new int[] { 1, 1 });
- KeyGenerator multiDimKeyVarLengthGenerator =
- new MultiDimKeyVarLengthGenerator(dimensionBitLength);
-
- IndexKey key =
- new IndexKey(multiDimKeyVarLengthGenerator.generateKey(new int[] { 1, 1 }), null);
- DataRefNode findFirstBlock = finder.findFirstDataBlock(dataBlock, key);
- assertEquals(0, findFirstBlock.nodeIndex());
- DataRefNode findLastBlock = finder.findLastDataBlock(dataBlock, key);
- assertEquals(0, findLastBlock.nodeIndex());
- }
-
- @Test public void testBtreeSearchIsWorkingAndGivingPorperBlockletWithDictionaryKey2()
- throws KeyGenException {
- BtreeBuilder builder = new BlockBTreeBuilder();
- List<DataFileFooter> footerList = getFileFooterListWithOnlyDictionaryKey();
- BTreeBuilderInfo infos = new BTreeBuilderInfo(footerList, null);
- builder.build(infos);
- DataRefNode dataBlock = builder.get();
- assertTrue(dataBlock != null);
- DataRefNodeFinder finder = new BTreeDataRefNodeFinder(new int[] { 2, 2 }, 2, 0);
- int[] dimensionBitLength =
- CarbonUtil.getDimensionBitLength(new int[] { 10000, 10000 }, new int[] { 1, 1 });
- KeyGenerator multiDimKeyVarLengthGenerator =
- new MultiDimKeyVarLengthGenerator(dimensionBitLength);
-
- IndexKey key =
- new IndexKey(multiDimKeyVarLengthGenerator.generateKey(new int[] { 0, 0 }), null);
-
- DataRefNode findFirstBlock = finder.findFirstDataBlock(dataBlock, key);
- assertEquals(0, findFirstBlock.nodeIndex());
- DataRefNode findLastBlock = finder.findLastDataBlock(dataBlock, key);
- assertEquals(0, findLastBlock.nodeIndex());
- }
-
- /**
- * Below method will test when key which is not present and key which is
- * more than
- * last node key is passes for searching it should give first block
- */
- @Test public void testBtreeSearchIsWorkingAndGivingPorperBlockletWithDictionaryKey()
- throws KeyGenException {
- BtreeBuilder builder = new BlockBTreeBuilder();
- List<DataFileFooter> footerList = getFileFooterListWithOnlyDictionaryKey();
- BTreeBuilderInfo infos = new BTreeBuilderInfo(footerList, null);
- builder.build(infos);
- DataRefNode dataBlock = builder.get();
- assertTrue(dataBlock != null);
- DataRefNodeFinder finder = new BTreeDataRefNodeFinder(new int[] { 2, 2 }, 2, 0);
- int[] dimensionBitLength =
- CarbonUtil.getDimensionBitLength(new int[] { 10000, 10000 }, new int[] { 1, 1 });
- KeyGenerator multiDimKeyVarLengthGenerator =
- new MultiDimKeyVarLengthGenerator(dimensionBitLength);
-
- IndexKey key =
- new IndexKey(multiDimKeyVarLengthGenerator.generateKey(new int[] { 10001, 10001 }), null);
-
- DataRefNode findFirstBlock = finder.findFirstDataBlock(dataBlock, key);
- assertEquals(99, findFirstBlock.nodeIndex());
- DataRefNode findLastBlock = finder.findLastDataBlock(dataBlock, key);
- assertEquals(99, findLastBlock.nodeIndex());
- }
-
- private List<DataFileFooter> getDataFileFooterList() {
- List<DataFileFooter> list = new ArrayList<DataFileFooter>();
- try {
- int[] dimensionBitLength =
- CarbonUtil.getDimensionBitLength(new int[] { 10000, 10000 }, new int[] { 1, 1 });
- KeyGenerator multiDimKeyVarLengthGenerator =
- new MultiDimKeyVarLengthGenerator(dimensionBitLength);
- int i = 1;
- while (i < 1001) {
- byte[] startKey = multiDimKeyVarLengthGenerator.generateKey(new int[] { i, i });
- byte[] endKey = multiDimKeyVarLengthGenerator.generateKey(new int[] { i + 10, i + 10 });
- ByteBuffer buffer = ByteBuffer.allocate(4 + 1);
- buffer.rewind();
- buffer.put((byte) 1);
- buffer.putInt(i);
- buffer.array();
- byte[] noDictionaryStartKey = buffer.array();
-
- ByteBuffer buffer1 = ByteBuffer.allocate(4 + 1);
- buffer1.rewind();
- buffer1.put((byte) 1);
- buffer1.putInt(i + 10);
- buffer1.array();
- byte[] noDictionaryEndKey = buffer1.array();
- DataFileFooter footer =
- getFileFooter(startKey, endKey, noDictionaryStartKey, noDictionaryEndKey);
- list.add(footer);
- i = i + 10;
- }
- } catch (Exception e) {
- LOGGER.error(e);
- }
- return list;
- }
-
- private List<DataFileFooter> getFileFooterListWithOnlyNoDictionaryKey() {
- List<DataFileFooter> list = new ArrayList<DataFileFooter>();
- try {
- int[] dimensionBitLength =
- CarbonUtil.getDimensionBitLength(new int[] { 10000, 10000 }, new int[] { 1, 1 });
- KeyGenerator multiDimKeyVarLengthGenerator =
- new MultiDimKeyVarLengthGenerator(dimensionBitLength);
- int i = 1;
- while (i < 1001) {
- byte[] startKey = multiDimKeyVarLengthGenerator.generateKey(new int[] { i, i });
- byte[] endKey = multiDimKeyVarLengthGenerator.generateKey(new int[] { i + 10, i + 10 });
- ByteBuffer buffer = ByteBuffer.allocate(2 + 4);
- buffer.rewind();
- buffer.putShort((short) 1);
- buffer.putInt(i);
- buffer.array();
- byte[] noDictionaryStartKey = buffer.array();
-
- ByteBuffer buffer1 = ByteBuffer.allocate(2 + 4);
- buffer1.rewind();
- buffer1.putShort((short) 2);
- buffer1.putInt(i + 10);
- buffer1.array();
- byte[] noDictionaryEndKey = buffer1.array();
- DataFileFooter footer =
- getFileMatadataWithOnlyNoDictionaryKey(startKey, endKey, noDictionaryStartKey,
- noDictionaryEndKey);
- list.add(footer);
- i = i + 10;
- }
- } catch (Exception e) {
- LOGGER.error(e);
- }
- return list;
- }
-
- private List<DataFileFooter> getFileFooterListWithOnlyDictionaryKey() {
- List<DataFileFooter> list = new ArrayList<DataFileFooter>();
- try {
- int[] dimensionBitLength =
- CarbonUtil.getDimensionBitLength(new int[] { 10000, 10000 }, new int[] { 1, 1 });
- KeyGenerator multiDimKeyVarLengthGenerator =
- new MultiDimKeyVarLengthGenerator(dimensionBitLength);
- int i = 1;
- while (i < 1001) {
- byte[] startKey = multiDimKeyVarLengthGenerator.generateKey(new int[] { i, i });
- byte[] endKey = multiDimKeyVarLengthGenerator.generateKey(new int[] { i + 10, i + 10 });
- ByteBuffer buffer = ByteBuffer.allocate(1 + 4);
- buffer.rewind();
- buffer.put((byte) 1);
- buffer.putInt(i);
- buffer.array();
- byte[] noDictionaryStartKey = buffer.array();
-
- ByteBuffer buffer1 = ByteBuffer.allocate(1 + 4);
- buffer1.rewind();
- buffer1.put((byte) 1);
- buffer1.putInt(i + 10);
- buffer1.array();
- byte[] noDictionaryEndKey = buffer1.array();
- DataFileFooter footer =
- getFileFooterWithOnlyDictionaryKey(startKey, endKey, noDictionaryStartKey,
- noDictionaryEndKey);
- list.add(footer);
- i = i + 10;
- }
- } catch (Exception e) {
- LOGGER.error(e);
- }
- return list;
- }
-
- private DataFileFooter getFileFooter(byte[] startKey, byte[] endKey,
- byte[] noDictionaryStartKey, byte[] noDictionaryEndKey) {
- DataFileFooter footer = new DataFileFooter();
- BlockletIndex index = new BlockletIndex();
- BlockletBTreeIndex btreeIndex = new BlockletBTreeIndex();
- ByteBuffer buffer = ByteBuffer.allocate(4 + startKey.length + 4 + noDictionaryStartKey.length);
- buffer.putInt(startKey.length);
- buffer.putInt(noDictionaryStartKey.length);
- buffer.put(startKey);
- buffer.put(noDictionaryStartKey);
- buffer.rewind();
- btreeIndex.setStartKey(buffer.array());
- ByteBuffer buffer1 = ByteBuffer.allocate(4 + startKey.length + 4 + noDictionaryEndKey.length);
- buffer1.putInt(endKey.length);
- buffer1.putInt(noDictionaryEndKey.length);
- buffer1.put(endKey);
- buffer1.put(noDictionaryEndKey);
- buffer1.rewind();
- btreeIndex.setEndKey(buffer1.array());
- BlockletMinMaxIndex minMax = new BlockletMinMaxIndex();
- minMax.setMaxValues(new byte[][] { endKey, noDictionaryEndKey });
- minMax.setMinValues(new byte[][] { startKey, noDictionaryStartKey });
- index.setBtreeIndex(btreeIndex);
- index.setMinMaxIndex(minMax);
- footer.setBlockletIndex(index);
- return footer;
- }
-
- private DataFileFooter getFileMatadataWithOnlyNoDictionaryKey(byte[] startKey, byte[] endKey,
- byte[] noDictionaryStartKey, byte[] noDictionaryEndKey) {
- DataFileFooter footer = new DataFileFooter();
- BlockletIndex index = new BlockletIndex();
- BlockletBTreeIndex btreeIndex = new BlockletBTreeIndex();
- ByteBuffer buffer = ByteBuffer.allocate(4 + 0 + 4 + noDictionaryStartKey.length);
- buffer.putInt(0);
- buffer.putInt(noDictionaryStartKey.length);
- buffer.put(noDictionaryStartKey);
- buffer.rewind();
- btreeIndex.setStartKey(buffer.array());
- ByteBuffer buffer1 = ByteBuffer.allocate(4 + 0 + 4 + noDictionaryEndKey.length);
- buffer1.putInt(0);
- buffer1.putInt(noDictionaryEndKey.length);
- buffer1.put(noDictionaryEndKey);
- buffer1.rewind();
- btreeIndex.setEndKey(buffer1.array());
- BlockletMinMaxIndex minMax = new BlockletMinMaxIndex();
- minMax.setMaxValues(new byte[][] { endKey, noDictionaryEndKey });
- minMax.setMinValues(new byte[][] { startKey, noDictionaryStartKey });
- index.setBtreeIndex(btreeIndex);
- index.setMinMaxIndex(minMax);
- footer.setBlockletIndex(index);
- return footer;
- }
-
- private DataFileFooter getFileFooterWithOnlyDictionaryKey(byte[] startKey, byte[] endKey,
- byte[] noDictionaryStartKey, byte[] noDictionaryEndKey) {
- DataFileFooter footer = new DataFileFooter();
- BlockletIndex index = new BlockletIndex();
- BlockletBTreeIndex btreeIndex = new BlockletBTreeIndex();
- ByteBuffer buffer = ByteBuffer.allocate(4 + startKey.length + 4 + 0);
- buffer.putInt(startKey.length);
- buffer.putInt(0);
- buffer.put(startKey);
- buffer.rewind();
- btreeIndex.setStartKey(buffer.array());
- ByteBuffer buffer1 = ByteBuffer.allocate(4 + 0 + 4 + noDictionaryEndKey.length);
- buffer1.putInt(endKey.length);
- buffer1.putInt(0);
- buffer1.put(endKey);
- buffer1.rewind();
- btreeIndex.setEndKey(buffer1.array());
- BlockletMinMaxIndex minMax = new BlockletMinMaxIndex();
- minMax.setMaxValues(new byte[][] { endKey });
- minMax.setMinValues(new byte[][] { startKey });
- index.setBtreeIndex(btreeIndex);
- index.setMinMaxIndex(minMax);
- footer.setBlockletIndex(index);
- return footer;
- }
-
-}