Array property indexing — design + reimplementation tracking

[QuantumExplorer]

Array element indexing for document types (reimplementation on v3.1-dev)

Summary

Add support for indexing individual elements of array fields in document types, so queries like "find posts where hashtags contains dash" resolve via the index rather than a full scan. Original design and test corpus live in #2974 (closed); this issue tracks a fresh implementation on v3.1-dev because the base PR's query-layer assumptions and several consensus-critical code paths have since diverged.

Use this issue as the spec. Treat #2974 as a reference, not a starting branch.

Scope

DPP (rs-dpp)

• Schema/validation: parse array properties with items definition; expose ITEMS property name constant.
• Validation rules for indexed arrays:
  • Array property must be the last field in a compound index.
  • At most one array property per index.
  • Array properties are not allowed in contested indexes (explicit error).
  • Bounded element types only (string with maxLength, byteArray with maxItems, integer, number, boolean, date, identifier).
• ArrayItemType::encode_element_for_tree_keys — encode a single element as an index key, with the same lex-ordering guarantees as the corresponding scalar encoders. In particular:
  • Date: must reject negative timestamps and use the same encoding as DocumentPropertyType::encode_date_timestamp (sign-bit-flipped u64), not a raw i64-as-u64 cast.
  • Integer: encode_i64 (sign-bit flip).
  • Number: encode_float (sign + negative handling).
  • String: empty string must not collide with null (use a sentinel byte).
  • ByteArray: empty bytes must not collide with null (same).
  • Identifier/Boolean: deterministic fixed encoding.
• ArrayItemType::read_from deserialization with hard bounds on element length (string and byte-array) to prevent DoS via large length prefixes. Bounds must be enforced before any Vec::with_capacity / allocation.
• Document::get_raw_array_elements_for_document_type — returns deduplicated, encoded array elements for indexing. Dedup must be by encoded form, not pre-encoded value.

Drive (rs-drive)

• add_indices_for_top_index_level_for_contract_operations and the nested-level counterpart: when the indexed property is an array, emit one index entry per element.
• remove_* counterparts: symmetric per-element removal.
• update_document_for_contract_operations:
  • Use remove-then-add ordering for array indexes to avoid GroveDB batch conflicts when element sets overlap.
  • The post-loop remove/add must run only for indexes that contain an array property — do not duplicate work for scalar-only indexes (this was a latent issue in feat(drive): add array element indexing support #2974).
• Cost estimation inside the per-element loop must key by (index_path, element), not by index_path alone, so per-element estimates accumulate instead of overwriting.
• Reject array properties in contested-index insertion path with an explicit error.

Query (rs-drive / platform protos)

• Add a Contains operator (with in SQL alias) — but design it into the v3.1 SQL-shaped getDocuments surface introduced by feat(platform): getDocuments v1 — SQL-shaped select + count surface #3633 / refactor: structure v1 getDocuments where/order_by/having as typed proto messages #3654, not the v3.0 query path that feat(drive): add array element indexing support #2974 modified.
• Query path construction must use the predicate value as the index key when traversing an array index node.
• Verify the proof side (rs-drive-proof-verifier): every new query shape must produce a verifier-checked proof in tests. feat(drive): add array element indexing support #2974 did not show proof-side test coverage.

Platform version

• New dpp_document_versions entry for get_raw_array_elements_for_document_type and any new DPP-side methods.
• Version-gate Drive behavior changes so existing contracts/documents on older protocol versions remain bit-identical.

Non-goals / explicit constraints

• Not consensus-breaking for existing contracts. Old documents without array-indexed fields must hash and index identically to today. Any behavior change must be gated on protocol version.
• No support in contested indexes in this iteration.
• No proof-less query paths — if Contains can be queried, it must be verifiable.

Tests to carry over from #2974

These are the salvageable artifacts; please port them and extend, don't restart from zero:

• packages/rs-drive/tests/supporting_files/contract/array-index/array-index-contract.json
• packages/rs-drive/tests/supporting_files/contract/array-index/array-index-with-types-contract.json
• packages/rs-drive/tests/supporting_files/contract/array-index/post0.json, post1.json
• The 13 unit tests added to packages/rs-drive/tests/query_tests.rs — treat as a behavioral spec. Resolve the duplicate test-module issue flagged by CodeRabbit in the port.

Add the following beyond what #2974 covered:

• Proof generation + verification round-trip for Contains queries.
• Update path: documents whose array values overlap with prior values, partially overlap, and fully replace — assert no GroveDB batch conflicts and idempotent reads after.
• Encoding round-trips for every ArrayItemType at length boundaries (empty, max, just-over-max → error).
• Lex-ordering tests: encoded array elements sort the same as scalar values of the same type would.
• A negative-timestamp Date element must be rejected at insert.
• A protocol-version bump where the contract existed pre-bump and is queried post-bump — must remain stable.

Known correctness issues from #2974 to NOT regress on

• Date encoded via raw i64-as-u64 cast (breaks lex ordering for negative values; in this design negatives are rejected, but ordering must still be tested).
• Empty String / empty ByteArray colliding with null.
• Unbounded Vec::with_capacity(array_len) on deserialization (DoS).
• Scalar-only indexes being re-processed in the update path.
• Cost-estimation HashMap entries overwriting per-element.
• Missing "date" arm in the items.type parse match.

References

• Closed PR with prior design + test corpus: feat(drive): add array element indexing support #2974
• Query-surface context this must integrate with: feat(platform)!: verifiable, bounded count queries on a unified endpoint #3623, feat(platform): getDocuments v1 — SQL-shaped select + count surface #3633, refactor: structure v1 getDocuments where/order_by/having as typed proto messages #3654, feat(drive): expand count-index group-by carrier shapes (G1a/G1b/G8a-c) #3652, feat(drive): document sum + average proof primitives, with SDK fan-out scaffolding and reproducible benchmarks #3661, refactor(drive): unify AVG no-prove dispatch into a single count+sum walk #3690