skip to content

Redis offers SINTER, SUNION and SDIFF plus SINTERSTORE, SUNIONSTORE and SDIFFSTORE. How do these behave, what do they cost, and when would you reach for the STORE variants?

level: middleimportance: should knowfreq 52%

answer

  1. SINTER ~ smallest set × number of sets
  2. SUNION/SDIFF ~ total members
  3. SDIFF: first minus the rest, order matters
  4. STORE overwrites dst, TTL NOT inherited
  5. SINTERCARD + LIMIT = count with early exit

basics

~20 s

They compute intersection, union and difference of Sets on the server. SINTER is roughly O(smallest set × number of sets), SUNION/SDIFF O(total members). STORE variants write the result into a destination key and return its size instead of shipping members — the destination is overwritten and gets no TTL.

solid answer

~60 s

`SINTER k1 k2 ...` returns members present in every set; Redis sorts the inputs by cardinality and iterates the smallest, testing membership in the rest, so cost is about O(smallest × number of sets). `SUNION` and `SDIFF` are O(total members across the inputs); `SDIFF` is the first set minus all the others, so **argument order matters**. The `*STORE` variants do the same computation but write the result into a destination key and return its cardinality. Two reasons to use them: you avoid transferring a large result to the client, and you get a materialised key you can paginate, re-query or intersect again. Two traps: the destination is **overwritten unconditionally** (and deleted if the result is empty), and it does **not inherit any TTL** — you must `EXPIRE` it yourself or it leaks. If you only need the size, `SINTERCARD` (7.0) computes the intersection cardinality with an optional `LIMIT` that lets Redis stop early — much cheaper than materialising a result you throw away. All of these are single commands on the server, so a large intersection is a long pause for every other client.

code

text · 16 lines
text
> SADD tag:kotlin i1 i2 i3
> SADD tag:backend i2 i3 i9
> SINTER tag:kotlin tag:backend
1) "i2"
2) "i3"
> SDIFF tag:kotlin tag:backend      # in kotlin, NOT in backend
1) "i1"
> SINTERCARD 2 tag:kotlin tag:backend LIMIT 1
(integer) 1                         # 'are there any?' — stops early

> SINTERSTORE q:req123 tag:kotlin tag:backend
(integer) 2
> TTL q:req123
(integer) -1                        # persistent! must expire it yourself
> EXPIRE q:req123 60
(integer) 1

go deeper

for a junior

Know what each of the three operations returns, that SDIFF is first-minus-rest, and that the STORE variants save the result into another key.

for a middle

Add the complexity story — intersection is bounded by the smallest set, union and difference by the total — and the two STORE gotchas: overwrite and no inherited TTL.

for a senior

Talk about blast radius and operations: pick a selective input, use SINTERCARD with LIMIT for counts, give every materialised result an explicit TTL in the same round trip, and keep huge unions off the hot instance.

for a principal

Treat set algebra as a query engine with a specific cost model and no distribution story — multi-key commands force co-location — and be explicit about when a filtering feature has outgrown it and belongs in a search index.

## The three operations Redis implements classic set algebra server-side, which is what makes Sets an *index* rather than just a container. - **`SINTER key [key ...]`** — members present in **all** the given sets. Order of arguments does not change the result. - **`SUNION key [key ...]`** — members present in **any** of them; duplicates collapse. - **`SDIFF key [key ...]`** — members in the **first** set that are in **none** of the rest. Order absolutely matters: `SDIFF a b` and `SDIFF b a` are different questions. A missing key is treated as an empty set, which is usually what you want but occasionally surprising: `SINTER tag:kotlin tag:typo` returns empty not because nothing matched but because the second key does not exist. If "tag does not exist" and "tag matches nothing" must be distinguished, check `EXISTS` first. ## Cost `SINTER` is documented as O(N×M) where N is the cardinality of the **smallest** set and M the number of sets. The implementation sorts the inputs by size and walks the smallest one, probing the others by hash lookup, and it bails out as soon as the running result cannot grow. Practically: **one selective set makes an intersection cheap regardless of how large the others are.** `SINTER tag:rare tag:common` where `tag:rare` has 50 members is 50 lookups, not millions. `SUNION` and `SDIFF` have no such shortcut — every member of every input must be examined, so they are O(total members). A union of two ten-million-member sets is tens of millions of operations inside one command, executed while the server serves nobody else. That is a latency incident, not a slow query. ## The STORE variants `SINTERSTORE dst k1 k2 ...`, `SUNIONSTORE dst ...`, `SDIFFSTORE dst ...` perform the same computation but store the result at `dst` and return its cardinality. Why that matters: 1. **No transfer.** A 500 000-member result never crosses the network. You then read it in pages with `SSCAN`, sample it with `SRANDMEMBER`, or check `SISMEMBER` against it. 2. **Composability.** You can build up a query in steps: `SINTERSTORE tmp a b`, then `SDIFFSTORE result tmp c`. Each step is materialised and reusable. 3. **Caching.** A recomputed facet or filter result is a natural cache: store it once, serve many paginated reads from it, and let it expire. The traps: - **Unconditional overwrite.** If `dst` already exists — with any type — it is replaced. Two concurrent requests writing the same destination will clobber each other, so include a request-specific component in the destination key name. - **No inherited TTL.** Even if every input key had a TTL, the destination is created **persistent**. Forgetting `EXPIRE dst ...` is one of the most common sources of slow memory growth in Redis deployments built on set algebra. Set the TTL in the same pipeline or transaction as the store. - **Empty result deletes the key.** If the computation yields nothing, `dst` is removed rather than left as an empty set. Code that assumes the key exists after a `*STORE` must handle a return value of 0. ## SINTERCARD Redis 7.0 added `SINTERCARD numkeys key [key ...] [LIMIT n]`, which returns *how many* members the intersection would have without building it. With `LIMIT n`, Redis stops counting once it reaches `n` and returns `n`. This is the right tool for "does this filter match anything?" (`LIMIT 1`) or "show 100+ results" style UI counts — it turns a potentially expensive materialisation into an early-exit scan. ## Multi-key commands and key placement All of these are multi-key commands. On a single Redis instance that is a non-issue. In a clustered deployment, every key involved must live in the same hash slot, which forces you to co-locate them with hash tags — a design constraint to be aware of before you build a feature on set algebra, since it concentrates related keys on one node. The mechanics of slots and tags belong to the cluster topic; the point here is simply that set algebra is not free to distribute. ## Putting it together A typical filtering flow: pick the most selective input first so `SINTER`'s smallest-set optimisation applies; use `SINTERCARD ... LIMIT` when you only need a count or an existence check; use `SINTERSTORE` into a per-request key with a short TTL when the user is going to page through results; and never let an unbounded `SUNION` of huge sets run on a latency-sensitive instance — precompute it, or run it on a replica or a dedicated instance where a long pause is acceptable.

  • Why is intersecting one tiny set with one enormous set cheap, while unioning them is not?
    SINTER sorts its inputs by cardinality and iterates only the smallest, probing the others with O(1) hash lookups, so the work is bounded by the smallest set. A union has no such bound — every member of every input must be visited to build the result, so its cost is the sum of all cardinalities. That asymmetry is why filter designs try to make at least one input highly selective.
  • Your destination keys from SINTERSTORE keep accumulating and memory grows. What went wrong?
    The destination of a STORE variant is created persistent regardless of the TTLs on the input keys, so a per-request result key lives forever unless you expire it explicitly. The fix is to issue EXPIRE on the destination in the same pipeline or transaction as the STORE, so no code path can create the key without a lifetime. Auditing for keys with TTL -1 in the result namespace finds the existing leak.
  • How would you check whether a multi-tag filter matches anything, as cheaply as possible?
    Use SINTERCARD with LIMIT 1 (Redis 7.0+), which stops as soon as one common member is found and returns 1, avoiding both the materialisation and the transfer. Before 7.0 the closest equivalent is SINTERSTORE into a scratch key and reading the returned cardinality, which still does the full work. Ordering the arguments so the most selective set comes first does not change correctness but helps the engine bail out sooner.

saying these in an interview costs you the question

  • Assuming the destination key of a *STORE command inherits a TTL from the source keys
  • Believing SDIFF is symmetric, or that argument order does not matter
  • Fetching two sets to the client and intersecting them in application code
  • Running a large SUNION on a latency-sensitive instance without considering that it blocks every other client
  • Expecting the destination key to exist as an empty set when the result is empty

context

resolving links…