sql - 为每个用户选择随机的非重复行

Question

用例是，我有一个表 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 ，然后才能选择新产品

Answer 1

我会采用方法 #1。

您可以通过计算 user_match_product 中的用户行数(假设唯一)来初步估计 C。如果他已经拥有一半可能的产品，则选择两倍数量的随机产品似乎是一个很好的启发式方法。

您还可以进行最后的修正，以验证提取的产品数量实际上是 X。如果是，比如说，X/3，您需要再运行两次相同的提取(避免已经-生成随机产品 ID)，并将该用户的 C 常量增加三倍。

此外，了解产品 ID 的范围后，您可以选择该范围内未出现在 user_match_product 中的随机数(即您的第一阶段查询仅针对 user_match_product) 必然比 products 具有(很多？)更低的基数。然后，可以从products中安全地选择那些通过测试的ID。