1use std::collections::HashMap;
24use std::fmt;
25use std::num::NonZeroU64;
26use std::sync::Arc;
27use std::time::{Duration, Instant, SystemTime, UNIX_EPOCH};
28
29use arrow::array::RecordBatch;
30use arrow::datatypes::SchemaRef;
31use datafusion::catalog::Session;
32use datafusion::execution::context::{SessionContext, SessionState};
33use delta_kernel::expressions::Scalar;
34use delta_kernel::table_features::ColumnMappingMode;
35use delta_kernel::table_properties::DataSkippingNumIndexedCols;
36use futures::future::BoxFuture;
37use futures::stream::BoxStream;
38use futures::{Future, StreamExt, TryStreamExt};
39use indexmap::IndexMap;
40use itertools::Itertools;
41
42use parquet::basic::{Compression, ZstdLevel};
43use parquet::errors::ParquetError;
44use parquet::file::properties::WriterProperties;
45use serde::{Deserialize, Deserializer, Serialize, Serializer, de::Error as DeError};
46use tracing::*;
47use uuid::Uuid;
48
49use super::{CustomExecuteHandler, Operation};
50use crate::datafile::writer::{PartitionWriter, PartitionWriterConfig, UploadBudget};
51use crate::delta_datafusion::{
52 DeltaScanConfig, DeltaScanNext, SessionFallbackPolicy, SessionResolveContext,
53 create_session_state_with_spill_config, resolve_session_state, update_datafusion_session,
54};
55use crate::errors::{ColumnMappingOperation, DeltaResult, DeltaTableError};
56use crate::kernel::transaction::{CommitBuilder, CommitProperties, DEFAULT_RETRIES, PROTOCOL};
57use crate::kernel::{Action, Add, DataType, PartitionsExt, Remove, StructType, Version};
58use crate::kernel::{EagerSnapshot, resolve_snapshot};
59use crate::logstore::{LogStore, LogStoreRef, ObjectStoreRef};
60use crate::parquet_utils::default_writer_properties;
61use crate::protocol::DeltaOperation;
62use crate::table::config::TablePropertiesExt as _;
63use crate::table::state::DeltaTableState;
64use crate::writer::utils::arrow_schema_without_partitions;
65use crate::{
66 DeltaTable, FilterLiteral, ObjectMeta, conjunction_to_kernel_predicate,
67 literal_to_predicate_string,
68};
69
70#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, Serialize, Deserialize)]
72#[serde(rename_all = "camelCase")]
73pub enum PlannerStrategy {
74 #[default]
76 UnknownLegacy,
77 PreserveLocality,
79 ZOrder,
81}
82
83#[derive(Default, Debug, PartialEq, Clone, Serialize, Deserialize)]
85#[serde(rename_all = "camelCase", from = "MetricsSerde")]
86pub struct Metrics {
87 pub num_files_added: u64,
89 pub num_files_removed: u64,
91 #[serde(
93 serialize_with = "serialize_metric_details",
94 deserialize_with = "deserialize_metric_details"
95 )]
96 pub files_added: MetricDetails,
97 #[serde(
99 serialize_with = "serialize_metric_details",
100 deserialize_with = "deserialize_metric_details"
101 )]
102 pub files_removed: MetricDetails,
103 pub partitions_optimized: u64,
105 pub num_batches: u64,
107 pub total_considered_files: usize,
109 pub total_files_skipped: usize,
111 pub preserve_insertion_order: bool,
113 pub planner_strategy: PlannerStrategy,
115 pub preserved_stable_order: bool,
117 pub max_bin_span_files: usize,
119}
120
121#[derive(Debug, Deserialize)]
122#[serde(rename_all = "camelCase")]
123struct MetricsSerde {
124 num_files_added: u64,
125 num_files_removed: u64,
126 #[serde(deserialize_with = "deserialize_metric_details")]
127 files_added: MetricDetails,
128 #[serde(deserialize_with = "deserialize_metric_details")]
129 files_removed: MetricDetails,
130 partitions_optimized: u64,
131 num_batches: u64,
132 total_considered_files: usize,
133 total_files_skipped: usize,
134 #[serde(default)]
135 preserve_insertion_order: Option<bool>,
136 #[serde(default)]
137 planner_strategy: PlannerStrategy,
138 #[serde(default)]
139 preserved_stable_order: Option<bool>,
140 #[serde(default)]
141 max_bin_span_files: usize,
142}
143
144impl From<MetricsSerde> for Metrics {
145 fn from(value: MetricsSerde) -> Self {
146 let preserve_insertion_order = value
147 .preserve_insertion_order
148 .or(value.preserved_stable_order)
149 .unwrap_or(false);
150 let preserved_stable_order = value.preserved_stable_order.unwrap_or(false);
151
152 Self {
153 num_files_added: value.num_files_added,
154 num_files_removed: value.num_files_removed,
155 files_added: value.files_added,
156 files_removed: value.files_removed,
157 partitions_optimized: value.partitions_optimized,
158 num_batches: value.num_batches,
159 total_considered_files: value.total_considered_files,
160 total_files_skipped: value.total_files_skipped,
161 preserve_insertion_order,
162 planner_strategy: value.planner_strategy,
163 preserved_stable_order,
164 max_bin_span_files: value.max_bin_span_files,
165 }
166 }
167}
168
169fn serialize_metric_details<S>(value: &MetricDetails, serializer: S) -> Result<S::Ok, S::Error>
171where
172 S: Serializer,
173{
174 serializer.serialize_str(&value.to_string())
175}
176
177fn deserialize_metric_details<'de, D>(deserializer: D) -> Result<MetricDetails, D::Error>
179where
180 D: Deserializer<'de>,
181{
182 let s: String = Deserialize::deserialize(deserializer)?;
183 serde_json::from_str(&s).map_err(DeError::custom)
184}
185
186#[derive(Debug, PartialEq, Clone, Serialize, Deserialize)]
189#[serde(rename_all = "camelCase")]
190pub struct MetricDetails {
191 pub avg: f64,
193 pub max: i64,
195 pub min: i64,
197 pub total_files: usize,
199 pub total_size: i64,
201}
202
203impl MetricDetails {
204 pub fn add(&mut self, partial: &MetricDetails) {
206 self.min = std::cmp::min(self.min, partial.min);
207 self.max = std::cmp::max(self.max, partial.max);
208 self.total_files += partial.total_files;
209 self.total_size += partial.total_size;
210 self.avg = self.total_size as f64 / self.total_files as f64;
211 }
212}
213
214impl fmt::Display for MetricDetails {
215 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
217 serde_json::to_string(self).map_err(|_| fmt::Error)?.fmt(f)
218 }
219}
220
221#[derive(Debug)]
222pub struct PartialMetrics {
224 pub num_files_added: u64,
226 pub num_files_removed: u64,
228 pub files_added: MetricDetails,
230 pub files_removed: MetricDetails,
232 pub num_batches: u64,
234}
235
236impl Metrics {
237 pub fn add(&mut self, partial: &PartialMetrics) {
239 self.num_files_added += partial.num_files_added;
240 self.num_files_removed += partial.num_files_removed;
241 self.files_added.add(&partial.files_added);
242 self.files_removed.add(&partial.files_removed);
243 self.num_batches += partial.num_batches;
244 }
245
246 fn apply_planner_stats(&mut self, planner_stats: &PlannerStats) {
247 self.planner_strategy = planner_stats.planner_strategy;
248 self.preserved_stable_order = planner_stats.preserved_stable_order;
249 self.preserve_insertion_order = planner_stats.preserved_stable_order;
250 self.max_bin_span_files = planner_stats.max_bin_span_files;
251 }
252}
253
254impl Default for MetricDetails {
255 fn default() -> Self {
256 MetricDetails {
257 min: i64::MAX,
258 max: 0,
259 avg: 0.0,
260 total_files: 0,
261 total_size: 0,
262 }
263 }
264}
265
266#[derive(Debug)]
268pub enum OptimizeType {
269 Compact,
271 ZOrder(Vec<String>),
273}
274
275pub struct OptimizeBuilder<'a> {
280 snapshot: Option<EagerSnapshot>,
282 log_store: LogStoreRef,
284 filters: &'a [FilterLiteral<'a>],
286 target_size: Option<NonZeroU64>,
288 writer_properties: Option<WriterProperties>,
290 commit_properties: CommitProperties,
292 max_concurrent_tasks: usize,
294 optimize_type: OptimizeType,
296 session: Option<Arc<dyn Session>>,
298 session_fallback_policy: SessionFallbackPolicy,
299 min_commit_interval: Option<Duration>,
300 custom_execute_handler: Option<Arc<dyn CustomExecuteHandler>>,
301}
302
303impl super::Operation for OptimizeBuilder<'_> {
304 fn log_store(&self) -> &LogStoreRef {
305 &self.log_store
306 }
307 fn get_custom_execute_handler(&self) -> Option<Arc<dyn CustomExecuteHandler>> {
308 self.custom_execute_handler.clone()
309 }
310}
311
312impl<'a> OptimizeBuilder<'a> {
313 pub(crate) fn new(log_store: LogStoreRef, snapshot: Option<EagerSnapshot>) -> Self {
315 Self {
316 snapshot,
317 log_store,
318 filters: &[],
319 target_size: None,
320 writer_properties: None,
321 commit_properties: CommitProperties::default(),
322 max_concurrent_tasks: std::thread::available_parallelism()
323 .map(|n| n.get())
324 .unwrap_or(1),
325 optimize_type: OptimizeType::Compact,
326 min_commit_interval: None,
327 session: None,
328 session_fallback_policy: SessionFallbackPolicy::default(),
329 custom_execute_handler: None,
330 }
331 }
332
333 pub fn with_type(mut self, optimize_type: OptimizeType) -> Self {
335 self.optimize_type = optimize_type;
336 self
337 }
338
339 pub fn with_filters(mut self, filters: &'a [FilterLiteral<'a>]) -> Self {
342 self.filters = filters;
343 self
344 }
345
346 pub fn with_target_size(mut self, target: NonZeroU64) -> Self {
348 self.target_size = Some(target);
349 self
350 }
351
352 pub fn with_writer_properties(mut self, writer_properties: WriterProperties) -> Self {
354 self.writer_properties = Some(writer_properties);
355 self
356 }
357
358 pub fn with_commit_properties(mut self, commit_properties: CommitProperties) -> Self {
360 self.commit_properties = commit_properties;
361 self
362 }
363
364 #[deprecated(
366 since = "0.32.0",
367 note = "compact always keeps partition file order, and z order does not; this setting has no effect"
368 )]
369 pub fn with_preserve_insertion_order(self, _preserve_insertion_order: bool) -> Self {
370 self
371 }
372
373 pub fn with_max_concurrent_tasks(mut self, max_concurrent_tasks: usize) -> Self {
375 self.max_concurrent_tasks = max_concurrent_tasks;
376 self
377 }
378
379 pub fn with_min_commit_interval(mut self, min_commit_interval: Duration) -> Self {
381 self.min_commit_interval = Some(min_commit_interval);
382 self
383 }
384
385 pub fn with_custom_execute_handler(mut self, handler: Arc<dyn CustomExecuteHandler>) -> Self {
387 self.custom_execute_handler = Some(handler);
388 self
389 }
390
391 pub fn with_session_state(mut self, session: Arc<dyn Session>) -> Self {
401 self.session = Some(session);
402 self
403 }
404
405 pub fn with_session_fallback_policy(mut self, policy: SessionFallbackPolicy) -> Self {
409 self.session_fallback_policy = policy;
410 self
411 }
412}
413
414impl<'a> std::future::IntoFuture for OptimizeBuilder<'a> {
415 type Output = DeltaResult<(DeltaTable, Metrics)>;
416 type IntoFuture = BoxFuture<'a, Self::Output>;
417
418 fn into_future(self) -> Self::IntoFuture {
419 let this = self;
420
421 Box::pin(async move {
422 let snapshot = resolve_snapshot(&this.log_store, this.snapshot.clone(), None).await?;
423 if snapshot.table_configuration().column_mapping_mode() != ColumnMappingMode::None {
424 return Err(DeltaTableError::unsupported_column_mapping(
425 ColumnMappingOperation::Write,
426 "OPTIMIZE",
427 ));
428 }
429 PROTOCOL.can_write_to(&snapshot)?;
430
431 let operation_id = this.get_operation_id();
432 this.pre_execute(operation_id).await?;
433
434 let writer_properties = this.writer_properties.unwrap_or_else(|| {
435 default_writer_properties(Compression::ZSTD(ZstdLevel::try_new(4).unwrap()))
436 });
437 let (session, _) = resolve_session_state(
438 this.session.as_deref(),
439 this.session_fallback_policy,
440 || create_session_state_with_spill_config(None, None),
441 SessionResolveContext {
442 operation: "optimize",
443 table_uri: Some(this.log_store.root_url()),
444 cdc: false,
445 },
446 )?;
447 let plan = create_merge_plan(
448 &this.log_store,
449 this.optimize_type,
450 &snapshot,
451 this.filters,
452 this.target_size.to_owned(),
453 writer_properties,
454 session,
455 )
456 .await?;
457
458 let metrics = plan
459 .execute(
460 this.log_store.clone(),
461 &snapshot,
462 this.max_concurrent_tasks,
463 this.min_commit_interval,
464 this.commit_properties.clone(),
465 operation_id,
466 this.custom_execute_handler.as_ref(),
467 )
468 .await?;
469
470 if let Some(handler) = this.custom_execute_handler {
471 handler.post_execute(&this.log_store, operation_id).await?;
472 }
473 let mut table =
474 DeltaTable::new_with_state(this.log_store, DeltaTableState::new(snapshot));
475 table.update_state().await?;
476 Ok((table, metrics))
477 })
478 }
479}
480
481#[derive(Debug, Clone)]
482struct OptimizeInput {
483 target_size: NonZeroU64,
484 predicate: Option<String>,
485}
486
487const MAX_OPTIMIZE_TARGET_SIZE: u64 = i64::MAX as u64;
488
489fn optimize_target_size_to_i64(target_size: NonZeroU64) -> Result<i64, DeltaTableError> {
490 i64::try_from(target_size.get()).map_err(|_| {
491 DeltaTableError::Generic(format!(
492 "optimize target_size {} exceeds i64::MAX ({MAX_OPTIMIZE_TARGET_SIZE})",
493 target_size.get()
494 ))
495 })
496}
497
498impl TryFrom<OptimizeInput> for DeltaOperation {
499 type Error = DeltaTableError;
500
501 fn try_from(opt_input: OptimizeInput) -> Result<Self, Self::Error> {
502 Ok(DeltaOperation::Optimize {
503 target_size: optimize_target_size_to_i64(opt_input.target_size)?,
504 predicate: opt_input.predicate,
505 })
506 }
507}
508
509fn create_remove(add: &Add) -> Action {
511 let deletion_time = SystemTime::now().duration_since(UNIX_EPOCH).unwrap();
513 let deletion_time = deletion_time.as_millis() as i64;
514
515 Action::Remove(Remove {
516 path: add.path.clone(),
517 deletion_timestamp: Some(deletion_time),
518 data_change: false,
519 extended_file_metadata: Some(true),
520 partition_values: Some(add.partition_values.clone()),
521 size: Some(add.size),
522 deletion_vector: add.deletion_vector.clone(),
523 tags: add.tags.clone(),
524 base_row_id: add.base_row_id,
525 default_row_commit_version: add.default_row_commit_version,
526 })
527}
528
529#[derive(Debug)]
534enum OptimizeOperations {
535 Compact(HashMap<String, (IndexMap<String, Scalar>, Vec<MergeBin>)>),
540 ZOrder(
542 Vec<String>,
543 HashMap<String, (IndexMap<String, Scalar>, MergeBin)>,
544 ),
545 }
547
548impl Default for OptimizeOperations {
549 fn default() -> Self {
550 OptimizeOperations::Compact(HashMap::new())
551 }
552}
553
554#[derive(Debug)]
555pub struct MergePlan {
557 operations: OptimizeOperations,
558 metrics: Metrics,
560 planner_stats: PlannerStats,
562 task_parameters: Arc<MergeTaskParameters>,
564 read_table_version: Version,
566 read_session: Arc<SessionState>,
568 scan_config: DeltaScanConfig,
570}
571
572#[derive(Debug, Clone, Default)]
573struct PlannerStats {
574 planner_strategy: PlannerStrategy,
575 preserved_stable_order: bool,
576 max_bin_span_files: usize,
577}
578
579impl PlannerStats {
580 fn preserve_locality() -> Self {
581 Self {
582 planner_strategy: PlannerStrategy::PreserveLocality,
583 preserved_stable_order: true,
584 max_bin_span_files: 0,
585 }
586 }
587
588 fn z_order(max_bin_span_files: usize) -> Self {
589 Self {
590 planner_strategy: PlannerStrategy::ZOrder,
591 preserved_stable_order: false,
592 max_bin_span_files,
593 }
594 }
595
596 fn absorb(&mut self, other: &PlannerStats) {
597 self.max_bin_span_files = self.max_bin_span_files.max(other.max_bin_span_files);
598 }
599}
600
601#[derive(Debug)]
603pub struct MergeTaskParameters {
604 file_schema: SchemaRef,
606 writer_properties: WriterProperties,
608 input_parameters: OptimizeInput,
610 num_indexed_cols: DataSkippingNumIndexedCols,
612 stats_columns: Option<Vec<String>>,
614 upload_budget: UploadBudget,
616}
617
618type ParquetReadStream = BoxStream<'static, Result<RecordBatch, ParquetError>>;
620
621#[derive(Clone)]
622struct SelectedFileScanFactory {
623 snapshot: EagerSnapshot,
624 log_store: LogStoreRef,
625 scan_config: DeltaScanConfig,
626 read_operation_id: Option<Uuid>,
627}
628
629impl SelectedFileScanFactory {
630 fn new(
631 snapshot: &EagerSnapshot,
632 log_store: LogStoreRef,
633 scan_config: DeltaScanConfig,
634 read_operation_id: Option<Uuid>,
635 ) -> Self {
636 Self {
637 snapshot: snapshot.clone(),
638 log_store,
639 scan_config,
640 read_operation_id,
641 }
642 }
643
644 fn provider_for(
645 &self,
646 adds: impl IntoIterator<Item = Add>,
647 ) -> Result<DeltaScanNext, DeltaTableError> {
648 let provider = DeltaScanNext::new(self.snapshot.clone(), self.scan_config.clone())?
649 .with_log_store(self.log_store.clone());
650 let provider = if let Some(operation_id) = self.read_operation_id {
651 provider.with_operation_id(operation_id)
652 } else {
653 provider
654 };
655 Ok(provider.with_adds(adds))
656 }
657}
658
659impl MergePlan {
660 async fn rewrite_files<F>(
665 task_parameters: Arc<MergeTaskParameters>,
666 partition_values: IndexMap<String, Scalar>,
667 files: MergeBin,
668 object_store: ObjectStoreRef,
669 read_stream: F,
670 ignore_target_size: bool,
671 ) -> Result<(Vec<Action>, PartialMetrics), DeltaTableError>
672 where
673 F: Future<Output = Result<ParquetReadStream, DeltaTableError>> + Send + 'static,
674 {
675 debug!("Rewriting files in partition: {partition_values:?}");
676 let mut partial_actions = files.iter().map(create_remove).collect::<Vec<_>>();
678
679 let files_removed = files
680 .iter()
681 .fold(MetricDetails::default(), |mut curr, file| {
682 curr.total_files += 1;
683 curr.total_size += file.size;
684 curr.max = std::cmp::max(curr.max, file.size);
685 curr.min = std::cmp::min(curr.min, file.size);
686 curr
687 });
688
689 let mut partial_metrics = PartialMetrics {
690 num_files_added: 0,
691 num_files_removed: files.len() as u64,
692 files_added: MetricDetails::default(),
693 files_removed,
694 num_batches: 0,
695 };
696
697 let writer_config = PartitionWriterConfig::try_new(
699 task_parameters.file_schema.clone(),
700 partition_values.clone(),
701 Some(task_parameters.writer_properties.clone()),
702 if ignore_target_size {
704 None
705 } else {
706 Some(task_parameters.input_parameters.target_size)
707 },
708 None,
709 None,
710 None,
711 )?
712 .with_upload_budget(task_parameters.upload_budget.clone());
713 let mut writer = PartitionWriter::try_with_config(
714 object_store,
715 writer_config,
716 task_parameters.num_indexed_cols,
717 task_parameters.stats_columns.clone(),
718 )?;
719
720 let mut read_stream = read_stream.await?;
721
722 while let Some(maybe_batch) = read_stream.next().await {
723 let mut batch = maybe_batch?;
724
725 batch = crate::kernel::schema::cast::cast_record_batch(
726 &batch,
727 task_parameters.file_schema.clone(),
728 false,
729 true,
730 )?;
731 partial_metrics.num_batches += 1;
732 writer.write(&batch).await?;
733 }
734
735 let add_actions = writer.close().await?.into_iter().map(|mut add| {
736 add.data_change = false;
737
738 let size = add.size;
739
740 partial_metrics.num_files_added += 1;
741 partial_metrics.files_added.total_files += 1;
742 partial_metrics.files_added.total_size += size;
743 partial_metrics.files_added.max = std::cmp::max(partial_metrics.files_added.max, size);
744 partial_metrics.files_added.min = std::cmp::min(partial_metrics.files_added.min, size);
745
746 Action::Add(add)
747 });
748 partial_actions.extend(add_actions);
749
750 debug!("Finished rewriting files in partition: {partition_values:?}");
751
752 Ok((partial_actions, partial_metrics))
753 }
754
755 async fn read_selected_files(
756 files: MergeBin,
757 context: Arc<SessionContext>,
758 scan_factory: SelectedFileScanFactory,
759 ) -> Result<ParquetReadStream, DeltaTableError> {
760 let provider = scan_factory.provider_for(files.iter().cloned())?;
761 let df = context.read_table(Arc::new(provider))?;
762 let stream = df
763 .execute_stream()
764 .await?
765 .map_err(|err| {
766 ParquetError::General(format!(
767 "Optimize selected-file scan failed while scanning data: {err}"
768 ))
769 })
770 .boxed();
771 Ok(stream)
772 }
773
774 async fn read_zorder(
776 files: MergeBin,
777 context: Arc<zorder::ZOrderExecContext>,
778 scan_factory: SelectedFileScanFactory,
779 ) -> Result<BoxStream<'static, Result<RecordBatch, ParquetError>>, DeltaTableError> {
780 use datafusion::functions::core::expr_ext::FieldAccessor;
781 use datafusion::logical_expr::expr::ScalarFunction;
782 use datafusion::logical_expr::{Expr, ScalarUDF, ident};
783
784 let provider = scan_factory.provider_for(files.iter().cloned())?;
785 let df = context.ctx.read_table(Arc::new(provider))?;
786
787 let cols = context
788 .columns
789 .iter()
790 .map(|col_name| {
791 let mut segments = col_name.split('.');
792 let first = segments.next().expect("column name cannot be empty");
793 let mut expr = ident(first);
794 for segment in segments {
795 expr = expr.field(segment);
796 }
797 expr
798 })
799 .collect_vec();
800 let expr = Expr::ScalarFunction(ScalarFunction::new_udf(
801 Arc::new(ScalarUDF::from(zorder::datafusion::ZOrderUDF)),
802 cols,
803 ));
804 let df = df.sort(vec![expr.sort(true, true)])?;
805
806 let stream = df
807 .execute_stream()
808 .await?
809 .map_err(|err| {
810 ParquetError::General(format!("Z-order failed while scanning data: {err}"))
811 })
812 .boxed();
813
814 Ok(stream)
815 }
816
817 #[allow(clippy::too_many_arguments)]
819 #[instrument(skip_all, fields(operation = "optimize", version = snapshot.version()))]
820 pub async fn execute(
821 mut self,
822 log_store: LogStoreRef,
823 snapshot: &EagerSnapshot,
824 max_concurrent_tasks: usize,
825 min_commit_interval: Option<Duration>,
826 commit_properties: CommitProperties,
827 operation_id: Uuid,
828 handle: Option<&Arc<dyn CustomExecuteHandler>>,
829 ) -> Result<Metrics, DeltaTableError> {
830 let operations = std::mem::take(&mut self.operations);
831 let read_session = self.read_session.clone();
832 info!("starting optimize execution");
833 let object_store = log_store.object_store(Some(operation_id));
834 update_datafusion_session(
835 read_session.as_ref(),
836 log_store.as_ref(),
837 Some(operation_id),
838 )?;
839
840 let mut stream = match operations {
841 OptimizeOperations::Compact(bins) => {
842 let read_context = Arc::new(SessionContext::new_with_state(
843 read_session.as_ref().clone(),
844 ));
845 let scan_factory = SelectedFileScanFactory::new(
846 snapshot,
847 log_store.clone(),
848 self.scan_config.clone(),
849 Some(operation_id),
850 );
851 let task_parameters = self.task_parameters.clone();
852
853 futures::stream::iter(bins)
854 .flat_map(|(_, (partition, bins))| {
855 futures::stream::iter(bins).map(move |bin| (partition.clone(), bin))
856 })
857 .map(move |(partition, files)| {
858 debug!(
859 "merging a group of {} files in partition {partition:?}",
860 files.len(),
861 );
862 for file in files.iter() {
863 debug!(" file {}", file.path);
864 }
865
866 let batch_stream = Self::read_selected_files(
867 files.clone(),
868 read_context.clone(),
869 scan_factory.clone(),
870 );
871
872 let rewrite_result = tokio::task::spawn(Self::rewrite_files(
873 task_parameters.clone(),
874 partition,
875 files,
876 object_store.clone(),
877 batch_stream,
878 true,
879 ));
880 util::flatten_join_error(rewrite_result)
881 })
882 .buffered(max_concurrent_tasks)
883 .boxed()
884 }
885 OptimizeOperations::ZOrder(zorder_columns, bins) => {
886 debug!(
887 zorder_columns = ?zorder_columns,
888 num_partitions = bins.len(),
889 "starting zorder"
890 );
891
892 let exec_context = Arc::new(zorder::ZOrderExecContext::new(
893 zorder_columns,
894 read_session.as_ref().clone(),
895 object_store,
896 )?);
897 let task_parameters = self.task_parameters.clone();
898 let scan_factory = SelectedFileScanFactory::new(
899 snapshot,
900 log_store.clone(),
901 self.scan_config.clone(),
902 Some(operation_id),
903 );
904
905 let log_store = log_store.clone();
908 futures::stream::iter(bins)
909 .map(move |(_, (partition, files))| {
910 let batch_stream = Self::read_zorder(
911 files.clone(),
912 exec_context.clone(),
913 scan_factory.clone(),
914 );
915 let rewrite_result = tokio::task::spawn(Self::rewrite_files(
916 task_parameters.clone(),
917 partition,
918 files,
919 log_store.object_store(Some(operation_id)),
920 batch_stream,
921 false,
922 ));
923 util::flatten_join_error(rewrite_result)
924 })
925 .buffer_unordered(max_concurrent_tasks)
926 .boxed()
927 }
928 };
929
930 let mut table =
931 DeltaTable::new_with_state(log_store.clone(), DeltaTableState::new(snapshot.clone()));
932
933 let mut actions = vec![];
936
937 let mut orig_metrics = std::mem::take(&mut self.metrics);
939 orig_metrics.apply_planner_stats(&self.planner_stats);
940 let mut buffered_metrics = orig_metrics.clone();
941 let mut total_metrics = orig_metrics.clone();
942
943 let mut last_commit = Instant::now();
944 let mut commits_made = 0;
945 let mut snapshot = snapshot.clone();
946 loop {
947 let next = stream.next().await.transpose()?;
948
949 let end = next.is_none();
950
951 if let Some((partial_actions, partial_metrics)) = next {
952 debug!("Recording metrics for a completed partition");
953 actions.extend(partial_actions);
954 buffered_metrics.add(&partial_metrics);
955 total_metrics.add(&partial_metrics);
956 }
957
958 let now = Instant::now();
959 let mature = match min_commit_interval {
960 None => false,
961 Some(i) => now.duration_since(last_commit) > i,
962 };
963 if !actions.is_empty() && (mature || end) {
964 let actions = std::mem::take(&mut actions);
965 last_commit = now;
966
967 let mut properties = CommitProperties::default();
968 properties.app_metadata = commit_properties.app_metadata.clone();
969 properties
970 .app_metadata
971 .insert("readVersion".to_owned(), self.read_table_version.into());
972 let maybe_map_metrics = serde_json::to_value(std::mem::replace(
973 &mut buffered_metrics,
974 orig_metrics.clone(),
975 ));
976 if let Ok(map) = maybe_map_metrics {
977 properties
978 .app_metadata
979 .insert("operationMetrics".to_owned(), map);
980 }
981
982 debug!("committing {} actions", actions.len());
983
984 let commit = CommitBuilder::from(properties)
985 .with_actions(actions)
986 .with_operation_id(operation_id)
987 .with_post_commit_hook_handler(handle.cloned())
988 .with_max_retries(DEFAULT_RETRIES + commits_made)
989 .build(
990 Some(&snapshot),
991 log_store.clone(),
992 self.task_parameters.input_parameters.clone().try_into()?,
993 )
994 .await?;
995 snapshot = commit.snapshot().snapshot;
996 commits_made += 1;
997 }
998
999 if end {
1000 break;
1001 }
1002 }
1003
1004 if total_metrics.num_files_added == 0 {
1005 total_metrics.files_added.min = 0;
1006 }
1007 if total_metrics.num_files_removed == 0 {
1008 total_metrics.files_removed.min = 0;
1009 }
1010
1011 table.state = Some(DeltaTableState::new(snapshot));
1012
1013 Ok(total_metrics)
1014 }
1015}
1016
1017#[instrument(skip_all, fields(operation = "create_merge_plan", version = snapshot.version()))]
1019pub async fn create_merge_plan(
1020 log_store: &dyn LogStore,
1021 optimize_type: OptimizeType,
1022 snapshot: &EagerSnapshot,
1023 filters: &[FilterLiteral<'_>],
1024 target_size: Option<NonZeroU64>,
1025 writer_properties: WriterProperties,
1026 session: SessionState,
1027) -> Result<MergePlan, DeltaTableError> {
1028 let target_size = target_size.unwrap_or_else(|| snapshot.table_properties().target_file_size());
1029 let _ = optimize_target_size_to_i64(target_size)?;
1030 let partitions_keys = snapshot.metadata().partition_columns();
1031
1032 let (operations, metrics, planner_stats) = match optimize_type {
1033 OptimizeType::Compact => {
1034 info!("building compaction plan");
1035 build_compaction_plan(log_store, snapshot, filters, target_size).await?
1036 }
1037 OptimizeType::ZOrder(zorder_columns) => {
1038 info!("building z-order plan");
1039 build_zorder_plan(
1040 log_store,
1041 zorder_columns,
1042 snapshot,
1043 partitions_keys,
1044 filters,
1045 )
1046 .await?
1047 }
1048 };
1049
1050 info!(
1051 partitions_optimized = metrics.partitions_optimized,
1052 total_considered_files = metrics.total_considered_files,
1053 "merge plan created"
1054 );
1055
1056 let rendered_filters: Vec<String> = filters.iter().map(literal_to_predicate_string).collect();
1059 let upload_budget = UploadBudget::for_write(Some(target_size));
1060 let input_parameters = OptimizeInput {
1061 target_size,
1062 predicate: serde_json::to_string(&rendered_filters).ok(),
1063 };
1064 let scan_config = DeltaScanConfig::new_from_session(&session);
1066 let file_schema = arrow_schema_without_partitions(
1067 &scan_config.table_schema(snapshot.table_configuration())?,
1068 partitions_keys,
1069 );
1070
1071 Ok(MergePlan {
1072 operations,
1073 metrics,
1074 planner_stats,
1075 task_parameters: Arc::new(MergeTaskParameters {
1076 file_schema,
1077 writer_properties,
1078 input_parameters,
1079 num_indexed_cols: snapshot.table_properties().num_indexed_cols(),
1080 stats_columns: snapshot
1081 .table_properties()
1082 .data_skipping_stats_columns
1083 .as_ref()
1084 .map(|v| v.iter().map(|v| v.to_string()).collect::<Vec<String>>()),
1085 upload_budget,
1086 }),
1087 read_table_version: snapshot.version(),
1088 read_session: Arc::new(session),
1089 scan_config,
1090 })
1091}
1092
1093#[derive(Debug, Clone)]
1095struct MergeBin {
1096 files: Vec<Add>,
1097 size_bytes: u64,
1098}
1099
1100impl MergeBin {
1101 pub fn new() -> Self {
1102 MergeBin {
1103 files: Vec::new(),
1104 size_bytes: 0,
1105 }
1106 }
1107
1108 fn total_file_size(&self) -> u64 {
1109 self.size_bytes
1110 }
1111
1112 fn is_empty(&self) -> bool {
1113 self.files.is_empty()
1114 }
1115
1116 fn len(&self) -> usize {
1117 self.files.len()
1118 }
1119
1120 fn from_file(add: Add) -> Self {
1121 let mut bin = Self::new();
1122 bin.add(add);
1123 bin
1124 }
1125
1126 fn add(&mut self, add: Add) {
1127 self.size_bytes += add.size as u64;
1128 self.files.push(add);
1129 }
1130
1131 fn iter(&self) -> impl Iterator<Item = &Add> {
1132 self.files.iter()
1133 }
1134}
1135
1136impl IntoIterator for MergeBin {
1137 type Item = Add;
1138 type IntoIter = std::vec::IntoIter<Self::Item>;
1139
1140 fn into_iter(self) -> Self::IntoIter {
1141 self.files.into_iter()
1142 }
1143}
1144
1145#[derive(Debug, Clone)]
1146struct OrderedFileCandidate {
1147 add: Add,
1148 stable_ordinal: usize,
1149 size_bytes: u64,
1150}
1151
1152fn plan_compaction_bins_in_stable_order(
1153 files: Vec<OrderedFileCandidate>,
1154 target_size: u64,
1155) -> (Vec<MergeBin>, PlannerStats) {
1156 let mut bins = Vec::new();
1157 let mut current = MergeBin::new();
1158 let mut current_first_ordinal = None;
1159 let mut current_last_ordinal = None;
1160 let mut planner_stats = PlannerStats::preserve_locality();
1161
1162 for file in files {
1163 if current.is_empty() {
1164 current = MergeBin::from_file(file.add);
1165 current_first_ordinal = Some(file.stable_ordinal);
1166 current_last_ordinal = Some(file.stable_ordinal);
1167 continue;
1168 }
1169
1170 let extends_contiguous_span = current_last_ordinal
1171 .map(|last| file.stable_ordinal == last + 1)
1172 .unwrap_or(false);
1173 if !extends_contiguous_span {
1174 if let (Some(first), Some(last)) = (current_first_ordinal, current_last_ordinal) {
1175 planner_stats.max_bin_span_files =
1176 planner_stats.max_bin_span_files.max(last - first + 1);
1177 }
1178
1179 bins.push(current);
1180 current = MergeBin::from_file(file.add);
1181 current_first_ordinal = Some(file.stable_ordinal);
1182 current_last_ordinal = Some(file.stable_ordinal);
1183 continue;
1184 }
1185
1186 if current.total_file_size() + file.size_bytes <= target_size {
1187 current.add(file.add);
1188 current_last_ordinal = Some(file.stable_ordinal);
1189 continue;
1190 }
1191
1192 if let (Some(first), Some(last)) = (current_first_ordinal, current_last_ordinal) {
1193 planner_stats.max_bin_span_files =
1194 planner_stats.max_bin_span_files.max(last - first + 1);
1195 }
1196
1197 bins.push(current);
1198 current = MergeBin::from_file(file.add);
1199 current_first_ordinal = Some(file.stable_ordinal);
1200 current_last_ordinal = Some(file.stable_ordinal);
1201 }
1202
1203 if !current.is_empty() {
1204 if let (Some(first), Some(last)) = (current_first_ordinal, current_last_ordinal) {
1205 planner_stats.max_bin_span_files =
1206 planner_stats.max_bin_span_files.max(last - first + 1);
1207 }
1208 bins.push(current);
1209 }
1210
1211 (bins, planner_stats)
1212}
1213
1214async fn build_compaction_plan(
1215 log_store: &dyn LogStore,
1216 snapshot: &EagerSnapshot,
1217 filters: &[FilterLiteral<'_>],
1218 target_size: NonZeroU64,
1219) -> Result<(OptimizeOperations, Metrics, PlannerStats), DeltaTableError> {
1220 type PartitionFileEntry = (IndexMap<String, Scalar>, usize, Vec<OrderedFileCandidate>);
1221
1222 let mut metrics = Metrics::default();
1223 let mut planner_stats = PlannerStats::preserve_locality();
1224 let mut partition_files: HashMap<String, PartitionFileEntry> = HashMap::new();
1225 let partition_columns = snapshot.metadata().partition_columns();
1226 let table_schema = snapshot.schema();
1227
1228 let predicate = if filters.is_empty() {
1229 None
1230 } else {
1231 Some(Arc::new(conjunction_to_kernel_predicate(
1232 filters,
1233 snapshot.schema().as_ref(),
1234 )?))
1235 };
1236
1237 let mut file_stream = snapshot.file_views(log_store, predicate);
1240 while let Some(file) = file_stream.next().await {
1241 let file = file?;
1242 metrics.total_considered_files += 1;
1243 let object_meta = ObjectMeta::try_from(&file)?;
1244 let partition_values =
1245 file.full_partition_values(partition_columns, table_schema.as_ref())?;
1246 let partition_path = partition_values.hive_partition_path();
1247 let entry = partition_files
1248 .entry(partition_path)
1249 .or_insert_with(|| (partition_values, 0, vec![]));
1250 let stable_ordinal = entry.1;
1251 entry.1 += 1;
1252
1253 if object_meta.size > target_size.get() {
1254 metrics.total_files_skipped += 1;
1255 continue;
1256 }
1257
1258 entry.2.push(OrderedFileCandidate {
1259 add: file.to_add(),
1260 stable_ordinal,
1261 size_bytes: object_meta.size,
1262 });
1263 }
1264
1265 let mut operations: HashMap<String, (IndexMap<String, Scalar>, Vec<MergeBin>)> = HashMap::new();
1266 for (part, (partition, _, files)) in partition_files {
1267 let (merge_bins, partition_stats) =
1268 plan_compaction_bins_in_stable_order(files, target_size.get());
1269 planner_stats.absorb(&partition_stats);
1270
1271 operations.insert(part, (partition, merge_bins));
1272 }
1273
1274 for (_, (_, bins)) in operations.iter_mut() {
1276 bins.retain(|bin| {
1277 if bin.len() == 1 {
1278 metrics.total_files_skipped += 1;
1279 false
1280 } else {
1281 true
1282 }
1283 });
1284 planner_stats.max_bin_span_files = planner_stats
1285 .max_bin_span_files
1286 .max(bins.iter().map(MergeBin::len).max().unwrap_or(0));
1287 }
1288 operations.retain(|_, (_, files)| !files.is_empty());
1289
1290 metrics.partitions_optimized = operations.len() as u64;
1291
1292 if operations.is_empty() {
1293 planner_stats.max_bin_span_files = 0;
1294 }
1295
1296 Ok((
1297 OptimizeOperations::Compact(operations),
1298 metrics,
1299 planner_stats,
1300 ))
1301}
1302
1303fn validate_zorder_column(schema: &StructType, column: &str) -> Result<(), DeltaTableError> {
1306 let mut segments = column.split('.').peekable();
1307 let mut current_struct = schema;
1308 while let Some(segment) = segments.next() {
1309 let field = current_struct.field(segment).ok_or_else(|| {
1310 DeltaTableError::Generic(format!(
1311 "Z-order column \"{column}\": field \"{segment}\" not found in schema"
1312 ))
1313 })?;
1314 if segments.peek().is_some() {
1315 match field.data_type() {
1316 DataType::Struct(inner) => current_struct = inner,
1317 _ => {
1318 return Err(DeltaTableError::Generic(format!(
1319 "Z-order column \"{column}\": \"{segment}\" is not a struct type"
1320 )));
1321 }
1322 }
1323 }
1324 }
1325 Ok(())
1326}
1327
1328async fn build_zorder_plan(
1329 log_store: &dyn LogStore,
1330 zorder_columns: Vec<String>,
1331 snapshot: &EagerSnapshot,
1332 partition_keys: &[String],
1333 filters: &[FilterLiteral<'_>],
1334) -> Result<(OptimizeOperations, Metrics, PlannerStats), DeltaTableError> {
1335 if zorder_columns.is_empty() {
1336 return Err(DeltaTableError::Generic(
1337 "Z-order requires at least one column".to_string(),
1338 ));
1339 }
1340 let zorder_partition_cols = zorder_columns
1341 .iter()
1342 .filter(|col| partition_keys.contains(col))
1343 .collect_vec();
1344 if !zorder_partition_cols.is_empty() {
1345 return Err(DeltaTableError::Generic(format!(
1346 "Z-order columns cannot be partition columns. Found: {zorder_partition_cols:?}"
1347 )));
1348 }
1349 for col in &zorder_columns {
1350 validate_zorder_column(snapshot.schema().as_ref(), col)?;
1351 }
1352
1353 let mut metrics = Metrics::default();
1355
1356 let mut partition_files: HashMap<String, (IndexMap<String, Scalar>, MergeBin)> = HashMap::new();
1357 let table_schema = snapshot.schema();
1358
1359 let predicate = if filters.is_empty() {
1360 None
1361 } else {
1362 Some(Arc::new(conjunction_to_kernel_predicate(
1363 filters,
1364 snapshot.schema().as_ref(),
1365 )?))
1366 };
1367
1368 let mut file_stream = snapshot.file_views(log_store, predicate);
1369 while let Some(file) = file_stream.next().await {
1370 let file = file?;
1371 let partition_values = file.full_partition_values(partition_keys, table_schema.as_ref())?;
1372 metrics.total_considered_files += 1;
1373 partition_files
1374 .entry(partition_values.hive_partition_path())
1375 .or_insert_with(|| (partition_values, MergeBin::new()))
1376 .1
1377 .add(file.to_add());
1378 debug!(
1379 num_partitions = partition_files.len(),
1380 "built zorder partition plan"
1381 );
1382 }
1383 metrics.partitions_optimized = partition_files.len() as u64;
1384
1385 let max_bin_span_files = partition_files
1386 .values()
1387 .map(|(_, bin)| bin.len())
1388 .max()
1389 .unwrap_or(0);
1390 let operation = OptimizeOperations::ZOrder(zorder_columns, partition_files);
1391 Ok((
1392 operation,
1393 metrics,
1394 PlannerStats::z_order(max_bin_span_files),
1395 ))
1396}
1397
1398#[cfg(test)]
1399mod compact_planner_tests {
1400 use super::*;
1401 use std::collections::HashMap;
1402
1403 fn candidate(stable_ordinal: usize, size_bytes: u64) -> OrderedFileCandidate {
1404 OrderedFileCandidate {
1405 add: Add {
1406 path: format!("part-{stable_ordinal}.parquet"),
1407 partition_values: HashMap::new(),
1408 size: size_bytes as i64,
1409 modification_time: stable_ordinal as i64,
1410 data_change: false,
1411 stats: None,
1412 tags: None,
1413 deletion_vector: None,
1414 base_row_id: None,
1415 default_row_commit_version: None,
1416 clustering_provider: None,
1417 },
1418 stable_ordinal,
1419 size_bytes,
1420 }
1421 }
1422
1423 fn ordinals(bin: &MergeBin) -> Vec<usize> {
1424 bin.iter()
1425 .map(|add| add.modification_time as usize)
1426 .collect::<Vec<_>>()
1427 }
1428
1429 #[test]
1430 fn test_ordered_compact_bins_are_contiguous() {
1431 let (bins, stats) = plan_compaction_bins_in_stable_order(
1432 vec![
1433 candidate(0, 6),
1434 candidate(1, 3),
1435 candidate(2, 6),
1436 candidate(3, 3),
1437 ],
1438 10,
1439 );
1440
1441 let planned_ordinals = bins.iter().map(ordinals).collect::<Vec<_>>();
1442
1443 assert_eq!(planned_ordinals, vec![vec![0, 1], vec![2, 3]]);
1444 assert_eq!(stats.max_bin_span_files, 2);
1445 }
1446
1447 #[test]
1448 fn test_ordered_compact_bins_do_not_merge_non_adjacent_files() {
1449 let (bins, _) = plan_compaction_bins_in_stable_order(
1450 vec![
1451 candidate(0, 8),
1452 candidate(1, 8),
1453 candidate(2, 2),
1454 candidate(3, 2),
1455 ],
1456 10,
1457 );
1458
1459 let planned_ordinals = bins.iter().map(ordinals).collect::<Vec<_>>();
1460
1461 assert_eq!(planned_ordinals, vec![vec![0], vec![1, 2], vec![3]]);
1462 assert!(
1463 planned_ordinals
1464 .iter()
1465 .all(|bin| { bin.windows(2).all(|window| window[1] == window[0] + 1) })
1466 );
1467 }
1468
1469 #[test]
1470 fn test_ordered_compact_bins_respect_ordinal_gaps() {
1471 let (bins, stats) =
1472 plan_compaction_bins_in_stable_order(vec![candidate(0, 3), candidate(2, 3)], 10);
1473
1474 let planned_ordinals = bins.iter().map(ordinals).collect::<Vec<_>>();
1475
1476 assert_eq!(planned_ordinals, vec![vec![0], vec![2]]);
1477 assert_eq!(stats.max_bin_span_files, 1);
1478 }
1479
1480 #[test]
1481 fn test_ordered_compact_bins_track_span_and_displacement() {
1482 let (_, stats) = plan_compaction_bins_in_stable_order(
1483 vec![
1484 candidate(0, 3),
1485 candidate(1, 3),
1486 candidate(2, 3),
1487 candidate(3, 9),
1488 ],
1489 10,
1490 );
1491
1492 assert_eq!(stats.planner_strategy, PlannerStrategy::PreserveLocality);
1493 assert!(stats.preserved_stable_order);
1494 assert_eq!(stats.max_bin_span_files, 3);
1495 }
1496
1497 #[test]
1498 fn test_optimize_input_target_size_must_fit_i64() {
1499 let input = OptimizeInput {
1500 target_size: std::num::NonZeroU64::new(i64::MAX as u64 + 1).unwrap(),
1501 predicate: None,
1502 };
1503
1504 let err = crate::protocol::DeltaOperation::try_from(input).unwrap_err();
1505 assert!(err.to_string().contains("optimize target_size"));
1506 assert!(err.to_string().contains("i64::MAX"));
1507 }
1508}
1509
1510pub(super) mod util {
1511 use super::*;
1512 use futures::Future;
1513 use tokio::task::JoinError;
1514
1515 pub async fn flatten_join_error<T, E>(
1516 future: impl Future<Output = Result<Result<T, E>, JoinError>>,
1517 ) -> Result<T, DeltaTableError>
1518 where
1519 E: Into<DeltaTableError>,
1520 {
1521 match future.await {
1522 Ok(Ok(result)) => Ok(result),
1523 Ok(Err(error)) => Err(error.into()),
1524 Err(error) => Err(DeltaTableError::GenericError {
1525 source: Box::new(error),
1526 }),
1527 }
1528 }
1529}
1530
1531pub(super) mod zorder {
1533 use super::*;
1534
1535 use arrow::buffer::{Buffer, OffsetBuffer, ScalarBuffer};
1536 use arrow_array::{Array, ArrayRef, BinaryArray};
1537 use arrow_buffer::bit_iterator::BitIndexIterator;
1538 use arrow_buffer::bit_util::set_bit_raw;
1539 use arrow_row::{RowConverter, SortField};
1540 use arrow_schema::ArrowError;
1541 pub use self::datafusion::ZOrderExecContext;
1544
1545 pub(super) mod datafusion {
1546 use super::*;
1547 use url::Url;
1548
1549 use ::datafusion::common::DataFusionError;
1550 use ::datafusion::logical_expr::{
1551 ColumnarValue, ScalarFunctionArgs, ScalarUDF, ScalarUDFImpl, Signature, TypeSignature,
1552 Volatility,
1553 };
1554 use ::datafusion::prelude::SessionContext;
1555 use arrow_schema::DataType;
1556 use itertools::Itertools;
1557
1558 pub const ZORDER_UDF_NAME: &str = "zorder_key";
1559
1560 pub struct ZOrderExecContext {
1561 pub columns: Arc<[String]>,
1562 pub ctx: SessionContext,
1563 }
1564
1565 impl ZOrderExecContext {
1566 pub fn new(
1567 columns: Vec<String>,
1568 session: SessionState,
1569 object_store_ref: ObjectStoreRef,
1570 ) -> Result<Self, DataFusionError> {
1571 let columns = columns.into();
1572
1573 let ctx = SessionContext::new_with_state(session);
1574 ctx.register_udf(ScalarUDF::from(datafusion::ZOrderUDF));
1575 ctx.register_object_store(&Url::parse("delta-rs://").unwrap(), object_store_ref);
1576 Ok(Self { columns, ctx })
1577 }
1578 }
1579
1580 #[derive(Debug, Hash, PartialEq, Eq)]
1582 pub struct ZOrderUDF;
1583
1584 impl ScalarUDFImpl for ZOrderUDF {
1585 fn name(&self) -> &str {
1586 ZORDER_UDF_NAME
1587 }
1588
1589 fn signature(&self) -> &Signature {
1590 static SIGNATURE: std::sync::LazyLock<Signature> =
1591 std::sync::LazyLock::new(|| Signature {
1592 type_signature: TypeSignature::VariadicAny,
1593 volatility: Volatility::Immutable,
1594 parameter_names: Some(vec![]),
1595 });
1596 &SIGNATURE
1597 }
1598
1599 fn return_type(&self, _arg_types: &[DataType]) -> Result<DataType, DataFusionError> {
1600 Ok(DataType::Binary)
1601 }
1602
1603 fn invoke_with_args(
1604 &self,
1605 args: ScalarFunctionArgs,
1606 ) -> ::datafusion::common::Result<ColumnarValue> {
1607 zorder_key_datafusion(&args.args)
1608 }
1609 }
1610
1611 fn zorder_key_datafusion(
1613 columns: &[ColumnarValue],
1614 ) -> Result<ColumnarValue, DataFusionError> {
1615 debug!(num_columns = columns.len(), "zorder_key_datafusion invoked");
1616 let length = columns
1617 .iter()
1618 .map(|col| match col {
1619 ColumnarValue::Array(array) => array.len(),
1620 ColumnarValue::Scalar(_) => 1,
1621 })
1622 .max()
1623 .ok_or(DataFusionError::NotImplemented(
1624 "z-order on zero columns.".to_string(),
1625 ))?;
1626 let columns: Vec<ArrayRef> = columns
1627 .iter()
1628 .map(|col| col.clone().into_array(length))
1629 .try_collect()?;
1630 let array = zorder_key(&columns)?;
1631 Ok(ColumnarValue::Array(array))
1632 }
1633
1634 #[cfg(test)]
1635 mod tests {
1636 use super::*;
1637 use ::datafusion::assert_batches_eq;
1638 use arrow_array::{Int32Array, StringArray};
1639 use arrow_ord::sort::sort_to_indices;
1640 use arrow_schema::Field;
1641 use arrow_select::take::take;
1642 use rand::RngExt;
1643
1644 #[test]
1645 fn test_order() {
1646 let int: ArrayRef = Arc::new(Int32Array::from(vec![1, 2, 3, 4, 5]));
1647 let str: ArrayRef = Arc::new(StringArray::from(vec![
1648 Some("a"),
1649 Some("x"),
1650 Some("a"),
1651 Some("x"),
1652 None,
1653 ]));
1654 let int_large: ArrayRef = Arc::new(Int32Array::from(vec![10000, 2000, 300, 40, 5]));
1655 let batch = RecordBatch::try_from_iter(vec![
1656 ("int", int),
1657 ("str", str),
1658 ("int_large", int_large),
1659 ])
1660 .unwrap();
1661
1662 let expected_1 = vec![
1663 "+-----+-----+-----------+",
1664 "| int | str | int_large |",
1665 "+-----+-----+-----------+",
1666 "| 1 | a | 10000 |",
1667 "| 2 | x | 2000 |",
1668 "| 3 | a | 300 |",
1669 "| 4 | x | 40 |",
1670 "| 5 | | 5 |",
1671 "+-----+-----+-----------+",
1672 ];
1673 let expected_2 = vec![
1674 "+-----+-----+-----------+",
1675 "| int | str | int_large |",
1676 "+-----+-----+-----------+",
1677 "| 5 | | 5 |",
1678 "| 1 | a | 10000 |",
1679 "| 3 | a | 300 |",
1680 "| 2 | x | 2000 |",
1681 "| 4 | x | 40 |",
1682 "+-----+-----+-----------+",
1683 ];
1684 let expected_3 = vec![
1685 "+-----+-----+-----------+",
1686 "| int | str | int_large |",
1687 "+-----+-----+-----------+",
1688 "| 5 | | 5 |",
1689 "| 4 | x | 40 |",
1690 "| 2 | x | 2000 |",
1691 "| 3 | a | 300 |",
1692 "| 1 | a | 10000 |",
1693 "+-----+-----+-----------+",
1694 ];
1695
1696 let expected = [expected_1, expected_2, expected_3];
1697
1698 let indices = Int32Array::from(shuffled_indices().to_vec());
1699 let shuffled_columns = batch
1700 .columns()
1701 .iter()
1702 .map(|c| take(c, &indices, None).unwrap())
1703 .collect::<Vec<_>>();
1704 let shuffled_batch =
1705 RecordBatch::try_new(batch.schema(), shuffled_columns).unwrap();
1706
1707 for i in 1..=batch.num_columns() {
1708 let columns = (0..i)
1709 .map(|idx| shuffled_batch.column(idx).clone())
1710 .collect::<Vec<_>>();
1711
1712 let order_keys = zorder_key(&columns).unwrap();
1713 let indices = sort_to_indices(order_keys.as_ref(), None, None).unwrap();
1714 let sorted_columns = shuffled_batch
1715 .columns()
1716 .iter()
1717 .map(|c| take(c, &indices, None).unwrap())
1718 .collect::<Vec<_>>();
1719 let sorted_batch =
1720 RecordBatch::try_new(batch.schema(), sorted_columns).unwrap();
1721
1722 assert_batches_eq!(expected[i - 1], &[sorted_batch]);
1723 }
1724 }
1725 fn shuffled_indices() -> [i32; 5] {
1726 let mut rng = rand::rng();
1727 let mut array = [0, 1, 2, 3, 4];
1728 for i in (1..array.len()).rev() {
1729 let j = rng.random_range(0..=i);
1730 array.swap(i, j);
1731 }
1732 array
1733 }
1734
1735 #[tokio::test]
1736 async fn test_zorder_mixed_case() {
1737 use arrow_schema::Schema as ArrowSchema;
1738 let schema = Arc::new(ArrowSchema::new(vec![
1739 Field::new("moDified", DataType::Utf8, true),
1740 Field::new("ID", DataType::Utf8, true),
1741 Field::new("vaLue", DataType::Int32, true),
1742 ]));
1743
1744 let batch = RecordBatch::try_new(
1745 schema.clone(),
1746 vec![
1747 Arc::new(arrow::array::StringArray::from(vec![
1748 "2021-02-01",
1749 "2021-02-01",
1750 "2021-02-02",
1751 "2021-02-02",
1752 ])),
1753 Arc::new(arrow::array::StringArray::from(vec!["A", "B", "C", "D"])),
1754 Arc::new(arrow::array::Int32Array::from(vec![1, 10, 20, 100])),
1755 ],
1756 )
1757 .unwrap();
1758 let table = crate::DeltaTable::new_in_memory()
1760 .write(vec![batch.clone()])
1761 .with_save_mode(crate::protocol::SaveMode::Append)
1762 .await
1763 .unwrap();
1764
1765 let res = table
1766 .optimize()
1767 .with_type(OptimizeType::ZOrder(vec!["moDified".into()]))
1768 .await;
1769 assert!(res.is_ok());
1770 }
1771
1772 #[tokio::test]
1774 async fn test_zorder_space_in_partition_value() {
1775 use arrow_schema::Schema as ArrowSchema;
1776 let _ = pretty_env_logger::try_init();
1777 let schema = Arc::new(ArrowSchema::new(vec![
1778 Field::new("modified", DataType::Utf8, true),
1779 Field::new("country", DataType::Utf8, true),
1780 Field::new("value", DataType::Int32, true),
1781 ]));
1782
1783 let batch = RecordBatch::try_new(
1784 schema.clone(),
1785 vec![
1786 Arc::new(arrow::array::StringArray::from(vec![
1787 "2021-02-01",
1788 "2021-02-01",
1789 "2021-02-02",
1790 "2021-02-02",
1791 ])),
1792 Arc::new(arrow::array::StringArray::from(vec![
1793 "Germany",
1794 "China",
1795 "Canada",
1796 "Dominican Republic",
1797 ])),
1798 Arc::new(arrow::array::Int32Array::from(vec![1, 10, 20, 100])),
1799 ],
1802 )
1803 .unwrap();
1804 let table = DeltaTable::new_in_memory()
1806 .write(vec![batch.clone()])
1807 .with_partition_columns(vec!["country"])
1808 .with_save_mode(crate::protocol::SaveMode::Overwrite)
1809 .await
1810 .unwrap();
1811
1812 let res = table
1813 .optimize()
1814 .with_type(OptimizeType::ZOrder(vec!["modified".into()]))
1815 .await;
1816 assert!(res.is_ok(), "Failed to optimize: {res:#?}");
1817 }
1818
1819 #[tokio::test]
1820 async fn test_zorder_space_in_partition_value_garbage() {
1821 use arrow_schema::Schema as ArrowSchema;
1822 let _ = pretty_env_logger::try_init();
1823 let schema = Arc::new(ArrowSchema::new(vec![
1824 Field::new("modified", DataType::Utf8, true),
1825 Field::new("country", DataType::Utf8, true),
1826 Field::new("value", DataType::Int32, true),
1827 ]));
1828
1829 let batch = RecordBatch::try_new(
1830 schema.clone(),
1831 vec![
1832 Arc::new(arrow::array::StringArray::from(vec![
1833 "2021-02-01",
1834 "2021-02-01",
1835 "2021-02-02",
1836 "2021-02-02",
1837 ])),
1838 Arc::new(arrow::array::StringArray::from(vec![
1839 "Germany", "China", "Canada", "USA$$!",
1840 ])),
1841 Arc::new(arrow::array::Int32Array::from(vec![1, 10, 20, 100])),
1842 ],
1843 )
1844 .unwrap();
1845 let table = DeltaTable::new_in_memory()
1847 .write(vec![batch.clone()])
1848 .with_partition_columns(vec!["country"])
1849 .with_save_mode(crate::protocol::SaveMode::Overwrite)
1850 .await
1851 .unwrap();
1852
1853 let res = table
1854 .optimize()
1855 .with_type(OptimizeType::ZOrder(vec!["modified".into()]))
1856 .await;
1857 assert!(res.is_ok(), "Failed to optimize: {res:#?}");
1858 }
1859 }
1860 }
1861
1862 pub fn zorder_key(columns: &[ArrayRef]) -> Result<ArrayRef, ArrowError> {
1868 if columns.is_empty() {
1869 return Err(ArrowError::InvalidArgumentError(
1870 "Cannot zorder empty columns".to_string(),
1871 ));
1872 }
1873
1874 let out_length = columns[0].len();
1876
1877 if columns.iter().any(|col| col.len() != out_length) {
1878 return Err(ArrowError::InvalidArgumentError(
1879 "All columns must have the same length".to_string(),
1880 ));
1881 }
1882
1883 let value_size: usize = columns.len() * 16;
1885
1886 let mut out: Vec<u8> = vec![0; out_length * value_size];
1888
1889 for (col_pos, col) in columns.iter().enumerate() {
1890 set_bits_for_column(col.clone(), col_pos, columns.len(), &mut out)?;
1891 }
1892
1893 let offsets = (0..=out_length)
1894 .map(|i| (i * value_size) as i32)
1895 .collect::<Vec<i32>>();
1896
1897 let out_arr = BinaryArray::try_new(
1898 OffsetBuffer::new(ScalarBuffer::from(offsets)),
1899 Buffer::from_vec(out),
1900 None,
1901 )?;
1902
1903 Ok(Arc::new(out_arr))
1904 }
1905
1906 fn set_bits_for_column(
1916 input: ArrayRef,
1917 col_pos: usize,
1918 num_columns: usize,
1919 out: &mut Vec<u8>,
1920 ) -> Result<(), ArrowError> {
1921 let converter = RowConverter::new(vec![SortField::new(input.data_type().clone())])?;
1923 let rows = converter.convert_columns(&[input])?;
1924
1925 for (row_i, row) in rows.iter().enumerate() {
1926 let row_offset = row_i * num_columns * 16;
1928 let bytes = row.as_ref();
1929 let prefix_bits = bytes.len().min(16) * 8;
1930 for bit_i in BitIndexIterator::new(bytes, 0, prefix_bits) {
1931 let bit_pos = (bit_i * num_columns) + col_pos;
1936 let out_pos = (row_offset * 8) + bit_pos;
1937 unsafe { set_bit_raw(out.as_mut_ptr(), out_pos) };
1939 }
1940 }
1941
1942 Ok(())
1943 }
1944
1945 #[cfg(test)]
1946 mod test {
1947 use arrow_array::{
1948 StringArray, UInt8Array, cast::as_generic_binary_array, new_empty_array,
1949 };
1950 use arrow_schema::DataType;
1951
1952 use super::*;
1953 use crate::ensure_table_uri;
1954
1955 #[test]
1956 fn test_rejects_no_columns() {
1957 let columns = vec![];
1958 let result = zorder_key(&columns);
1959 assert!(result.is_err());
1960 }
1961
1962 #[test]
1963 fn test_handles_no_rows() {
1964 let columns: Vec<ArrayRef> = vec![
1965 Arc::new(new_empty_array(&DataType::Int64)),
1966 Arc::new(new_empty_array(&DataType::Utf8)),
1967 ];
1968 let result = zorder_key(columns.as_slice());
1969 assert!(result.is_ok());
1970 let result = result.unwrap();
1971 assert_eq!(result.len(), 0);
1972 }
1973
1974 #[test]
1975 fn test_basics() {
1976 let columns: Vec<ArrayRef> = vec![
1977 Arc::new(StringArray::from(vec![Some("a"), Some("b"), None])),
1979 Arc::new(StringArray::from(vec![
1981 "delta-rs: A native Rust library for Delta Lake, with bindings into Python",
1982 "cat",
1983 "",
1984 ])),
1985 Arc::new(UInt8Array::from(vec![Some(1), Some(4), None])),
1986 ];
1987 let result = zorder_key(columns.as_slice()).unwrap();
1988 assert_eq!(result.len(), 3);
1989 assert_eq!(result.data_type(), &DataType::Binary);
1990 assert_eq!(result.null_count(), 0);
1991
1992 let data: &BinaryArray = as_generic_binary_array(result.as_ref());
1993 assert_eq!(data.value_data().len(), 3 * 16 * 3);
1994 assert!(data.iter().all(|x| x.unwrap().len() == 3 * 16));
1995 assert_eq!(
1997 data.value_data(),
1998 &[
1999 28, 0, 0, 133, 128, 13, 130, 0, 9, 128, 4, 9, 128, 32, 9, 2, 0, 9, 130, 4, 1,
2000 16, 32, 9, 18, 32, 9, 147, 36, 73, 16, 36, 1, 0, 0, 1, 2, 0, 8, 0, 0, 1, 144,
2001 4, 9, 2, 0, 9, 28, 0, 0, 26, 129, 13, 2, 0, 9, 128, 32, 9, 0, 0, 0, 0, 0, 0, 0,
2002 0, 0, 0, 0, 0, 0, 0, 0, 19, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2003 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2004 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
2005 ]
2006 );
2007 }
2008
2009 #[tokio::test]
2010 async fn works_on_spark_table() {
2011 use tempfile::TempDir;
2012 let tmp_dir = TempDir::new().expect("Failed to make temp dir");
2014 let table_name = "delta-1.2.1-only-struct-stats";
2015
2016 let source_path = format!("../test/tests/data/{table_name}");
2018 fs_extra::dir::copy(source_path, tmp_dir.path(), &Default::default()).unwrap();
2019
2020 let table_uri =
2021 ensure_table_uri(tmp_dir.path().join(table_name).to_str().unwrap()).unwrap();
2022 let (_, metrics) = DeltaTable::try_from_url(table_uri)
2024 .await
2025 .unwrap()
2026 .optimize()
2027 .await
2028 .unwrap();
2029
2030 assert_eq!(metrics.num_files_added, 1);
2032 }
2033 }
2034}