Таблица генов человеческого генома невелика, всего 60434 записей:
CREATE TABLE `genes-g38-201505` (
`chr` varchar(2) NOT NULL,
`left` bigint(20) NOT NULL,
`right` int(11) NOT NULL,
`Complement` int(11) NOT NULL,
`Name` tinytext NOT NULL,
`source` tinytext NOT NULL,
`ENSEMBL` tinytext NOT NULL,
`gene_version` tinytext NOT NULL,
`gene_name` tinytext NOT NULL,
`gene_source` tinytext NOT NULL,
`gene_biotypeid` tinytext NOT NULL,
`id` bigint(20) NOT NULL AUTO_INCREMENT,
UNIQUE KEY `id_UNIQUE` (`id`)
) ENGINE=MyISAM;
Таблица повторов человеческого генома, уже хуже - более 5 с половиной миллионов записей:
CREATE TABLE `repeats-g38-201505` (
`id` int(11) NOT NULL,
`chr` varchar(2) DEFAULT NULL,
`left` int(11) DEFAULT NULL,
`right` int(11) DEFAULT NULL,
`name` tinytext,
PRIMARY KEY (`id`)
) ENGINE=MyISAM;
Это - две служебных таблицы. Из них нам, по большому счёту, важны лишь chr - название хромосомы, left и right - левая и правая координата целого гена/повтора или его части (частей может быть несколько, в этом случае одному name соответствует несколько наборов {chr, left, right}) и name - название гена/повтора.
Все данные для таблиц.
Теперь данные экспериментов на тканях онкологических больных. Формат таблицы таков:
CREATE TABLE `51k-80-80-ignore-random-noreverse` (
`chr` varchar(2) NOT NULL,
`left` bigint(20) NOT NULL,
`right` bigint(20) NOT NULL,
`count` int(11) NOT NULL,
`id` bigint(20) NOT NULL AUTO_INCREMENT,
UNIQUE KEY `chr_left_right` (`chr`,`left`,`right`),
`id` bigint(20) NOT NULL AUTO_INCREMENT
) ENGINE=MyISAM;
он одинаков для каждого эксперимента. Каждая запись описывает паттерн ДНК, принадлежащий хромосоме chr, с координатами left и right, количеством штук count. Количество записей разное, от 4 до 7 с половиной миллиона на эксперимент. Каждая запись - уникальный набор по координатам {chr, left, right}
И финальная таблица, в которую нужно собрать данные 4х экспериментов:
CREATE TABLE `pk47-pk51-gene-repeat` (
`chr` varchar(2) NOT NULL,
`left` bigint(20) NOT NULL,
`right` bigint(20) NOT NULL,
`count_k51` int(11) DEFAULT '0',
`count_p51` int(11) DEFAULT '0',
`count_p47` int(11) DEFAULT '0',
`count_k47` int(11) DEFAULT '0',
`name_left` varchar(29) NOT NULL,
`name_right` varchar(17) NOT NULL,
UNIQUE KEY `pos_name` (`chr`,`left`,`right`,`name_left`,`name_right`)
) ENGINE=MyISAM;
Фактически, всё просто: нужно найти только те паттерны, которые левым краем попадают на ген, а правым - на повтор, посчитать их количество и вывести в сводную таблицу. С запросом вроде бы проблем не возникло, 4 раза повторяю такой запрос, меняя лишь count_k51 на count_p51 и саму таблицу-источник :
INSERT INTO `pk47-pk51-gene-repeat` (
`chr`,`left`, `right`,`count_k51`,`name_left`, `name_right`
)
SELECT
a.`chr`, a.`left`, a.`right`, a.`count` as `count_k51`,
g.`name` as `name_left`,
r.`name` as `name_right`
FROM `
51k-80-80-ignore-random-noreverse` a,
`genes-g38-201505` g,
`repeats-g38-201505` r
WHERE
a.`chr`=g.`chr` and a.`chr`=r.`chr` and
a.`left` < g.`right` and a.`left` > g.`left` and
a.`right` < r.`right` and a.`right` > r.`left`
on duplicate key
update
`pk47-pk51-gene-repeat`.`count_k51`=a.`count`;
В первый запуск on duplicate key можно не использовать. Наверное, можно составить и единственный запрос вместо 4х, но он будет чрезвычайно громоздким, и я пока решил пробовать так.
Разумеется, запрос не выполнился, отвалился по таймауту, который я и так сильно увеличил. limit 0,1000; limit 1001,2000 и так далее, как я понимаю, использовать бесполезно, поскольку каждый следующий этап сервер всё равно будет проходить предыдущие.
Решил итерировать запросы по id, добавляя ограничение 20000*i< a.id <20000*(i+1) в запрос, но ситуация не улучшилась, видимо, id надо переопределить, либо заставить сервер проводить данную проверку первой.
Как итог, нужны идеи, как можно оптимизировать запрос, перестроить таблицы или поменять подход, чтобы решить эту задачу (не обязательно чистым SQL-запросом, работать с базой из языков программирования я умею). Скажу спасибо и за советы по физическому ускорению сервера: памяти на машине 32Гб, сервер использует мало, может, какие-то переменные подкрутить?
Update 1. Привожу результаты EXPLAIN для запроса:
Изначальное состояние:
# id, select_type, table, type, possible_keys, key, key_len, ref, rows, Extra
'1', 'SIMPLE', 'g', 'ALL', NULL, NULL, NULL, NULL, '60433', NULL
'1', 'SIMPLE', 'a', 'ref', 'chr_left_right', 'chr_left_right', '4', 'dna_homo_pairs.g.chr', '47216', 'Using index condition'
'1', 'SIMPLE', 'r', 'ALL', NULL, NULL, NULL, NULL, '5317291', 'Using where; Using join buffer (Block Nested Loop)'
Добавлены индексы (chr, left, right) по совету @Mike:
# id, select_type, table, type, possible_keys, key, key_len, ref, rows, Extra
'1', 'SIMPLE', 'a', 'ALL', 'chr_left_right', NULL, NULL, NULL, '4721638', NULL
'1', 'SIMPLE', 'g', 'ref', 'chr_left_right', 'chr_left_right', '4', 'methyl_base.a.chr', '604', 'Using index condition'
'1', 'SIMPLE', 'r', 'ref', 'chr_left_right', 'chr_left_right', '5', 'methyl_base.a.chr', '53172', 'Using index condition'
Update 2. Заставить mysqld работать в несколько потоков.
Взглянул на загрузку CPU во время запроса. Поскольку сейчас я работаю в монопольном режиме, я один обращаюсь в локальному серверу. Можно ли как-то заставить mysqld обрабатывать один запрос в несколько потоков? А то 8 ядер/16 потоков в его распоряжении, а он пользует только один.
Кстати, раскидывание разных таблиц в папки на разных физических жестких дисках даёт, пусть небольшое, но ускорение работы.
Update 3 На данный момент я программно разбил все исходные таблицы в зависимости от того, какая хромосома и скрипт (точнее, серия скриптов, тоже вызываются программно) сейчас выглядит так ( допустим, обрабатывается 7я хромосома):
INSERT INTO `pk47-pk51-gene-repeat` (
`chr`,`left`, `right`,`count_k51`,`name_left`, `name_right`
)
SELECT
"7", a.`left`, a.`right`, a.`count` as `count_k51`,
g.`name` as `name_left`,
r.`name` as `name_right`
FROM `
51k-80-80-ignore-random-noreverse-chr7` a,
`genes-g38-201505-chr7` g,
`repeats-g38-201505-chr7` r
WHERE
a.`left` < g.`right` and a.`left` > g.`left` and
a.`right` < r.`right` and a.`right` > r.`left`
on duplicate key
update
`pk47-pk51-gene-repeat`.`count_k51`=a.`count`;
Но особого прогресса не отмечаю.
Ответ
Обычные методы оптимизации, применяемые СУБД обычно берут 1 запись из первой таблицы и ищут по всей второй таблице подходящие записи. При наличии индекса это происходит довольно быстро, за log2(m), но все таки это обращения к десятку страниц индекса ... Ваш запрос при обычном Join должен выполняться в лучшем случае за O=n*(log2(m)+log2(k)) (Где n,m,k количество записей в 3х таблицах в запросе) (хотя если посмотреть статьи по оптимизации MySQL там вообще выйдет O=n*log2(m)*log2(k))
С другой стороны, ваши данные довольно специфичны (жаль СУБД не способна это оценить). В таблицах genes и repeats лежат не пересекающиеся интервалы, следовательно при сортировке по полю left записи оказываются отсортированы и по right. В таблицах с паттернами же интервалы временами пересекаются, в итоге при сортировке по left поле right иногда немного "возвращается назад", но таких ситуаций порядка 8%.
Сравнивать один отсортированный список с отсортированным же списком возможных интервалов можно гораздо проще, идя параллельно по обоим спискам одновременно, сдвигая указатель вперед в том списке, в котором записи еще меньше, чем в другом. Причем так можно проходить параллельно по более чем по 2 спискам одновременно. При этом сложность поиска оказывается O=n+m+k
К сожалению из за того, что список паттернов не может быть одновременно отсортирован и по left и по right нам иногда надо откатывать указатель в repeats немного назад. В MySQL при работе с курсорами это невозможно, по этой причине я решил запоминать те записи, которые выпали из последовательности возрастающих right и при этом могли попасть в интервал предыдущей записи repeats (таких оказалось совсем мало 2k из 438k). Этого можно избежать помня несколько последних записей repeats, но на MySQL это будет слишком громоздко. Сохраненные записи приходится обрабатывать за второй проход, проходя по repeats отсортированной по полю right
На основе вышеизложенного у меня вышла следующая хранимая процедура:
create table miss_rows(`left` int not null, `right` int not null,
`count` int not null,`name_left` varchar(100) not null);
drop procedure if exists genjoin;
delimiter $$
create procedure genjoin()
begin
declare endOfData integer default 0;
declare done int default 0;
declare cnt int default 0;
declare g_left int default 0; -- Переменные для genes
declare g_right int default 0;
declare g_name varchar(100);
declare gen_eof int default 0; -- Признак конца genes
declare r_left int default 0; -- Переменные для repeats
declare r_right int default 0;
declare r_Oright int default 0; -- Значение правого конца предыдущей записи
declare r_name varchar(100);
declare rep_eof int default 0; -- Признак конца repeats
declare t_left int default 0; -- Переменные рабочей таблицы
declare t_right int default 0;
declare t_Oright int default 0; -- Значение правого конца предыдущей записи
declare t_count int default 0;
declare gen_cur cursor for
select `left`,`right`,`name` from genes order by 1,2;
declare rep_cur cursor for
select `left`,`right`,`name` from repeats order by 1,2;
declare data_cur cursor for
select `left`,`right`,`count` from t47k order by 1,2;
declare miss_cur cursor for
select `left`, `right`, `count`, `name_left` from miss_rows order by 2;
declare rep2_cur cursor for
select `left`,`right`,`name` from repeats order by 2;
DECLARE CONTINUE HANDLER FOR SQLSTATE '02000' SET endOfData=1;
open gen_cur;
open rep_cur;
open data_cur;
truncate table miss_rows;
row: while done=0 do
if t_Oright
while t_right >= r_right and rep_eof=0 do
if r_Oright
insert into `pk47-pk51-gene-repeat`
(`left`, `right`, `count_k47`,`name_left`,`name_right`)
values(t_left, t_right, t_count, g_name, r_name)
on duplicate key update `count_k47`=t_count;
end while;
close gen_cur;
close rep_cur;
close data_cur;
open rep2_cur;
open miss_cur;
set r_left=0,r_right=0,rep_eof=0,done=0;
while done=0 do
fetch miss_cur into t_left, t_right, t_count, g_name;
if endOfData=1 then set done=1,endOfData=0; end if;
while t_right >= r_right and rep_eof=0 do
fetch rep2_cur into r_left, r_right, r_name;
if endOfData=1 then set rep_eof=1,endOfData=0; end if;
end while;
if t_right > r_left then
insert into `pk47-pk51-gene-repeat`
(`left`, `right`, `count_k47`,`name_left`,`name_right`)
values(t_left, t_right, t_count, g_name, r_name)
on duplicate key update `count_k47`=t_count;
end if;
end while;
end$$
Время выполнения данной процедуры на контрольном примере из 6k / 444k / 438k записей, составило 45 секунд ... Правда в контрольном примере не было поля chr, когда оно есть, оно конечно должно так же участвовать в сортировке списков и сравниваться во всех условиях. Таблицы 47, 51 и т.п. стоит обрабатывать за отдельные проходы. Если бы была возможность возвращаться назад, можно было бы попробовать обработать все за один проход. Аналогичный алгоритм на perl, беря данные из отсортированных csv файлов работает 4 секунды...
В связи с тем, что в repeats все таки могут быть пересечения интервалов, все немного сложнее и для получения всех вариантов (коих примерно на 200 записей больше изначального варианта (в 130k записей)) лучше все таки использовать массивы, что бы можно было заглядывать немного вперед. на perl это выглядит так
Комментариев нет:
Отправить комментарий