我为了〜100K的顶点和大小〜1K边缘的一个相当稳定的有向图。 它是二维的，只要它的顶点可通过一对整数来标识(x, y)基数〜100×1000〜）和所有边缘都在严格递增x 。
有进一步〜1k的一个字典(key, val)与每个顶点相关联的对。
我目前存储在三个（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)对，使得对于每一个这样的对，与该识别的所有顶点x具有其字典内，用于将一个值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 Using index; Using temporary
1 SIMPLE c ref PRIMARY,reverse,fx,rx PRIMARY 2 db.k.x 1 Using where
1 SIMPLE v ref PRIMARY,dict PRIMARY 4 const,db.c.head_y 136 Using index
1 SIMPLE u eq_ref PRIMARY,dict PRIMARY 156 db.c.tail_x,db.c.tail_y,db.k.key 1 Using where
但此查询需要10秒〜完成。 被敲打我的头撞墙试图改善的事项，但无济于事。
可以查询得到改善，或者，我应该考虑不同的数据结构？ 万分感谢您的想法！
UPDATE
我还是这个越来越行不通，虽然我没有重建表，发现EXPLAIN输出略有不同（如现在如上图所示，从提取的行数v从1增加到136！）; 查询仍然采取〜10S执行。
我真的不明白是怎么回事。 查询获得所有(x, y, SpecialValue)和所有的(x, y, key)元组是非常快的（〜30毫秒和150毫秒〜分别）两种，但本质上连接两个花费的时间比他们的合并时间长了五十次..我怎样才能提高执行加入所需的时间？
的输出SHOW VARIABLES LIKE '%innodb%'; 下面：
Variable_name Value
------------------------------------------------------------
have_innodb YES
ignore_builtin_innodb ON
innodb_adaptive_flushing ON
innodb_adaptive_hash_index ON
innodb_additional_mem_pool_size 2097152
innodb_autoextend_increment 8
innodb_autoinc_lock_mode 1
innodb_buffer_pool_size 1179648000
innodb_change_buffering inserts
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 ON
innodb_fast_shutdown 1
innodb_file_format Antelope
innodb_file_format_check Barracuda
innodb_file_per_table ON
innodb_flush_log_at_trx_commit 1
innodb_flush_method O_DIRECT
innodb_force_recovery 0
innodb_io_capacity 200
innodb_lock_wait_timeout 50
innodb_locks_unsafe_for_binlog OFF
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 OFF
innodb_spin_wait_delay 6
innodb_stats_method nulls_equal
innodb_stats_on_metadata ON
innodb_stats_sample_pages 8
innodb_strict_mode OFF
innodb_support_xa ON
innodb_sync_spin_loops 30
innodb_table_locks ON
innodb_thread_concurrency 0
innodb_thread_sleep_delay 10000
innodb_use_sys_malloc ON
innodb_version 1.0.16
innodb_write_io_threads 4
Answer 1:
无需花费时间测试它，你提供了一个不完整的例子吗？ 你一定要尝试连接表的重新排序 。 解释输出提供了一些信息，比方说通过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
;
“行”建议“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
;
希望这可以帮助。
UPDATE（避免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
;
Answer 2:
其他人可能不同意，但我已经和定期提供STRAIGHT_JOIN用于查询......一旦你知道的数据和关系。 作为您的WHERE子句是对“V”表的别名和它的“x”的价值，你是好与索引。 此举在靠前的位置，然后从该加入。
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}
好奇地想知道这个调整成效如何
Answer 3:
尝试重建阶段中的查询; 或者至少给我们一些更多的积分，以确定瓶颈在哪里。 以下查询的一些组合应该给你合理的性能，是否有可能与出修改架构或数据集。
什么是（有一个SpecialKey即）行和exec时间用于获取合适的尾巴verticies列表下面的查询数
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.
同样，我希望这些回报或者小的结果集的那一个，或者至少是快速产生结果。 如果低基数及大结果应用于不同。
如果它跌倒在这一点上，以及有没有它越变越快申请的最后阶段的太多的希望和最佳尝试不同的方法。
由于头部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不同）？
如果它的快速和/或小，尝试使用它作为一个子查询和连接到SpecialKeys＆VertexDictionary的任何其它子查询potentiall如果这是小（即前三个查询之一，如果他们的工作很好）。
Answer 4:
我怀疑你的问题是一切的语法
（ k 。 x ， k 。 key ）=（ u 。 x ， u 。 key ）
你可以重写为？
KX = YX和k.key = u.key
当你有一个条款的左手侧的计算，数据库管理系统不能优化。 通过设置比较的直接比较，你可以改善你的表现。
如
年（my_date）= '2012'
比慢
'2012'=年（my_date）
我不知道如果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
等等...
第三优化
如果选择2帮助，您可能要创建索引视图，并从这些，而不是直接从表中工作。
第四优化
不使用MySQL。 除非你有一个团队的DBA不断监视性能和调整的，你会遇到不好的时候与MySQL。 MySQL的是罚款和快速与简单的事情，但如果你做任何事情比较复杂的开始吸引非常糟糕。 4年前，我从MySQL迁移到SQL Server Express和我10分钟查询了<2秒，相同的表，索引和查询......
如果你想开源，Postgres的是比MySQL聪明得多，以及
创建结合了第一3个表即在v.key索引，u.val字段的图。 然后运行查询离4表和视图。 确保指标都是建立在视图运行前。
Answer 5:
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
Answer 6:
我不认为这迫使specifique指标的使用是个不错的想法。 Mysql的优化器有常不错的估计。
你有一个索引v 。 x ？
文章来源: Optimising MySQL queries across hierarchical data
