Keep IN/OR conditions indexed when ANDed with a non-indexable condition - #4786

Summary

An indexable IN (...) / OR condition was dropped from the shape filter index as soon as it was ANDed with a condition that is not itself a single indexable operation:

"category_id" IN ('c1', 'c2', 'c3') AND "deleted_at" IS NULL

WhereCondition.optimise_where/1 only recognised a %{operation: _} map on either side of an AND. An OR tree (which is what an IN list is turned into since #4134) returns {:or, left, right}, which matched neither pattern, so the whole conjunction fell through to :not_optimised and landed in other_shapes. Every change on that table then evaluated the full where clause, IN list included, for every such shape on the node — O(shapes × IN-list size) per change instead of an index lookup.

The same thing happened one level down the tree. "tenant_id" = $1 AND "category_id" IN (...) AND "deleted_at" IS NULL indexes the equality at the root, but the residual handed to the child node is IN (...) AND IS NULL, which hit the same bug there. Filter.indexed_shape?/1 reported true for that shape while routing under a given tenant was still linear.

The docs list optimized_condition AND non_optimized_condition as an optimised form, so this is a bug against documented behaviour.

Fix

Distribute the AND over the OR tree: (a OR b) AND c becomes (a AND c) OR (b AND c). Each branch is indexable AND residual, which the existing and_where / branch-key machinery already handles: the branch is indexed and c is only evaluated for the shapes the index selects. remove_shape dispatches on the same optimise_where result, so cleanup stays symmetric.

Three new cases in the AND clause of optimise_where:

• {:or, ...} AND :not_optimised (either order) → distribute, unconditionally. The number of index leaves is the same as for the OR tree on its own.
• {:or, ...} AND {:or, ...} (e.g. id IN (...) AND number IN (...)) → distribute over the left tree; the right tree becomes the residual of each branch and is split again by the child node, giving a nested trie (n entries at the parent, m under each). This multiplies the number of index leaves, so it is only done while the product of both sides' leaf counts is within a cap. Above the cap the clause falls back to other_shapes, i.e. today's behaviour. Leaf counts are accumulated by optimise_where/2 as it recurses (each indexable operation carries leaves:, an OR tree carries the sum of its branches, :not_optimised is one other_shapes entry), so the count is exactly what the tree will build — a non-indexable OR such as (d > 1 OR d IS NULL) next to two IN lists counts as one residual leaf, not its branches — and no subtree is optimised twice.

No change for clauses that were already indexed.

Configurable cap

The cap is shape_filter_max_distributed_leaves, default 1000, settable with ELECTRIC_TWEAKS_SHAPE_FILTER_MAX_DISTRIBUTED_LEAVES and wired like the other performance tweaks (Electric.Config default → tweaks → stack config). Filter.new/1 and Filter.indexed_shape?/2 resolve it from an explicit option, then the stack config, then the application default, so the filter and the ShapeStatus indexability check in a stack always agree. 0 disables distribution over two trees while leaving OR-tree AND <non-indexable> indexed.

Why it's a knob — the trade-off is workload-dependent. Measured on a dev build for one a IN (n) AND b IN (m) shape:

Add/remove cost lands on the serialised ShapeLogCollector path and is paid again for every shape on restart, so a deployment that creates/removes many such shapes may want a lower cap; one with many long-lived shapes and high write volume may want a higher one.

Per-leaf cost (~1 KB, dominated by the branch_key path list on each where_cond leaf row) is pre-existing: a bare IN (K) list is already O(K²) memory and O(K³) add_shape time on main (IN (1000) ≈ 8 MB / 8 s). This PR doesn't change that; IN (K) AND <residual> shapes now inherit it where they used to be cheap-to-add / slow-to-route. A compact branch-key representation is the follow-up that would make raising the default reasonable.

Before / after

Running the reproduction script from #4742 on this branch:

IN(3): true
IN(3) AND TRUE: true          # was false
IN(3) AND IS NULL: true       # was false

The new reduction-budget tests in filter_test.exs (--include performance) fail on main with routing cost growing linearly in the number of shapes and pass here within the same budget as the existing field = const1 OR field = const2 test.

Fixes #4742

Notes

• add_shape is O(node population) for unindexed clauses: the whole other_shapes map is copied in and out of ETS per insert #4743 (the other_shapes map being copied in and out of ETS on every insert) is independent and not addressed here. This change moves the affected shapes out of other_shapes, which removes the trigger the reporter hit, but the quadratic build cost for genuinely non-indexable shapes remains.
• Tweak env vars aren't documented on the config page today; this one follows that convention.

🤖 Generated with Claude Code

https://claude.ai/code/session_018WW5twMXeovo29MyQdGWkW