Fast Group Retrieval over 1M Objects

Problem Given 1 million objects, each with 3-4 properties, choose a data structure to store all records such that a query retrieving a group of records — all objects matching one or more property values — runs as fast as possible.

Requirements

• insert(object) / update(id, fields) / delete(id)
• findByProperty(property, value) -> List<Object> — returns the whole matching group
• findByProperties(Map<property, value>) -> List<Object> — multi-property conjunctive query
• Group retrieval must not scan all 1M records
• Indices must stay consistent across mutations

Core design

• The naive store — one array of 1M objects — makes every query an O(n) scan. The whole problem is trading memory and write cost for read speed.
• Secondary indices: one hash map per queryable property, value -> Set<recordId> (or direct object references). A group lookup is then a single O(1) hash hit returning the entire bucket, no scan. With 3-4 properties that is 3-4 indices over the same primary store.
• Primary store keyed by ID (Map<id, Object>) is the single source of truth; indices hold IDs pointing back into it, so an update mutates the object once rather than once per index copy.
• Index type per property, chosen by query shape: hash index for equality/grouping (O(1), no ordering); sorted structure (balanced BST / skip list / sorted array) for range and prefix queries at O(log n + k). A hash index cannot answer "rating > 4" at all — this is the key selection criterion.
• Multi-property queries: either intersect the per-property ID sets (start with the most selective property so the intersection shrinks fastest), or build a composite index keyed on the property tuple for an O(1) direct hit. Composite is faster but only serves that exact combination and, if ordered, only its prefixes.
• Index maintenance is the correctness risk: on insert, add to every index; on update, remove from the old value's bucket and add to the new one; on delete, purge from all. Every mutation path must go through one encapsulated method, or an index silently drifts from the store and starts returning ghosts.

Discussion points

• Memory arithmetic: 1M records with 4 indices means ~4M extra ID entries plus hash overhead — a few hundred MB in a managed runtime. This fits in memory, which is exactly why indexing beats scanning here; at 100x the size the answer changes to a real database or a sharded/disk-backed index.
• Read/write trade-off: each index makes writes strictly slower and reads dramatically faster. Index only the properties actually queried — speculative indices are pure cost.
• Cardinality decides whether an index is worth anything: a boolean property splits 1M into two 500k buckets, so the "index" returns half the dataset and saves nothing. High-cardinality properties are where indices pay.
• Trade-off: set intersection is flexible (any property combination, N indices) vs. composite indices (faster, but combinatorial explosion if every combination needs one).
• Returning references vs. copies: references are O(1) but let callers mutate indexed fields behind the index's back — the classic source of corruption. Immutable records sidestep this entirely.
• Concurrency: the store and its indices must update atomically, or a reader sees a record in the store but not the index. Discuss copy-on-write snapshots vs. locking.
• Extension: partial/filtered indices over hot subsets, and lazy index rebuild for bulk loads where per-row maintenance dominates.