You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@hivemall.apache.org by my...@apache.org on 2020/01/23 10:21:02 UTC
[incubator-hivemall] branch master updated: [HIVEMALL-291] Support
deduplication in to_order_list UDAF
This is an automated email from the ASF dual-hosted git repository.
myui pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/incubator-hivemall.git
The following commit(s) were added to refs/heads/master by this push:
new 17d0215 [HIVEMALL-291] Support deduplication in to_order_list UDAF
17d0215 is described below
commit 17d0215385f3d72d6b899d104cf258e0f3fe174f
Author: Makoto Yui <my...@apache.org>
AuthorDate: Thu Jan 23 19:20:55 2020 +0900
[HIVEMALL-291] Support deduplication in to_order_list UDAF
## What changes were proposed in this pull request?
Add -dedup option to to_ordered_list.
## What type of PR is it?
Improvement
## What is the Jira issue?
https://issues.apache.org/jira/browse/HIVEMALL-291
## How was this patch tested?
manual tests on EMR
## How to use this feature?
```sql
WITH data as (
SELECT 5 as key, 'apple' as value
UNION ALL
SELECT 3 as key, 'banana' as value
UNION ALL
SELECT 4 as key, 'candy' as value
UNION ALL
SELECT 1 as key, 'donut' as value
UNION ALL
SELECT 2 as key, 'egg' as value
UNION ALL
SELECT 4 as key, 'candy' as value -- both key and value duplicates
)
select
to_ordered_list(value, key, '-k 4 -dedup -vk_map'),
to_ordered_list(value, key, '-k 4 -vk_map'),
to_ordered_list(value, key, '-k 4 -dedup'),
to_ordered_list(value, key, '-k 4')
from
data
```
> {"apple":5,"candy":4,"banana":3,"egg":2} {"apple":5,"candy":4,"banana":3} ["apple","candy","banana","egg"] [
"apple","candy","candy","banana"]
## Checklist
- [x] Did you apply source code formatter, i.e., `./bin/format_code.sh`, for your commit?
- [x] Did you run system tests on Hive (or Spark)?
Author: Makoto Yui <my...@apache.org>
Closes #226 from myui/HIVEMALL-291.
---
.../hivemall/tools/list/UDAFToOrderedList.java | 169 ++++++++++++++++-----
.../utils/collections/BoundedPriorityQueue.java | 4 +
2 files changed, 133 insertions(+), 40 deletions(-)
diff --git a/core/src/main/java/hivemall/tools/list/UDAFToOrderedList.java b/core/src/main/java/hivemall/tools/list/UDAFToOrderedList.java
index 6435a5f..c139d65 100644
--- a/core/src/main/java/hivemall/tools/list/UDAFToOrderedList.java
+++ b/core/src/main/java/hivemall/tools/list/UDAFToOrderedList.java
@@ -31,7 +31,7 @@ import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
-import java.util.HashMap;
+import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
@@ -72,26 +72,41 @@ import org.apache.hadoop.io.IntWritable;
@Description(name = "to_ordered_list",
value = "_FUNC_(PRIMITIVE value [, PRIMITIVE key, const string options])"
+ " - Return list of values sorted by value itself or specific key",
- extended = "WITH t as (\n" + " SELECT 5 as key, 'apple' as value\n" + " UNION ALL\n"
- + " SELECT 3 as key, 'banana' as value\n" + " UNION ALL\n"
- + " SELECT 4 as key, 'candy' as value\n" + " UNION ALL\n"
- + " SELECT 2 as key, 'donut' as value\n" + " UNION ALL\n"
- + " SELECT 3 as key, 'egg' as value\n" + ")\n"
- + "SELECT -- expected output\n"
- + " to_ordered_list(value, key, '-reverse'), -- [apple, candy, (banana, egg | egg, banana), donut] (reverse order)\n"
- + " to_ordered_list(value, key, '-k 2'), -- [apple, candy] (top-k)\n"
- + " to_ordered_list(value, key, '-k 100'), -- [apple, candy, (banana, egg | egg, banana), dunut]\n"
- + " to_ordered_list(value, key, '-k 2 -reverse'), -- [donut, (banana | egg)] (reverse top-k = tail-k)\n"
- + " to_ordered_list(value, key), -- [donut, (banana, egg | egg, banana), candy, apple] (natural order)\n"
- + " to_ordered_list(value, key, '-k -2'), -- [donut, (banana | egg)] (tail-k)\n"
- + " to_ordered_list(value, key, '-k -100'), -- [donut, (banana, egg | egg, banana), candy, apple]\n"
- + " to_ordered_list(value, key, '-k -2 -reverse'), -- [apple, candy] (reverse tail-k = top-k)\n"
- + " to_ordered_list(value, '-k 2'), -- [egg, donut] (alphabetically)\n"
- + " to_ordered_list(key, '-k -2 -reverse'), -- [5, 4] (top-2 keys)\n"
- + " to_ordered_list(key), -- [2, 3, 3, 4, 5] (natural ordered keys)\n"
- + " to_ordered_list(value, key, '-k 2 -kv_map'), -- {4:\"candy\",5:\"apple\"}\n"
- + " to_ordered_list(value, key, '-k 2 -vk_map') -- {\"candy\":4,\"apple\":5}\n"
- + "FROM\n" + " t")
+ extended = "WITH data as (\n" +
+ " SELECT 5 as key, 'apple' as value\n" +
+ " UNION ALL\n" +
+ " SELECT 3 as key, 'banana' as value\n" +
+ " UNION ALL\n" +
+ " SELECT 4 as key, 'candy' as value\n" +
+ " UNION ALL\n" +
+ " SELECT 1 as key, 'donut' as value\n" +
+ " UNION ALL\n" +
+ " SELECT 2 as key, 'egg' as value \n" +
+ " UNION ALL\n" +
+ " SELECT 4 as key, 'candy' as value -- both key and value duplicates\n" +
+ ")\n" +
+ "SELECT -- expected output\n" +
+ " to_ordered_list(value, key, '-reverse'), -- [apple, candy, (banana, egg | egg, banana), donut] (reverse order)\n" +
+ " to_ordered_list(value, key, '-k 2'), -- [apple, candy] (top-k)\n" +
+ " to_ordered_list(value, key, '-k 100'), -- [apple, candy, (banana, egg | egg, banana), dunut]\n" +
+ " to_ordered_list(value, key, '-k 2 -reverse'), -- [donut, (banana | egg)] (reverse top-k = tail-k)\n" +
+ " to_ordered_list(value, key), -- [donut, (banana, egg | egg, banana), candy, apple] (natural order)\n" +
+ " to_ordered_list(value, key, '-k -2'), -- [donut, (banana | egg)] (tail-k)\n" +
+ " to_ordered_list(value, key, '-k -100'), -- [donut, (banana, egg | egg, banana), candy, apple]\n" +
+ " to_ordered_list(value, key, '-k -2 -reverse'), -- [apple, candy] (reverse tail-k = top-k)\n" +
+ " to_ordered_list(value, '-k 2'), -- [egg, donut] (alphabetically)\n" +
+ " to_ordered_list(key, '-k -2 -reverse'), -- [5, 4] (top-2 keys)\n" +
+ " to_ordered_list(key), -- [2, 3, 3, 4, 5] (natural ordered keys)\n" +
+ " to_ordered_list(value, key, '-k 2 -kv_map'), -- {5:\"apple\",4:\"candy\"}\n" +
+ " to_ordered_list(value, key, '-k 2 -vk_map'), -- {\"apple\":5,\"candy\":4}\n" +
+ " to_ordered_list(value, key, '-k -2 -kv_map'), -- {1:\"donut\",2:\"egg\"}\n" +
+ " to_ordered_list(value, key, '-k -2 -vk_map'), -- {\"donut\":1,\"egg\":2}\n" +
+ " to_ordered_list(value, key, '-k 4 -dedup -vk_map'), -- {\"apple\":5,\"candy\":4,\"banana\":3,\"egg\":2}\n" +
+ " to_ordered_list(value, key, '-k 4 -vk_map'), -- {\"apple\":5,\"candy\":4,\"banana\":3}\n" +
+ " to_ordered_list(value, key, '-k 4 -dedup'), -- [\"apple\",\"candy\",\"banana\",\"egg\"]\n" +
+ " to_ordered_list(value, key, '-k 4') -- [\"apple\",\"candy\",\"candy\",\"banana\"]\n" +
+ "FROM\n" +
+ " data")
//@formatter:on
public final class UDAFToOrderedList extends AbstractGenericUDAFResolver {
@@ -144,6 +159,7 @@ public final class UDAFToOrderedList extends AbstractGenericUDAFResolver {
@Nonnegative
private int size;
private boolean reverseOrder;
+ private boolean dedup;
private boolean sortByKey;
private boolean outKV, outVK;
@@ -156,6 +172,7 @@ public final class UDAFToOrderedList extends AbstractGenericUDAFResolver {
"Return Map<K, V> for the result of to_ordered_list(V, K)");
opts.addOption("vk", "vk_map", false,
"Return Map<V, K> for the result of to_ordered_list(V, K)");
+ opts.addOption("dedup", false, "Eliminate/ignore duplications");
return opts;
}
@@ -199,13 +216,14 @@ public final class UDAFToOrderedList extends AbstractGenericUDAFResolver {
}
int k = 0;
- boolean reverseOrder = false;
+ boolean reverseOrder = false, dedup = false;
boolean outKV = false, outVK = false;
if (argOIs.length >= optionIndex + 1) {
String rawArgs = HiveUtils.getConstString(argOIs[optionIndex]);
cl = parseOptions(rawArgs);
reverseOrder = cl.hasOption("reverse_order");
+ dedup = cl.hasOption("dedup");
if (cl.hasOption("k")) {
k = Integer.parseInt(cl.getOptionValue("k"));
@@ -230,6 +248,7 @@ public final class UDAFToOrderedList extends AbstractGenericUDAFResolver {
this.size = Math.abs(k);
this.outKV = outKV;
this.outVK = outVK;
+ this.dedup = dedup;
if ((k > 0 && reverseOrder) || (k < 0 && reverseOrder == false)
|| (k == 0 && reverseOrder == false)) {
@@ -359,7 +378,7 @@ public final class UDAFToOrderedList extends AbstractGenericUDAFResolver {
public void reset(@SuppressWarnings("deprecation") AggregationBuffer agg)
throws HiveException {
QueueAggregationBuffer myagg = (QueueAggregationBuffer) agg;
- myagg.reset(size, reverseOrder, outKV, outVK);
+ myagg.reset(size, reverseOrder, dedup, outKV, outVK);
}
@Override
@@ -444,7 +463,7 @@ public final class UDAFToOrderedList extends AbstractGenericUDAFResolver {
reverseOrderObj);
QueueAggregationBuffer myagg = (QueueAggregationBuffer) agg;
- myagg.setOptions(size, reverseOrder, outKV, outVK);
+ myagg.setOptions(size, reverseOrder, dedup, outKV, outVK);
myagg.merge(keyList, valueList);
}
@@ -467,22 +486,24 @@ public final class UDAFToOrderedList extends AbstractGenericUDAFResolver {
@Nonnegative
private int size;
- private boolean reverseOrder;
+ private boolean reverseOrder, dedup;
private boolean outKV, outVK;
QueueAggregationBuffer() {
super();
}
- void reset(@Nonnegative int size, boolean reverseOrder, boolean outKV, boolean outVK) {
- setOptions(size, reverseOrder, outKV, outVK);
+ void reset(@Nonnegative int size, boolean reverseOrder, boolean dedup, boolean outKV,
+ boolean outVK) {
+ setOptions(size, reverseOrder, dedup, outKV, outVK);
this.queueHandler = null;
}
- void setOptions(@Nonnegative int size, boolean reverseOrder, boolean outKV,
- boolean outVK) {
+ void setOptions(@Nonnegative int size, boolean reverseOrder, boolean dedup,
+ boolean outKV, boolean outVK) {
this.size = size;
this.reverseOrder = reverseOrder;
+ this.dedup = dedup;
this.outKV = outKV;
this.outVK = outVK;
}
@@ -491,6 +512,9 @@ public final class UDAFToOrderedList extends AbstractGenericUDAFResolver {
if (queueHandler == null) {
initQueueHandler();
}
+ if (dedup && queueHandler.contains(tuple)) {
+ return;
+ }
queueHandler.offer(tuple);
}
@@ -498,9 +522,19 @@ public final class UDAFToOrderedList extends AbstractGenericUDAFResolver {
if (queueHandler == null) {
initQueueHandler();
}
- for (int i = 0, n = keys.size(); i < n; i++) {
- queueHandler.offer(new TupleWithKey(keys.get(i), values.get(i)));
+ if (dedup) {
+ for (int i = 0, n = keys.size(); i < n; i++) {
+ TupleWithKey tuple = new TupleWithKey(keys.get(i), values.get(i));
+ if (!queueHandler.contains(tuple)) {
+ queueHandler.offer(tuple);
+ }
+ }
+ } else {
+ for (int i = 0, n = keys.size(); i < n; i++) {
+ queueHandler.offer(new TupleWithKey(keys.get(i), values.get(i)));
+ }
}
+
}
@Deprecated
@@ -547,15 +581,21 @@ public final class UDAFToOrderedList extends AbstractGenericUDAFResolver {
}
final int n = queueHandler.size();
- final Map<Object, Object> map = new HashMap<>(n * 2);
+ final Object[] keys = new Object[n];
+ final Object[] values = new Object[n];
for (int i = n - 1; i >= 0; i--) { // head element in queue should be stored to tail of array
TupleWithKey tuple = queueHandler.poll();
- Object k = tuple.getKey();
+ keys[i] = tuple.getKey();
+ values[i] = tuple.getValue();
+ }
+
+ final Map<Object, Object> map = new LinkedHashMap<>(n * 2);
+ for (int i = 0; i < n; i++) {
+ final Object k = keys[i];
if (map.containsKey(k)) {
- continue; // avoid duplicate
+ continue;
}
- Object v = tuple.getValue();
- map.put(k, v);
+ map.put(k, values[i]);
}
queueHandler.clear();
@@ -569,15 +609,21 @@ public final class UDAFToOrderedList extends AbstractGenericUDAFResolver {
}
final int n = queueHandler.size();
- final Map<Object, Object> map = new HashMap<>(n * 2);
+ final Object[] keys = new Object[n];
+ final Object[] values = new Object[n];
for (int i = n - 1; i >= 0; i--) { // head element in queue should be stored to tail of array
TupleWithKey tuple = queueHandler.poll();
- Object k = tuple.getValue();
+ keys[i] = tuple.getValue();
+ values[i] = tuple.getKey();
+ }
+
+ final Map<Object, Object> map = new LinkedHashMap<>(n * 2);
+ for (int i = 0; i < n; i++) {
+ final Object k = keys[i];
if (map.containsKey(k)) {
continue; // avoid duplicate
}
- Object v = tuple.getKey();
- map.put(k, v);
+ map.put(k, values[i]);
}
queueHandler.clear();
@@ -607,6 +653,8 @@ public final class UDAFToOrderedList extends AbstractGenericUDAFResolver {
*/
private static abstract class AbstractQueueHandler {
+ abstract boolean contains(@Nonnull TupleWithKey tuple);
+
abstract void offer(@Nonnull TupleWithKey tuple);
abstract int size();
@@ -630,6 +678,11 @@ public final class UDAFToOrderedList extends AbstractGenericUDAFResolver {
}
@Override
+ boolean contains(@Nonnull TupleWithKey tuple) {
+ return queue.contains(tuple);
+ }
+
+ @Override
void offer(TupleWithKey tuple) {
queue.offer(tuple);
}
@@ -661,6 +714,11 @@ public final class UDAFToOrderedList extends AbstractGenericUDAFResolver {
}
@Override
+ boolean contains(@Nonnull TupleWithKey tuple) {
+ return queue.contains(tuple);
+ }
+
+ @Override
void offer(TupleWithKey tuple) {
queue.offer(tuple);
}
@@ -709,6 +767,37 @@ public final class UDAFToOrderedList extends AbstractGenericUDAFResolver {
Comparable<? super Object> k = (Comparable<? super Object>) key;
return k.compareTo(o.getKey());
}
+
+ @Override
+ public int hashCode() {
+ final int prime = 31;
+ int result = 1;
+ result = prime * result + ((key == null) ? 0 : key.hashCode());
+ result = prime * result + ((value == null) ? 0 : value.hashCode());
+ return result;
+ }
+
+ @Override
+ public boolean equals(@Nullable Object obj) {
+ if (this == obj)
+ return true;
+ if (obj == null)
+ return false;
+ if (getClass() != obj.getClass())
+ return false;
+ TupleWithKey other = (TupleWithKey) obj;
+ if (key == null) {
+ if (other.key != null)
+ return false;
+ } else if (!key.equals(other.key))
+ return false;
+ if (value == null) {
+ if (other.value != null)
+ return false;
+ } else if (!value.equals(other.value))
+ return false;
+ return true;
+ }
}
}
}
diff --git a/core/src/main/java/hivemall/utils/collections/BoundedPriorityQueue.java b/core/src/main/java/hivemall/utils/collections/BoundedPriorityQueue.java
index 6844e81..34fb0e4 100644
--- a/core/src/main/java/hivemall/utils/collections/BoundedPriorityQueue.java
+++ b/core/src/main/java/hivemall/utils/collections/BoundedPriorityQueue.java
@@ -45,6 +45,10 @@ public final class BoundedPriorityQueue<E> {
this.comparator = comparator;
this.queue = new PriorityQueue<E>(size + 10, comparator);
}
+
+ public boolean contains(@Nonnull E e) {
+ return queue.contains(e);
+ }
public boolean offer(@Nonnull E e) {
if (e == null) {