mysql - 加快MYSQL中的自我加入

Question

我有一个不同对象之间的连接表，我基本上是在尝试使用自连接进行图遍历。我的表定义为：

CREATE TABLE `connections` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `position` int(11) NOT NULL,
  `dId` bigint(20) NOT NULL,
  `sourceId` bigint(20) NOT NULL,
  `targetId` bigint(20) NOT NULL,
  `type` bigint(20) NOT NULL,
  `weight` float NOT NULL DEFAULT '1',
  `refId` bigint(20) NOT NULL,
  `ts` bigint(20) NOT NULL,
  PRIMARY KEY (`id`),
  KEY `sourcetype` (`type`,`sourceId`,`targetId`),
  KEY `targettype` (`type`,`targetId`,`sourceId`),
  KEY `complete` (`dId`,`sourceId`,`targetId`,`type`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;

该表包含大约 3M 个条目（约 1K 类型 1、1M 类型 2 和 2M 类型 3）。

超过 2 或 3 跳的查询实际上非常快（当然接收所有结果需要一段时间），但是获取 3 跳的查询计数非常慢（> 30 秒）。

这是查询（返回 2M）：

SELECT
  count(*)
FROM
  `connections` AS `t0`
JOIN
  `connections` AS `t1` ON `t1`.`targetid`=`t0`.`sourceid`
JOIN
  `connections` AS `t2` ON `t2`.`targetid`=`t1`.`sourceid`
WHERE
  `t2`.dId = 1
  AND
  `t2`.`sourceid` = 1
  AND
  `t2`.`type` = 1
  AND
  `t1`.`type` = 2
  AND
  `t0`.`type` = 3;

这是相应的解释：

id  select_type  table  type  possible_keys                   key         key_len  ref                         rows  Extra  
1   SIMPLE       t2     ref   targettype,complete,sourcetype  complete    16       const,const                  100  Using where; Using index
1   SIMPLE       t1     ref   targettype,sourcetype           targettype   8       const                       2964  Using where; Using index
1   SIMPLE       t0     ref   targettype,sourcetype           sourcetype  16       const,travtest.t1.targetId  2964  Using index

编辑：这是添加和索引后的解释type：

id  select_type  table  type  possible_keys                        key         key_len  ref                         rows  Extra     
1   SIMPLE       t2     ref   type,complete,sourcetype,targettype  complete    16       const,const                 100   Using where; Using index
1   SIMPLE       t1     ref   type,sourcetype,targettype           sourcetype  16       const,travtest.t2.targetId    2   Using index
1   SIMPLE       t0     ref   type,sourcetype,targettype           sourcetype  16       const,travtest.t1.targetId    2   Using index

有没有办法改善这一点？

第二次编辑：

EXPLAN EXTENDED:
+----+-------------+-------+------+-------------------------------------+------------+---------+----------------------------+------+----------+--------------------------+
| id | select_type | table | type | possible_keys                       | key        | key_len | ref                        | rows | filtered | Extra                    |
+----+-------------+-------+------+-------------------------------------+------------+---------+----------------------------+------+----------+--------------------------+
|  1 | SIMPLE      | t2    | ref  | type,complete,sourcetype,targettype | complete   | 16      | const,const                |  100 |   100.00 | Using where; Using index |
|  1 | SIMPLE      | t1    | ref  | type,sourcetype,targettype          | sourcetype | 16      | const,travtest.t2.targetId |    1 |   100.00 | Using index              |
|  1 | SIMPLE      | t0    | ref  | type,sourcetype,targettype          | sourcetype | 16      | const,travtest.t1.targetId |    1 |   100.00 | Using index              |
+----+-------------+-------+------+-------------------------------------+------------+---------+----------------------------+------+----------+--------------------------+

SHOW WARNINGS;
+-------+------+--------------------------------------------------------------------------------------------+
| Level | Code | Message                                                                                    |
+-------+------+--------------------------------------------------------------------------------------------+
| Note  | 1003 | /* select#1 */ select count(0) AS `count(*)` from `travtest`.`connections` `t0`            |
|       |      | join `travtest`.`connections` `t1` join `travtest`.`connections` `t2`                      |
|       |      | where ((`travtest`.`t0`.`sourceId` = `travtest`.`t1`.`targetId`) and                       |
|       |      | (`travtest`.`t1`.`sourceId` = `travtest`.`t2`.`targetId`) and (`travtest`.`t0`.`type` = 3) |
|       |      | and (`travtest`.`t1`.`type` = 2) and (`travtest`.`t2`.`type` = 1) and                      |
|       |      | (`travtest`.`t2`.`sourceId` = 1) and (`travtest`.`t2`.`dId` = 1))                          |
+-------+------+--------------------------------------------------------------------------------------------+

score 1 · Accepted Answer

sourceid为,targetid和列创建索引，type然后尝试使用此查询：

SELECT
  count(*)
FROM
  `connections` AS `t0`
JOIN
  `connections` AS `t1` ON `t1`.`targetid`=`t0`.`sourceid` and `t1`.`type` = 2
JOIN
  `connections` AS `t2` ON `t2`.`targetid`=`t1`.`sourceid` and `t2`.dId = 1 AND `t2`.`sourceid` = 1 AND `t2`.`type` = 1
WHERE
  `t0`.`type` = 3;

- - - -更新 - - -

我认为这些索引是正确的，并且通过这些大表，您可以实现最佳优化。我认为您无法通过其他优化（例如表分区/分片）来改进此查询。

如果这些数据不经常更改或者我看到的唯一方法是垂直缩放，您可以实现某种缓存

score 1 · Accepted Answer

可能，您正在处理图形数据，对吗？

您的 3 跳查询有一点优化的机会。它是浓密的树。建立了很多联系。我认为 JOIN order 和 INDEX 是对的。

EXPLAIN 告诉我 t2 产生大约 100 个 targetId。如果您从 join 中删除 t2 并添加 t1.sourceId IN (100 targetId). 这将需要与 3 次自我加入相同的时间。

但是如何将 100 个目标分解为 10 个子 IN 列表。如果这减少了响应时间，多线程一次运行 10 个查询。

MySQL 没有并行功能。所以你做你自己。

你试过像jena、sesame这样的图形数据库吗？我不确定图形数据库是否比 MYSQL 快。

score 1 · Accepted Answer

这不是答案。仅供参考。

如果 MySQL 或其他数据库对您来说很慢，您可以实现自己的图形数据库。那么这篇论文Literature Survey of Graph Databases[1] 是关于 Graph Database 的一个很好的工作。调查了几个图数据库，让我们知道了很多技术。

SCALABLE SEMANTIC WEB DATA MANAGEMENT USING VERTICAL PARTITIONING[2] 引入垂直分区但是，你的 3M 边缘不大，垂直分区帮不了你。[2] 引入了另一个概念Materialized Path Expressions。我认为这可以帮助你。

[1] http://www.systap.com/pubs/graph_databases.pdf

[2] http://db.csail.mit.edu/projects/cstore/abadirdf.pdf

score 0 · Accepted Answer

您评论说您的查询返回 2M（假设您的意思是 200 万）是最终计数，或者只是它通过 200 万。您的查询似乎专门寻找单个 T2.ID、Source AND Type 连接到其他表，但从连接 0 开始。

我会删除您现有的索引并拥有以下索引，因此引擎不会尝试使用其他索引并导致其连接方式的混乱。此外，通过在两者中都有目标 ID（正如您已经拥有的那样）意味着这些将涵盖索引，并且引擎不必转到页面上的实际原始数据来确认任何其他标准或从中提取值。

唯一的索引是基于您的最终标准，如 T2 中的来源、类型和 ID。由于 targetID（索引的一部分）是菊花链中下一个的源，因此您对源和类型使用相同的索引，沿着链向上。任何索引都没有混淆

索引打开 (sourceId, type, dId, targetid)

我会尝试反转到希望是最小的集合并努力工作......就像

SELECT
      COUNT(*)
   FROM
      `connections` t2
         JOIN `connections` t1
            ON t2.targetID = t1.sourceid
            AND t1.`type` = 2
            JOIN `connections` t0
               ON t1.targetid = t0.sourceid
               AND t0.`type` = 3
   where
          t2.sourceid = 1
      AND t2.type = 1
      AND t2.dID = 1

mysql - 加快MYSQL中的自我加入

4 回答 4

Related

Reference