database - 按随机排序(): how many rows can a table hold before becoming the worst solution?

Question

我已经知道按 random() 排序是检索随机行的最差方法。我已经实现了添加 random_number 列并在检索随机行时使用该列的解决方案，然后在每次检索时更新 random_number。所有这些都用于参加返回随机代理 IP 的服务:

select proxy_ip from proxy where random_number > 0.63 limit 1

0.63 只是应用程序内部生成的随机数的一个示例。

问题是，当我使用“最差”的解决方案时:

select proxy_ip from proxy
order by random()
limit 1

调用服务时似乎运行得更快。该表包含 9300 行，所以我的问题是，一个表必须包含多少行才能使 sort by random() 成为最差的解决方案？

在应用程序中引入了一些开销，它不直接与数据库一起工作，而是使用一个数据层来依次运行查询，这解释了为什么更好的解决方案运行缓慢(除了它执行 1针对数据库的更多查询，不仅是 1，因为它需要更新 random_number)。

解释分析的结果:

随机排序()

Limit  (cost=837.03..837.03 rows=1 width=18) (actual time=34.954..34.956 rows=1 loops=1)
  ->  Sort  (cost=837.03..860.46 rows=9373 width=18) (actual time=34.950..34.950 rows=1 loops=1)
        Sort Key: (random())
        Sort Method: top-N heapsort  Memory: 25kB
        ->  Seq Scan on proxy  (cost=0.00..790.16 rows=9373 width=18) (actual time=0.013..17.951 rows=9363 loops=1)
Total runtime: 34.993 ms

使用随机列:

Limit  (cost=0.00..0.23 rows=1 width=18) (actual time=0.038..0.045 rows=1 loops=1)
  ->  Seq Scan on proxy  (cost=0.00..790.16 rows=3481 width=18) (actual time=0.029..0.029 rows=1 loops=1)
        Filter: (random_number > 0.63::double precision)
Total runtime: 0.078 ms

该表有 1 个索引:

CREATE UNIQUE INDEX proxy_pkey ON proxy USING btree (id)

Answer 1

几个想法...

1. 您的问题的答案将非常针对硬件和实现。 9300 行在现代硬件上并不多。很有可能您的整个表在第一次读取后都存储在内存中。因此后续的 ORDER BY RANDOM() 查询会非常快。

2. 您还因为没有为该列编制索引而损害了随机数列的性能，这意味着您实际上仍然必须读取整个表以避免...必须读取整个表.

   因此，向您的 random_number 列添加一个索引，看看它有什么帮助。

3. 您还可以通过进行更新和选择同时进行以下操作来减少必要的往返次数:

   UPDATE proxy
   FROM (
       SELECT id 
       FROM proxy
       ORDER BY random_number
       LIMIT 1
   ) AS r
   SET random_number=RANDOM()
   WHERE proxy.id=r.id
   RETURNING proxy.*
   

4. 您并没有真正以这种方式随机化您的代理服务器。假设你有 5 个服务器，A-E，并且它们最初被分配了 random_numbers 1-5:

   A: 1
   B: 2
   C: 3
   D: 4
   E: 5
   

   在您的第一次运行中，您将选择服务器 A，其 random_number 为 1。然后您为其分配一个新的随机数，1-5。比方说你得到 3:

   B: 2
   C: 3
   A: 3
   D: 4
   E: 5
   

   在第二次运行中，您得到 B，并为其分配一个新的随机数，比如 4:

   C: 3
   A: 3
   D: 4
   B: 4
   E: 5
   

   然后得到C，给它一个新的随机数，2:

   C: 2
   A: 3
   D: 4
   B: 4
   E: 5
   

   应该很容易看出您将如何让您的一些服务器挨饿……任何“不幸”到出现在列表末尾的服务器，可能会永远留在那里。

5. 更好的实际上是随机的方法是为每个服务器分配一个指定范围内的静态数字，然后随机选择那个数字(或使用哈希伪随机) .这对性能更好，因为您不会进行大量写入，而且它实际上是随机的!

   SELECT proxy_ip
   FROM proxy 
   WHERE id=(RANDOM()*9300)::INT