_filter_labels_element rebuilds set(ids_to_keep) inside a comprehension: O(n_labels × n_keep) in right/inner joins with filter_label_pixels=True

[!NOTE]
This whole message is AI-generated. The issue was automatically discovered and reported by an AI agent (Claude) during an autonomous bug hunt on the spatialdata code base. It has not been verified or triaged by a human yet; the needs: triage label is set so that a maintainer can confirm it. The reproduction script below was executed by the agent in an isolated environment (see Environment) and its output is pasted verbatim.

Summary

set(ids_to_keep) is rebuilt for every label id. Measured (keep half of the ids): n=10k → 0.33 s, 20k → 0.82 s, 40k → 3.8 s, 80k → 12.9 s (quadratic; ~20 min extrapolated for 1 M labels) versus milliseconds for a set built once. Reached through join_spatialelement_table(how="right"|"inner", filter_label_pixels=True), match_sdata_to_table, filter_by_table_query.

Severity (agent's assessment): high for real data — minutes to hours of pure-Python work for 1e5–1e6 cells before any pixel work starts

Where: src/spatialdata/_core/query/relational_query.py::_filter_labels_element (ids_to_remove = [i for i in element_instances if i not in set(ids_to_keep)])

Expected behaviour

Linear time.

Reproduction

Save as repro.py and run uv run repro.py (the PEP 723 header pins spatialdata to the commit the bug was found on; replace the URL fragment with @main to test the current main branch).

# /// script
# requires-python = ">=3.12"
# dependencies = [
#     "spatialdata @ git+https://github.com/scverse/spatialdata.git@ccf1ea048d054b6624214bf618008a9f9ae223e0",
# ]
# ///
"""_filter_labels_element (used by right/inner joins with filter_label_pixels=True) is O(n_labels * n_keep)."""
import time
import warnings
import numpy as np
from spatialdata.models import Labels2DModel
from spatialdata._core.query.relational_query import _filter_labels_element

warnings.simplefilter("ignore")
timings = []
for n in [10_000, 20_000, 40_000]:
    labels = Labels2DModel.parse(np.arange(n, dtype=np.int32).reshape(-1, 100))
    ids_to_keep = list(range(0, n, 2))
    t0 = time.time()
    _filter_labels_element(labels, ids_to_keep)
    t_current = time.time() - t0
    t0 = time.time()
    keep = set(ids_to_keep)
    _ = [i for i in np.arange(n) if i not in keep]  # linear reference
    t_reference = time.time() - t0
    timings.append(t_current)
    print(f"n={n:6d} labels, keep half: current {t_current:6.2f}s   set-once reference {t_reference:6.3f}s")
ratio = timings[-1] / timings[0]
print(f"time ratio for 4x more labels: {ratio:.1f}x (quadratic would be ~16x, linear ~4x)")
print("VERDICT:", "BUG REPRODUCED (quadratic)" if ratio > 8 else "NOT REPRODUCED")

Observed output

n= 10000 labels, keep half: current   0.85s   set-once reference  0.000s
n= 20000 labels, keep half: current   1.18s   set-once reference  0.001s
n= 40000 labels, keep half: current   8.40s   set-once reference  0.002s
time ratio for 4x more labels: 9.9x (quadratic would be ~16x, linear ~4x)
VERDICT: BUG REPRODUCED (quadratic)

Possible fix direction (unverified)

ids_to_remove = np.setdiff1d(np.asarray(element_instances), np.asarray(ids_to_keep)). Bonus: _mask_block could use a boolean lookup table instead of np.isin per block, and for DataTree inputs the pyramid is recomputed from scale0 — filtering each scale independently would avoid the downsampling cost.

Environment

uv run repro.py with the PEP 723 metadata in the script (fresh, isolated environment; spatialdata built from main @ ccf1ea0 (2026-08-28); Python 3.13, latest releases of the dependencies at run time: pandas 3.0, anndata 0.13, zarr 3.3, dask 2026.8, numpy 2.5, geopandas 1.1, shapely 2.1). macOS (arm64). Also reproduced in a second environment with pandas 2.3.3 / anndata 0.12.11 / numpy 2.4.4 / zarr 3.2.1.

Automatically generated; discovered by an AI agent (Claude) and not yet reviewed by a human.

Read src/spatialdata/_core/query/relational_query.py at _filter_labels_element, then run the provided repro.py with uv to confirm the scaling on the affected join paths. Done means filtering avoids the demonstrated quadratic behavior while preserving the expected ids removed and the right/inner join behavior.