`add_shape` is O(node population) for unindexed clauses: the whole `other_shapes` map is copied in and out of ETS per insert

Summary

WhereCondition.add_shape_to_other_shapes/5 reads a node's entire other_shapes map out of ETS, puts one key into it, and writes the whole map back:

defp add_shape_to_other_shapes(table, condition_id, shape_id, branch_key, where_clause) do
  [{_, {index_keys, other_shapes}}] = :ets.lookup(table, condition_id)
  other_shapes = Map.put(other_shapes, {shape_id, branch_key}, where_clause)
  :ets.insert(table, {condition_id, {index_keys, other_shapes}})
end

Each insert costs O(shapes already on that node), so building a set of m unindexed shapes on one node costs O(m²). remove_shape has the same cost.

Any shape whose where clause is not fully optimized lands here, so ordinary workloads reach this path.

Expected: adding a shape costs about the same regardless of how many shapes are already on the node.

Actual: per-shape cost grows linearly with the node's population.

Versions: Electric sync-service v1.7.8, also reproduced on main @ 917589195. Plain HTTP client; this is server-side filter behaviour and does not depend on the client.

Impact

Filter.add_shape/3 on v1.7.8, µs per shape, where n is the number of shapes accumulating on the same node. K is the size of an IN list in the clause, which sets the residual size.

Per-shape cost grows roughly linearly with n, so total build cost is quadratic. We could not build the n = 20,000 configurations within a 700s per-segment budget; those are reported as not built rather than extrapolated.

This also affects startup, since restoring shapes re-adds every shape to the filter and pays the same map-copy cost on each insert.

Suggested direction

Store other_shapes entries as individual ETS rows keyed by {condition_id, shape_id, branch_key} rather than as one map inside a single row. Insert and delete become O(1), and the linear scan at routing time becomes a bounded-prefix match/select over the same rows. This is the approach #4134 already used for the subquery index with :ordered_set.

We can open a PR if that direction is useful.

Related

#4742 reports the clause pattern that put large numbers of shapes on a single node in our case, an indexable IN/OR conjunct being dropped from the index when ANDed with a non-optimized condition. The two are independent, since this one applies to any other_shapes population however it arises, but they compound: #4742 causes shapes that should have been indexed to accumulate here instead.

Environment

• Electric sync-service v1.7.8, also verified on main @ 917589195.
• Elixir 1.20.2 / OTP 29.0.2.

Written with AI assistance and reviewed by a human before filing. The timings are measured rather than estimated, on one machine. We can share the benchmark harness if the numbers are hard to reproduce.