MySQL：这个查询是否有可能更快？

Question

我有一张名为“test”的表，其中包含数百万条记录。每行都包含一个浮点型“特征”，以及该特征在“id”项中出现的“次数”。该表的主键是“id”和“feature”的组合，即每个项可能具有多个特征。通常每个项目ID会有几百到几千个特征条目。

create table test 
(
    id      int not null,
    feature double not null,
    count   int not null
);

任务是查找与给定参考项最相似的500个项。相似性是根据两个项中相同的特征值数量来衡量的。我想到的查询如下所示，但即使正确使用索引，其执行计划仍包含“using temporary”和“using filesort”，这对我的用例来说性能不可接受。

select 
    t1.id,
    t2.id,
    sum( least( t1.count, t2.count )) as priority 
from test as t1
inner join test as t2 
     on t2.feature = t1.feature
where t1.id = {some user supplied id value} 
group by t1.id, t2.id 
order by priority desc
limit 500;

有没有关于如何改进这个的想法？方案可以根据需要进行修改并添加索引。

- BuschnicK

---

请问您能否发布 SHOW CREATE TABLE test 的输出结果？ - Quassnoi

创建表test ( id int(11) NOT NULL, feature double NOT NULL, count int(11) NOT NULL, KEY idx_one (feature), KEY idx_two (id) ) ENGINE=InnoDB DEFAULT CHARSET=utf8' - BuschnicK

如果您需要的话，我也可以发送给您一个2MB、1,000,000行的数据转储文件... - BuschnicK

你有多少个项目？SELECT COUNT(DISTINCT id) FROM test 返回什么？ - Quassnoi

对于大约1,000,000个条目的样本数据，有大约10,000个唯一项。这个比例很可能代表未来的插入情况。 - BuschnicK

按照我的建议创建一个表格。大约有5,000,000条记录，这并不算太多，维护成本相当低廉，查询速度也会很快。 - Quassnoi

Answer 1

根据当前的模式，这个查询很难进行改进。

你已经在feature上创建了索引，并且在当前的模式设计下，这是你所能做到的最好的。

问题在于“更相似”不是一种顺序关系。如果a与b比c更相似，那么不能推断出c与a之间的相似度低于b与a之间的相似度。因此，你不能建立一个描述这种关系的单一索引，需要为每个项目分别建立索引，这将使你的索引长度为N^2，其中N是项目数。

如果你总是只需要前500个项目，你可以将你的索引限制在这个数字（在这种情况下，它将包含500 * N个条目）。

MySQL不支持索引或材料化视图，所以你必须自己完成：

1. Create a table like this:

   CREATE TABLE similarity
           (
           id1 INT NOT NULL,
           id2 INT NOT NULL,
           similarity DOUBLE NOT NULL,
           PRIMARY KEY (id1, id2),
           KEY (id1, similarity)
           )
   

2. Whenever you insert a new feature into the table, reflect the changes in the similarity:

   INSERT
   INTO    similarity
   SELECT  @newid, id,
           LEAST(@newcount, count) AS ns
   FROM    test
   WHERE   feature = @newfeature
           AND id <> @newid
   ON DUPLICATE KEY UPDATE
   SET     similarity = similarity + ns;
   
   
   INSERT
   INTO    similarity
   SELECT  @newid, id,
           LEAST(@newcount, count) AS ns
   FROM    test
   WHERE   feature = @newfeature
           AND id <> @newid
   ON DUPLICATE KEY UPDATE
   SET     similarity = similarity + ns;
   

3. On a timely basis, remove the excess similarities:

   DELETE  s
   FROM    (
           SELECT  id1,
                   (
                   SELECT  similarity
                   FROM    similarity si
                   WHERE   si.id1 = s.id1
                   ORDER BY
                           si.id1 DESC, si.similarity DESC
                   LIMIT 499, 1
                   ) AS cs
           FROM    (
                   SELECT  DISTINCT id1
                   FROM    similarity
                   ) s
           ) q
   JOIN    similarity s
   ON      s.id1 = q.id1
           AND s.similarity < q.cs
   

4. Query your data:

   SELECT  id2
   FROM    similarity
   WHERE   id1 = @myid
   ORDER BY
           similarity DESC
   LIMIT 500
   

- Quassnoi

Answer 2

在主键（PK）中使用浮点数是致命的。对于唯一键（UK）、外键（FK）等约束，也不应该使用浮点数。

为了将SQL查询性能提高多倍，请尝试按以下方式更改您的架构：

CREATE TABLE test ( 
item_id      INTEGER,
feature_id INTEGER,
count   INTEGER );

CREATE TABLE features (
id   INTEGER, feature_value double not null );

CREATE TABLE items (
id   INTEGER, item_description varchar2(100) not null );

ALTER TABLE test ADD CONSTRAINT fk_test_item_id foreign key (item_id) references items(id);

ALTER TABLE test ADD CONSTRAINT fk_test_feature_id foreign key(feature_id) references features(id);

通过对测试表进行上述归一化处理，我已经将项目和特征分别放在了它们自己的表中。这不再是一个简单的映射表，而是承载着每个映射计数的表。

如果你现在使用稍作修改的SQL查询语句重新执行之前已经执行过的查询，应该会看到SQL查询性能有显著/极大的提升。

select t1.id, t2.id, sum( least( t1.count, t2.count )) as priority 
from test as t1 inner join test as t2 on t2.feature_id = t1.feature_id 
where t1.id = {some user supplied id value}
group by t1.id, t2.id 
order by priority desc
limit 500;

干杯！

- karthiks

---

我回到办公室后会尝试一下 - 谢谢你的建议，听起来很有道理！ - BuschnicK

那么为什么浮点数杀手会出现在这里呢？它只是要比较一些位而已，没有进行任何浮点数运算。 - Imre L

好的，我已经测试过了，它似乎有一点帮助，但不是很大。在两种情况下，查询计划看起来都是相同的，所以唯一可以改进的就是处理索引/比较中的整数与浮点数。这是一个微观层面上值得优化的地方，但我担心我需要先有一个更有效率的算法/查询。 - BuschnicK

Answer 3

一种优化方法是从自连接中排除该项本身：

inner join test as t2 
     on t2.feature = t1.feature and t2.id <> t1.id
                                    ^^^^^^^^^^^^^^

为了进一步提升速度，可以在(feature, id, count)上创建一个覆盖索引。

- Andomar

---

我已经避免了自连接，但为了使查询更简单而将其删除。在更大的方案中，它的性能影响是微不足道的。 - BuschnicK

我刚刚尝试了使用覆盖索引代替单独的索引，但它并没有消除临时/文件排序，所以帮助不大。恐怕只要我在计算值上排序，临时文件就无法避免。因此，需要进行模式更改或备用查询的问题。 - BuschnicK

@BuschnicK：表格中的数据有多频繁更改？更改是否需要立即在查询中可见？ - Andomar

它不断变化。更准确地说，现有条目永远不会发生改变，但新条目不断添加。 - BuschnicK

Answer 4

我会从这里开始……很想知道您所期望的性能。 我认为您不需要LEAST（t1与t2计数的最小值）。如果您首先基于ID = {某个值}进行where限定，那么显然会得到所有这些“features”。然后通过自连接只关注匹配的“features”，您就可以得到计数。由于您正在根据ID1和ID2进行拆分，因此各自的“feature”将被计算一次。在此查询结束时，由于我没有明确排除t2.ID等于{某个用户值}，因此它的计数应该是t1中feature的完全相同计数，而其下的任何其他内容则是您的其他最接近匹配项。

我会确保在ID和FEATURE上有索引。

select STRAIGHT_JOIN
      t1.id,
      t2.id, 
      count(*) as MatchedInBoth
   from 
      test as t1,
      test as t2
   where 
          t1.id = {some user value}
      and t1.feature = t2.feature
   group by
      t1.id,
      t2.id
   order by 
      MatchedInBoth desc 
   limit 
      500; 

结果可能会得到类似的东西

t1            t2           MatchedInBoth
{user value}  {user value} 275
{user value}  Other ID 1   270
{user value}  Other ID 2   241
{user value}  Other ID 3   218
{user value}  Other ID 4   197
{user value}  Other ID 5   163, etc

- DRapp

Answer 5

你能把它简化成一个表吗？使用子查询可能可以避免连接，如果子查询更快、有索引并且只执行一次，那么这将是一个胜利。类似这样（未经测试）。

选择
t2.id，
SUM（t2.count）作为优先级
来自测试的t2
其中t2.id = {一些用户提供的id值} AND
t2.count >（SELECT MIN（count）FROM test t1 WHERE id = {一些用户提供的值}）AND
t2.feature IN（SELECT feature FROM test t1 WHERE id = {一些用户提供的值}）
按t1.id分组
按优先级降序排序
限制500个;

如果这不起作用，Mysql很糟糕，无法意识到内部选择是常量表，并且会为每行重新执行它们。再次包含它们强制进行常量表查找。这是一个hack：


选择
t1.id,
SUM( t2.count ) as 优先级
从测试中 as t2
where t2.id = {一些用户提供的id值} AND
t2.count > (
SELECT * FROM (
SELECT MIN(count) FROM test t1 WHERE id= {一些用户提供的值} ) as const ) AND
t2.feature IN ( SELECT * from (
SELECT feature FROM test t1 WHERE id= {一些用户提供的值}) as const )
group by t1.id
order by 优先级 desc
limit 500;


- bot403

---

抱歉，我不认为这个查询能够提供等效的结果。 - BuschnicK

我认为你是正确的。通过将连接条件移动到带有子选择的where子句中，它可以正确地删除连接，但它不能复制正确的sum(least())逻辑。 - bot403