Efficiently finds shapes that are affected by a change when the shape's where clause has array_field @> const_array in it.

The index is a tree stored in ETS. Each node in the tree represents a value in the array.

When adding a shape to the tree, the shape's array is sorted and deduplicated, then first value is used to find the child node of the root node. The child to that node is then found using the next value and so on. When there are no values left, the shape is then added to the last node. Adding the shape to the last node is done by adding the shape the node's WhereCondition which represents the rest of the where clause of the shape (the @> comparison may be only part of the where clause) and can also contain many shapes.

To find the shapes affected by a change, the values of the array in the change are sorted and deduplicated. The tree is then traversed using the values and any nodes that contain shapes on the way are added to the result set, because if the node has been reached the shape's array must be a subset of the change's array.

ETS Storage

Tree nodes are stored in the incl_index_table with keys of the form: {condition_id, field, path} -> %{keys: [...], condition_id: condition_id | nil}

Where path is the list of array values traversed to reach this node (e.g., [] for root, [1], [1, 2], etc.).

Additionally, the field type is cached at: {:type, condition_id, field} -> type This enables O(1) type lookup for parsing record values.