人类基因组的基因表很小,只有 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;
人类基因组的重复表,已经更糟了——超过 550 万个条目:
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 对我们很重要 - 染色体的名称,左右 - 整个基因/重复或其部分的左右坐标(可能有几个部分,在这种情况下是几组{chr, left, right 对应一个名称}) 和名称是基因/重复的名称。
现在是癌症患者组织的实验数据。表格格式为:
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 染色体的 DNA 模式,带有左右坐标,计数。记录的数量是不同的,每个实验从 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`;
在第一次运行时,可以省略重复键。可能可以进行单个查询而不是 4x,但这会非常麻烦,现在我决定尝试一下。
当然,请求没有执行,由于超时而下降,我已经增加了很多。limit 0,1000; limit 1001,2000
依此类推,据我了解,使用它是没用的,因为服务器的每个下一个阶段仍然会经历前一个阶段。
我决定通过 迭代请求id
,对请求添加限制20000*i< a.id <20000*(i+1)
,但情况并没有改善,显然需要重新定义 id,或者应该强制服务器先执行此检查。
因此,我们需要有关如何优化查询、重建表或更改解决此问题的方法的想法(不一定是纯 SQL 查询,我可以使用编程语言中的数据库)。还要感谢您对服务器物理加速的建议:机器上有32GB内存,服务器使用很少,也许调整一些变量?
更新 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)'
按照@Mike 的建议添加了索引(chr、left、right):
# 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'
更新 2。使 mysqld 在多个线程中运行。
在查询期间查看了 CPU 使用率。由于我目前在独占模式下工作,因此我是唯一访问本地服务器的人。是否有可能以某种方式强制 mysqld 在多个线程中处理一个查询?然后他可以使用 8 核 / 16 线程,但他只使用了一个。
顺便说一句,将不同的表分散到不同物理硬盘驱动器上的文件夹中,虽然很小,但可以加速工作。
更新 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`;
但我没有看到太大的进展。
DBMS 使用的常用优化方法通常从第一个表中取出一条记录,然后在整个第二个表中搜索匹配的记录。在存在索引的情况下,这种情况发生得很快,在 中
log2(m)
,但这些仍然是对十几个索引页面的调用......您的常规 Join 查询应该在最佳情况下执行O=n*(log2(m)+log2(k))
(其中 n,m,k是查询中3张表的记录数)(虽然看MySQL优化的文章,根本就出来O=n*log2(m)*log2(k)
)另一方面,您的数据非常具体(遗憾的是 DBMS 无法对此进行评估)。在基因和重复表中,存在不相交的区间,因此,在按左字段排序时,记录也按右排序。在有模式的表格中,区间时不时会相交,因此在按left排序时, right字段有时会“回退”一点,但这种情况大约是 8%。
将一个排序列表与可能间隔的排序列表进行比较可以容易得多,方法是同时并行遍历两个列表,在列表中向前移动指针,其中条目比另一个列表中的条目更少。此外,可以同时并行处理超过 2 个列表。在这种情况下,搜索的复杂度是
O=n+m+k
.不幸的是,由于模式列表不能同时按左右排序,我们有时需要在重复中将指针回滚一点。在 MySQL 中,当使用游标时,这是不可能的,因此我决定记住那些落在右递增序列之外的记录,同时可能落入上一个重复记录的区间(很少438k 中的 2k)。这可以通过记住最后几个重复条目来避免,但这在 MySQL 上会很麻烦。保存的记录必须在第二遍中处理,通过按正确字段排序的重复。
基于以上,我想出了以下存储过程:
这个过程在一个 6k / 444k / 438k 记录的控制示例上的执行时间是 45 秒......确实,在控制示例中没有 chr 字段,当它是时,它当然也必须参与排序列表并且是在所有条件下进行比较。表 47、51 等 应在单独的通道中处理。如果可以返回,可以尝试一次性处理所有内容。一个类似的perl 算法,从排序的 csv 文件中获取数据,需要 4 秒......
由于重复中仍然可能存在间隔交叉点,所以一切都稍微复杂一些,并且要获得所有选项(比原始选项(130k 记录)多约 200 条记录),最好使用数组所以你可以向前看一点。在 perl 中它看起来像这样
我首先考虑了问题文本中给出的请求。尽管 EXPLAIN PLAN 看起来不错,但查询速度非常慢,以至于它读取整个表而不是访问索引。编辑索引没有太大变化。
然后是这一刻的理解:在提到基因表时,我们只为列标明了一个边界
g.left
,即:a.left > g.left
。因此,我们要求g.left
基因的极限小于a.left
实验的极限。就是这样。如果有边界怎么办a.left
实验价值很高,比如1亿?嗯,是的,要处理实验表的一行,您将需要阅读几乎整个基因表。索引的排列方式是,如果没有等号,那么事情就很糟糕。基因表相对较小,但这些考虑也适用于处理非常大的重复表:a.right > r.left
. 这是请求的主要问题。笔者提供的真实数据片段显示,对于genes和repeats, and in one line的差异可以达到150万和50万,这个太多了,但是我还是尝试优化查询条件,没有得到任何收获。出于某种原因,它甚至反过来。
left
right
正如其他参与者已经提到的,基因、重复和实验可以被认为是坐标轴上的范围,从
left
到right
。但是,这只是成功的一半 :) 您还可以将坐标轴本身划分为范围。将轴划分为多个范围,然后我们可以为这些范围中的每一个找到至少落在一个边缘的所有基因和重复。
几个例子
例子1:
坐标
left
=10,right
=50的基因。轴分为 100 个单位的范围,即 0-99, 100-199, 200-299, ...
在这种情况下,基因只落在一个范围内:0-99。
示例 2:
坐标
left
=140,right
=360 的基因。轴以相同的方式分为范围:0-99、100-199、200-299、300-399、...
在这种情况下,基因分为三个范围:100-199、200-299、300 -399。该基因部分覆盖了第一个和第三个范围,完全覆盖了第二个(中间)范围。
为什么我们需要对坐标轴上的范围大惊小怪?
为了理解,让我们回到问题的条件:找到
left
落在基因左边缘的实验,落在right
右边缘的重复上。最初,我们使用测试条件中的不等式来寻找基因命中和重复,这样做时,SQL 服务器在表中查找的行数比我们想要的多得多。
现在,知道实验左边界的值落在坐标轴的哪个范围内
a.left
,我们可以立即检查这个特定范围内是否存在任何基因(在该范围内)。与重复类似,我们只检查右边界a.right
。还有一个微妙之处:可能会发现基因位于坐标
left
=10,right
=20,而实验位于坐标left
=25,right
=45。在这种情况下,它们位于相同的 0-99 范围内,但它们不满足问题的条件。事实证明,通过检查范围,我们只是初步选择了或多或少合适的基因,但为了完全确定,我们必须应用原始请求中的条件。这样一来,如果坐标轴被分成几万份,对范围进行编号,坐标除以10000,那么解决问题的查询会是这样的:
В данном запросе таблицы
unwind-genes
иunwind-repeats
содержат сведения обо всех диапазонах оси координат, поделённой на отрезки в 10000 единиц, куда попадают, соответственно гены и повторы.Прикладываю скрипт на обе таблицы, и на хранимые процедуры для их заполнения. https://pastebin.com/72Rp6Pfy
Время выполнения на моем компьютере (под виртуальной машиной) на полученном фрагменте реальных данных:
Хочу отдельно упомянуть, что вызов хранимых процедур (для формирования промежуточных данных по диапазонам) нужен только однократный. Вызывать их повторно нет нужды до тех пор, пока не изменятся служебные данные по генам/повторам.
Плюсы данного метода решения:
- высокая скорость
- чистый SQL, без использования дополнительных инструментов
- нечувствительность к наличию пересечений по интервалам в таблицах генов и повторов, в том смысле что ничего не "сломается" и никакие данные не будут упущены из рассмотрения
- если таблицы генов и повторов не меняются, то промежуточные данные не нужно пересчитывать для каждого нового эксперимента - экономия времени обработки для каждого нового эксперимента
Минусы:
- база увеличивается в размерах из-за хранения промежуточных данных по диапазонам
Возможные пути для дальнейшей оптимизации решения:
- разбивка оси координат по диапазонам другого размера; при уменьшении размера диапазонов можно получить ускорение в выполнении запроса, но увеличится объём промежуточных данных, их объём может стать в десятки раз больше объёма исходных таблиц
- можно попробовать в таблицы с промежуточными данными закинуть имена генов и повторов, чтобы избавиться от соединения с исходными таблицами (вместо 5-и таблиц запрос будет обходиться 3-мя)
На всякий случай, оставляю полный скрипт своей тестовой БД
https://pastebin.com/eCviySbB
P.S.:
Признаться, раньше с MySQL дела не имел, работал с данной СУБД впервые на данной задаче.
Благодарю, что дали повод и с MySQL ознакомиться, и поучаствовать в решении интересной реальной задачи :)
И прошу прощения за много буков. Не нашёл, как сделать сворачиваемые куски текста (прятать под спойлер)
很酷的话题!只有在纯 SQL 上才有可能做这样的死亡过程。滚动脚本(例如,PHP)要容易得多——虽然更长,但会做所有事情——不是使用单个 INSERT-SELECT,而是一次插入一个,或分批插入事务。所以我理解问题不在于性能,而在于原则上不可能完成到最后。最好改变你的方法。
也就是说,我建议您
51k-80-80-ignore-random-noreverse
从表中为其每条记录选择根据表genes-g38-201505
和repeats-g38-201505
. 如果找到匹配项,则运行INSERT
.您可以在没有脚本的情况下进行限制。首先,要一次选择一条记录,
51k-80-80-ignore-random-noreverse
您需要在表中添加一个主键:然后根据您自己的要求,您现在可以根据表格进行任何细分
51k-80-80-ignore-random-noreverse
:并且不会出现您写的这种情况
limit 0,1000; limit 1001,2000 и так далее, как я понимаю, использовать бесполезно, поскольку каждый следующий этап сервер всё равно будет проходить предыдущие
,因为索引现在正在工作id
。其次,我们需要专门针对请求的正确索引:
为查询创建索引非常容易 - 您需要将参与的所有列(每个表一个多索引)添加到索引中,
WHERE
除了主键,顺序:从具有最少数量的列选择最大的一个,以便 BTREE 以最佳方式工作。最后一件事——你正在使用 SQL 完成一项非常非典型的任务,这是我最后一次看到表在工作代码中成倍增加(它们使 JOIN 不是运算符 = ) 5 年前:很难提出一些符合公牛的建议——眼睛,除了点击一个“胖”“请求执行更多“瘦”查询。相当牛的眼睛是检查连接到 SQL 的脚本循环中的匹配项 - 但显然您需要能够制作和运行这样的脚本,或者联系自由职业者。
Данное сообщение является не ответом, а подведением итогов конкурса.
Кратко поблагодарю всех, кто участвовал ответами, комментариями и участием в чате.
Синтез ответов и непосредственное взаимодействие @Mike и @velial, на мой взгляд, позволило разработать оптимальный вариант решения вопроса. Поэтому я создал дополнительный конкурс и вручил награду за конкурс, таким образом, обоим.
Что было до публикации вопроса. Удаленный сервер, на который выкладывались тестовые (Пока тестовые. Это не значит, что они ненастоящие, это значит, что их мало :) ) результаты исследования тканей онко-больных, как раковых клеток, так и чистых клеток того же органа (p,k). Предполагалось, что сотрудник, которому необходимо сравнение по определенным параметрам, мог запустить подобное сравнение в виде скрипта, с сохранением результат в таблицу, для которой устанавливался срок жизни в 30 суток (если результаты требовались ещё кому-то срок жизни автоматически увеличивался, либо мог быть определен как вечный вручную). Мы столкнулись с тем, что ряд запросов (самый длинный по времени был выставлен в вопросе) выполняются чрезмерно долго. Хотелось сократить время выполнения сравнения, желательно без использования сторонних программ и скачивания/закачивания данных на сервер.
Что сделано сейчас, по результатам ответов на вопрос.
Проведена оптимизация почти всех таблиц. Изменены запросы на их создание и заполнение данными. Многие запросы сравнения стали выполняться приемлемо быстро. Оставшиеся "лимитные" запросы пока заменены на комплексные: частично запросы + частично обработка программой, для этого задействована временно неиспользуемая 16-потоковая машина, куда данные сбрасываются по FibreChannel.
Что делается, что будет сделано. Проводятся испытания использования stored procedures. Но на другой машине, куда были частично перенесены данные, поскольку делать испытания на рабочем сервере, который постоянно включен в систему обмена данных, нецелесообразно.
Заказан новый сервер, где будет установлена PostgreSQL (и, возможно, испытаны другие форматы БД) для оценки целесообразности перехода.
Кроме того Сам узнал много нового в процессе общения и изучения представленных ответов. Возможно, что это - самый ценный результат :)
Update 2019-06-25 Шесть месяцев уже как крутится сервер на PostgreSQL. База с момента задания вопроса выросла более, чем в 100 раз. В принципе, нормально: самое длительное обращение сейчас занимает менее 20 секунд (это приемлемо, поскольку сами расчёты иногда занимают несколько суток, а порой и недель). Еще раз спасибо всем! :)