You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@orc.apache.org by om...@apache.org on 2021/02/23 18:50:27 UTC
[orc] branch master updated: ORC-747: Abstract Dictionary interface
to enable a hash dictionary.
This is an automated email from the ASF dual-hosted git repository.
omalley pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/orc.git
The following commit(s) were added to refs/heads/master by this push:
new 8c5814b ORC-747: Abstract Dictionary interface to enable a hash dictionary.
8c5814b is described below
commit 8c5814bcaed49c93f181751316ad42dcf6080857
Author: Lei Sun <le...@linkedin.com>
AuthorDate: Wed Jan 27 10:43:04 2021 -0800
ORC-747: Abstract Dictionary interface to enable a hash dictionary.
Fixes #637
Signed-off-by: Owen O'Malley <oo...@linkedin.com>
---
java/core/src/java/org/apache/orc/OrcConf.java | 6 ++
.../src/java/org/apache/orc/impl/Dictionary.java | 97 ++++++++++++++++++++++
.../org/apache/orc/impl/StringRedBlackTree.java | 53 ++----------
.../orc/impl/writer/StringBaseTreeWriter.java | 34 ++++++--
.../apache/orc/impl/TestStringRedBlackTree.java | 4 +-
5 files changed, 138 insertions(+), 56 deletions(-)
diff --git a/java/core/src/java/org/apache/orc/OrcConf.java b/java/core/src/java/org/apache/orc/OrcConf.java
index 34c498e..6c2b7ae 100644
--- a/java/core/src/java/org/apache/orc/OrcConf.java
+++ b/java/core/src/java/org/apache/orc/OrcConf.java
@@ -105,6 +105,12 @@ public enum OrcConf {
"(default 10000 rows) else dictionary check will happen before\n" +
"writing first stripe. In both cases, the decision to use\n" +
"dictionary or not will be retained thereafter."),
+ DICTIONARY_IMPL("orc.dictionary.implementation", "orc.dictionary.implementation",
+ "rbtree",
+ "the implementation for the dictionary used for string-type column encoding.\n" +
+ "The choices are:\n"
+ + " rbtree - use red-black tree as the implementation for the dictionary.\n"
+ + " hash (yet to be implemented) - use hash table as the implementation for the dictionary."),
BLOOM_FILTER_COLUMNS("orc.bloom.filter.columns", "orc.bloom.filter.columns",
"", "List of columns to create bloom filters for when writing."),
BLOOM_FILTER_WRITE_VERSION("orc.bloom.filter.write.version",
diff --git a/java/core/src/java/org/apache/orc/impl/Dictionary.java b/java/core/src/java/org/apache/orc/impl/Dictionary.java
new file mode 100644
index 0000000..2b8f45a
--- /dev/null
+++ b/java/core/src/java/org/apache/orc/impl/Dictionary.java
@@ -0,0 +1,97 @@
+/*
+ * 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.orc.impl;
+
+import java.io.IOException;
+import java.io.OutputStream;
+
+import org.apache.hadoop.io.Text;
+
+
+/**
+ * Interface to define the dictionary used for encoding value in columns of specific types like string, char, varchar, etc.
+ */
+public interface Dictionary {
+ enum IMPL {
+ RBTREE,
+ HASH
+ }
+
+ int INITIAL_DICTIONARY_SIZE = 4096;
+
+ /**
+ * Traverse the whole dictionary and apply the action.
+ */
+ void visit(Visitor visitor) throws IOException;
+
+ void clear();
+
+ /**
+ * Given the position index, return the original string before being encoded.
+ */
+ void getText(Text result, int position);
+
+ int add(byte[] bytes, int offset, int length);
+
+ int size();
+
+ long getSizeInBytes();
+
+ /**
+ * The information about each node.
+ */
+ interface VisitorContext {
+ /**
+ * Get the position where the key was originally added.
+ * @return the number returned by add.
+ */
+ int getOriginalPosition();
+
+ /**
+ * Write the bytes for the string to the given output stream.
+ * @param out the stream to write to.
+ * @throws IOException
+ */
+ void writeBytes(OutputStream out) throws IOException;
+
+ /**
+ * Get the original string.
+ * @return the string
+ */
+ Text getText();
+
+ /**
+ * Get the number of bytes.
+ * @return the string's length in bytes
+ */
+ int getLength();
+ }
+
+ /**
+ * The interface for visitors.
+ */
+ interface Visitor {
+ /**
+ * Called once for each node of the tree in sort order.
+ * @param context the information about each node
+ * @throws IOException
+ */
+ void visit(VisitorContext context) throws IOException;
+ }
+}
diff --git a/java/core/src/java/org/apache/orc/impl/StringRedBlackTree.java b/java/core/src/java/org/apache/orc/impl/StringRedBlackTree.java
index ae1d858..44232c7 100644
--- a/java/core/src/java/org/apache/orc/impl/StringRedBlackTree.java
+++ b/java/core/src/java/org/apache/orc/impl/StringRedBlackTree.java
@@ -26,7 +26,7 @@ import org.apache.hadoop.io.Text;
* A red-black tree that stores strings. The strings are stored as UTF-8 bytes
* and an offset for each entry.
*/
-public class StringRedBlackTree extends RedBlackTree {
+public class StringRedBlackTree extends RedBlackTree implements Dictionary {
private final DynamicByteArray byteArray = new DynamicByteArray();
private final DynamicIntArray keyOffsets;
private final Text newKey = new Text();
@@ -55,6 +55,7 @@ public class StringRedBlackTree extends RedBlackTree {
return addNewKey();
}
+ @Override
public int add(byte[] bytes, int offset, int length) {
newKey.set(bytes, offset, length);
return addNewKey();
@@ -73,49 +74,7 @@ public class StringRedBlackTree extends RedBlackTree {
start, end - start);
}
- /**
- * The information about each node.
- */
- public interface VisitorContext {
- /**
- * Get the position where the key was originally added.
- * @return the number returned by add.
- */
- int getOriginalPosition();
-
- /**
- * Write the bytes for the string to the given output stream.
- * @param out the stream to write to.
- * @throws IOException
- */
- void writeBytes(OutputStream out) throws IOException;
-
- /**
- * Get the original string.
- * @return the string
- */
- Text getText();
-
- /**
- * Get the number of bytes.
- * @return the string's length in bytes
- */
- int getLength();
- }
-
- /**
- * The interface for visitors.
- */
- public interface Visitor {
- /**
- * Called once for each node of the tree in sort order.
- * @param context the information about each node
- * @throws IOException
- */
- void visit(VisitorContext context) throws IOException;
- }
-
- private class VisitorContextImpl implements VisitorContext {
+ private class VisitorContextImpl implements Dictionary.VisitorContext {
private int originalPosition;
private int start;
private int end;
@@ -153,7 +112,7 @@ public class StringRedBlackTree extends RedBlackTree {
}
}
- private void recurse(int node, Visitor visitor, VisitorContextImpl context
+ private void recurse(int node, Dictionary.Visitor visitor, VisitorContextImpl context
) throws IOException {
if (node != NULL) {
recurse(getLeft(node), visitor, context);
@@ -168,7 +127,8 @@ public class StringRedBlackTree extends RedBlackTree {
* @param visitor the action to be applied to each node
* @throws IOException
*/
- public void visit(Visitor visitor) throws IOException {
+ @Override
+ public void visit(Dictionary.Visitor visitor) throws IOException {
recurse(root, visitor, new VisitorContextImpl());
}
@@ -182,6 +142,7 @@ public class StringRedBlackTree extends RedBlackTree {
keyOffsets.clear();
}
+ @Override
public void getText(Text result, int originalPosition) {
int offset = keyOffsets.get(originalPosition);
int length;
diff --git a/java/core/src/java/org/apache/orc/impl/writer/StringBaseTreeWriter.java b/java/core/src/java/org/apache/orc/impl/writer/StringBaseTreeWriter.java
index 08f0964..36194ce 100644
--- a/java/core/src/java/org/apache/orc/impl/writer/StringBaseTreeWriter.java
+++ b/java/core/src/java/org/apache/orc/impl/writer/StringBaseTreeWriter.java
@@ -26,6 +26,7 @@ import org.apache.orc.OrcProto;
import org.apache.orc.StringColumnStatistics;
import org.apache.orc.TypeDescription;
import org.apache.orc.impl.CryptoUtils;
+import org.apache.orc.impl.Dictionary;
import org.apache.orc.impl.DynamicIntArray;
import org.apache.orc.impl.IntegerWriter;
import org.apache.orc.impl.OutStream;
@@ -39,13 +40,16 @@ import java.util.ArrayList;
import java.util.List;
import java.util.function.Consumer;
+import static org.apache.orc.OrcConf.DICTIONARY_IMPL;
+import static org.apache.orc.impl.Dictionary.INITIAL_DICTIONARY_SIZE;
+
+
public abstract class StringBaseTreeWriter extends TreeWriterBase {
- private static final int INITIAL_DICTIONARY_SIZE = 4096;
+ // Stream for dictionary's key
private final OutStream stringOutput;
protected final IntegerWriter lengthOutput;
+ // Stream for dictionary-encoded value
private final IntegerWriter rowOutput;
- protected final StringRedBlackTree dictionary =
- new StringRedBlackTree(INITIAL_DICTIONARY_SIZE);
protected final DynamicIntArray rows = new DynamicIntArray();
protected final PositionedOutputStream directStreamOutput;
private final List<OrcProto.RowIndexEntry> savedRowIndex =
@@ -55,15 +59,32 @@ public abstract class StringBaseTreeWriter extends TreeWriterBase {
// If the number of keys in a dictionary is greater than this fraction of
//the total number of non-null rows, turn off dictionary encoding
private final double dictionaryKeySizeThreshold;
+ protected Dictionary dictionary;
protected boolean useDictionaryEncoding = true;
private boolean isDirectV2 = true;
private boolean doneDictionaryCheck;
private final boolean strideDictionaryCheck;
+ private static Dictionary createDict(Configuration conf) {
+ String dictImpl = conf.get(DICTIONARY_IMPL.name(),
+ DICTIONARY_IMPL.getDefaultValue().toString()).toUpperCase();
+ switch (Dictionary.IMPL.valueOf(dictImpl)) {
+ case RBTREE:
+ return new StringRedBlackTree(INITIAL_DICTIONARY_SIZE);
+ case HASH:
+ throw new UnsupportedOperationException("hash based implementation is under development(ORC-50).");
+ default:
+ throw new UnsupportedOperationException("Unknown implementation:" + dictImpl);
+ }
+ }
+
StringBaseTreeWriter(TypeDescription schema,
WriterEncryptionVariant encryption,
WriterContext writer) throws IOException {
super(schema, encryption, writer);
+ Configuration conf = writer.getConfiguration();
+
+ this.dictionary = createDict(conf);
this.isDirectV2 = isNewWriteFormat(writer);
directStreamOutput = writer.createStream(
new StreamName(id, OrcProto.Stream.Kind.DATA, encryption));
@@ -79,7 +100,6 @@ public abstract class StringBaseTreeWriter extends TreeWriterBase {
}
rowIndexValueCount.add(0L);
buildIndex = writer.buildIndex();
- Configuration conf = writer.getConfiguration();
dictionaryKeySizeThreshold = writer.getDictionaryKeySizeThreshold(id);
strideDictionaryCheck =
OrcConf.ROW_INDEX_STRIDE_DICTIONARY_CHECK.getBoolean(conf);
@@ -109,7 +129,6 @@ public abstract class StringBaseTreeWriter extends TreeWriterBase {
// checking would not have happened. So do it again here.
checkDictionaryEncoding();
- checkDictionaryEncoding();
if (!useDictionaryEncoding) {
stringOutput.suppress();
}
@@ -140,12 +159,11 @@ public abstract class StringBaseTreeWriter extends TreeWriterBase {
// Write the dictionary by traversing the red-black tree writing out
// the bytes and lengths; and creating the map from the original order
// to the final sorted order.
-
- dictionary.visit(new StringRedBlackTree.Visitor() {
+ dictionary.visit(new Dictionary.Visitor() {
private int currentId = 0;
@Override
- public void visit(StringRedBlackTree.VisitorContext context
+ public void visit(Dictionary.VisitorContext context
) throws IOException {
context.writeBytes(stringOutput);
lengthOutput.write(context.getLength());
diff --git a/java/core/src/test/org/apache/orc/impl/TestStringRedBlackTree.java b/java/core/src/test/org/apache/orc/impl/TestStringRedBlackTree.java
index 1e2c8fa..34dc64a 100644
--- a/java/core/src/test/org/apache/orc/impl/TestStringRedBlackTree.java
+++ b/java/core/src/test/org/apache/orc/impl/TestStringRedBlackTree.java
@@ -108,7 +108,7 @@ public class TestStringRedBlackTree {
}
}
- private static class MyVisitor implements StringRedBlackTree.Visitor {
+ private static class MyVisitor implements Dictionary.Visitor {
private final String[] words;
private final int[] order;
private final DataOutputBuffer buffer = new DataOutputBuffer();
@@ -120,7 +120,7 @@ public class TestStringRedBlackTree {
}
@Override
- public void visit(StringRedBlackTree.VisitorContext context
+ public void visit(Dictionary.VisitorContext context
) throws IOException {
String word = context.getText().toString();
assertEquals("in word " + current, words[current], word);