Set Operations

Verified on Redis 8.10.2 (redis:8.10.2-alpine), ioredis 6.0.0, Node 24, Apple-silicon Mac. The # cli/... transcripts are one session in document order, replayed by the course harness. Timings are server-side microseconds from SLOWLOG (threshold 0) on this machine: orders of magnitude, not benchmarks.

Server-side set algebra

Redis computes intersection, union and difference of two or more Sets on the server, so you never pull the members to the client to combine them. The catch is that the work happens on the single command thread; the cost section below measures it.

SINTER, SUNION, SDIFF

SINTER returns members present in every Set, SUNION members in any, SDIFF members of the first Set that are in none of the others. SINTERCARD (7.0+) returns only the size of the intersection.

cli/sets-sorted-sets-set-operations-1.redis

127.0.0.1:6379> SADD user:1:follows "alice" "bob" "carol" "dave"
(integer) 4
127.0.0.1:6379> SADD user:2:follows "bob" "carol" "eve" "frank"
(integer) 4
127.0.0.1:6379> SINTER user:1:follows user:2:follows
1) "bob"
2) "carol"
127.0.0.1:6379> SINTERCARD 2 user:1:follows user:2:follows
(integer) 2
127.0.0.1:6379> SUNION user:1:follows user:2:follows
1) "carol"
2) "frank"
3) "eve"
4) "bob"
5) "alice"
6) "dave"
127.0.0.1:6379> SDIFF user:1:follows user:2:follows
1) "dave"
2) "alice"
127.0.0.1:6379> SDIFF user:2:follows user:1:follows
1) "frank"
2) "eve"
127.0.0.1:6379> SINTER user:1:follows nosuchkey
(empty array)
127.0.0.1:6379> SET title "not a set"
OK
127.0.0.1:6379> SINTER user:1:follows title
(error) WRONGTYPE Operation against a key holding the wrong kind of value

Read the output carefully:

• The order of the result is not defined. SUNION came back carol frank eve bob alice dave, which matches neither set’s order. Sort on the client if you display it. (An earlier version of this lesson showed neatly sorted samples; those were invented.)
• SDIFF is not symmetric: user:1 minus user:2 is dave, alice; user:2 minus user:1 is frank, eve.
• A missing key counts as the empty set, so SINTER with it is empty. A key of another type is a WRONGTYPE error for the whole command.

SADD user:1:follows "alice" "bob" "carol" "dave"
SADD user:2:follows "bob" "carol" "eve" "frank"
SINTER user:1:follows user:2:follows

Copy commands ⧉

SADD campaign:A "user:1" "user:2" "user:3"
SADD campaign:B "user:2" "user:4" "user:5"
SUNION campaign:A campaign:B

Copy commands ⧉

SADD plan:premium "user:1" "user:2" "user:3"
SADD notified:promo "user:2" "user:3"
SDIFF plan:premium notified:promo

Copy commands ⧉

SINTERSTORE, SUNIONSTORE, SDIFFSTORE

The *STORE variants write the result to a destination key and return its size. The destination is a normal Set that other clients can read at once. Two behaviours worth seeing:

cli/sets-sorted-sets-set-operations-2.redis

127.0.0.1:6379> SADD group:eng "alice" "bob" "carol"
(integer) 3
127.0.0.1:6379> SADD group:ops "carol" "dave"
(integer) 2
127.0.0.1:6379> SINTERSTORE overlap group:eng group:ops
(integer) 1
127.0.0.1:6379> SMEMBERS overlap
1) "carol"
127.0.0.1:6379> SUNIONSTORE all:staff group:eng group:ops
(integer) 4
127.0.0.1:6379> SCARD all:staff
(integer) 4
127.0.0.1:6379> SET overlap "important string"
OK
127.0.0.1:6379> SINTERSTORE overlap group:eng group:ops
(integer) 1
127.0.0.1:6379> TYPE overlap
set
127.0.0.1:6379> SADD gone x
(integer) 1
127.0.0.1:6379> SINTERSTORE gone group:eng nosuchkey
(integer) 0
127.0.0.1:6379> EXISTS gone
(integer) 0

1. The destination is overwritten whatever it held. overlap was a string with important string; after SINTERSTORE it is a set. No WRONGTYPE, no warning.
2. An empty result deletes the destination (gone existed, the intersection was empty, EXISTS gone is 0) — the same “empty collections do not exist” rule as everywhere else.

The stored result is a snapshot: later changes to the sources do not update it. Give it a TTL (EXPIRE, ideally in the same MULTI, as in the Node.js example) if it is a cache.

SADD group:eng "alice" "bob" "carol"
SADD group:ops "carol" "dave"
SINTERSTORE overlap:eng-ops group:eng group:ops
SMEMBERS overlap:eng-ops
SUNIONSTORE all:staff group:eng group:ops
SCARD all:staff

Copy commands ⧉

What it costs

SINTER is O(N*M) (N = the smallest set, M = number of sets): it walks the smallest set and probes the others. I built A = u1..u100000 and B = u50001..u150000 (50,000 in common), and C = 10 members, then read SLOWLOG:

Command	Server time	Result
SINTERCARD 2 A B	6,336 µs	50,000
SINTERCARD 2 A B LIMIT 10	20 µs	10 (stops early)
SINTER A B	8,983 µs	50,000 members to ship
SINTER A C (small set present)	18 µs	10 members
SINTERSTORE AB A B	13,858 µs	writes 50,000 members
SUNIONSTORE AUB A B	26,908 µs	150,000 members
SDIFFSTORE AmB A B	13,722 µs	50,000 members

Three lessons: the cost follows the smallest set for an intersection (A ∩ C is 18 µs even though A is huge), the STORE and union variants are the heavy ones because they must write every result member, and SINTERCARD ... LIMIT n is the way to answer “are there at least n?” without doing the work. All of it runs on the command thread, so a 27 ms union is 27 ms during which no other client is served.

From Node.js: mutual friends, suggestions and a cached result

src/sets-sorted-sets-set-operations-friends.ts

// @run
import { Redis } from 'ioredis';

const redis = new Redis(process.env.REDIS_URL!);
await redis.del('b2:f:1', 'b2:f:2', 'b2:f:3', 'b2:mutual:1:2');
await redis.sadd('b2:f:1', 'alice', 'bob', 'carol', 'dave');
await redis.sadd('b2:f:2', 'bob', 'carol', 'eve', 'frank');
await redis.sadd('b2:f:3', 'eve', 'zoe');

// mutual friends: the result order is NOT defined, sort if you display it
console.log((await redis.sinter('b2:f:1', 'b2:f:2')).sort());          // [ 'bob', 'carol' ]

// "10+ mutual friends" badge: stop counting at 10 instead of materialising everything
console.log(await redis.sintercard(2, 'b2:f:1', 'b2:f:2', 'LIMIT', 10)); // 2

// suggestions for user 1: friends of user 2 or 3 that user 1 does not follow yet
await redis.sunionstore('b2:tmp:fof', 'b2:f:2', 'b2:f:3');
console.log((await redis.sdiff('b2:tmp:fof', 'b2:f:1')).sort());        // [ 'eve', 'frank', 'zoe' ]

// cache the mutual set for 60 s; SINTERSTORE replaces the destination, EXPIRE in the same MULTI
const res = await redis.multi().sinterstore('b2:mutual:1:2', 'b2:f:1', 'b2:f:2').expire('b2:mutual:1:2', 60).exec();
console.log(res);                                                       // [ [ null, 2 ], [ null, 1 ] ]
console.log(await redis.ttl('b2:mutual:1:2'));                          // 60

await redis.del('b2:f:1', 'b2:f:2', 'b2:f:3', 'b2:tmp:fof', 'b2:mutual:1:2');
await redis.quit();

Real output: [ 'bob', 'carol' ], 2, [ 'eve', 'frank', 'zoe' ], [ [ null, 2 ], [ null, 1 ] ], 60. Note multi().exec() returns [error, result] pairs, one per command.

Reading AI-generated code

An assistant adds a “12 mutual friends” badge to a profile page. Both users follow about 100,000 accounts:

🐛 Spot the bug

async function mutualCount(a: string, b: string) {
const mutual = await redis.sinter(`follows:${a}`, `follows:${b}`);
return mutual.length;   // the UI shows "10+" above 10
}

Show the answer

Correct, and it makes Redis build and ship every common member just to count them. On the two 100,000-member sets above that is 8,983 µs of command thread and 50,000 members on the wire, on every profile view. The badge only needs “how many, up to 10”, which SINTERCARD answers with an early stop in 20 µs:

async function mutualCount(a: string, b: string) {
  return redis.sintercard(2, `follows:${a}`, `follows:${b}`, 'LIMIT', 10);
}

The runnable sets-sorted-sets-set-operations-friends.ts above uses exactly this call.

Mental Model

Set algebra is a join the database does for you, on the one thread everyone shares. The price is proportional to the smallest set you intersect and to the size of what you write. Ask for the cheapest answer to the real question (a count with LIMIT, a small set first), and store results only when you will read them more than once.

Trade-offs

Choice	Benefit	Cost
Server-side SINTER/SUNION/SDIFF	No members shipped to compute an answer locally	Runs on the command thread: 9 ms for two 100k sets, other clients wait
SINTERCARD ... LIMIT n	Answers “at least n?” in 20 µs instead of 6 ms	Gives a count, not the members
*STORE variants	Materialise once, read many times	Overwrite the destination unconditionally; the result is a snapshot; big results cost 14-27 ms to write
A Set instead of a SQL JOIN	Fast for simple many-to-many membership	Only membership algebra, no filters or columns

Common Misconceptions

• “The result comes back sorted, or in the first set’s order.” The order is not defined (SUNION returned carol frank eve bob ...).
• “SINTERSTORE fails if the destination exists.” It silently replaces it, even a string.
• “SDIFF A B equals SDIFF B A.” It is a subtraction from the first key.
• “Intersection cost depends on the biggest set.” It follows the smallest (18 µs for A ∩ C although A has 100,000 members).

Common mistakes

• Materialising a result to count it — SINTERCARD (with LIMIT) counts without building it.
• Storing into a key that already holds data — the old value is overwritten with no warning; use a dedicated destination name with a TTL.
• Recomputing a big union on every request — store it once with a TTL, or the command thread spends 27 ms per call.

Real-world example

Redis’s own documentation lists the complexity of each command: SINTER is O(N*M) with N the smallest set and M the number of sets, and it recommends SINTERCARD when only the size matters (SINTER, SINTERCARD).

Which command returns members present in ALL listed sets?

SUNION SDIFF SINTER SMEMBERS

What does SDIFF key1 key2 return?

Members in key2 but not key1 Members in key1 but not key2 Members in both key1 and key2 All members from key1 and key2

You run SINTERSTORE overlap a b and overlap already holds a string. What happens?

WRONGTYPE error The command is ignored and returns 0 The string is silently replaced by the resulting set The result is appended to the string

SUNION across two sets with overlapping members returns how many copies of a shared member?

Two Zero One It depends on insertion order

You only need to know whether two 100,000-member sets share at least 10 members. Best command?

SINTER then check .length SINTERCARD 2 a b LIMIT 10 SUNION then count SMEMBERS on both and compare in Node

SINTER of a 100,000-member set with a 10-member set took 18 microseconds. Why so fast?

Redis caches every intersection The cost follows the smallest set: it walks 10 members and probes the big set SINTER only looks at the first 100 members The big set was on disk

Submit

Mark as complete