skip to content

You are designing catalog filtering by multiple tags on top of Redis Sets — users pick several tags and see the matching items. How would you model it, and what breaks as the catalog and tag cardinalities grow?

level: principalimportance: should knowfreq 38%

answer

  1. tag:<name> forward + item:<id>:tags reverse
  2. smallest-set optimisation saves selective queries
  3. SINTERCARD LIMIT for '200+' counts
  4. SINTERSTORE + EXPIRE for pagination cache
  5. cost = (tag,item) pairs, not items

basics

~20 s

Model one Set per tag holding item ids, plus a reverse Set per item for maintenance. AND is SINTER, OR is SUNION, exclusion SDIFF. It degrades when every selected tag is huge: the work happens in one blocking command. Mitigate with selective-tag ordering, SINTERCARD LIMIT, SINTERSTORE into short-TTL result keys, and precomputed hot combinations.

solid answer

~1 min

**Model.** `tag:<name>` → Set of item ids (integer ids where possible), and `item:<id>:tags` → Set of tag names so you can maintain and repair the index. A filter becomes `SINTER tag:a tag:b` for AND, `SUNION` for OR, `SDIFF` to exclude. **Why it works.** Redis walks the smallest input set and probes the rest, so as long as one selected tag is selective, the query is cheap no matter how big the others are. **Where it breaks.** - Every selected tag is high-cardinality → millions of probes inside one command, and that command blocks every other client. - Counts and pagination: users want "1 240 results, page 7". Materialise with `SINTERSTORE result:<hash-of-filter>` plus an explicit `EXPIRE` (STORE destinations never inherit TTLs), then page with `SSCAN`; or use `SINTERCARD ... LIMIT 200` when the UI only needs "200+". - Ordering. Sets are unordered, so "newest first" needs a Sorted Set or client-side sorting. - Clustering: multi-key set ops require co-located keys, concentrating the index on one node. - Memory: one entry per (tag, item) pair; string ids cost noticeably more than integer ids. **When to leave.** Once you need relevance ranking, facet counts for every tag, or text search, this is an index pretending to be a query engine — move to a search engine and keep Redis for the hot paths.

code

text · 18 lines
text
# write path: keep both directions in sync (pipeline these)
SADD tag:kotlin 88
SADD tag:backend 88
SADD item:88:tags kotlin backend

# cheap existence / capped count for the UI
SINTERCARD 2 tag:kotlin tag:backend LIMIT 200

# materialise once, page many times — TTL is mandatory
SINTERSTORE filter:9f3a tag:kotlin tag:backend
EXPIRE filter:9f3a 120
SSCAN filter:9f3a 0 COUNT 50

# delete an item without scanning every tag set
SMEMBERS item:88:tags   # -> kotlin, backend
SREM tag:kotlin 88
SREM tag:backend 88
DEL item:88:tags

go deeper

for a junior

Describe the basic model — a Set per tag holding item ids — and that AND filtering is SINTER.

for a middle

Add the reverse index for maintenance, the smallest-set optimisation that makes selective queries cheap, and the need to EXPIRE any materialised result key.

for a senior

Focus on operating it: cardinality-aware query admission, SINTERCARD with LIMIT for counts, cached result keys for pagination, and the fact that one heavy intersection degrades every other client on the instance.

for a principal

Frame the whole thing as a capability boundary — exact boolean filtering with great constants, bought at the price of no ranking, no facet counts, and no distribution — and state the memory sizing and the migration trigger to a real search index.

## The data model The forward index is the obvious half: for each tag, a Set of the item ids carrying it. ``` tag:kotlin -> {1042, 88, 9001, ...} tag:backend -> {88, 9001, 77, ...} ``` The reverse index is the half people forget: for each item, the Set of its tags. ``` item:88:tags -> {kotlin, backend} ``` Without the reverse index, deleting an item means scanning every tag set to remove it. With it, deletion is: read the item's tags, `SREM` the item from each of those tag sets, then `DEL` the reverse key — a bounded amount of work, issued as one pipeline. Keeping the two directions in sync is the main correctness burden of this design; do both writes together and accept that a crash between them leaves a stale entry, which a periodic repair job (or a filter step that drops ids whose item no longer exists) can clean up. Prefer **integer item ids** as members. Redis stores all-integer sets far more compactly than string sets, and at tens of millions of (tag, item) pairs the difference is measured in gigabytes. ## The query - AND across tags → `SINTER tag:a tag:b tag:c` - OR → `SUNION ...` - "has a, not b" → `SDIFF tag:a tag:b` - "(a OR b) AND c" → compose: `SUNIONSTORE tmp tag:a tag:b`, then `SINTER tmp tag:c` The engine's saving grace is that `SINTER` sorts inputs by cardinality and iterates the **smallest**, probing the others in O(1). So a query mixing one rare tag with several common ones costs roughly the size of the rare tag. Most real filter traffic looks like that, which is why this design survives far longer than its worst-case complexity suggests. ## What actually breaks **1. All-common-tag queries.** `SINTER tag:electronics tag:in-stock` where both hold millions of ids does millions of probes inside one command. Redis serves nothing else meanwhile, so a single such query raises p99 for every unrelated caller — a shared-fate failure that is invisible in per-query metrics and obvious in latency percentiles. Defences: reject or degrade filter combinations with no selective term; keep a cardinality map (`SCARD` per tag, refreshed periodically) and use it to decide, in the application, whether to run the query, serve a precomputed answer, or ask the user to narrow down. **2. Counts.** "1 240 results" requires the full intersection. `SINTERCARD numkeys ... LIMIT n` (Redis 7.0+) counts with an early exit, which is exactly right for UIs that display "200+" — the cost is bounded by the limit rather than the data. **3. Pagination.** Sets are unordered and there is no offset. Materialise the result once with `SINTERSTORE result:<filterHash>`, `EXPIRE` it (STORE destinations are created **persistent** — forgetting this is the classic memory leak in this design), and serve pages from the frozen key. Subsequent pages hit the cached result, which also makes the expensive computation happen once per filter rather than once per page. **4. Ordering and ranking.** Sets carry no order. "Newest first" or "most popular" needs either a Sorted Set holding the sort key, intersected with the filter, or a client-side sort of a bounded result. If ranking must combine relevance signals, you have left set algebra's competence. **5. Distribution.** Multi-key set operations require all participating keys to be reachable in one place. In a clustered deployment that means co-locating tag keys, which pins the whole index to one node and caps it at that node's memory and CPU. Sharding the *catalog* is possible (per-region, per-category indexes queried in parallel and merged), but a globally-consistent multi-tag intersection across shards is not something Redis will do for you. **6. Memory.** Cost scales with the number of (tag, item) pairs, not items. A catalog of 10M items averaging 8 tags each is 80M set entries. That is a sizing exercise to do with real data before committing, and it interacts with everything memory-bound in the deployment — snapshot forks, replica sync time, eviction headroom. ## Operational shape of a good implementation - A cardinality cache so the app knows which tags are selective before it issues a query. - A hard rule that every `*STORE` destination gets an `EXPIRE` in the same pipeline; enforce it in a client wrapper, not by discipline. - Precomputation for the small number of filter combinations that dominate traffic (they always follow a power law), refreshed on a schedule rather than on demand. - Read traffic served from replicas where slight staleness is acceptable; writes to the index go to the primary. - Latency alerting on the instance, not just on the feature — the failure mode is collateral damage to other users of the same Redis. ## Knowing when to stop Sets give you exact boolean filtering with excellent constants and no ranking, no text analysis, no per-facet counts, and no distribution story. The moment product asks for relevance ordering, typo tolerance, or counts for every available facet on every query, you are re-implementing a search engine badly. The mature call is to move the query surface to a search index and keep Redis for what it is genuinely unbeatable at: O(1) membership checks and short, selective intersections on hot paths.

  • How do you stop one expensive filter query from degrading latency for every other user of that Redis instance?
    Bound the work before you issue it: keep a periodically refreshed cardinality map so the application knows the size of each tag set, and refuse, degrade, or serve a precomputed answer when no selected tag is selective. Use SINTERCARD with LIMIT for counts so the cost is capped by the limit rather than the data, and cache materialised results so an expensive intersection runs once per filter instead of once per page. Structurally, move this workload onto its own Redis instance or a replica so a long command cannot stall unrelated features.
  • How do you paginate results when Sets have no order and no offset?
    Materialise the intersection into a destination key with SINTERSTORE, give it a short explicit TTL, and iterate that frozen key with SSCAN, carrying the cursor in the page token. If the product requires a specific sort order rather than an arbitrary one, intersect against a Sorted Set carrying the sort key so the result comes back ordered, or bound the result size and sort in the application. Offset-based paging over an unordered set is not something Redis supports and simulating it client-side re-reads the whole result each page.
  • At what point would you move this feature off Redis Sets entirely?
    When queries need relevance ranking, per-facet counts on every request, text analysis such as stemming or typo tolerance, or a result set that must be distributed across shards. Those are search-engine capabilities, and reimplementing them on set algebra produces a fragile, memory-hungry system. The usual endgame keeps a search index as the query surface and retains Redis for O(1) membership checks and a small number of hot, highly selective intersections.

It is a library card catalog: one drawer per subject listing shelf numbers. Cross-referencing two narrow subjects is quick; cross-referencing 'Books' with 'Published after 1900' means reading half the library, and only one librarian is on duty.

saying these in an interview costs you the question

  • Building only the forward tag→items index and then needing a full scan to delete an item
  • Leaving SINTERSTORE destination keys without an EXPIRE and calling the resulting growth a Redis memory leak
  • Assuming worst-case intersection cost never happens because typical queries are fast
  • Expecting Sets to return results in a stable or sortable order
  • Planning to shard the tag index across cluster nodes without accounting for multi-key commands needing co-located keys

context

resolving links…