Skip to content

Commit 39d36f0

Browse files
authored
Add support for dictionary for approx_distinct (apache#24646)
## Which issue does this PR close? - Relates to apache#22989 but does not close it. More types are coming. ## Rationale for this change - Support the Arrow type `Dictionary` for `approx_distinct` ## What changes are included in this PR? - Enable `HLLAccumulator` and `HllGroupsAccumulator` to support `Dictionary` - Tests ## Are these changes tested? Yes ## Are there any user-facing changes? Yes, `approx_distinct` supports now `Dictionary` but no breaking changes.
1 parent f96892a commit 39d36f0

2 files changed

Lines changed: 144 additions & 10 deletions

File tree

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

Lines changed: 83 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -735,11 +735,9 @@ impl AggregateUDFImpl for ApproxDistinct {
735735
)
736736
.into(),
737737
]),
738-
DataType::Boolean
739-
| DataType::UInt8
740-
| DataType::Int8
741-
| DataType::UInt16
742-
| DataType::Int16 => get_fixed_domain_state_field(args.name, data_type),
738+
_ if is_fixed_domain_type(data_type) => {
739+
get_fixed_domain_state_field(args.name, data_type)
740+
}
743741
_ => Ok(vec![
744742
Field::new(
745743
format_state_name(args.name, "hll_registers"),
@@ -756,11 +754,7 @@ impl AggregateUDFImpl for ApproxDistinct {
756754

757755
// For primitive types, use specialized accumulators for better performance.
758756
let accumulator: Box<dyn Accumulator> = match data_type {
759-
DataType::Boolean
760-
| DataType::UInt8
761-
| DataType::Int8
762-
| DataType::UInt16
763-
| DataType::Int16 => {
757+
_ if is_fixed_domain_type(data_type) => {
764758
return get_fixed_domain_approx_accumulator(data_type);
765759
}
766760
DataType::UInt32 => Box::new(NumericHLLAccumulator::<UInt32Type>::new()),
@@ -841,6 +835,9 @@ impl AggregateUDFImpl for ApproxDistinct {
841835
| DataType::Struct(_)
842836
| DataType::Union(_, _)
843837
| DataType::LargeBinary => Box::new(HLLAccumulator::new()),
838+
DataType::Dictionary(_, _) if is_supported_type(data_type) => {
839+
Box::new(HLLAccumulator::new())
840+
}
844841
DataType::Null => {
845842
Box::new(NoopAccumulator::new(ScalarValue::UInt64(Some(0))))
846843
}
@@ -876,10 +873,40 @@ impl AggregateUDFImpl for ApproxDistinct {
876873
}
877874
}
878875

876+
fn is_fixed_domain_type(data_type: &DataType) -> bool {
877+
matches!(
878+
data_type,
879+
DataType::Boolean
880+
| DataType::UInt8
881+
| DataType::Int8
882+
| DataType::UInt16
883+
| DataType::Int16
884+
)
885+
}
886+
887+
fn is_supported_type(data_type: &DataType) -> bool {
888+
let value_type = dictionary_value_type(data_type);
889+
matches!(value_type, DataType::Null)
890+
|| is_fixed_domain_type(value_type)
891+
|| is_hll_groups_type(value_type)
892+
}
893+
894+
fn dictionary_value_type(data_type: &DataType) -> &DataType {
895+
let mut value_type = data_type;
896+
while let DataType::Dictionary(_, inner) = value_type {
897+
value_type = inner;
898+
}
899+
value_type
900+
}
901+
879902
/// Returns true for the data types backed by the HyperLogLog
880903
/// [`HllGroupsAccumulator`]. The fixed-domain types (booleans / small ints) and
881904
/// `Null` fall back to the per-group [`Accumulator`] path.
882905
fn is_hll_groups_type(data_type: &DataType) -> bool {
906+
if matches!(data_type, DataType::Dictionary(_, _)) {
907+
return is_supported_type(data_type);
908+
}
909+
883910
matches!(
884911
data_type,
885912
DataType::UInt32
@@ -927,6 +954,52 @@ mod tests {
927954
use super::*;
928955
use std::hash::BuildHasher;
929956

957+
#[test]
958+
fn dictionary_support() {
959+
for value_type in [
960+
DataType::Boolean,
961+
DataType::UInt8,
962+
DataType::Int8,
963+
DataType::UInt16,
964+
DataType::Int16,
965+
DataType::Int64,
966+
DataType::Null,
967+
DataType::Utf8,
968+
DataType::Binary,
969+
] {
970+
let dict_type = DataType::Dictionary(
971+
Box::new(DataType::Int32),
972+
Box::new(value_type.clone()),
973+
);
974+
assert!(is_hll_groups_type(&dict_type));
975+
}
976+
977+
// Nested dictionaries resolve to the innermost value
978+
assert!(is_hll_groups_type(&DataType::Dictionary(
979+
Box::new(DataType::Int32),
980+
Box::new(DataType::Dictionary(
981+
Box::new(DataType::Int32),
982+
Box::new(DataType::Utf8)
983+
))
984+
)));
985+
986+
// Unsupported value types are rejected
987+
for value_type in [DataType::Float16, DataType::Float32, DataType::Float64] {
988+
let dict_type = DataType::Dictionary(
989+
Box::new(DataType::Int32),
990+
Box::new(value_type.clone()),
991+
);
992+
let nested_dict_type = DataType::Dictionary(
993+
Box::new(DataType::Int32),
994+
Box::new(dict_type.clone()),
995+
);
996+
assert!(!is_hll_groups_type(&value_type));
997+
assert!(!is_supported_type(&dict_type));
998+
assert!(!is_hll_groups_type(&dict_type));
999+
assert!(!is_hll_groups_type(&nested_dict_type));
1000+
}
1001+
}
1002+
9301003
#[cfg(not(feature = "force_hash_collisions"))]
9311004
mod real_hash_test {
9321005
use super::*;

‎datafusion/sqllogictest/test_files/aggregate.slt‎

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1793,6 +1793,67 @@ SELECT g, approx_distinct(arrow_cast(arrow_cast(s, 'Binary'), 'FixedSizeBinary(1
17931793
4 1
17941794

17951795

1796+
# Dictionary: dictionary-encoded values must hash identically to the plain
1797+
# (non-dictionary) values, so the counts below match the Utf8 case above.
1798+
1799+
# Dictionary non-grouped
1800+
query I
1801+
SELECT approx_distinct(arrow_cast(s, 'Dictionary(Int32, Utf8)')) FROM approx_distinct_group_test WHERE g = 2;
1802+
----
1803+
2
1804+
1805+
# Dictionary grouped
1806+
query II
1807+
SELECT g, approx_distinct(arrow_cast(s, 'Dictionary(Int32, Utf8)')) FROM approx_distinct_group_test GROUP BY g ORDER BY g;
1808+
----
1809+
1 2
1810+
2 2
1811+
3 0
1812+
4 1
1813+
1814+
# Dictionary with a non-string value type (Int32), also exercising a
1815+
# larger (Int64) key type
1816+
query I
1817+
SELECT approx_distinct(arrow_cast(i, 'Dictionary(Int64, Int32)')) FROM approx_distinct_group_test WHERE g = 2;
1818+
----
1819+
2
1820+
1821+
query II
1822+
SELECT g, approx_distinct(arrow_cast(i, 'Dictionary(Int64, Int32)')) FROM approx_distinct_group_test GROUP BY g ORDER BY g;
1823+
----
1824+
1 2
1825+
2 2
1826+
3 0
1827+
4 1
1828+
1829+
# Dictionary over a fixed-domain value type (Int8). The bitmap accumulator only
1830+
# understands its native value array, so these go through the HyperLogLog groups
1831+
# accumulator and must still match the Int32 counts above.
1832+
query I
1833+
SELECT approx_distinct(arrow_cast(arrow_cast(i, 'Int8'), 'Dictionary(Int32, Int8)')) FROM approx_distinct_group_test WHERE g = 2;
1834+
----
1835+
2
1836+
1837+
query II
1838+
SELECT g, approx_distinct(arrow_cast(arrow_cast(i, 'Int8'), 'Dictionary(Int32, Int8)')) FROM approx_distinct_group_test GROUP BY g ORDER BY g;
1839+
----
1840+
1 2
1841+
2 2
1842+
3 0
1843+
4 1
1844+
1845+
# A dictionary is supported exactly when its value type is: floats are rejected
1846+
# just like a bare Float64 is, rather than silently reaching the HLL accumulator.
1847+
statement error DataFusion error: This feature is not implemented: Support for 'approx_distinct' for data type Float64 is not implemented
1848+
SELECT approx_distinct(arrow_cast(i, 'Float64')) FROM approx_distinct_group_test;
1849+
1850+
statement error DataFusion error: This feature is not implemented: Support for 'approx_distinct' for data type Dictionary\(Int32, Float64\) is not implemented
1851+
SELECT approx_distinct(arrow_cast(i, 'Dictionary(Int32, Float64)')) FROM approx_distinct_group_test;
1852+
1853+
statement error DataFusion error: This feature is not implemented: Support for 'approx_distinct' for data type Dictionary\(Int32, Float64\) is not implemented
1854+
SELECT g, approx_distinct(arrow_cast(i, 'Dictionary(Int32, Float64)')) FROM approx_distinct_group_test GROUP BY g;
1855+
1856+
17961857
# List
17971858
statement ok
17981859
CREATE TABLE approx_distinct_list_test (g INT, l INT[]) AS VALUES

0 commit comments

Comments
 (0)