You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@orc.apache.org by pg...@apache.org on 2021/06/04 11:16:28 UTC
[orc] branch main updated: ORC-757: HashTable dictionary (#651)
This is an automated email from the ASF dual-hosted git repository.
pgaref pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/orc.git
The following commit(s) were added to refs/heads/main by this push:
new 802bd59 ORC-757: HashTable dictionary (#651)
802bd59 is described below
commit 802bd5922e18543080ac938c5ab7242a14975857
Author: Lei Sun <au...@gmail.com>
AuthorDate: Wed Jan 27 10:43:04 2021 -0800
ORC-757: HashTable dictionary (#651)
### What changes were proposed in this pull request?
- Add a straightforward implementation for `Dictionary` using hash table.
- Refactored RB-Tree to make code reusable, like `VisitorContextImpl`. Moving it into `DictionaryUtils.java` to make is sharable between different implementation of `Dictionary` interface.
- Enabling hash-based dictionary for existing tests that enables dictionary-encoding.
- Added `ORCWriterBenchmark` for benchmarking writer performance with different options.
### Why are the changes needed?
We find RB-Tree based dictionary implementation being slow in our production workload. The performance comparison for the new hash-table based implementation will be done as part of ORC-50.
### How was this patch tested?
Mostly tested with added unit tests for hash-table and enabled hash-table based dictionary in some of the existing tests.
Signed-off-by: Panagiotis Garefalakis <pg...@apache.org>
Change-Id: I91a27ef13e9433231dc684a2d02a0793b9612ed3
---
java/bench/README.md | 3 +
.../apache/orc/bench/core/BenchmarkOptions.java | 2 +
.../core/{ReadCounters.java => IOCounters.java} | 35 ++--
.../java/org/apache/orc/bench/core/Utilities.java | 3 +
.../orc/bench/hive/ColumnProjectionBenchmark.java | 6 +-
.../apache/orc/bench/hive/FullReadBenchmark.java | 10 +-
.../apache/orc/bench/hive/ORCWriterBenchMark.java | 157 ++++++++++++++++
.../bench/hive/RowFilterProjectionBenchmark.java | 6 +-
.../org/apache/orc/bench/spark/SparkBenchmark.java | 10 +-
java/core/src/java/org/apache/orc/OrcConf.java | 4 +-
.../java/org/apache/orc/impl/DictionaryUtils.java | 45 +++++
.../apache/orc/impl/StringHashTableDictionary.java | 206 +++++++++++++++++++++
.../org/apache/orc/impl/StringRedBlackTree.java | 53 +-----
.../org/apache/orc/impl/VisitorContextImpl.java | 75 ++++++++
.../orc/impl/writer/StringBaseTreeWriter.java | 7 +-
.../org/apache/orc/StringDictTestingUtils.java | 65 +++++++
.../test/org/apache/orc/TestStringDictionary.java | 34 +++-
.../orc/impl/TestStringHashTableDictionary.java | 153 +++++++++++++++
.../apache/orc/impl/TestStringRedBlackTree.java | 41 +---
19 files changed, 789 insertions(+), 126 deletions(-)
diff --git a/java/bench/README.md b/java/bench/README.md
index c0ee992..0a85d44 100644
--- a/java/bench/README.md
+++ b/java/bench/README.md
@@ -33,6 +33,9 @@ To run full read benchmark:
```% java -jar hive/target/orc-benchmarks-hive-*-uber.jar read-all data```
+To run a write benchmark:
+```% java -jar hive/target/orc-benchmarks-hive-*-uber.jar write data```
+
To run column projection benchmark:
```% java -jar hive/target/orc-benchmarks-hive-*-uber.jar read-some data```
diff --git a/java/bench/core/src/java/org/apache/orc/bench/core/BenchmarkOptions.java b/java/bench/core/src/java/org/apache/orc/bench/core/BenchmarkOptions.java
index a64c605..27f1717 100644
--- a/java/bench/core/src/java/org/apache/orc/bench/core/BenchmarkOptions.java
+++ b/java/bench/core/src/java/org/apache/orc/bench/core/BenchmarkOptions.java
@@ -34,6 +34,7 @@ public class BenchmarkOptions {
public static final String MIN_MEMORY = "min-memory";
public static final String MAX_MEMORY = "max-memory";
public static final String GC = "gc";
+ public static final String STACK_PROFILE = "stack";
public static CommandLine parseCommandLine(String[] args) {
Options options = new Options()
@@ -44,6 +45,7 @@ public class BenchmarkOptions {
.addOption("t", TIME, true, "How long each iteration is in seconds")
.addOption("m", MIN_MEMORY, true, "The minimum size of each JVM")
.addOption("M", MAX_MEMORY, true, "The maximum size of each JVM")
+ .addOption("p", STACK_PROFILE, false, "Should enable stack profiler in JMH")
.addOption("g", GC, false, "Should GC be profiled");
CommandLine result;
try {
diff --git a/java/bench/core/src/java/org/apache/orc/bench/core/ReadCounters.java b/java/bench/core/src/java/org/apache/orc/bench/core/IOCounters.java
similarity index 73%
rename from java/bench/core/src/java/org/apache/orc/bench/core/ReadCounters.java
rename to java/bench/core/src/java/org/apache/orc/bench/core/IOCounters.java
index 6c07458..d1f6b9d 100644
--- a/java/bench/core/src/java/org/apache/orc/bench/core/ReadCounters.java
+++ b/java/bench/core/src/java/org/apache/orc/bench/core/IOCounters.java
@@ -26,20 +26,22 @@ import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.TearDown;
/**
- * A class to track the number of rows, bytes, and read operations that have
- * been read.
+ * A class to track the number of rows, bytes, and read/write operations that have
+ * been read/write.
+ * The read/write is named as "IO" instead of "RW" to avoid ambiguity as the latter could indicate the
+ * counts including both read and write, instead of either read or write.
*/
@AuxCounters(AuxCounters.Type.EVENTS)
@State(Scope.Thread)
-public class ReadCounters {
- long bytesRead;
- long reads;
+public class IOCounters {
+ long bytesIO;
+ long io;
RecordCounters recordCounters;
@Setup(Level.Iteration)
public void setup(RecordCounters records) {
- bytesRead = 0;
- reads = 0;
+ bytesIO = 0;
+ io = 0;
recordCounters = records;
}
@@ -48,13 +50,13 @@ public class ReadCounters {
if (recordCounters != null) {
recordCounters.print();
}
- System.out.println("Reads: " + reads);
- System.out.println("Bytes: " + bytesRead);
+ System.out.println("io: " + io);
+ System.out.println("Bytes: " + bytesIO);
}
public double bytesPerRecord() {
return recordCounters == null || recordCounters.records == 0 ?
- 0 : ((double) bytesRead) / recordCounters.records;
+ 0 : ((double) bytesIO) / recordCounters.records;
}
public long records() {
@@ -62,9 +64,12 @@ public class ReadCounters {
0 : recordCounters.records / recordCounters.invocations;
}
- public long reads() {
+ /**
+ * Capture the number of I/O on average in each invocation.
+ */
+ public long ops() {
return recordCounters == null || recordCounters.invocations == 0 ?
- 0 : reads / recordCounters.invocations;
+ 0 : io / recordCounters.invocations;
}
public void addRecords(long value) {
@@ -79,8 +84,8 @@ public class ReadCounters {
}
}
- public void addBytes(long newReads, long newBytes) {
- bytesRead += newBytes;
- reads += newReads;
+ public void addBytes(long newIOs, long newBytes) {
+ bytesIO += newBytes;
+ io += newIOs;
}
}
diff --git a/java/bench/core/src/java/org/apache/orc/bench/core/Utilities.java b/java/bench/core/src/java/org/apache/orc/bench/core/Utilities.java
index 17f208d..92ae0d4 100644
--- a/java/bench/core/src/java/org/apache/orc/bench/core/Utilities.java
+++ b/java/bench/core/src/java/org/apache/orc/bench/core/Utilities.java
@@ -90,6 +90,9 @@ public class Utilities {
if (options.hasOption(BenchmarkOptions.GC)) {
builder.addProfiler("hs_gc");
}
+ if (options.hasOption(BenchmarkOptions.STACK_PROFILE)) {
+ builder.addProfiler("stack");
+ }
builder.measurementIterations(Integer.parseInt(options.getOptionValue(
BenchmarkOptions.ITERATIONS, "5")));
builder.warmupIterations(Integer.parseInt(options.getOptionValue(
diff --git a/java/bench/hive/src/java/org/apache/orc/bench/hive/ColumnProjectionBenchmark.java b/java/bench/hive/src/java/org/apache/orc/bench/hive/ColumnProjectionBenchmark.java
index 146a6e7..4c9948e 100644
--- a/java/bench/hive/src/java/org/apache/orc/bench/hive/ColumnProjectionBenchmark.java
+++ b/java/bench/hive/src/java/org/apache/orc/bench/hive/ColumnProjectionBenchmark.java
@@ -36,7 +36,7 @@ import org.apache.orc.Reader;
import org.apache.orc.RecordReader;
import org.apache.orc.TypeDescription;
import org.apache.orc.bench.core.OrcBenchmark;
-import org.apache.orc.bench.core.ReadCounters;
+import org.apache.orc.bench.core.IOCounters;
import org.apache.orc.bench.core.Utilities;
import org.apache.parquet.hadoop.ParquetInputFormat;
import org.openjdk.jmh.annotations.Benchmark;
@@ -82,7 +82,7 @@ public class ColumnProjectionBenchmark implements OrcBenchmark {
}
@Benchmark
- public void orc(ReadCounters counters) throws Exception{
+ public void orc(IOCounters counters) throws Exception{
Configuration conf = new Configuration();
TrackingLocalFileSystem fs = new TrackingLocalFileSystem();
fs.initialize(new URI("file:///"), conf);
@@ -110,7 +110,7 @@ public class ColumnProjectionBenchmark implements OrcBenchmark {
}
@Benchmark
- public void parquet(ReadCounters counters) throws Exception {
+ public void parquet(IOCounters counters) throws Exception {
JobConf conf = new JobConf();
conf.set("fs.track.impl", TrackingLocalFileSystem.class.getName());
conf.set("fs.defaultFS", "track:///");
diff --git a/java/bench/hive/src/java/org/apache/orc/bench/hive/FullReadBenchmark.java b/java/bench/hive/src/java/org/apache/orc/bench/hive/FullReadBenchmark.java
index 2bbcf60..b391fe6 100644
--- a/java/bench/hive/src/java/org/apache/orc/bench/hive/FullReadBenchmark.java
+++ b/java/bench/hive/src/java/org/apache/orc/bench/hive/FullReadBenchmark.java
@@ -43,7 +43,7 @@ import org.apache.orc.RecordReader;
import org.apache.orc.TypeDescription;
import org.apache.orc.bench.core.CompressionKind;
import org.apache.orc.bench.core.OrcBenchmark;
-import org.apache.orc.bench.core.ReadCounters;
+import org.apache.orc.bench.core.IOCounters;
import org.apache.orc.bench.core.Utilities;
import org.apache.parquet.hadoop.ParquetInputFormat;
import org.openjdk.jmh.annotations.Benchmark;
@@ -91,7 +91,7 @@ public class FullReadBenchmark implements OrcBenchmark {
}
@Benchmark
- public void orc(ReadCounters counters) throws Exception{
+ public void orc(IOCounters counters) throws Exception{
Configuration conf = new Configuration();
TrackingLocalFileSystem fs = new TrackingLocalFileSystem();
fs.initialize(new URI("file:///"), conf);
@@ -112,7 +112,7 @@ public class FullReadBenchmark implements OrcBenchmark {
}
@Benchmark
- public void avro(ReadCounters counters) throws Exception {
+ public void avro(IOCounters counters) throws Exception {
Configuration conf = new Configuration();
conf.set("fs.track.impl", TrackingLocalFileSystem.class.getName());
conf.set("fs.defaultFS", "track:///");
@@ -134,7 +134,7 @@ public class FullReadBenchmark implements OrcBenchmark {
}
@Benchmark
- public void parquet(ReadCounters counters) throws Exception {
+ public void parquet(IOCounters counters) throws Exception {
JobConf conf = new JobConf();
conf.set("fs.track.impl", TrackingLocalFileSystem.class.getName());
conf.set("fs.defaultFS", "track:///");
@@ -159,7 +159,7 @@ public class FullReadBenchmark implements OrcBenchmark {
}
@Benchmark
- public void json(ReadCounters counters) throws Exception {
+ public void json(IOCounters counters) throws Exception {
Configuration conf = new Configuration();
TrackingLocalFileSystem fs = new TrackingLocalFileSystem();
fs.initialize(new URI("file:///"), conf);
diff --git a/java/bench/hive/src/java/org/apache/orc/bench/hive/ORCWriterBenchMark.java b/java/bench/hive/src/java/org/apache/orc/bench/hive/ORCWriterBenchMark.java
new file mode 100644
index 0000000..6dd8bd9
--- /dev/null
+++ b/java/bench/hive/src/java/org/apache/orc/bench/hive/ORCWriterBenchMark.java
@@ -0,0 +1,157 @@
+/*
+ * 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.bench.hive;
+
+import java.net.URI;
+import java.nio.charset.StandardCharsets;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Random;
+import java.util.concurrent.TimeUnit;
+
+import org.apache.hadoop.conf.Configuration;
+import org.apache.hadoop.fs.FileSystem;
+import org.apache.hadoop.fs.Path;
+import org.apache.hadoop.fs.TrackingLocalFileSystem;
+import org.apache.hadoop.hive.ql.exec.vector.BytesColumnVector;
+import org.apache.hadoop.hive.ql.exec.vector.VectorizedRowBatch;
+import org.apache.orc.CompressionKind;
+import org.apache.orc.OrcConf;
+import org.apache.orc.OrcFile;
+import org.apache.orc.TypeDescription;
+import org.apache.orc.Writer;
+import org.apache.orc.bench.core.IOCounters;
+import org.apache.orc.bench.core.OrcBenchmark;
+import org.apache.orc.bench.core.Utilities;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Level;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Param;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.TearDown;
+import org.openjdk.jmh.runner.Runner;
+
+import com.google.auto.service.AutoService;
+
+
+@BenchmarkMode(Mode.AverageTime)
+@OutputTimeUnit(TimeUnit.MICROSECONDS)
+@State(Scope.Thread)
+@AutoService(OrcBenchmark.class)
+public class ORCWriterBenchMark implements OrcBenchmark {
+ private static final Path root = Utilities.getBenchmarkRoot();
+ private Path dumpDir = new Path(root, "dumpDir");
+ private List<VectorizedRowBatch> batches = new ArrayList<>();
+
+ @Override
+ public String getName() {
+ return "write";
+ }
+
+ @Override
+ public String getDescription() {
+ return "Benchmark ORC Writer with different DICT options";
+ }
+
+ @Setup(Level.Trial)
+ public void prepareData() {
+ TypeDescription schema = TypeDescription.fromString("struct<str:string>");
+ VectorizedRowBatch batch = schema.createRowBatch();
+ BytesColumnVector strVector = (BytesColumnVector) batch.cols[0];
+
+ Random rand = new Random();
+ for (int i = 0; i < 32 * 1024; i++) {
+ if (batch.size == batch.getMaxSize()) {
+ batches.add(batch);
+ batch = schema.createRowBatch();
+ strVector = (BytesColumnVector) batch.cols[0];
+ }
+ int randomNum = rand.nextInt(distinctCount - 10 + 1) + 10;
+ byte[] value = String.format("row %06d", randomNum).getBytes(StandardCharsets.UTF_8);
+ strVector.setRef(batch.size, value, 0, value.length);
+ ++batch.size;
+ }
+
+ batches.add(batch);
+ }
+
+ @Param({"RBTREE", "HASH", "NONE"})
+ public String dictImpl;
+
+ /**
+ * Controlling the bound of randomly generated data which is used to control the number of distinct keys
+ * appeared in the dictionary.
+ */
+ @Param({"10000", "2500", "500"})
+ public int distinctCount;
+
+
+ @TearDown(Level.Invocation)
+ public void tearDownBenchmark()
+ throws Exception {
+ // Cleaning up the dump files.
+ Configuration conf = new Configuration();
+ TrackingLocalFileSystem fs = new TrackingLocalFileSystem();
+ fs.initialize(new URI("file:///"), conf);
+ fs.delete(dumpDir, true);
+ }
+
+ @Override
+ public void run(String[] args)
+ throws Exception {
+ new Runner(Utilities.parseOptions(args, getClass())).run();
+ }
+
+ @Benchmark
+ public void dictBench(IOCounters counters)
+ throws Exception {
+ Configuration conf = new Configuration();
+ if (dictImpl.equalsIgnoreCase("NONE")) {
+ // turn off the dictionaries
+ OrcConf.DICTIONARY_KEY_SIZE_THRESHOLD.setDouble(conf, 0);
+ } else {
+ OrcConf.DICTIONARY_IMPL.setString(conf, dictImpl);
+ }
+
+ TrackingLocalFileSystem fs = new TrackingLocalFileSystem();
+ fs.initialize(new URI("file:///"), conf);
+ FileSystem.Statistics statistics = fs.getLocalStatistics();
+ statistics.reset();
+ Path testFilePath = new Path(dumpDir, "dictBench");
+
+ TypeDescription schema = TypeDescription.fromString("struct<str:string>");
+ // Note that the total data volume will be around 100 * 1024 * 1024
+ Writer writer = OrcFile.createWriter(testFilePath,
+ OrcFile.writerOptions(conf).fileSystem(fs).setSchema(schema).compress(CompressionKind.NONE)
+ .stripeSize(128 * 1024));
+
+ for (VectorizedRowBatch batch : batches) {
+ writer.addRowBatch(batch);
+ counters.addRecords(batch.size);
+ }
+
+ writer.close();
+ counters.addBytes(statistics.getWriteOps(), statistics.getBytesWritten());
+ counters.addInvocation();
+ }
+}
diff --git a/java/bench/hive/src/java/org/apache/orc/bench/hive/RowFilterProjectionBenchmark.java b/java/bench/hive/src/java/org/apache/orc/bench/hive/RowFilterProjectionBenchmark.java
index a804a4a..4cbfbe2 100644
--- a/java/bench/hive/src/java/org/apache/orc/bench/hive/RowFilterProjectionBenchmark.java
+++ b/java/bench/hive/src/java/org/apache/orc/bench/hive/RowFilterProjectionBenchmark.java
@@ -28,7 +28,7 @@ import org.apache.orc.Reader;
import org.apache.orc.RecordReader;
import org.apache.orc.TypeDescription;
import org.apache.orc.bench.core.OrcBenchmark;
-import org.apache.orc.bench.core.ReadCounters;
+import org.apache.orc.bench.core.IOCounters;
import org.apache.orc.bench.core.Utilities;
import org.apache.orc.OrcFilterContext;
import org.openjdk.jmh.annotations.Benchmark;
@@ -107,7 +107,7 @@ public class RowFilterProjectionBenchmark implements OrcBenchmark {
}
@Benchmark
- public void orcRowFilter(ReadCounters counters) throws Exception {
+ public void orcRowFilter(IOCounters counters) throws Exception {
Configuration conf = new Configuration();
TrackingLocalFileSystem fs = new TrackingLocalFileSystem();
fs.initialize(new URI("file:///"), conf);
@@ -165,7 +165,7 @@ public class RowFilterProjectionBenchmark implements OrcBenchmark {
}
@Benchmark
- public void orcNoFilter(ReadCounters counters) throws Exception {
+ public void orcNoFilter(IOCounters counters) throws Exception {
Configuration conf = new Configuration();
TrackingLocalFileSystem fs = new TrackingLocalFileSystem();
fs.initialize(new URI("file:///"), conf);
diff --git a/java/bench/spark/src/java/org/apache/orc/bench/spark/SparkBenchmark.java b/java/bench/spark/src/java/org/apache/orc/bench/spark/SparkBenchmark.java
index 8a87aa5..f01c140 100644
--- a/java/bench/spark/src/java/org/apache/orc/bench/spark/SparkBenchmark.java
+++ b/java/bench/spark/src/java/org/apache/orc/bench/spark/SparkBenchmark.java
@@ -25,7 +25,7 @@ import org.apache.hadoop.fs.Path;
import org.apache.hadoop.fs.TrackingLocalFileSystem;
import org.apache.orc.TypeDescription;
import org.apache.orc.bench.core.OrcBenchmark;
-import org.apache.orc.bench.core.ReadCounters;
+import org.apache.orc.bench.core.IOCounters;
import org.apache.orc.bench.core.Utilities;
import org.apache.spark.sql.SparkSession;
import org.apache.spark.sql.avro.AvroFileFormat;
@@ -153,7 +153,7 @@ public class SparkBenchmark implements OrcBenchmark {
static void processReader(Iterator<InternalRow> reader,
FileSystem.Statistics statistics,
- ReadCounters counters,
+ IOCounters counters,
Blackhole blackhole) {
while (reader.hasNext()) {
Object row = reader.next();
@@ -170,7 +170,7 @@ public class SparkBenchmark implements OrcBenchmark {
@Benchmark
public void fullRead(InputSource source,
- ReadCounters counters,
+ IOCounters counters,
Blackhole blackhole) {
FileSystem.Statistics statistics = source.fs.getLocalStatistics();
statistics.reset();
@@ -199,7 +199,7 @@ public class SparkBenchmark implements OrcBenchmark {
@Benchmark
public void partialRead(InputSource source,
- ReadCounters counters,
+ IOCounters counters,
Blackhole blackhole) {
FileSystem.Statistics statistics = source.fs.getLocalStatistics();
statistics.reset();
@@ -246,7 +246,7 @@ public class SparkBenchmark implements OrcBenchmark {
@Benchmark
public void pushDown(InputSource source,
- ReadCounters counters,
+ IOCounters counters,
Blackhole blackhole) {
FileSystem.Statistics statistics = source.fs.getLocalStatistics();
statistics.reset();
diff --git a/java/core/src/java/org/apache/orc/OrcConf.java b/java/core/src/java/org/apache/orc/OrcConf.java
index 30b7ed6..13335df 100644
--- a/java/core/src/java/org/apache/orc/OrcConf.java
+++ b/java/core/src/java/org/apache/orc/OrcConf.java
@@ -106,11 +106,11 @@ public enum OrcConf {
"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",
+ "hash",
"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."),
+ + " hash - 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/DictionaryUtils.java b/java/core/src/java/org/apache/orc/impl/DictionaryUtils.java
new file mode 100644
index 0000000..91a397a
--- /dev/null
+++ b/java/core/src/java/org/apache/orc/impl/DictionaryUtils.java
@@ -0,0 +1,45 @@
+/**
+ * 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 org.apache.hadoop.io.Text;
+
+
+public class DictionaryUtils {
+ private DictionaryUtils() {
+ // Utility class does nothing in constructor
+ }
+
+ /**
+ * Obtain the UTF8 string from the byteArray using the offset in index-array.
+ * @param result Container for the UTF8 String.
+ * @param position position in the keyOffsets
+ * @param keyOffsets starting offset of the key (in byte) in the byte array.
+ * @param byteArray storing raw bytes of all key seen in dictionary
+ */
+ public static void getTextInternal(Text result, int position, DynamicIntArray keyOffsets, DynamicByteArray byteArray) {
+ int offset = keyOffsets.get(position);
+ int length;
+ if (position + 1 == keyOffsets.size()) {
+ length = byteArray.size() - offset;
+ } else {
+ length = keyOffsets.get(position + 1) - offset;
+ }
+ byteArray.setText(result, offset, length);
+ }
+}
diff --git a/java/core/src/java/org/apache/orc/impl/StringHashTableDictionary.java b/java/core/src/java/org/apache/orc/impl/StringHashTableDictionary.java
new file mode 100644
index 0000000..b33dfd4
--- /dev/null
+++ b/java/core/src/java/org/apache/orc/impl/StringHashTableDictionary.java
@@ -0,0 +1,206 @@
+/*
+ * 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.util.Arrays;
+
+import org.apache.hadoop.io.Text;
+
+
+/**
+ * Using HashTable to represent a dictionary. The strings are stored as UTF-8 bytes
+ * and an offset for each entry. It is using chaining for collision resolution.
+ *
+ * This implementation is not thread-safe.
+ */
+public class StringHashTableDictionary implements Dictionary {
+
+ // containing all keys every seen in bytes.
+ private final DynamicByteArray byteArray = new DynamicByteArray();
+ // containing starting offset of the key (in byte) in the byte array.
+ private final DynamicIntArray keyOffsets;
+
+ private final Text newKey = new Text();
+
+ private DynamicIntArray[] hashBuckets;
+
+ private int capacity;
+
+ private int threshold;
+
+ private float loadFactor;
+
+ private static float DEFAULT_LOAD_FACTOR = 0.75f;
+
+ /**
+ * Picked based on :
+ * 1. default strip size (64MB),
+ * 2. an assumption that record size is around 500B,
+ * 3. and an assumption that there are 20% distinct keys among all keys seen within a stripe.
+ * We then have the following equation:
+ * 4096 * 0.75 (capacity without resize) * avgBucketSize * 5 (20% distinct) = 64 * 1024 * 1024 / 500
+ * from which we deduce avgBucketSize ~8
+ */
+ private static final int BUCKET_SIZE = 8;
+
+ /**
+ * The maximum size of array to allocate, value being the same as {@link java.util.Hashtable},
+ * given the fact that the stripe size could be increased to larger value by configuring "orc.stripe.size".
+ */
+ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
+
+ public StringHashTableDictionary(int initialCapacity) {
+ this(initialCapacity, DEFAULT_LOAD_FACTOR);
+ }
+
+ public StringHashTableDictionary(int initialCapacity, float loadFactor) {
+ this.capacity = initialCapacity;
+ this.loadFactor = loadFactor;
+ this.keyOffsets = new DynamicIntArray(initialCapacity);
+ initHashBuckets(initialCapacity);
+ this.threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
+ }
+
+ private void initHashBuckets(int capacity) {
+ DynamicIntArray[] buckets = new DynamicIntArray[capacity];
+ for (int i = 0; i < capacity; i++) {
+ // We don't need large bucket: If we have more than a handful of collisions,
+ // then the table is too small or the function isn't good.
+ buckets[i] = createBucket();
+ }
+ hashBuckets = buckets;
+ }
+
+ private DynamicIntArray createBucket() {
+ return new DynamicIntArray(BUCKET_SIZE);
+ }
+
+ @Override
+ public void visit(Visitor visitor)
+ throws IOException {
+ traverse(visitor, new VisitorContextImpl(this.byteArray, this.keyOffsets));
+ }
+
+ private void traverse(Visitor visitor, VisitorContextImpl context) throws IOException {
+ for (DynamicIntArray intArray : hashBuckets) {
+ for (int i = 0; i < intArray.size() ; i ++) {
+ context.setPosition(intArray.get(i));
+ visitor.visit(context);
+ }
+ }
+ }
+
+ @Override
+ public void clear() {
+ byteArray.clear();
+ keyOffsets.clear();
+ initHashBuckets(this.capacity);
+ }
+
+ @Override
+ public void getText(Text result, int positionInKeyOffset) {
+ DictionaryUtils.getTextInternal(result, positionInKeyOffset, this.keyOffsets, this.byteArray);
+ }
+
+ @Override
+ public int add(byte[] bytes, int offset, int length) {
+ newKey.set(bytes, offset, length);
+ return add(newKey);
+ }
+
+ public int add(Text text) {
+ resizeIfNeeded();
+ newKey.set(text);
+
+ int index = getIndex(text);
+ DynamicIntArray candidateArray = hashBuckets[index];
+
+ Text tmpText = new Text();
+ for (int i = 0; i < candidateArray.size(); i++) {
+ getText(tmpText, candidateArray.get(i));
+ if (tmpText.equals(newKey)) {
+ return candidateArray.get(i);
+ }
+ }
+
+ // if making it here, it means no match.
+ int len = newKey.getLength();
+ int currIdx = keyOffsets.size();
+ keyOffsets.add(byteArray.add(newKey.getBytes(), 0, len));
+ candidateArray.add(currIdx);
+ return currIdx;
+ }
+
+ private void resizeIfNeeded() {
+ if (keyOffsets.size() >= threshold) {
+ int oldCapacity = this.capacity;
+ int newCapacity = (oldCapacity << 1) + 1;
+ this.capacity = newCapacity;
+
+ doResize(newCapacity, oldCapacity);
+
+ this.threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
+ }
+ }
+
+ @Override
+ public int size() {
+ return keyOffsets.size();
+ }
+
+ /**
+ * Compute the hash value and find the corresponding index.
+ *
+ */
+ int getIndex(Text text) {
+ return Math.floorMod(text.hashCode(), capacity);
+ }
+
+ // Resize the hash table, re-hash all the existing keys.
+ // byteArray and keyOffsetsArray don't have to be re-filled.
+ private void doResize(int newCapacity, int oldCapacity) {
+ DynamicIntArray[] resizedHashBuckets = new DynamicIntArray[newCapacity];
+ for (int i = 0; i < newCapacity; i++) {
+ resizedHashBuckets[i] = createBucket();
+ }
+
+ Text tmpText = new Text();
+ for (int i = 0; i < oldCapacity; i++) {
+ DynamicIntArray oldBucket = hashBuckets[i];
+ for (int j = 0; j < oldBucket.size(); j++) {
+ getText(tmpText, oldBucket.get(j));
+ resizedHashBuckets[getIndex(tmpText)].add(oldBucket.get(j));
+ }
+ }
+
+ Arrays.fill(hashBuckets, null);
+ hashBuckets = resizedHashBuckets;
+ }
+
+ @Override
+ public long getSizeInBytes() {
+ long bucketTotalSize = 0L;
+ for (DynamicIntArray dynamicIntArray : hashBuckets) {
+ bucketTotalSize += dynamicIntArray.size();
+ }
+
+ return byteArray.getSizeInBytes() + keyOffsets.getSizeInBytes() + bucketTotalSize ;
+ }
+}
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 44232c7..e8088cc 100644
--- a/java/core/src/java/org/apache/orc/impl/StringRedBlackTree.java
+++ b/java/core/src/java/org/apache/orc/impl/StringRedBlackTree.java
@@ -18,7 +18,6 @@
package org.apache.orc.impl;
import java.io.IOException;
-import java.io.OutputStream;
import org.apache.hadoop.io.Text;
@@ -74,46 +73,10 @@ public class StringRedBlackTree extends RedBlackTree implements Dictionary {
start, end - start);
}
- private class VisitorContextImpl implements Dictionary.VisitorContext {
- private int originalPosition;
- private int start;
- private int end;
- private final Text text = new Text();
- @Override
- public int getOriginalPosition() {
- return originalPosition;
- }
-
- @Override
- public Text getText() {
- byteArray.setText(text, start, end - start);
- return text;
- }
-
- @Override
- public void writeBytes(OutputStream out) throws IOException {
- byteArray.write(out, start, end - start);
- }
-
- @Override
- public int getLength() {
- return end - start;
- }
-
- void setPosition(int position) {
- originalPosition = position;
- start = keyOffsets.get(originalPosition);
- if (position + 1 == keyOffsets.size()) {
- end = byteArray.size();
- } else {
- end = keyOffsets.get(originalPosition + 1);
- }
- }
- }
- private void recurse(int node, Dictionary.Visitor visitor, VisitorContextImpl context
- ) throws IOException {
+ private void recurse(int node, Dictionary.Visitor visitor,
+ VisitorContextImpl context) throws IOException {
if (node != NULL) {
recurse(getLeft(node), visitor, context);
context.setPosition(node);
@@ -129,7 +92,8 @@ public class StringRedBlackTree extends RedBlackTree implements Dictionary {
*/
@Override
public void visit(Dictionary.Visitor visitor) throws IOException {
- recurse(root, visitor, new VisitorContextImpl());
+ recurse(root, visitor,
+ new VisitorContextImpl(this.byteArray, this.keyOffsets));
}
/**
@@ -144,14 +108,7 @@ public class StringRedBlackTree extends RedBlackTree implements Dictionary {
@Override
public void getText(Text result, int originalPosition) {
- int offset = keyOffsets.get(originalPosition);
- int length;
- if (originalPosition + 1 == keyOffsets.size()) {
- length = byteArray.size() - offset;
- } else {
- length = keyOffsets.get(originalPosition + 1) - offset;
- }
- byteArray.setText(result, offset, length);
+ DictionaryUtils.getTextInternal(result, originalPosition, this.keyOffsets, this.byteArray);
}
/**
diff --git a/java/core/src/java/org/apache/orc/impl/VisitorContextImpl.java b/java/core/src/java/org/apache/orc/impl/VisitorContextImpl.java
new file mode 100644
index 0000000..ec97688
--- /dev/null
+++ b/java/core/src/java/org/apache/orc/impl/VisitorContextImpl.java
@@ -0,0 +1,75 @@
+/**
+ * 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;
+
+
+/**
+ * Base implementation for {@link org.apache.orc.impl.Dictionary.VisitorContext} used to traversing
+ * all nodes in a dictionary.
+ */
+public class VisitorContextImpl implements Dictionary.VisitorContext {
+ private int originalPosition;
+ private int start;
+ private int end;
+ private final DynamicIntArray keyOffsets;
+ private final DynamicByteArray byteArray;
+ private final Text text = new Text();
+
+ public VisitorContextImpl(DynamicByteArray byteArray, DynamicIntArray keyOffsets) {
+ this.byteArray = byteArray;
+ this.keyOffsets = keyOffsets;
+ }
+
+ @Override
+ public int getOriginalPosition() {
+ return originalPosition;
+ }
+
+ @Override
+ public Text getText() {
+ byteArray.setText(text, start, end - start);
+ return text;
+ }
+
+ @Override
+ public void writeBytes(OutputStream out)
+ throws IOException {
+ byteArray.write(out, start, end - start);
+ }
+
+ @Override
+ public int getLength() {
+ return end - start;
+ }
+
+ public void setPosition(int position) {
+ originalPosition = position;
+ start = keyOffsets.get(originalPosition);
+ if (position + 1 == keyOffsets.size()) {
+ end = byteArray.size();
+ } else {
+ end = keyOffsets.get(originalPosition + 1);
+ }
+ }
+}
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 36194ce..fc5bb80 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
@@ -33,6 +33,7 @@ import org.apache.orc.impl.OutStream;
import org.apache.orc.impl.PositionRecorder;
import org.apache.orc.impl.PositionedOutputStream;
import org.apache.orc.impl.StreamName;
+import org.apache.orc.impl.StringHashTableDictionary;
import org.apache.orc.impl.StringRedBlackTree;
import java.io.IOException;
@@ -66,13 +67,13 @@ public abstract class StringBaseTreeWriter extends TreeWriterBase {
private final boolean strideDictionaryCheck;
private static Dictionary createDict(Configuration conf) {
- String dictImpl = conf.get(DICTIONARY_IMPL.name(),
+ String dictImpl = conf.get(DICTIONARY_IMPL.getAttribute(),
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).");
+ return new StringHashTableDictionary(INITIAL_DICTIONARY_SIZE);
default:
throw new UnsupportedOperationException("Unknown implementation:" + dictImpl);
}
@@ -156,7 +157,7 @@ public abstract class StringBaseTreeWriter extends TreeWriterBase {
final int[] dumpOrder = new int[dictionary.size()];
if (useDictionaryEncoding) {
- // Write the dictionary by traversing the red-black tree writing out
+ // Write the dictionary by traversing the dictionary writing out
// the bytes and lengths; and creating the map from the original order
// to the final sorted order.
dictionary.visit(new Dictionary.Visitor() {
diff --git a/java/core/src/test/org/apache/orc/StringDictTestingUtils.java b/java/core/src/test/org/apache/orc/StringDictTestingUtils.java
new file mode 100644
index 0000000..cbe22eb
--- /dev/null
+++ b/java/core/src/test/org/apache/orc/StringDictTestingUtils.java
@@ -0,0 +1,65 @@
+/*
+ * 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;
+
+import java.io.IOException;
+import java.nio.charset.StandardCharsets;
+
+import org.apache.hadoop.io.DataOutputBuffer;
+import org.apache.orc.impl.Dictionary;
+
+import static org.junit.Assert.assertEquals;
+
+
+/**
+ * The utility class for testing different implementation of dictionary.
+ */
+public class StringDictTestingUtils {
+ private StringDictTestingUtils() {
+ // Avoid accidental instantiate
+ }
+
+ public static void checkContents(Dictionary dict, int[] order, String... params)
+ throws IOException {
+ dict.visit(new MyVisitor(params, order));
+ }
+
+ public static class MyVisitor implements Dictionary.Visitor {
+ private final String[] words;
+ private final int[] order;
+ private final DataOutputBuffer buffer = new DataOutputBuffer();
+ int current = 0;
+
+ MyVisitor(String[] args, int[] order) {
+ words = args;
+ this.order = order;
+ }
+
+ @Override
+ public void visit(Dictionary.VisitorContext context)
+ throws IOException {
+ String word = context.getText().toString();
+ assertEquals("in word " + current, words[current], word);
+ assertEquals("in word " + current, order[current], context.getOriginalPosition());
+ buffer.reset();
+ context.writeBytes(buffer);
+ assertEquals(word, new String(buffer.getData(), 0, buffer.getLength(), StandardCharsets.UTF_8));
+ current += 1;
+ }
+ }
+}
diff --git a/java/core/src/test/org/apache/orc/TestStringDictionary.java b/java/core/src/test/org/apache/orc/TestStringDictionary.java
index 1cba6f4..81d52ca 100644
--- a/java/core/src/test/org/apache/orc/TestStringDictionary.java
+++ b/java/core/src/test/org/apache/orc/TestStringDictionary.java
@@ -22,6 +22,8 @@ import static org.junit.Assert.assertTrue;
import java.io.File;
import java.nio.charset.StandardCharsets;
+import java.util.Arrays;
+import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
@@ -49,7 +51,11 @@ import org.junit.Before;
import org.junit.Rule;
import org.junit.Test;
import org.junit.rules.TestName;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
public class TestStringDictionary {
private Path workDir = new Path(System.getProperty("test.tmp.dir", "target" + File.separator + "test"
@@ -58,6 +64,7 @@ public class TestStringDictionary {
private Configuration conf;
private FileSystem fs;
private Path testFilePath;
+ private String dictImplString;
@Rule
public TestName testCaseName = new TestName();
@@ -68,6 +75,19 @@ public class TestStringDictionary {
fs = FileSystem.getLocal(conf);
testFilePath = new Path(workDir, "TestStringDictionary." + testCaseName.getMethodName() + ".orc");
fs.delete(testFilePath, false);
+ OrcConf.DICTIONARY_IMPL.setString(conf, dictImplString);
+ }
+
+ @Parameterized.Parameters
+ public static Collection params() {
+ return Arrays.asList(new Object[][] {
+ { "RBTREE" },
+ { "HASH" }
+ });
+ }
+
+ public TestStringDictionary(String dictImpl) {
+ this.dictImplString = dictImpl;
}
@Test
@@ -116,21 +136,23 @@ public class TestStringDictionary {
@Test
public void testHalfDistinct() throws Exception {
- TypeDescription schema = TypeDescription.createString();
+ final int totalSize = 20000;
+ final int bound = 10000;
+ TypeDescription schema = TypeDescription.createString();
Writer writer = OrcFile.createWriter(
testFilePath,
OrcFile.writerOptions(conf).setSchema(schema).compress(CompressionKind.NONE)
- .bufferSize(10000));
+ .bufferSize(bound));
Random rand = new Random(123);
- int[] input = new int[20000];
- for (int i = 0; i < 20000; i++) {
- input[i] = rand.nextInt(10000);
+ int[] input = new int[totalSize];
+ for (int i = 0; i < totalSize; i++) {
+ input[i] = rand.nextInt(bound);
}
VectorizedRowBatch batch = schema.createRowBatch();
BytesColumnVector col = (BytesColumnVector) batch.cols[0];
- for (int i = 0; i < 20000; i++) {
+ for (int i = 0; i < totalSize; i++) {
if (batch.size == batch.getMaxSize()) {
writer.addRowBatch(batch);
batch.reset();
diff --git a/java/core/src/test/org/apache/orc/impl/TestStringHashTableDictionary.java b/java/core/src/test/org/apache/orc/impl/TestStringHashTableDictionary.java
new file mode 100644
index 0000000..b3a5470
--- /dev/null
+++ b/java/core/src/test/org/apache/orc/impl/TestStringHashTableDictionary.java
@@ -0,0 +1,153 @@
+/**
+ * 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.util.List;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
+
+import org.apache.hadoop.io.Text;
+import org.apache.orc.StringDictTestingUtils;
+import org.junit.Assert;
+import org.junit.Test;
+
+
+public class TestStringHashTableDictionary {
+
+ /**
+ * Basic test cases by adding bytes directly and uses real hash function.
+ */
+ @Test
+ public void test0()
+ throws Exception {
+ StringHashTableDictionary htDict = new StringHashTableDictionary(5);
+
+ List<Text> testTexts =
+ Stream.of(new String[]{"Alice", "Bob", "Cindy", "David", "Eason"}).map(Text::new).collect(Collectors.toList());
+ List<byte[]> testBytes = testTexts.stream().map(Text::getBytes).collect(Collectors.toList());
+
+ Assert.assertEquals(0, htDict.getSizeInBytes());
+ Assert.assertEquals(0, htDict.add(testBytes.get(0), 0, testBytes.get(0).length));
+ Assert.assertEquals(1, htDict.add(testBytes.get(1), 0, testBytes.get(1).length));
+ Assert.assertEquals(0, htDict.add(testBytes.get(0), 0, testBytes.get(0).length));
+ Assert.assertEquals(1, htDict.add(testBytes.get(1), 0, testBytes.get(1).length));
+ Assert.assertEquals(2, htDict.add(testBytes.get(2), 0, testBytes.get(2).length));
+
+ Text text = new Text();
+ htDict.getText(text, 0);
+ Assert.assertEquals("Alice", text.toString());
+ htDict.getText(text, 1);
+ Assert.assertEquals("Bob", text.toString());
+ htDict.getText(text, 2);
+ Assert.assertEquals("Cindy", text.toString());
+
+ Assert.assertEquals(htDict.size(), 3);
+
+ // entering the fourth and fifth element which triggers rehash
+ Assert.assertEquals(3, htDict.add(testBytes.get(3), 0, testBytes.get(3).length));
+ htDict.getText(text, 3);
+ Assert.assertEquals("David", text.toString());
+ Assert.assertEquals(4, htDict.add(testBytes.get(4), 0, testBytes.get(4).length));
+ htDict.getText(text, 4);
+ Assert.assertEquals("Eason", text.toString());
+
+ Assert.assertEquals(htDict.size(), 5);
+
+ // Re-ensure no all previously existed string still have correct encoded value
+ htDict.getText(text, 0);
+ Assert.assertEquals("Alice", text.toString());
+ htDict.getText(text, 1);
+ Assert.assertEquals("Bob", text.toString());
+ htDict.getText(text, 2);
+ Assert.assertEquals("Cindy", text.toString());
+
+ // Peaking the hashtable and obtain the order sequence since the hashArray object needs to be private.
+ StringDictTestingUtils.checkContents(htDict, new int[]{1, 2, 3, 0 ,4}, "Bob", "Cindy", "David", "Alice", "Eason");
+
+ htDict.clear();
+ Assert.assertEquals(0, htDict.size());
+ }
+
+ /**
+ * A extension for {@link StringHashTableDictionary} for testing purpose by overwriting the hash function,
+ * just to save the effort of obtaining order sequence manually.
+ */
+ private static class SimpleHashDictionary extends StringHashTableDictionary {
+ public SimpleHashDictionary(int initialCapacity) {
+ super(initialCapacity);
+ }
+
+ /**
+ * Obtain the prefix for each string as the hash value.
+ * All the string being used in this test suite will contains its hash value as the prefix for the string content.
+ * this way we know the order of the traverse() method.
+ */
+ @Override
+ int getIndex(Text text) {
+ String s = text.toString();
+ int underscore = s.indexOf("_");
+ return Integer.parseInt(text.toString().substring(0, underscore));
+ }
+ }
+
+ @Test
+ public void test1()
+ throws Exception {
+ SimpleHashDictionary hashTableDictionary = new SimpleHashDictionary(5);
+ // Non-resize trivial cases
+ Assert.assertEquals(0, hashTableDictionary.getSizeInBytes());
+ Assert.assertEquals(0, hashTableDictionary.add(new Text("2_Alice")));
+ Assert.assertEquals(1, hashTableDictionary.add(new Text("3_Bob")));
+ Assert.assertEquals(0, hashTableDictionary.add(new Text("2_Alice")));
+ Assert.assertEquals(1, hashTableDictionary.add(new Text("3_Bob")));
+ Assert.assertEquals(2, hashTableDictionary.add(new Text("1_Cindy")));
+
+ Text text = new Text();
+ hashTableDictionary.getText(text, 0);
+ Assert.assertEquals("2_Alice", text.toString());
+ hashTableDictionary.getText(text, 1);
+ Assert.assertEquals("3_Bob", text.toString());
+ hashTableDictionary.getText(text, 2);
+ Assert.assertEquals("1_Cindy", text.toString());
+
+ // entering the fourth and fifth element which triggers rehash
+ Assert.assertEquals(3, hashTableDictionary.add(new Text("0_David")));
+ hashTableDictionary.getText(text, 3);
+ Assert.assertEquals("0_David", text.toString());
+ Assert.assertEquals(4, hashTableDictionary.add(new Text("4_Eason")));
+ hashTableDictionary.getText(text, 4);
+ Assert.assertEquals("4_Eason", text.toString());
+
+ // Re-ensure no all previously existed string still have correct encoded value
+ hashTableDictionary.getText(text, 0);
+ Assert.assertEquals("2_Alice", text.toString());
+ hashTableDictionary.getText(text, 1);
+ Assert.assertEquals("3_Bob", text.toString());
+ hashTableDictionary.getText(text, 2);
+ Assert.assertEquals("1_Cindy", text.toString());
+
+ // The order of words are based on each string's prefix given their index in the hashArray will be based on that.
+ StringDictTestingUtils
+ .checkContents(hashTableDictionary, new int[]{3, 2, 0, 1, 4}, "0_David", "1_Cindy", "2_Alice", "3_Bob",
+ "4_Eason");
+
+ hashTableDictionary.clear();
+ Assert.assertEquals(0, hashTableDictionary.size());
+ }
+}
\ No newline at end of file
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 34dc64a..f5eca83 100644
--- a/java/core/src/test/org/apache/orc/impl/TestStringRedBlackTree.java
+++ b/java/core/src/test/org/apache/orc/impl/TestStringRedBlackTree.java
@@ -21,9 +21,9 @@ package org.apache.orc.impl;
import static org.junit.Assert.assertEquals;
import java.io.IOException;
-import java.nio.charset.StandardCharsets;
-import org.apache.hadoop.io.DataOutputBuffer;
+
import org.apache.hadoop.io.IntWritable;
+import org.apache.orc.StringDictTestingUtils;
import org.junit.Test;
/**
@@ -108,37 +108,6 @@ public class TestStringRedBlackTree {
}
}
- private static class MyVisitor implements Dictionary.Visitor {
- private final String[] words;
- private final int[] order;
- private final DataOutputBuffer buffer = new DataOutputBuffer();
- int current = 0;
-
- MyVisitor(String[] args, int[] order) {
- words = args;
- this.order = order;
- }
-
- @Override
- public void visit(Dictionary.VisitorContext context
- ) throws IOException {
- String word = context.getText().toString();
- assertEquals("in word " + current, words[current], word);
- assertEquals("in word " + current, order[current],
- context.getOriginalPosition());
- buffer.reset();
- context.writeBytes(buffer);
- assertEquals(word, new String(buffer.getData(),0,buffer.getLength(), StandardCharsets.UTF_8));
- current += 1;
- }
- }
-
- void checkContents(StringRedBlackTree tree, int[] order,
- String... params
- ) throws IOException {
- tree.visit(new MyVisitor(params, order));
- }
-
StringRedBlackTree buildTree(String... params) throws IOException {
StringRedBlackTree result = new StringRedBlackTree(1000);
for(String word: params) {
@@ -181,7 +150,7 @@ public class TestStringRedBlackTree {
checkTree(tree);
assertEquals(9, tree.add("z"));
checkTree(tree);
- checkContents(tree, new int[]{2,5,1,4,6,3,7,0,9,8},
+ StringDictTestingUtils.checkContents(tree, new int[]{2,5,1,4,6,3,7,0,9,8},
"alan", "arun", "ashutosh", "eric", "eric14", "greg",
"o", "owen", "z", "ziggy");
assertEquals(32888, tree.getSizeInBytes());
@@ -212,7 +181,7 @@ public class TestStringRedBlackTree {
buildTree("a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l",
"m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z");
assertEquals(26, tree.size());
- checkContents(tree, new int[]{0,1,2, 3,4,5, 6,7,8, 9,10,11, 12,13,14,
+ StringDictTestingUtils.checkContents(tree, new int[]{0,1,2, 3,4,5, 6,7,8, 9,10,11, 12,13,14,
15,16,17, 18,19,20, 21,22,23, 24,25},
"a", "b", "c", "d", "e", "f", "g", "h", "i", "j","k", "l", "m", "n", "o",
"p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z");
@@ -224,7 +193,7 @@ public class TestStringRedBlackTree {
buildTree("z", "y", "x", "w", "v", "u", "t", "s", "r", "q", "p", "o", "n",
"m", "l", "k", "j", "i", "h", "g", "f", "e", "d", "c", "b", "a");
assertEquals(26, tree.size());
- checkContents(tree, new int[]{25,24,23, 22,21,20, 19,18,17, 16,15,14,
+ StringDictTestingUtils.checkContents(tree, new int[]{25,24,23, 22,21,20, 19,18,17, 16,15,14,
13,12,11, 10,9,8, 7,6,5, 4,3,2, 1,0},
"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o",
"p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z");