Оптимизация запросов MySQL к иерархическим данным
У меня есть достаточно устойчивая направленная граф порядка ~100k вершин и размера ~1k ребер. Он двумерный -постольку, поскольку его вершины могут быть идентифицированы парой целых чисел(x, y)(мощности ~100 x ~1000 )и все ребра строго возрастают в x.
Кроме того, существует словарь из ~1k (key, val)пар, связанных с каждой вершиной.
В настоящее время я храню граф в базе данных MySQL в трех (таблицах InnoDB ):таблице вершин (, которая, как я думаю, не имеет отношения к моему вопросу, поэтому я опустил включите его и ограничения внешнего ключа, которые ссылаются на него, в моих выдержках ниже ); стол со словарями; и «замыкающая таблица» связных вершин, столь красноречиво описанная Биллом Карвином.
Таблица словарей вершин определяется следующим образом:
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 с. Бился головой о кирпичную стену, пытаясь исправить ситуацию, но безрезультатно.
Можно ли улучшить запрос или следует рассмотреть другую структуру данных? Безмерно благодарен за ваши мысли!
ОБНОВЛЕНИЕ
У меня все еще ничего не получается,хотя я перестроил таблицы и обнаружил, что вывод EXPLAINнемного отличается от (, как показано выше, количество строк, извлеченных из v, увеличилось с 1 до 136! ); выполнение запроса по-прежнему занимает ~10 с.
Я действительно не понимаю, что здесь происходит. Запросы для получения всех (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