electric-sql / electric-sql/electric

An indexable `IN`/`OR` conjunct is dropped from the filter index when `AND`ed with a non-optimized condition

Open
#4,742 0 comments 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

The shapes guide lists "Mixed optimized and non-optimized conditions with `AND`/`OR`" as an optimized where-clause pattern, and states that Electric maintains "a consistent throughput of ~5,000 row changes per second no matter how many shapes you have".

That combination is not optimized. When an `IN` list (or any `OR` tree) is `AND`ed with a condition
that is not itself a single indexable operation, the whole conjunction is dropped into `other_shapes` and evaluated per shape on every change. The indexable `IN` goes with it. Routing then costs O(shapes on that node) per change.

`"field" IN (...)` on its own indexes correctly. Adding any non-optimized conjunct removes it from the index, including a constant that folds to `TRUE`.

**Expected:** the `IN` list stays indexed, and the non-optimized conjunct is evaluated as a residual against the shapes the index selects.

**Actual:** the `IN` list is dropped from the index and the whole clause is evaluated against every shape on the node, for every change.

**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.

## Reproduction

Save as `packages/sync-service/repro_in_and.exs`, run with `MIX_ENV=test mix run --no-start repro_in_and.exs`:

```elixir
alias Electric.Shapes.Filter
alias Electric.Shapes.Shape
alias Support.StubInspector

inspector =
StubInspector.new(
tables: ["items"],
columns: [
%{name: "id", type: "text", pk_position: 0},
%{name: "tenant_id", type: "text"},
%{name: "category_id", type: "text"},
%{name: "deleted_at", type: "timestamptz"}
]
)

indexed? = fn where ->
Filter.indexed_shape?(Shape.new!("items", where: where, inspector: inspector))
end

IO.inspect(indexed?.(~s|"category_id" IN ('c1','c2','c3')|), label: "IN(3)")
IO.inspect(indexed?.(~s|"category_id" IN ('c1','c2','c3') AND TRUE|), label: "IN(3) AND TRUE")

IO.inspect(indexed?.(~s|"category_id" IN ('c1','c2','c3') AND "deleted_at" IS NULL|),
label: "IN(3) AND IS NULL"
)
```

Output on v1.7.8:

```
IN(3): true
IN(3) AND TRUE: false
IN(3) AND IS NULL: false
```

## Mechanism

```elixir
defp optimise_where(%Func{name: "and", args: [left, right]}) do
case {optimise_where(left), optimise_where(right)} do
{%{operation: _} = optimisation, _} -> # index left, residualise right
{_, %{operation: _} = optimisation} -> # index right, residualise left
_ -> :not_optimised
end
end
```

`optimise_where` on an `OR` returns an `{:or, left, right}` tuple, which matches neither `%{operation: _}` pattern. `AND(or_tree, non_indexable)` therefore falls through to `:not_optimised`, and `add_shape/5` sends the whole clause to `add_shape_to_other_shapes/5`.

An `and_where` residual is re-optimised inside a child `WhereCondition` node, so this does not have to happen at the top level. It happens at whichever node's residual has the form `AND(or_tree, non_indexable)`.

**Control:** `"tenant_id" = 't1' AND "category_id" IN ('c1'..'c5')` indexes at both levels, `tenant_id` at the root and the `IN` splitting per value in the child node. Hierarchical indexing works, and the `IN` would be indexed. The trigger is one non-optimized conjunct in the residual.

Adding a third conjunct to that working clause breaks it:

```sql
"tenant_id" = $1 AND "category_id" IN ($2..$n) AND "deleted_at" IS NULL
```

Every change matching `tenant_id` now evaluates the `IN` list of every shape on that node.

## Impact

`Filter.affected_shapes/2`, µs per change, v1.7.8. `K` is the `IN` list size, `n` the number of
shapes sharing the indexed parent value. Medians of 5 to 10 interleaved samples, spreads within a
few percent.

| K | n | µs/change | implied row changes/sec |
| --- | --- | --- | --- |
| 1 | 20,000 | 35 | 28,000 |
| 10 | 100 | 763 | 1,300 |
| 10 | 1,000 | 7,954 | 126 |
| 10 | 5,000 | 39,843 | 25 |
| 45 | 1,000 | 27,084 | 37 |
| 45 | 5,000 | 150,237 | **6.7** |
| 150 | 100 | 10,519 | 95 |
| 150 | 1,000 | 96,697 | 10 |

Cost is linear in `n × K` at roughly 0.8 µs per (shape × `IN` element). At K=45 and n=5,000 the filter sustains about 6.7 changes/sec, against a documented ~5,000 that should hold "no matter how many shapes you have". This is filter routing alone, which is serialized in the `ShapeLogCollector`.

`K = 1` is unaffected, as expected, since a one-element `IN` is a plain equality.

## Prior art

- #2359 added multi-condition `AND` indexing and the `@>` inclusion index.
- #3963 indexed `IN` lists via `flatten_or_equalities`. Review comment on that PR: "it should just
handle OR rather than special case IN".
- #4134 generalised to `OR` splitting and removed the `IN` special case, with the rule "split OR
branches only when both sides are indexable". The interaction with a non-indexable `AND` sibling
does not appear to have been considered, and we could not find an existing issue covering it.
- `Eval.Decomposer` and `DnfPlan` implement full DNF decomposition but are wired only into subquery
routing (`maybe_register_subquery_shape`), so they are unavailable to plain shapes.

## Suggested direction

Distribute `AND` over `OR`, so `(a OR b) AND c` becomes `(a AND c) OR (b AND c)` and each disjunct still reaches an index. Two guards keep the expansion bounded: refuse distribution unless the residual is `OR`-free, so `a IN (n) AND b IN (m)` falls back to current behaviour instead of fanning out to `n × m`; and cap the number of disjuncts.

We run a patch along these lines in production and can open a PR with benchmarks and differential tests if that direction is useful.

## Environment

- Electric sync-service v1.7.8, also verified on `main` @ `917589195`. The affected code is
unchanged from v1.6.10 through `main`.
- Elixir 1.20.2 / OTP 29.0.2.

---

*Written with AI assistance and reviewed by a human before filing. The reproduction script was run against v1.7.8 and produces the output shown. The timings are measured rather than estimated, on one machine, with both arms on the same toolchain image. We can re-run anything or share the benchmark harness if the numbers are hard to reproduce.*

Contributor guide

Open the contributing guide

Research direction

Start with packages/sync-service/repro_in_and.exs and run it with MIX_ENV=test mix run --no-start to reproduce the indexing results. Read optimise_where, add_shape/5, and add_shape_to_other_shapes/5, then inspect Filter.indexed_shape? and Filter.affected_shapes/2. Done means an indexable IN/OR remains indexed beside a non-optimized residual, with bounded distribution and differential tests or benchmarks.

Written by the indexing model from the issue text.

Assessment

Tech stack
elixir, postgresql
Domain
backend, databases, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.