Skip to content

Commit cdc5fd7

Browse files
mkleenOmega359
authored andcommitted
feat: Support RunEndEncoded type in approx_distinct (apache#25951)
## Which issue does this PR close? - Closes apache#22989 ## Rationale for this change - Support the Arrow type `RunEndEncoded` type for `approx_distinct` ## What changes are included in this PR? - Enable `HLLAccumulator` and `HllGroupsAccumulator` to support `RunEndEncoded` - Tests for the non-grouped and grouped path as part of `aggregate.slt` ## Are these changes tested? Yes. ## Are there any user-facing changes? Yes, `approx_distinct` supports now `RunEndEncoded` but no breaking changes.
1 parent c36a1b7 commit cdc5fd7

2 files changed

Lines changed: 64 additions & 7 deletions

File tree

‎datafusion/functions-aggregate/src/approx_distinct.rs‎

Lines changed: 15 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -835,7 +835,9 @@ impl AggregateUDFImpl for ApproxDistinct {
835835
| DataType::Struct(_)
836836
| DataType::Union(_, _)
837837
| DataType::LargeBinary => Box::new(HLLAccumulator::new()),
838-
DataType::Dictionary(_, _) if is_supported_type(data_type) => {
838+
DataType::Dictionary(_, _) | DataType::RunEndEncoded(_, _)
839+
if is_supported_type(data_type) =>
840+
{
839841
Box::new(HLLAccumulator::new())
840842
}
841843
DataType::Null => {
@@ -894,25 +896,31 @@ fn is_fixed_domain_type(data_type: &DataType) -> bool {
894896
}
895897

896898
fn is_supported_type(data_type: &DataType) -> bool {
897-
let value_type = dictionary_value_type(data_type);
899+
let value_type = encoded_value_type(data_type);
898900
matches!(value_type, DataType::Null)
899901
|| is_fixed_domain_type(value_type)
900902
|| is_hll_groups_type(value_type)
901903
}
902904

903-
fn dictionary_value_type(data_type: &DataType) -> &DataType {
905+
fn encoded_value_type(data_type: &DataType) -> &DataType {
904906
let mut value_type = data_type;
905-
while let DataType::Dictionary(_, inner) = value_type {
906-
value_type = inner;
907+
loop {
908+
match value_type {
909+
DataType::Dictionary(_, inner) => value_type = inner,
910+
DataType::RunEndEncoded(_, values) => value_type = values.data_type(),
911+
_ => return value_type,
912+
}
907913
}
908-
value_type
909914
}
910915

911916
/// Returns true for the data types backed by the HyperLogLog
912917
/// [`HllGroupsAccumulator`]. The fixed-domain types (booleans / small ints) and
913918
/// `Null` fall back to the per-group [`Accumulator`] path.
914919
fn is_hll_groups_type(data_type: &DataType) -> bool {
915-
if matches!(data_type, DataType::Dictionary(_, _)) {
920+
if matches!(
921+
data_type,
922+
DataType::Dictionary(_, _) | DataType::RunEndEncoded(_, _)
923+
) {
916924
return is_supported_type(data_type);
917925
}
918926

‎datafusion/sqllogictest/test_files/aggregate.slt‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1862,6 +1862,55 @@ SELECT approx_distinct(arrow_cast(i, 'Dictionary(Int32, Float64)')) FROM approx_
18621862
statement error DataFusion error: This feature is not implemented: Support for 'approx_distinct' for data type Dictionary\(Int32, Float64\) is not implemented
18631863
SELECT g, approx_distinct(arrow_cast(i, 'Dictionary(Int32, Float64)')) FROM approx_distinct_group_test GROUP BY g;
18641864

1865+
# RunEndEncoded: run-end encoded values must hash identically to the plain
1866+
# values, so the counts below match the Utf8 / Int32 cases above.
1867+
query I
1868+
SELECT approx_distinct(arrow_cast(s, 'RunEndEncoded("run_ends": non-null Int32, "values": Utf8)')) FROM approx_distinct_group_test WHERE g = 2;
1869+
----
1870+
2
1871+
1872+
query II
1873+
SELECT g, approx_distinct(arrow_cast(s, 'RunEndEncoded("run_ends": non-null Int32, "values": Utf8)')) FROM approx_distinct_group_test GROUP BY g ORDER BY g;
1874+
----
1875+
1 2
1876+
2 2
1877+
3 0
1878+
4 1
1879+
1880+
query II
1881+
SELECT g, approx_distinct(arrow_cast(i, 'RunEndEncoded("run_ends": non-null Int64, "values": Int32)')) FROM approx_distinct_group_test GROUP BY g ORDER BY g;
1882+
----
1883+
1 2
1884+
2 2
1885+
3 0
1886+
4 1
1887+
1888+
# RunEndEncoded over a fixed-domain value type (Int8) goes through the
1889+
# HyperLogLog accumulators and must match the Int32 counts above.
1890+
query II
1891+
SELECT g, approx_distinct(arrow_cast(arrow_cast(i, 'Int8'), 'RunEndEncoded("run_ends": non-null Int32, "values": Int8)')) FROM approx_distinct_group_test GROUP BY g ORDER BY g;
1892+
----
1893+
1 2
1894+
2 2
1895+
3 0
1896+
4 1
1897+
1898+
# RunEndEncoded over a dictionary
1899+
query II
1900+
SELECT g, approx_distinct(arrow_cast(s, 'RunEndEncoded("run_ends": non-null Int32, "values": Dictionary(Int32, Utf8))')) FROM approx_distinct_group_test GROUP BY g ORDER BY g;
1901+
----
1902+
1 2
1903+
2 2
1904+
3 0
1905+
4 1
1906+
1907+
# Unsupported value types are rejected, as for a bare Float64
1908+
statement error DataFusion error: This feature is not implemented: Support for 'approx_distinct' for data type RunEndEncoded
1909+
SELECT approx_distinct(arrow_cast(i, 'RunEndEncoded("run_ends": non-null Int32, "values": Float64)')) FROM approx_distinct_group_test;
1910+
1911+
statement error DataFusion error: This feature is not implemented: Support for 'approx_distinct' for data type RunEndEncoded
1912+
SELECT g, approx_distinct(arrow_cast(i, 'RunEndEncoded("run_ends": non-null Int32, "values": Float64)')) FROM approx_distinct_group_test GROUP BY g;
1913+
18651914

18661915
# List
18671916
statement ok

0 commit comments

Comments
 (0)