sql - mySQL:是否有可能使这个查询更快？

Question

我有一个包含数百万条目的表“test”。每行包含一个浮点“特征”和一个“计数”，该特征在项目“id”中出现的频率。该表的主键是“id”和“feature”的组合，即每个项目可能有多个特征。每个项目 ID 通常有几百到几千个特征条目。

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

任务是找到与给定引用项目最相似的 500 个项目。相似性以两个项目中相同特征值的数量来衡量。下面引用了我提出的查询，但尽管正确使用了索引，它的执行计划仍然包含“使用临时”和“使用文件排序”，为我的用例提供了 Not Acceptable 性能。

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;

关于如何改进这个的任何想法？可以根据需要修改架构并添加索引。

Answer 1

使用当前架构，此查询几乎无法改进。

您已经有了一个关于feature 的索引，这是您可以使用当前模式设计做的最好的事情。

问题是比更相似不是顺序关系。如果 a 与 b 的相似度高于与 c 的相似度，并不意味着 c 不太相似a 比 b 更重要。因此，您不能构建描述这种关系的单个索引，而需要分别为每个项目执行此操作，这会使您的索引 N^2 条目很长，其中 N 是项目的数量。

如果您总是只需要前 500 项，您可以将索引限制为该数字(在这种情况下它将包含 500 * N 项)。

MySQL 不支持索引或物化 View ，因此您必须自己做:

1. 像这样创建一个表:

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

2. 每当您向表中插入一个新特征时，反射(reflect)相似度中的变化:

   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. 及时去除多余的相似点:

   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. 查询您的数据:

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