13

我有一个相当稳定的有向图，其阶数约为 100k 个顶点，边数约为 1k。它是二维的，因为它的顶点可以通过一对整数(x, y)（基数 ~100 x ~1000）来识别，并且所有边都严格递增x。

此外，还有一个(key, val)与每个顶点相关联的约 1k 对字典。

我目前将图形存储在三个（InnoDB）表的 MySQL 数据库中：一个顶点表（我认为这与我的问题无关，所以我省略了包括它和引用的外键约束它在我下面的摘录中）；存放字典的表；以及 Bill Karwin 雄辩地描述的连接顶点的“闭合表”。

顶点字典表定义如下：

CREATE TABLE `VertexDictionary` (
  `x`   smallint(6) unsigned NOT NULL,
  `y`   smallint(6) unsigned NOT NULL,
  `key` varchar(50) NOT NULL DEFAULT '',
  `val` smallint(1) DEFAULT NULL,
  PRIMARY KEY (`x`, `y`  , `key`),
  KEY  `dict` (`x`, `key`, `val`)
);

连接顶点的闭包表为：

CREATE TABLE `ConnectedVertices` (
  `tail_x` smallint(6) unsigned NOT NULL,
  `tail_y` smallint(6) unsigned NOT NULL,
  `head_x` smallint(6) unsigned NOT NULL,
  `head_y` smallint(6) unsigned NOT NULL,
  PRIMARY KEY   (`tail_x`, `tail_y`, `head_x`),
  KEY `reverse` (`head_x`, `head_y`, `tail_x`),
  KEY `fx` (`tail_x`, `head_x`),
  KEY `rx` (`head_x`, `tail_x`)
);

还有一个字典(x, key)对，这样对于每个这样的对，所有用 that 标识的顶点x在它们的字典中都有一个 that 的值key。该字典存储在第四个表中：

CREATE TABLE `SpecialKeys` (
  `x`   smallint(6) unsigned NOT NULL,
  `key` varchar(50) NOT NULL DEFAULT '',
  PRIMARY KEY (`x`),
  KEY `xkey`  (`x`, `key`)
);

我经常希望提取具有特定 的所有顶点的字典中使用的键集，以及任何连接到左侧x=X的相关值：SpecialKeys

SELECT DISTINCT
  `v`.`key`,
  `u`.`val`
FROM
       `ConnectedVertices` AS `c`
  JOIN `VertexDictionary`  AS `u` ON (`u`.`x`, `u`.`y`  ) = (`c`.`tail_x`, `c`.`tail_y`)
  JOIN `VertexDictionary`  AS `v` ON (`v`.`x`, `v`.`y`  ) = (`c`.`head_x`, `c`.`head_y`)
  JOIN `SpecialKeys`       AS `k` ON (`k`.`x`, `k`.`key`) = (`u`.`x`, `u`.`key`)
WHERE
  `v`.`x` = X
;

其EXPLAIN输出为：

id select_type table type possible_keys key key_len ref rows Extra
 1 SIMPLE k index PRIMARY,xkey xkey 154 NULL 40 使用索引；使用临时
 1 SIMPLE c ref PRIMARY,reverse,fx,rx PRIMARY 2 db.kx 1 使用 where
 1 SIMPLE v ref PRIMARY,dict PRIMARY 4 const,db.c.head_y 136 使用索引
 1 SIMPLE u eq_ref PRIMARY,dict PRIMARY 156 db.c.tail_x,db.c.tail_y,db.k.key 1 使用 where

但是这个查询需要大约 10 秒才能完成。一直把我的头撞在砖墙上试图改善问题，但无济于事。

可以改进查询，还是应该考虑不同的数据结构？非常感谢您的想法！

更新

尽管我确实重建了表并发现EXPLAIN输出略有不同，但我仍然无能为力（如上所示，从中获取的行数v已从 1 增加到 136！）；查询仍然需要大约 10 秒才能执行。

我真的不明白这里发生了什么。获取所有元组(x, y, SpecialValue)和所有(x, y, key)元组的查询都非常快（分别约为 30 毫秒和 150 毫秒），但实际上加入这两者的时间比它们的总时间长 50 倍......我如何才能缩短执行该连接所花费的时间？

下面的输出SHOW VARIABLES LIKE '%innodb%';：

变量名值
-------------------------------------------------- ----------
have_innodb 是
ignore_builtin_innodb ON
innodb_adaptive_flushing ON
innodb_adaptive_hash_index 开启
innodb_additional_mem_pool_size 2097152
innodb_autoextend_increment 8
innodb_autoinc_lock_mode 1
innodb_buffer_pool_size 1179648000
innodb_change_buffering 插入
innodb_checksums ON
innodb_commit_concurrency 0
innodb_concurrency_tickets 500
innodb_data_file_path ibdata1:10M:autoextend
innodb_data_home_dir /rdsdbdata/db/innodb
innodb_doublewrite 开启
innodb_fast_shutdown 1
innodb_file_format 羚羊
innodb_file_format_check 梭子鱼
innodb_file_per_table ON
innodb_flush_log_at_trx_commit 1
innodb_flush_method O_DIRECT
innodb_force_recovery 0
innodb_io_容量 200
innodb_lock_wait_timeout 50
innodb_locks_unsafe_for_binlog 关闭
innodb_log_buffer_size 8388608
innodb_log_file_size 134217728
innodb_log_files_in_group 2
innodb_log_group_home_dir /rdsdbdata/log/innodb
innodb_max_dirty_pages_pct 75
innodb_max_purge_lag 0
innodb_mirrored_log_groups 1
innodb_old_blocks_pct 37
innodb_old_blocks_time 0
innodb_open_files 300
innodb_read_ahead_threshold 56
innodb_read_io_threads 4
innodb_replication_delay 0
innodb_rollback_on_timeout 关闭
innodb_spin_wait_delay 6
innodb_stats_method nulls_equal
innodb_stats_on_metadata 开启
innodb_stats_sample_pages 8
innodb_strict_mode 关闭
innodb_support_xa 开启
innodb_sync_spin_loops 30
innodb_table_locks 开启
innodb_thread_concurrency 0
innodb_thread_sleep_delay 10000
innodb_use_sys_malloc 开启
innodb_version 1.0.16
innodb_write_io_threads 4
4

6 回答 6

2

没有花时间测试它，你提供了一个不完整的例子？您绝对应该尝试重新排序连接的表。解释输出提供了一些信息，假设通过 key_len 排序应该是启发式最快的。我相信，要过滤的第一个表应该列在最后，以防优化器无法解决这个问题。

所以，假设'c，v，k，u'顺序是最好的。

SELECT DISTINCT
  `v`.`key`,
  `u`.`val`
FROM
  `VertexDictionary`  AS `u`
  JOIN `SpecialKeys`       AS `k` ON (`k`.`x`, `k`.`key`) = (`u`.`x`, `u`.`key`)
  JOIN `VertexDictionary`  AS `v`
  JOIN `ConnectedVertices` AS `c` ON (`u`.`x`, `u`.`y`  ) = (`c`.`tail_x`, `c`.`tail_y`)
           AND (`v`.`x`, `v`.`y`  ) = (`c`.`head_x`, `c`.`head_y`)
WHERE
  `v`.`x` = X
;

'rows' 会建议 'c/u, k, v' 顺序，但这取决于数据：

SELECT DISTINCT
  `v`.`key`,
  `u`.`val`
FROM
  `VertexDictionary`  AS `u`
  JOIN `VertexDictionary`  AS `v`
  JOIN `SpecialKeys`       AS `k` ON (`k`.`x`, `k`.`key`) = (`u`.`x`, `u`.`key`)
  JOIN `ConnectedVertices` AS `c` ON (`u`.`x`, `u`.`y`  ) = (`c`.`tail_x`, `c`.`tail_y`)
                                 AND (`v`.`x`, `v`.`y`  ) = (`c`.`head_x`, `c`.`head_y`)
 WHERE
  `v`.`x` = X
;

希望这可以帮助。

更新（避免 varchar 连接）：

SELECT DISTINCT
  `v`.`key`,
  `u`.`val`
FROM
       `ConnectedVertices` AS `c`
  JOIN `VertexDictionary`  AS `u` ON (`u`.`x`, `u`.`y`  ) = (`c`.`tail_x`, `c`.`tail_y`)
  JOIN `VertexDictionary`  AS `v` ON (`v`.`x`, `v`.`y`  ) = (`c`.`head_x`, `c`.`head_y`)
WHERE
  (`u`.`x`, `u`.`key`) IN (SELECT `k`.`x`, `k`.`key` FROM `SpecialKeys` AS `k`)
AND
  `v`.`x` = X
;
于 2012-04-20T23:10:45.383 回答
0

我不认为强制使用特定索引是一个好主意。Mysql 优化器通常有很好的估计。

你有索引吗v？x?

于 2012-04-27T15:34:55.813 回答
0

我怀疑你的问题是语法的一切

( k. x, k. key) = ( u. x, u. key)

可以改写成吗？

kx = yx 和 k.key = u.key

当您在子句的左侧进行计算时，dbms 无法优化。通过将比较设置为直接比较，您可以提高性能。

例如

年（我的日期）='2012'

比

'2012' = 年（我的日期）

我不确定mysql是否将比较视为列比较或计算。

请尝试修改您的查询以进行列值比较。

二次优化

另外 - 您正在交叉连接 4 张桌子。乘法不是加法 - 它是指数的。你确定这是你想要的吗？从最小的结果集开始，然后只将该结果集加入下一个集，您可能会得到更好的服务。

select a.c1
from (
select t1.c1
from t1
join t2 on t1.c1 = t2.c1
) a
join t3 on t3.c1 = a.c1

ETC...

第三次优化

如果选项 2 有帮助，您可能希望创建索引视图并从这些视图而不是直接从表中工作。

第四次优化

不要使用mysql。除非您有一个 dbas 团队不断监控性能和调整，否则您将遇到 mysql 的糟糕时期。mysql 在简单的事情上很好而且很快，但是如果你做一些中等复杂的事情，它就会变得很糟糕。4 年前，我从 mysql 迁移到 sql server express，我的 10 分钟查询用相同的表、索引和查询花费了 <2 秒...

如果你想要开源，postgres 也比 mysql 聪明得多

创建一个视图，其中包含在 v.key、u.val 字段上编制索引的前 3 个表。然后从第 4 个表和视图中运行查询。在运行之前确保索引是建立在视图上的。

于 2012-04-26T16:01:21.273 回答
0

尝试分阶段重建查询；或者至少给我们更多的点来确定瓶颈在哪里。如果可以在不修改架构或数据集的情况下，以下查询的某些组合应该可以为您提供合理的性能。

以下查询的行数和执行时间是多少，以获取合适的尾顶点列表（即，具有 SpecialKey）

SELECT -- DISTINCT
    vd.x as tail_x, vd.y as tail_y, vd.val
FROM
    VertexDictionary vd
WHERE
    EXISTS (
        SELECT
            1
        FROM
            SpecialKeys sk
        WHERE
            vd.x = sk.x
        AND
            vd.key = sk.key
    )

或者

SELECT -- DISTINCT
    vd.x as tail_x, vd.y as tail_y, vd.val
FROM
    VertexDictionary vd
JOIN
    SpecialKeys sk
ON
    vd.x = sk.x
AND
    vd.key = sk.key

或者

SELECT -- DISTINCT
    vd.x as tail_x, vd.y as tail_y, vd.val
FROM
    VertexDictionary vd
WHERE
(vd.x, vd.key) IN (SELECT x, key FROM SpecialKeys)
-- also could try vd.key IN (SELECT sk.key FROM SpecialKeys sk WHERE sk.x = vd.x)

我希望其中一个返回小的结果集，或者至少可以快速产生结果。如果低基数和大结果应用不同。

从前两个查询中选择最好的一个，然后添加到下一步：将这些合适的“尾巴”连接到“合适的头”

SELECT -- DISTINCT
    cv.head_y as y,
    tv.val
FROM
(
    -- ADD SUB QUERY HERE also try nesting the subquery like: (select tail_x, tail_y, val from ([SUBQUERY]) as sq)

) as tv -- tail verticies
JOIN
    ConnectedVerticies cv
ON
    cv.tail_x = tv.tail_x
AND
    cv.tail_y = tv.tail_y
WHERE
    cv.head_x = X -- lets reduce the result set here.

同样，我希望其中一个返回小的结果集，或者至少可以快速产生结果。如果低基数和大结果应用不同。

如果它在这一点上倒下，那么应用最后一个阶段的速度并没有太大希望，最好尝试不同的方法。

由于从前面的查询中知道了 head x，我们现在只需要加入 head_y 和 X 即可获得 v.key

SELECT DISTINCT
    inner_query.val,
    head.key
FROM
(
 -- previous nested subquery behemoth here, again, try a few things that might work.

) as inner_query
JOIN
    VertexDictionary as head
ON
    head.x = X
AND
    head.y = inner_query.y

另一种方法是获取 head.key、tail_x 和 tail_y 的列表

SELECT -- DISTINCT
    cv.tail_x as x,
    cv.tail_y as y,
    vd.key
FROM
    VertexDictionary vd
JOIN
    ConnectedVerticies cv
ON
    cv.head_x = vd.x
AND
    cv.head_y = vd.y
WHERE
    vd.head_x = X

这需要多长时间才能执行，有和没有不同？有多少结果（w & w/o distinct）？

如果它很快和/或很小，请尝试将其用作子查询，并加入到 SpecialKeys 和 VertexDictionary 的另一个子查询（如果它们运行良好的话）。

于 2012-04-25T12:29:28.457 回答
0

其他人可能不同意，但我已经并定期提供 STRAIGHT_JOIN 用于查询......一旦你知道数据和关系。由于您的 WHERE 子句针对“V”表别名并且它是“x”值，因此您对索引很好。将 THAT 移到前面位置，然后从那里加入。 

SELECT STRAIGHT_JOIN DISTINCT
      v.`key`,
      u.`val`
   FROM
      VertexDictionary AS v 

         JOIN ConnectedVertices AS c
            ON v.x = c.head_x
            AND v.y = c.head_y

            JOIN VertexDictionary AS u 
               ON c.tail_x = u.x 
               AND c.tail_y = u.y

               JOIN SpecialKeys AS k
                  ON u.x = k.x
                  AND u.key = k.key
   WHERE
      v.x = {some value}

很想知道这种重新调整如何为您服务

于 2012-04-20T17:12:01.137 回答
0

DISTINCT往往是个坏朋友。尝试将其替换为GROUP BY. 像这样 ：

SELECT sub.key, sub.val
FROM (
    SELECT 
      v.key,
      u.val
    FROM
      ConnectedVertices AS c
      JOIN VertexDictionary  AS u ON (u.x, u.y  ) = (c.tail_x, c.tail_y)
      JOIN VertexDictionary  AS v ON (v.x, v.y  ) = (c.head_x, c.head_y)
      JOIN SpecialKeys       AS k ON (k.x, k.key) = (u.x, u.key)
    WHERE (v.x = @X)
) AS sub
GROUP BY sub.key, sub.val

更新：

然后尝试以下查询强制使用索引：

SELECT DISTINCT
  v.key,
  u.val
FROM
  ConnectedVertices AS c USE INDEX (fx,rx)
  JOIN VertexDictionary  AS u USE INDEX (primary) ON (u.x, u.y  ) = (c.tail_x, c.tail_y) 
  JOIN VertexDictionary  AS v USE INDEX (primary) ON (v.x, v.y  ) = (c.head_x, c.head_y)
  JOIN SpecialKeys       AS k USE INDEX (primary) ON (k.x, k.key) = (u.x, u.key)
WHERE (v.x = @X)

如果还是不行，试试这个：

SELECT DISTINCT
  v.key,
  u.val
FROM
       ConnectedVertices AS c
  JOIN VertexDictionary  AS u ON (u.x=c.tail_x) AND (u.y=c.tail_y)
  JOIN VertexDictionary  AS v ON (v.x=@X) AND (v.y=c.head_y)
  JOIN SpecialKeys       AS k ON (k.x=u.x) AND (k.key=u.key)
WHERE
  v.x = @X
于 2012-04-26T23:22:01.777 回答