Как правильно построить работу с БД, хранящей огромные данные генома человека?
1,00
р.
Таблица генов человеческого генома невелика, всего 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 надо переопределить, либо заставить сервер проводить данную проверку первой. <br>Как итог, нужны идеи, как можно оптимизировать запрос, перестроить таблицы или поменять подход, чтобы решить эту задачу (не обязательно чистым 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_left >= g_right and gen_eof=0 do fetch gen_cur into g_left, g_right, g_name if endOfData=1 then set gen_eof=1,endOfData=0 end if end while
while t_right >= r_right and rep_eof=0 do if r_Oright if t_left <= g_left or t_left >= g_right then iterate row end if if t_Oright > t_right then -- Концы не по порядку, пересечение интервалов ! if t_right < r_Oright then -- Мы могли попасть в предыдущую запись repeats ! -- но пропустили ее ... insert into miss_rows values(t_left, t_right, t_count,g_name) end if end if if t_right <= r_left or t_right>= r_right then iterate row end if
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 это выглядит так
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 надо переопределить, либо заставить сервер проводить данную проверку первой. <br>Как итог, нужны идеи, как можно оптимизировать запрос, перестроить таблицы или поменять подход, чтобы решить эту задачу (не обязательно чистым 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_left >= g_right and gen_eof=0 do fetch gen_cur into g_left, g_right, g_name if endOfData=1 then set gen_eof=1,endOfData=0 end if end while
while t_right >= r_right and rep_eof=0 do if r_Oright if t_left <= g_left or t_left >= g_right then iterate row end if if t_Oright > t_right then -- Концы не по порядку, пересечение интервалов ! if t_right < r_Oright then -- Мы могли попасть в предыдущую запись repeats ! -- но пропустили ее ... insert into miss_rows values(t_left, t_right, t_count,g_name) end if end if if t_right <= r_left or t_right>= r_right then iterate row end if
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 это выглядит так
