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

[whygee-dev]

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

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

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:

"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

• feat(sync-service): index for array contains #2359 added multi-condition AND indexing and the @> inclusion index.
• Optimize filter conditions for ANY and IN operators #3963 indexed IN lists via flatten_or_equalities. Review comment on that PR: "it should just
  handle OR rather than special case IN".
• Where clause optimisation for OR operator #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.