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

Question

我建立了一个网站，我需要选择随机加权记录来自数据库。

SQL : select one row randomly, but taking into account a weight 中有一段代码

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

它适用于小样本记录。

当尝试接近 100 万条记录时，速度会变慢(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;

使用之前查询的 Weight 和 Target 得到结果: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) 中运行