Set Operations

ทดสอบบน Redis 8.10.2 (redis:8.10.2-alpine), ioredis 6.0.0, Node 24 บน Mac (Apple silicon) transcript แบบ # cli/... คือ session เดียวเรียงตามเอกสารที่ harness ของคอร์สรันซ้ำ ตัวเลขเวลาเป็นไมโครวินาทีฝั่งเซิร์ฟเวอร์จาก SLOWLOG (threshold 0) บนเครื่องนี้ ถือเป็นระดับขนาด ไม่ใช่ benchmark

พีชคณิตของ Set ฝั่งเซิร์ฟเวอร์

Redis คำนวณ intersection, union และ difference ของ Set สองก้อนขึ้นไปบนเซิร์ฟเวอร์ คุณจึงไม่ต้องดึง member มาที่ client เพื่อรวมกัน ข้อแม้คืองานนั้นเกิดบน command thread เดียว ส่วนต้นทุนวัดไว้ด้านล่าง

SINTER, SUNION, SDIFF

SINTER คืน member ที่อยู่ใน Set ทุกก้อน, SUNION คืน member ที่อยู่ใน ก้อนใดก้อนหนึ่ง, SDIFF คืน member ของ Set ก้อนแรก ที่ไม่อยู่ในก้อนอื่นเลย SINTERCARD (7.0+) คืนเฉพาะขนาดของ 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

อ่าน output ให้ละเอียด:

• ลำดับของผลลัพธ์ไม่ได้ถูกกำหนด SUNION คืน carol frank eve bob alice dave ซึ่งไม่ตรงกับลำดับของ set ใดเลย ให้ sort ฝั่ง client ถ้าจะแสดงผล (บทเวอร์ชันก่อนแสดงตัวอย่างที่เรียงสวย; นั่นเป็นค่าที่แต่งขึ้น)
• SDIFF ไม่สมมาตร: user:1 ลบ user:2 ได้ dave, alice; user:2 ลบ user:1 ได้ frank, eve
• key ที่ไม่มีนับเป็น set ว่าง SINTER กับมันจึงว่าง key ที่เป็น type อื่นทำให้ทั้งคำสั่งเป็น error WRONGTYPE

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

ตัวแปร *STORE เขียนผลลัพธ์ลงใน destination key และคืนขนาดของมัน destination เป็น Set ปกติที่ client อื่นอ่านได้ทันที มีสองพฤติกรรมที่ควรเห็น:

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. destination ถูกเขียนทับไม่ว่ามันเก็บอะไรอยู่ overlap เป็น string ที่เก็บ important string; หลัง SINTERSTORE มันกลายเป็น set ไม่มี WRONGTYPE ไม่มีคำเตือน
2. ผลลัพธ์ว่างลบ destination (gone มีอยู่ แต่ intersection ว่าง EXISTS gone เป็น 0) — กฎ “collection ว่างไม่มีอยู่” เดียวกับที่อื่น

ผลที่เก็บไว้เป็น snapshot: การเปลี่ยนแปลงของต้นทางภายหลังไม่อัปเดตมัน ให้ TTL (EXPIRE ควรอยู่ใน MULTI เดียวกัน ดังในตัวอย่าง Node.js) ถ้ามันเป็น 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 ⧉

ต้นทุนเป็นเท่าไร

SINTER เป็น O(N*M) (N = set ที่เล็กที่สุด, M = จำนวน set): เดินผ่าน set ที่เล็กที่สุดและตรวจในก้อนอื่น ผมสร้าง A = u1..u100000 และ B = u50001..u150000 (ซ้ำกัน 50,000) กับ C = 10 member แล้วอ่าน SLOWLOG:

คำสั่ง	เวลาฝั่งเซิร์ฟเวอร์	ผลลัพธ์
SINTERCARD 2 A B	6,336 µs	50,000
SINTERCARD 2 A B LIMIT 10	20 µs	10 (หยุดเร็ว)
SINTER A B	8,983 µs	ต้องส่ง 50,000 member
SINTER A C (มี set เล็กอยู่)	18 µs	10 member
SINTERSTORE AB A B	13,858 µs	เขียน 50,000 member
SUNIONSTORE AUB A B	26,908 µs	150,000 member
SDIFFSTORE AmB A B	13,722 µs	50,000 member

สามบทเรียน: ต้นทุนของ intersection ตาม set ที่ เล็กที่สุด (A ∩ C ใช้ 18 µs แม้ A ใหญ่มาก), ตัวแปร STORE และ union หนักเพราะต้องเขียนทุก member ของผลลัพธ์ และ SINTERCARD ... LIMIT n คือวิธีตอบ “มีอย่างน้อย n ไหม?” โดยไม่ต้องทำงานทั้งหมด ทั้งหมดรันบน command thread ดังนั้น union 27 ms คือ 27 ms ที่ไม่มี client อื่นถูกให้บริการ

จาก Node.js: เพื่อนร่วม, คำแนะนำ และผลลัพธ์ที่แคช

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();

Output จริง: [ 'bob', 'carol' ], 2, [ 'eve', 'frank', 'zoe' ], [ [ null, 2 ], [ null, 1 ] ], 60 สังเกตว่า multi().exec() คืนคู่ [error, result] หนึ่งคู่ต่อคำสั่ง

Reading AI-generated code

AI เพิ่มป้าย “เพื่อนร่วม 12 คน” ในหน้าโปรไฟล์ ผู้ใช้ทั้งสองติดตามราว 100,000 บัญชี:

🐛 หา 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
}

เฉลย

ถูกต้อง และทำให้ Redis สร้างและส่งทุก member ที่ซ้ำกันเพียงเพื่อนับ บน set 100,000 member สองก้อนข้างบน นั่นคือ command thread 8,983 µs และ 50,000 member บน wire ทุกครั้งที่เปิดโปรไฟล์ ป้ายต้องการแค่ “กี่คน ไม่เกิน 10” ซึ่ง SINTERCARD ตอบด้วยการหยุดเร็วใน 20 µs:

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

sets-sorted-sets-set-operations-friends.ts ที่รันได้ข้างบนใช้คำเรียกนี้เป๊ะ

Mental Model

พีชคณิตของ set คือ JOIN ที่ฐานข้อมูลทำให้ บน thread เดียวที่ทุกคนใช้ร่วมกัน ราคาเป็นสัดส่วนกับ set ที่เล็กที่สุดที่คุณ intersect และกับขนาดของสิ่งที่เขียน ขอคำตอบที่ถูกที่สุดสำหรับคำถามจริง (นับด้วย LIMIT, เอา set เล็กมาก่อน) และเก็บผลลัพธ์เมื่อจะอ่านมากกว่าหนึ่งครั้งเท่านั้น

Trade-offs

ตัวเลือก	ข้อดี	ข้อเสีย
SINTER/SUNION/SDIFF ฝั่งเซิร์ฟเวอร์	ไม่ต้องส่ง member มาคำนวณเอง	รันบน command thread: 9 ms สำหรับ set 100k สองก้อน client อื่นต้องรอ
SINTERCARD ... LIMIT n	ตอบ “อย่างน้อย n ไหม?” ใน 20 µs แทน 6 ms	ได้จำนวน ไม่ใช่ member
ตัวแปร *STORE	สร้างครั้งเดียว อ่านหลายครั้ง	เขียนทับ destination โดยไม่มีเงื่อนไข; ผลเป็น snapshot; ผลใหญ่ใช้ 14-27 ms ในการเขียน
Set แทน SQL JOIN	เร็วสำหรับ membership แบบ many-to-many ง่ายๆ	เป็นแค่พีชคณิตของ membership ไม่มี filter หรือ column

Common Misconceptions

• “ผลลัพธ์กลับมาเรียง หรือตามลำดับของ set แรก” ลำดับไม่ได้ถูกกำหนด (SUNION คืน carol frank eve bob ...)
• “SINTERSTORE ล้มเหลวถ้า destination มีอยู่” มันแทนที่เงียบๆ แม้เป็น string
• “SDIFF A B เท่ากับ SDIFF B A” มันคือการลบจาก key แรก
• “ต้นทุน intersection ขึ้นกับ set ที่ใหญ่ที่สุด” ตาม set ที่เล็กที่สุด (18 µs สำหรับ A ∩ C ทั้งที่ A มี 100,000 member)

Common mistakes

• สร้างผลลัพธ์ขึ้นมาเพื่อนับ — SINTERCARD (พร้อม LIMIT) นับโดยไม่สร้าง
• เก็บลง key ที่มีข้อมูลอยู่แล้ว — ค่าเก่าถูกเขียนทับโดยไม่เตือน ใช้ชื่อ destination เฉพาะพร้อม TTL
• คำนวณ union ใหญ่ใหม่ทุก request — เก็บครั้งเดียวพร้อม TTL ไม่เช่นนั้น command thread เสีย 27 ms ต่อครั้ง

Real-world example

เอกสารของ Redis เอง ระบุความซับซ้อนของแต่ละคำสั่ง: SINTER เป็น O(N*M) โดย N คือ set ที่เล็กที่สุดและ M คือจำนวน set และแนะนำ SINTERCARD เมื่อต้องการแค่ขนาด (SINTER, SINTERCARD)

คำสั่งไหนคืน member ที่อยู่ใน set ที่ระบุ ทุกก้อน?

SUNION SDIFF SINTER SMEMBERS

SDIFF key1 key2 คืนอะไร?

member ใน key2 แต่ไม่อยู่ใน key1 member ใน key1 แต่ไม่อยู่ใน key2 member ที่อยู่ทั้ง key1 และ key2 member ทั้งหมดจาก key1 และ key2

คุณรัน SINTERSTORE overlap a b แต่ overlap เก็บ string อยู่ เกิดอะไรขึ้น?

error WRONGTYPE คำสั่งถูกเพิกเฉยและคืน 0 string ถูกแทนที่เงียบๆ ด้วย set ผลลัพธ์ ผลลัพธ์ต่อท้าย string

SUNION ของสอง set ที่มี member ซ้ำกันบางตัว คืน member ที่ใช้ร่วมกันกี่ชุด?

สอง ศูนย์ หนึ่ง ขึ้นกับลำดับการใส่

คุณแค่ต้องรู้ว่า set 100,000 member สองก้อนมี member ร่วมกันอย่างน้อย 10 ตัวหรือไม่ คำสั่งที่ดีที่สุดคือ?

SINTER แล้วเช็ก .length SINTERCARD 2 a b LIMIT 10 SUNION แล้วนับ SMEMBERS ทั้งสองแล้วเทียบใน Node

SINTER ของ set 100,000 member กับ set 10 member ใช้ 18 ไมโครวินาที ทำไมเร็วขนาดนั้น?

Redis แคชทุก intersection ต้นทุนตาม set ที่เล็กที่สุด: เดิน 10 member แล้วตรวจใน set ใหญ่ SINTER ดูแค่ 100 member แรก set ใหญ่อยู่บนดิสก์

Submit

Mark as complete