Skip to content

Commit 3943ff1

Browse files
committed
feat: add approx_top_k aggregate function
Add a new approx_top_k(expression, k) aggregate function that returns the approximate top-k most frequent values with their estimated counts, using the Filtered Space-Saving algorithm. The implementation uses a capacity multiplier of 3 (matching ClickHouse's default) and includes an alpha map for improved accuracy by filtering low-frequency noise before it enters the main summary. Return type is List(Struct({value: T, count: UInt64})) ordered by count descending, where T matches the input column type. Closes apache#20967
1 parent 22eb8ff commit 3943ff1

7 files changed

Lines changed: 1566 additions & 4 deletions

File tree

‎datafusion/core/tests/dataframe/dataframe_functions.rs‎

Lines changed: 25 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -19,7 +19,9 @@ use datafusion_common::test_util::batches_to_string;
1919
use datafusion_common::{DFSchema, ScalarValue};
2020
use datafusion_expr::expr::Alias;
2121
use datafusion_expr::{ExprSchemable, LogicalPlanBuilder, table_scan};
22-
use datafusion_functions_aggregate::expr_fn::{approx_median, approx_percentile_cont};
22+
use datafusion_functions_aggregate::expr_fn::{
23+
approx_median, approx_percentile_cont, approx_top_k,
24+
};
2325
use datafusion_functions_nested::map::map;
2426
use insta::assert_snapshot;
2527

@@ -396,6 +398,28 @@ async fn test_fn_approx_median() -> Result<()> {
396398
Ok(())
397399
}
398400

401+
#[tokio::test]
402+
async fn test_fn_approx_top_k() -> Result<()> {
403+
// Column b has values [1, 10, 10, 100] -- 10 appears twice, others once.
404+
// Use k=1 to avoid non-deterministic ordering among tied items.
405+
let expr = approx_top_k(vec![col("b"), lit(1)]);
406+
407+
let df = create_test_table().await?;
408+
let batches = df.aggregate(vec![], vec![expr]).unwrap().collect().await?;
409+
410+
assert_snapshot!(
411+
batches_to_string(&batches),
412+
@r"
413+
+-------------------------------+
414+
| approx_top_k(test.b,Int32(1)) |
415+
+-------------------------------+
416+
| [{value: 10, count: 2}] |
417+
+-------------------------------+
418+
");
419+
420+
Ok(())
421+
}
422+
399423
#[tokio::test]
400424
async fn test_fn_approx_percentile_cont() -> Result<()> {
401425
let expr = approx_percentile_cont(col("b").sort(true, false), lit(0.5), None);

0 commit comments

Comments
 (0)