在大数据库上快速mysql随机加权选择

Question

我建立了一个网站,我需要从数据库中选择随机加权记录.

SQL中有一段代码:随机选择一行,但要考虑权重

SELECT t.*, RAND() * t.weight AS w 
FROM table t 
ORDER BY w DESC
LIMIT 1

它适用于小型记录样本.

当尝试接近1百万的记录时,它在我的本地机器上变慢(1.3 - 1.8秒),我想我会在更大的设备上花更长的时间.

怎么可以优化？有没有更好的方法来随机选择加权记录？

我的尝试是定期计算权重,将它们存储在单独的表中,选择随机数编程并搜索与此数字最接近的记录.

Answer 1

您可以根据权重对数据进行分区，然后随机选择一个分区。

确定要使用的分区：O(n)

SELECT Weight, FLOOR(RAND()*COUNT(*)) as Target 
FROM test 
GROUP BY Weight
ORDER BY RAND()*(Weight)*count(Weight)/100 DESC
LIMIT 1;

使用先前查询中的权重和目标来获取结果：O( Log(n) )

SELECT test.*
FROM test
WHERE Weight = $Weight
LIMIT $Target, 1

测试一下：

CREATE TABLE `test` (
  `Id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
  `Weight` int(11) NOT NULL,
  PRIMARY KEY (`Id`),
  KEY `Weight` (`Weight`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;


insert into test (Weight) ( select FLOOR(RAND()*1000) );

运行 20 次以创建 100 万个测试行：

insert into test (Weight) select FLOOR(rand()*1000) as Weight from test;

由于 GROUP BY，第一个查询的运行时间为 O(n)。如果您维护第二个表来跟踪每个权重的计数，则可以将其减少到 log(n) 运行时间。

在我的数据库中，测试表中有 800 万行，第一个查询运行在(6.089 s)，第二个查询运行在(0.001 s)