Skip to content

Commit 9163b77

Browse files
cetra3bowenlan-amzn
authored andcommitted
Compact more aggressively in TopK based upon memory usage (apache#20381)
Sort of addresses apache#19386 Compaction in TopK values currently uses some hard set heuristics to decide when to compact. Instead we can use the memory size of the batches as a bound. Adjusts TopK compaction to compact more aggressively, based upon memory size. Yes and a test has been added. No I'm struggling (in this PR and other PRs...) to get some good reliable benchmarks through. However with this one it seems like it's *mostly* the same speed as `main` or a little faster in some cases: ``` + critcmp main topk_memory_batch group main topk_memory_batch ----- ---- ----------------- aggregate 10000000 time-series rows 1.05 45.5±2.13ms ? ?/sec 1.00 43.5±2.09ms ? ?/sec aggregate 10000000 worst-case rows 1.06 43.9±1.12ms ? ?/sec 1.00 41.5±1.03ms ? ?/sec distinct 10000000 rows asc [TopK] 1.00 4.3±0.25ms ? ?/sec 1.00 4.3±0.07ms ? ?/sec distinct 10000000 rows asc [no TopK] 1.00 42.9±1.83ms ? ?/sec 1.06 45.5±1.65ms ? ?/sec distinct 10000000 rows desc [TopK] 1.00 4.3±0.07ms ? ?/sec 1.01 4.3±0.06ms ? ?/sec distinct 10000000 rows desc [no TopK] 1.00 42.4±1.48ms ? ?/sec 1.05 44.7±1.88ms ? ?/sec top k=10 aggregate 10000000 time-series rows 1.13 10.6±0.54ms ? ?/sec 1.00 9.4±0.64ms ? ?/sec top k=10 aggregate 10000000 time-series rows [Utf8View] 1.08 11.0±0.65ms ? ?/sec 1.00 10.2±0.48ms ? ?/sec top k=10 aggregate 10000000 worst-case rows 1.04 16.8±1.47ms ? ?/sec 1.00 16.1±1.44ms ? ?/sec top k=10 aggregate 10000000 worst-case rows [Utf8View] 1.10 17.9±1.51ms ? ?/sec 1.00 16.2±1.16ms ? ?/sec top k=10 string aggregate 10000000 time-series rows [Utf8View] 1.11 9.1±0.36ms ? ?/sec 1.00 8.2±0.35ms ? ?/sec top k=10 string aggregate 10000000 time-series rows [Utf8] 1.12 7.8±0.48ms ? ?/sec 1.00 6.9±0.26ms ? ?/sec top k=10 string aggregate 10000000 worst-case rows [Utf8View] 1.06 8.6±0.21ms ? ?/sec 1.00 8.1±0.20ms ? ?/sec top k=10 string aggregate 10000000 worst-case rows [Utf8] 1.07 7.4±0.17ms ? ?/sec 1.00 6.9±0.13ms ? ?/sec ```
1 parent 3fddbcc commit 9163b77

2 files changed

Lines changed: 207 additions & 26 deletions

File tree

‎Cargo.toml‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -96,6 +96,7 @@ arrow = { version = "58.0.0", features = [
9696
"chrono-tz",
9797
] }
9898
arrow-buffer = { version = "58.0.0", default-features = false }
99+
arrow-data = { version = "58.0.0", default-features = false }
99100
arrow-flight = { version = "58.0.0", features = [
100101
"flight-sql-experimental",
101102
] }

‎datafusion/physical-plan/src/topk/mod.rs‎

Lines changed: 206 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -220,7 +220,7 @@ impl TopK {
220220
expr,
221221
row_converter,
222222
scratch_rows,
223-
heap: TopKHeap::new(k, batch_size),
223+
heap: TopKHeap::new(k),
224224
common_sort_prefix_converter: prefix_row_converter,
225225
common_sort_prefix: Arc::from(common_sort_prefix),
226226
finished: false,
@@ -662,8 +662,6 @@ impl TopKMetrics {
662662
struct TopKHeap {
663663
/// The maximum number of elements to store in this heap.
664664
k: usize,
665-
/// The target number of rows for output batches
666-
batch_size: usize,
667665
/// Storage for up at most `k` items using a BinaryHeap. Reversed
668666
/// so that the smallest k so far is on the top
669667
inner: BinaryHeap<TopKRow>,
@@ -674,11 +672,10 @@ struct TopKHeap {
674672
}
675673

676674
impl TopKHeap {
677-
fn new(k: usize, batch_size: usize) -> Self {
675+
fn new(k: usize) -> Self {
678676
assert!(k > 0);
679677
Self {
680678
k,
681-
batch_size,
682679
inner: BinaryHeap::new(),
683680
store: RecordBatchStore::new(),
684681
owned_bytes: 0,
@@ -791,24 +788,26 @@ impl TopKHeap {
791788
/// Compact this heap, rewriting all stored batches into a single
792789
/// input batch
793790
pub fn maybe_compact(&mut self) -> Result<()> {
794-
// we compact if the number of "unused" rows in the store is
795-
// past some pre-defined threshold. Target holding up to
796-
// around 20 batches, but handle cases of large k where some
797-
// batches might be partially full
798-
let max_unused_rows = (20 * self.batch_size) + self.k;
799-
let unused_rows = self.store.unused_rows();
800-
801-
// don't compact if the store has one extra batch or
802-
// unused rows is under the threshold
803-
if self.store.len() <= 2 || unused_rows < max_unused_rows {
791+
// Don't compact if there's only one batch (compacting into itself is pointless)
792+
if self.store.len() <= 1 {
793+
return Ok(());
794+
}
795+
796+
let total_rows = self.store.total_rows;
797+
let num_rows = self.inner.len();
798+
799+
// Compact when current store memory exceeds 2x what the compacted
800+
// result would need. The multiplier avoids compacting when the
801+
// savings would be marginal.
802+
if total_rows <= num_rows * 2 {
804803
return Ok(());
805804
}
805+
806806
// at first, compact the entire thing always into a new batch
807807
// (maybe we can get fancier in the future about ignoring
808808
// batches that have a high usage ratio already
809809

810810
// Note: new batch is in the same order as inner
811-
let num_rows = self.inner.len();
812811
let (new_batch, mut topk_rows) = self.emit_with_state()?;
813812
let Some(new_batch) = new_batch else {
814813
return Ok(());
@@ -968,6 +967,8 @@ struct RecordBatchStore {
968967
batches: HashMap<u32, RecordBatchEntry>,
969968
/// total size of all record batches tracked by this store
970969
batches_size: usize,
970+
/// row count of all the batches
971+
total_rows: usize,
971972
}
972973

973974
impl RecordBatchStore {
@@ -976,6 +977,7 @@ impl RecordBatchStore {
976977
next_id: 0,
977978
batches: HashMap::new(),
978979
batches_size: 0,
980+
total_rows: 0,
979981
}
980982
}
981983

@@ -993,6 +995,7 @@ impl RecordBatchStore {
993995
// uses of 0 means that none of the rows in the batch were stored in the topk
994996
if entry.uses > 0 {
995997
self.batches_size += get_record_batch_memory_size(&entry.batch);
998+
self.total_rows += entry.batch.num_rows();
996999
self.batches.insert(entry.id, entry);
9971000
}
9981001
}
@@ -1001,6 +1004,7 @@ impl RecordBatchStore {
10011004
fn clear(&mut self) {
10021005
self.batches.clear();
10031006
self.batches_size = 0;
1007+
self.total_rows = 0;
10041008
}
10051009

10061010
fn get(&self, id: u32) -> Option<&RecordBatchEntry> {
@@ -1012,15 +1016,6 @@ impl RecordBatchStore {
10121016
self.batches.len()
10131017
}
10141018

1015-
/// Returns the total number of rows in batches minus the number
1016-
/// which are in use
1017-
fn unused_rows(&self) -> usize {
1018-
self.batches
1019-
.values()
1020-
.map(|batch_entry| batch_entry.batch.num_rows() - batch_entry.uses)
1021-
.sum()
1022-
}
1023-
10241019
/// returns true if the store has nothing stored
10251020
fn is_empty(&self) -> bool {
10261021
self.batches.is_empty()
@@ -1044,6 +1039,11 @@ impl RecordBatchStore {
10441039
.batches_size
10451040
.checked_sub(get_record_batch_memory_size(&old_entry.batch))
10461041
.unwrap();
1042+
1043+
self.total_rows = self
1044+
.total_rows
1045+
.checked_sub(old_entry.batch.num_rows())
1046+
.unwrap();
10471047
}
10481048
}
10491049

@@ -1059,7 +1059,7 @@ impl RecordBatchStore {
10591059
#[cfg(test)]
10601060
mod tests {
10611061
use super::*;
1062-
use arrow::array::{Float64Array, Int32Array, RecordBatch};
1062+
use arrow::array::{BooleanArray, Float64Array, Int32Array, RecordBatch};
10631063
use arrow::datatypes::{DataType, Field, Schema};
10641064
use arrow_schema::SortOptions;
10651065
use datafusion_common::assert_batches_eq;
@@ -1242,4 +1242,184 @@ mod tests {
12421242

12431243
Ok(())
12441244
}
1245+
1246+
/// Tests that memory-based compaction triggers when a large batch
1247+
/// has very few rows referenced by the top-k heap.
1248+
#[tokio::test]
1249+
async fn test_topk_memory_compaction() -> Result<()> {
1250+
let schema = Arc::new(Schema::new(vec![Field::new("a", DataType::Int32, false)]));
1251+
1252+
let sort_expr = PhysicalSortExpr {
1253+
expr: col("a", schema.as_ref())?,
1254+
options: SortOptions::default(),
1255+
};
1256+
1257+
let full_expr = LexOrdering::from([sort_expr.clone()]);
1258+
let prefix = vec![sort_expr];
1259+
1260+
let runtime = Arc::new(RuntimeEnv::default());
1261+
let metrics = ExecutionPlanMetricsSet::new();
1262+
1263+
let k = 5;
1264+
let mut topk = TopK::try_new(
1265+
0,
1266+
Arc::clone(&schema),
1267+
prefix,
1268+
full_expr,
1269+
k,
1270+
8192,
1271+
runtime,
1272+
&metrics,
1273+
Arc::new(RwLock::new(TopKDynamicFilters::new(Arc::new(
1274+
DynamicFilterPhysicalExpr::new(vec![], lit(true)),
1275+
)))),
1276+
)?;
1277+
1278+
// Insert a large batch (100,000 rows) with values 1..=100_000.
1279+
// Only the smallest 5 values (1..=5) will end up in the heap.
1280+
let large_values: Vec<i32> = (1..=100_000).collect();
1281+
let array1: ArrayRef = Arc::new(Int32Array::from(large_values));
1282+
let batch1 = RecordBatch::try_new(Arc::clone(&schema), vec![array1])?;
1283+
topk.insert_batch(batch1)?;
1284+
1285+
// After the first batch, store has 1 batch — compaction should
1286+
// not trigger (guard: store.len() <= 1).
1287+
assert_eq!(
1288+
topk.heap.store.len(),
1289+
1,
1290+
"should have 1 batch before second insert"
1291+
);
1292+
1293+
// Insert a second batch whose values displace entries in the heap.
1294+
// -1 and 0 are smaller than the current top-5 (1..=5), so they
1295+
// produce 2 replacements. With replacements > 0, `insert_batch`
1296+
// calls `insert_batch_entry` (briefly making store.len() == 2)
1297+
// and then `maybe_compact`, which should collapse it back to 1.
1298+
let array2: ArrayRef = Arc::new(Int32Array::from(vec![-1, 0]));
1299+
let batch2 = RecordBatch::try_new(Arc::clone(&schema), vec![array2])?;
1300+
let replacements_before = topk.metrics.row_replacements.value();
1301+
topk.insert_batch(batch2)?;
1302+
1303+
// Sanity check: batch2 was actually integrated. Without
1304+
// replacements, `maybe_compact` is never called and the
1305+
// store-length assertion below would pass vacuously.
1306+
assert!(
1307+
topk.metrics.row_replacements.value() > replacements_before,
1308+
"batch2 must produce replacements so compaction is exercised"
1309+
);
1310+
1311+
// The compacted-estimate guard is `total_rows <= num_rows * 2`,
1312+
// i.e. 100_002 <= 10, which is false, so compaction fires and
1313+
// collapses the two stored batches back into one.
1314+
assert_eq!(
1315+
topk.heap.store.len(),
1316+
1,
1317+
"store should be compacted to 1 batch"
1318+
);
1319+
1320+
// Verify the emitted results are correct (top 5 ascending).
1321+
let results: Vec<_> = topk.emit()?.try_collect().await?;
1322+
assert_batches_eq!(
1323+
&[
1324+
"+----+", "| a |", "+----+", "| -1 |", "| 0 |", "| 1 |", "| 2 |",
1325+
"| 3 |", "+----+",
1326+
],
1327+
&results
1328+
);
1329+
1330+
Ok(())
1331+
}
1332+
1333+
/// Negative path: when stored rows are close to the heap size,
1334+
/// compaction must NOT fire even with multiple batches present,
1335+
/// because the savings would be marginal
1336+
/// (guard: `total_rows <= num_rows * 2`).
1337+
///
1338+
/// Uses a bit-packed `BooleanArray` so that future changes to the
1339+
/// compaction heuristic that reintroduce a per-byte estimate
1340+
/// (where integer truncation could misbehave on sub-byte types)
1341+
/// are caught here.
1342+
#[tokio::test]
1343+
async fn test_topk_memory_compaction_skipped_when_marginal() -> Result<()> {
1344+
let schema =
1345+
Arc::new(Schema::new(vec![Field::new("a", DataType::Boolean, false)]));
1346+
1347+
let sort_expr = PhysicalSortExpr {
1348+
expr: col("a", schema.as_ref())?,
1349+
options: SortOptions::default(),
1350+
};
1351+
let full_expr = LexOrdering::from([sort_expr.clone()]);
1352+
let prefix = vec![sort_expr];
1353+
1354+
let runtime = Arc::new(RuntimeEnv::default());
1355+
let metrics = ExecutionPlanMetricsSet::new();
1356+
1357+
let k = 10;
1358+
let mut topk = TopK::try_new(
1359+
0,
1360+
Arc::clone(&schema),
1361+
prefix,
1362+
full_expr,
1363+
k,
1364+
8192,
1365+
runtime,
1366+
&metrics,
1367+
Arc::new(RwLock::new(TopKDynamicFilters::new(Arc::new(
1368+
DynamicFilterPhysicalExpr::new(vec![], lit(true)),
1369+
)))),
1370+
)?;
1371+
1372+
// Two small batches; every row from both batches ends up referenced
1373+
// by the heap, so total_rows == num_rows == 10.
1374+
let batch1 = RecordBatch::try_new(
1375+
Arc::clone(&schema),
1376+
vec![
1377+
Arc::new(BooleanArray::from(vec![false, false, true, true, true]))
1378+
as ArrayRef,
1379+
],
1380+
)?;
1381+
topk.insert_batch(batch1)?;
1382+
1383+
let batch2 = RecordBatch::try_new(
1384+
Arc::clone(&schema),
1385+
vec![
1386+
Arc::new(BooleanArray::from(vec![false, false, false, true, true]))
1387+
as ArrayRef,
1388+
],
1389+
)?;
1390+
topk.insert_batch(batch2)?;
1391+
1392+
// Guard `total_rows <= num_rows * 2` should hold (10 <= 20),
1393+
// so compaction is skipped and BOTH batches remain in the store.
1394+
assert_eq!(
1395+
topk.heap.store.len(),
1396+
2,
1397+
"store must keep 2 batches when savings would be marginal"
1398+
);
1399+
assert_eq!(topk.heap.inner.len(), 10, "heap should hold all 10 rows");
1400+
1401+
// Output is still correct (5 falses then 5 trues ascending).
1402+
let results: Vec<_> = topk.emit()?.try_collect().await?;
1403+
assert_batches_eq!(
1404+
&[
1405+
"+-------+",
1406+
"| a |",
1407+
"+-------+",
1408+
"| false |",
1409+
"| false |",
1410+
"| false |",
1411+
"| false |",
1412+
"| false |",
1413+
"| true |",
1414+
"| true |",
1415+
"| true |",
1416+
"| true |",
1417+
"| true |",
1418+
"+-------+",
1419+
],
1420+
&results
1421+
);
1422+
1423+
Ok(())
1424+
}
12451425
}

0 commit comments

Comments
 (0)