Skip to content

Commit 790d533

Browse files
committed
Compare upsert rows with PyArrow instead of Python
get_rows_to_update compared the matched rows one cell at a time, one PyArrow call per row and per column, so an upsert got slower with every column of the table. It compares one column at a time now: 20k matched rows over 200 columns takes about 0.15s instead of about 20s. PyArrow cannot compare struct columns, so a struct is compared field by field, recursing into the structs its fields hold. Lists and maps are still compared in Python, a slice at a time so the objects of a whole column are never held at once. When PyArrow refuses to compare two columns because their types differ, the source is cast to the type of the target. The full table cast this removes used to do that, and without it a naive timestamp and a zoned one holding the same instant are reported as different on every run. Closes apache#3860
1 parent 7539661 commit 790d533

2 files changed

Lines changed: 341 additions & 36 deletions

File tree

‎pyiceberg/table/upsert_util.py‎

Lines changed: 105 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -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+
56124
def 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

Comments
 (0)