用例是,我有一个表 products 和 user_match_product。对于特定用户,我想选择 X 个随机产品,该用户没有匹配的产品。
最简单的方法是做类似的东西
SELECT * FROM products WHERE id NOT IN (SELECT p_id FROM user_match_product WHERE u_id = 123) ORDER BY random() 限制 X
但当有数百万行时,这将成为性能瓶颈。
我想到了一些可能的解决方案,现在将在此处展示。我很想听听您对该问题的解决方案或关于我的解决方案的建议。
解决方案 1:相信随机性
基于产品 id 单调递增这一事实,可以乐观地生成 X*C
随机数 R_i
其中 i
在 1
和 X*C
,它们在 [min_id, max_id]
范围内,希望像下面这样的 select 返回 X 个元素。
SELECT * FROM products p1 WHERE p1.id IN (R_1, R_2, ..., R_XC) AND NOT EXISTS (SELECT * FROM user_match_product WHERE u_id = 123 AND p_id = p1.id) 限制 X
优点
- 如果随机数生成器很好,这可能会在 O(1) 内很好地工作
- 老产品和新产品被选中的概率相同
缺点
- 如果匹配的数量接近于产品的数量,碰撞概率可能会非常高。
解决方案 2: block 式 PRNG
可以为域 [START, END]
创建一个置换函数 permutate(seed, start, end, value)
使用 seed
随机性。在时间 t0
,用户 A
有 0
匹配的产品,并观察到 E0
产品存在。 t0
用户 A
的第一个 block 是域 [1, E0]
。用户记住了一个计数器 C
,它最初是 0
。
要选择 X 产品,用户 A
首先必须创建排列 P_i
,例如
P_i = permutate(seed, START, END, C + i)
以下必须满足该功能。
permutate(seed, start, end, value)
是[start, end]
的元素value
是[start, end]
的元素
以下查询将返回 X 个非重复元素。
SELECT * FROM products WHERE id IN (P_1, ..., P_X)
当 C
到达 END 时,使用 END + 1
作为新的 START
分配下一个 block ,当前产品计数 E1
作为新的 END
。 seed
和 C
保持不变。
优点
- 不可能发生碰撞
- 保证 O(1)
缺点
- 必须先完成当前区 block ,然后才能选择新产品
最佳答案
我会采用方法 #1。
您可以通过计算 user_match_product
中的用户行数(假设唯一)来初步估计 C
。如果他已经拥有一半可能的产品,则选择两倍数量的随机产品似乎是一个很好的启发式方法。
您还可以进行最后的修正,以验证提取的产品数量实际上是 X。如果是,比如说,X/3,您需要再运行两次相同的提取(避免已经-生成随机产品 ID),并将该用户的 C
常量增加三倍。
此外,了解产品 ID 的范围后,您可以选择该范围内未出现在 user_match_product
中的随机数(即您的第一阶段查询仅针对 user_match_product
) 必然比 products
具有(很多?)更低的基数。然后,可以从products
中安全地选择那些通过测试的ID。
关于sql - 为每个用户选择随机的非重复行,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26951444/