Skip to content

Commit 7fc4a37

Browse files
liyafan82emkornfield
liyafan82
authored and
emkornfield
committed
ARROW-6672: [Java] Extract a common interface for dictionary builders
We need a common interface for dictionary builders to support more sophisticated scenarios, like collecting dictionary statistics. Closes apache#5486 from liyafan82/fly_0923_build and squashes the following commits: 04e8e65 <liyafan82> Extract a common interface for dictionary builders Authored-by: liyafan82 <fan_li_ya@foxmail.com> Signed-off-by: Micah Kornfield <emkornfield@gmail.com>
1 parent 776165c commit 7fc4a37

4 files changed

Lines changed: 84 additions & 53 deletions

File tree

‎java/algorithm/src/main/java/org/apache/arrow/algorithm/dictionary/DictionaryBuilder.java‎

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
/*
2+
* Licensed to the Apache Software Foundation (ASF) under one or more
3+
* contributor license agreements. See the NOTICE file distributed with
4+
* this work for additional information regarding copyright ownership.
5+
* The ASF licenses this file to You under the Apache License, Version 2.0
6+
* (the "License"); you may not use this file except in compliance with
7+
* the License. You may obtain a copy of the License at
8+
*
9+
* http://www.apache.org/licenses/LICENSE-2.0
10+
*
11+
* Unless required by applicable law or agreed to in writing, software
12+
* distributed under the License is distributed on an "AS IS" BASIS,
13+
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14+
* See the License for the specific language governing permissions and
15+
* limitations under the License.
16+
*/
17+
18+
package org.apache.arrow.algorithm.dictionary;
19+
20+
import org.apache.arrow.vector.ValueVector;
21+
22+
/**
23+
* A dictionary builder is intended for the scenario frequently encountered in practice:
24+
* the dictionary is not known a priori, so it is generated dynamically.
25+
* In particular, when a new value arrives, it is tested to check if it is already
26+
* in the dictionary. If so, it is simply neglected, otherwise, it is added to the dictionary.
27+
* <p>
28+
* The dictionary builder is intended to build a single dictionary.
29+
* So it cannot be used for different dictionaries.
30+
* </p>
31+
* <p>Below gives the sample code for using the dictionary builder
32+
* <pre>{@code
33+
* DictionaryBuilder dictionaryBuilder = ...
34+
* ...
35+
* dictionaryBuild.addValue(newValue);
36+
* ...
37+
* }</pre>
38+
* </p>
39+
* <p>
40+
* With the above code, the dictionary vector will be populated,
41+
* and it can be retrieved by the {@link DictionaryBuilder#getDictionary()} method.
42+
* After that, dictionary encoding can proceed with the populated dictionary..
43+
* </p>
44+
*
45+
* @param <V> the dictionary vector type.
46+
*/
47+
public interface DictionaryBuilder<V extends ValueVector> {
48+
49+
/**
50+
* Try to add all values from the target vector to the dictionary.
51+
*
52+
* @param targetVector the target vector containing values to probe.
53+
* @return the number of values actually added to the dictionary.
54+
*/
55+
int addValues(V targetVector);
56+
57+
/**
58+
* Try to add an element from the target vector to the dictionary.
59+
*
60+
* @param targetVector the target vector containing new element.
61+
* @param targetIndex the index of the new element in the target vector.
62+
* @return the index of the new element in the dictionary.
63+
*/
64+
int addValue(V targetVector, int targetIndex);
65+
66+
/**
67+
* Gets the dictionary built.
68+
*
69+
* @return the dictionary.
70+
*/
71+
V getDictionary();
72+
}

‎java/algorithm/src/main/java/org/apache/arrow/algorithm/dictionary/HashTableBasedDictionaryBuilder.java‎

Lines changed: 4 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -25,37 +25,13 @@
2525
import org.apache.arrow.vector.ElementAddressableVector;
2626

2727
/**
28-
* A dictionary builder is intended for the scenario frequently encountered in practice:
29-
* the dictionary is not known a priori, so it is generated dynamically.
30-
* In particular, when a new value arrives, it is tested to check if it is already
31-
* in the dictionary. If so, it is simply neglected, otherwise, it is added to the dictionary.
32-
*
33-
* <p>
3428
* This class builds the dictionary based on a hash table.
3529
* Each add operation can be finished in O(1) time,
3630
* where n is the current dictionary size.
37-
* </p>
38-
* <p>
39-
* The dictionary builder is intended to build a single dictionary.
40-
* So it cannot be used for different dictionaries.
41-
* </p>
42-
* <p>Below gives the sample code for using the dictionary builder
43-
* <pre>{@code
44-
* HashTableBasedDictionaryBuilder dictionaryBuilder = ...
45-
* ...
46-
* dictionaryBuild.addValue(newValue);
47-
* ...
48-
* }</pre>
49-
* </p>
50-
* <p>
51-
* With the above code, the dictionary vector will be populated,
52-
* and it can be retrieved by the {@link HashTableBasedDictionaryBuilder#getDictionary()} method.
53-
* After that, dictionary encoding can proceed with the populated dictionary encoder.
54-
* </p>
5531
*
5632
* @param <V> the dictionary vector type.
5733
*/
58-
public class HashTableBasedDictionaryBuilder<V extends ElementAddressableVector> {
34+
public class HashTableBasedDictionaryBuilder<V extends ElementAddressableVector> implements DictionaryBuilder<V> {
5935

6036
/**
6137
* The dictionary to be built.
@@ -121,6 +97,7 @@ public HashTableBasedDictionaryBuilder(V dictionary, boolean encodeNull, ArrowBu
12197
*
12298
* @return the dictionary.
12399
*/
100+
@Override
124101
public V getDictionary() {
125102
return dictionary;
126103
}
@@ -131,6 +108,7 @@ public V getDictionary() {
131108
* @param targetVector the target vector containing values to probe.
132109
* @return the number of values actually added to the dictionary.
133110
*/
111+
@Override
134112
public int addValues(V targetVector) {
135113
int oldDictSize = dictionary.getValueCount();
136114
for (int i = 0; i < targetVector.getValueCount(); i++) {
@@ -150,6 +128,7 @@ public int addValues(V targetVector) {
150128
* @param targetIndex the index of the new element in the target vector.
151129
* @return the index of the new element in the dictionary.
152130
*/
131+
@Override
153132
public int addValue(V targetVector, int targetIndex) {
154133
targetVector.getDataPointer(targetIndex, nextPointer);
155134

‎java/algorithm/src/main/java/org/apache/arrow/algorithm/dictionary/SearchTreeBasedDictionaryBuilder.java‎

Lines changed: 7 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -23,36 +23,13 @@
2323
import org.apache.arrow.vector.ValueVector;
2424

2525
/**
26-
* A dictionary builder is intended for the scenario frequently encountered in practice:
27-
* the dictionary is not known a priori, so it is generated dynamically.
28-
* In particular, when a new value arrives, it is tested to check if it is already
29-
* in the dictionary. If so, it is simply neglected, otherwise, it is added to the dictionary.
26+
* This class builds the dictionary based on a binary search tree.
27+
* Each add operation can be finished in O(log(n)) time,
28+
* where n is the current dictionary size.
3029
*
31-
* <p>
32-
* This class builds the dictionary based on a binary search tree.
33-
* Each add operation can be finished in O(log(n)) time,
34-
* where n is the current dictionary size.
35-
* </p>
36-
* <p>
37-
* The dictionary builder is intended to build a single dictionary.
38-
* So it cannot be used for different dictionaries.
39-
* </p>
40-
* <p>Below gives the sample code for using the dictionary builder
41-
* <pre>{@code
42-
* SearchTreeBasedDictionaryBuilder dictionaryBuilder = ...
43-
* ...
44-
* dictionaryBuild.addValue(newValue);
45-
* ...
46-
* }</pre>
47-
* </p>
48-
* <p>
49-
* With the above code, the dictionary vector will be populated,
50-
* and it can be retrieved by the {@link SearchTreeBasedDictionaryBuilder#getDictionary()} method.
51-
* After that, dictionary encoding can proceed with the populated dictionary.
52-
* </p>
5330
* @param <V> the dictionary vector type.
5431
*/
55-
public class SearchTreeBasedDictionaryBuilder<V extends ValueVector> {
32+
public class SearchTreeBasedDictionaryBuilder<V extends ValueVector> implements DictionaryBuilder<V> {
5633

5734
/**
5835
* The dictionary to be built.
@@ -106,6 +83,7 @@ public SearchTreeBasedDictionaryBuilder(V dictionary, VectorValueComparator<V> c
10683
* {@link SearchTreeBasedDictionaryBuilder#populateSortedDictionary(ValueVector)}.
10784
* @return the dictionary.
10885
*/
86+
@Override
10987
public V getDictionary() {
11088
return dictionary;
11189
}
@@ -115,6 +93,7 @@ public V getDictionary() {
11593
* @param targetVector the target vector containing values to probe.
11694
* @return the number of values actually added to the dictionary.
11795
*/
96+
@Override
11897
public int addValues(V targetVector) {
11998
int oldDictSize = dictionary.getValueCount();
12099
for (int i = 0; i < targetVector.getValueCount(); i++) {
@@ -132,6 +111,7 @@ public int addValues(V targetVector) {
132111
* @param targetIndex the index of the new element in the target vector.
133112
* @return the index of the new element in the dictionary.
134113
*/
114+
@Override
135115
public int addValue(V targetVector, int targetIndex) {
136116
// first copy the value to the end of the dictionary
137117
int dictSize = dictionary.getValueCount();

java/algorithm/src/test/java/org/apache/arrow/algorithm/dictionary/TestHashTableBasedDictionaryEncoder.java renamed to java/algorithm/src/test/java/org/apache/arrow/algorithm/dictionary/TestHashTableBasedDictionaryBuilder.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -33,7 +33,7 @@
3333
/**
3434
* Test cases for {@link HashTableBasedDictionaryBuilder}.
3535
*/
36-
public class TestHashTableBasedDictionaryEncoder {
36+
public class TestHashTableBasedDictionaryBuilder {
3737

3838
private BufferAllocator allocator;
3939

0 commit comments

Comments
 (0)