electric-sql / electric-sql/electric

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

Open
#4,743 1 comment 3 reactions 0 assignees View on GitHub
Dominant language
TypeScript
Stars
10.4k
Forks
375
Avg merge
3d 1h
Merged PRs (30d)
18

Description

## 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:

```elixir
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.

| K | n | add µs/shape |
| --- | --- | --- |
| 10 | 100 | 191 |
| 10 | 1,000 | 2,539 |
| 10 | 5,000 | 14,616 |
| 45 | 5,000 | 61,341 |
| 150 | 1,000 | 36,151 |

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 `AND`ed 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.*

Contributor guide

Open the contributing guide

Research direction

Start by tracing WhereCondition.add_shape_to_other_shapes/5 and remove_shape, then follow Filter.add_shape/3 to understand how ETS rows are inserted, removed, and scanned during routing and shape restoration. Compare the proposed individual ETS-row layout with the subquery index approach in #4134. Done means inserts and deletes no longer copy the full other_shapes map and retain correct routing behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
elixir
Domain
backend-api-design, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
52/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.