@@ -53,17 +53,93 @@ def has_duplicate_rows(df: pyarrow_table, join_cols: list[str]) -> bool:
5353 return len (df .select (join_cols ).group_by (join_cols ).aggregate ([([], "count_all" )]).filter (pc .field ("count_all" ) > 1 )) > 0
5454
5555
56+ # How many values of a column are turned into Python objects at a time, when PyArrow cannot
57+ # compare them itself
58+ _PYTHON_COMPARISON_SLICE = 10_000
59+
60+
61+ def _get_changed_struct_mask (source_column : pa .ChunkedArray , target_column : pa .ChunkedArray ) -> pa .ChunkedArray :
62+ """Compare two struct columns field by field, which PyArrow can do even though it cannot compare the structs."""
63+ # `struct_field` carries the null of the struct into its fields, so the fields of two null
64+ # structs compare equal and only the struct itself decides for those rows
65+ changed = pc .not_equal (pc .is_null (source_column ), pc .is_null (target_column ))
66+
67+ # By name, so that two structs holding the same fields in another order are compared field
68+ # against field rather than by position
69+ for field in source_column .type :
70+ changed = pc .or_ (
71+ changed ,
72+ _get_changed_mask (pc .struct_field (source_column , field .name ), pc .struct_field (target_column , field .name )),
73+ )
74+
75+ return changed
76+
77+
78+ def _get_changed_mask (source_column : pa .ChunkedArray , target_column : pa .ChunkedArray ) -> pa .ChunkedArray :
79+ """Return a boolean mask that flags the positions where the two columns differ, treating two nulls as equal."""
80+ try :
81+ differs = pc .not_equal (source_column , target_column )
82+ except (pa .ArrowNotImplementedError , pa .ArrowInvalid ):
83+ # PyArrow cannot compare columns with complex types
84+ # See: https://github.com/apache/arrow/issues/35785
85+ if pa .types .is_struct (source_column .type ) and source_column .type == target_column .type :
86+ return _get_changed_struct_mask (source_column , target_column )
87+
88+ # Two columns PyArrow refuses to compare may still hold the same values in another type:
89+ # a naive timestamp against a zoned one, or the string of a dataframe against the
90+ # large_string a scan reads. Comparing those in Python would call every row changed, on
91+ # every run, and would leave a struct out of the comparison by field above. The types have
92+ # to differ for this to make progress, the cast leaves them equal and the next round
93+ # settles it one way or the other
94+ if source_column .type != target_column .type :
95+ try :
96+ return _get_changed_mask (source_column .cast (target_column .type ), target_column )
97+ except pa .ArrowException :
98+ # Whatever PyArrow makes of the cast, the comparison in Python below still holds
99+ pass
100+
101+ # A list or a map is left to be compared in Python, value by value. A slice at a time,
102+ # so that the objects of a whole column are never held at once
103+ return pa .chunked_array (
104+ [
105+ [
106+ source_val != target_val
107+ for source_val , target_val in zip (
108+ source_column .slice (offset , _PYTHON_COMPARISON_SLICE ).to_pylist (),
109+ target_column .slice (offset , _PYTHON_COMPARISON_SLICE ).to_pylist (),
110+ strict = True ,
111+ )
112+ ]
113+ for offset in range (0 , len (source_column ), _PYTHON_COMPARISON_SLICE )
114+ ]
115+ or [[]],
116+ type = pa .bool_ (),
117+ )
118+
119+ # `not_equal` is null as soon as either side is null, and a null differs from a value
120+ # but not from another null
121+ return pc .fill_null (differs , pc .not_equal (pc .is_null (source_column ), pc .is_null (target_column )))
122+
123+
56124def get_rows_to_update (source_table : pa .Table , target_table : pa .Table , join_cols : list [str ]) -> pa .Table :
57125 """
58126 Return a table with rows that need to be updated in the target table based on the join columns.
59127
60128 The table is joined on the identifier columns, and then checked if there are any updated rows.
61129 Those are selected and everything is renamed correctly.
62130 """
63- all_columns = set (source_table .column_names )
64- join_cols_set = set (join_cols )
131+ source_columns , target_columns = set (source_table .column_names ), set (target_table .column_names )
132+ if source_columns != target_columns :
133+ raise ValueError (
134+ f"Source table's field names are not matching the target's field names, "
135+ f"missing: { sorted (target_columns - source_columns )} , "
136+ f"unexpected: { sorted (source_columns - target_columns )} "
137+ )
65138
66- non_key_cols = list (all_columns - join_cols_set )
139+ # Kept in the order of the source rather than taken from a set difference, whose order
140+ # varies from one process to the next
141+ join_cols_set = set (join_cols )
142+ non_key_cols = [col for col in source_table .column_names if col not in join_cols_set ]
67143
68144 if has_duplicate_rows (target_table , join_cols ):
69145 raise ValueError ("Target table has duplicate rows, aborting upsert" )
@@ -72,10 +148,6 @@ def get_rows_to_update(source_table: pa.Table, target_table: pa.Table, join_cols
72148 # When the target table is empty, there is nothing to update :)
73149 return source_table .schema .empty_table ()
74150
75- # We need to compare non_key_cols in Python as PyArrow
76- # 1. Cannot do a join when non-join columns have complex types
77- # 2. Cannot compare columns with complex types
78- # See: https://github.com/apache/arrow/issues/35785
79151 SOURCE_INDEX_COLUMN_NAME = "__source_index"
80152 TARGET_INDEX_COLUMN_NAME = "__target_index"
81153
@@ -86,39 +158,38 @@ def get_rows_to_update(source_table: pa.Table, target_table: pa.Table, join_cols
86158 ) from None
87159
88160 # Step 1: Prepare source index with join keys and a marker index
89- # Cast to target table schema , so we can do the join
161+ # Only the join columns are cast , so the width of the table does not weigh on the join
90162 # See: https://github.com/apache/arrow/issues/37542
91163 source_index = (
92- source_table .cast ( target_table . schema )
93- .select (join_cols_set )
164+ source_table .select ( join_cols )
165+ .cast ( target_table . select (join_cols ). schema )
94166 .append_column (SOURCE_INDEX_COLUMN_NAME , pa .array (range (len (source_table ))))
95167 )
96168
97169 # Step 2: Prepare target index with join keys and a marker
98- target_index = target_table .select (join_cols_set ).append_column (TARGET_INDEX_COLUMN_NAME , pa .array (range (len (target_table ))))
170+ target_index = target_table .select (join_cols ).append_column (TARGET_INDEX_COLUMN_NAME , pa .array (range (len (target_table ))))
99171
100172 # Step 3: Perform an inner join to find which rows from source exist in target
101- matching_indices = source_index .join (target_index , keys = list (join_cols_set ), join_type = "inner" )
102-
103- # Step 4: Compare all rows using Python
104- to_update_indices = []
105- for source_idx , target_idx in zip (
106- matching_indices [SOURCE_INDEX_COLUMN_NAME ].to_pylist (),
107- matching_indices [TARGET_INDEX_COLUMN_NAME ].to_pylist (),
108- strict = True ,
109- ):
110- source_row = source_table .slice (source_idx , 1 )
111- target_row = target_table .slice (target_idx , 1 )
112-
113- for key in non_key_cols :
114- source_val = source_row .column (key )[0 ].as_py ()
115- target_val = target_row .column (key )[0 ].as_py ()
116- if source_val != target_val :
117- to_update_indices .append (source_idx )
118- break
119-
120- # Step 5: Take rows from source table using the indices and cast to target schema
121- if to_update_indices :
122- return source_table .take (to_update_indices )
123- else :
173+ matching_indices = source_index .join (target_index , keys = join_cols , join_type = "inner" )
174+
175+ if len (matching_indices ) == 0 :
124176 return source_table .schema .empty_table ()
177+
178+ source_indices = matching_indices [SOURCE_INDEX_COLUMN_NAME ]
179+ target_indices = matching_indices [TARGET_INDEX_COLUMN_NAME ]
180+
181+ # Step 4: Compare the matched rows one column at a time. Comparing them cell by cell instead
182+ # would allocate a PyArrow scalar per cell, which does not fit in memory on a wide table.
183+ changed = pa .chunked_array ([pa .repeat (False , len (matching_indices ))])
184+ for col in non_key_cols :
185+ changed = pc .or_ (
186+ changed ,
187+ _get_changed_mask (source_table .column (col ).take (source_indices ), target_table .column (col ).take (target_indices )),
188+ )
189+ # Once every matched row has changed, the columns that are left cannot add anything, and
190+ # asking is far cheaper than taking and comparing them
191+ if pc .all (changed ).as_py ():
192+ break
193+
194+ # Step 5: Take rows from source table using the indices
195+ return source_table .take (source_indices .filter (changed ))
0 commit comments