Помоготе выбрать БД

Question

[igamity]

Добрый день!

Требуется совет по выбору системы хранения данных. Усходные данные: потенциально неограниченный массив числовых данных, например:

ID		VALUE
1		10.01
2		11.13
3		9.78
4		10.00
5		9.99
6		12.45
...		...

Требуется выбрать хранилище, которое позволяло бы выбирать данные по условиям их взаимных отношений, например, выбрать значения X_i, которые являются локальными максимами:
где X_i+1 < X_i > X_i-1.

Подобное условие самое простое, возможны и более сложные, но общее у них одно: требуется сравнивать текущее значение, с любым другим, в порядке увеличения индекса (или уменьшения). Т. е., например, есть некоторое значение X_i, требуется найти ближайшее по значению индекса значение Y_j, такое что Y_j > X_i, и j > i.

Answer 1

[Shedal]

SELECT *
FROM myTable t1
JOIN myTable t2
    ON t1.Id < t2.Id
    AND t1.Value > t2.Value
WHERE t2.Id = 100
ORDER BY t1.Id DESC
LIMIT 1;

Это так, к слову :)
Если нужно сделать такую выборку для всех Id, то можно сделать подзапрос, или GROUP BY.

Comments

[igamity]

Ок. Локальный максимум, по описанному мной условию как найти?

[Shedal]

Просто элементы, которые больше двух соседних? Элементарно. Или вы имеете в виду локальные максимумы в пределах плюс-минус n элементов?

[igamity]

Найти элемент, который больше предыдущего и следующего. Да, сейчас заметил, что в топике неправильное условие записал. Правильно так: X_i+1 < X_i > X_i-1.

[igamity]

Да, с подзапросами, найти локальный максимум достаточно просто (особенно если индексы, как в условии идут последовательно и соседние отличаются на единицу, хотя в реале это будет далеко не так), но желательно обойтись без них, т. к. я упомянул в топике, что это первое что пришло на ум и условия могут быть и будут значительно сложнее.

[Shedal]

Я просто хотел показать, что с помощью SQL можно сделать больше, чем кажется на первый взгляд. Не факт, что он вам подойдет, но и не факт, что не подойдет :)
Может быть, стоит взять пример самого сложного условия, какое сможете придумать, и попробовать его решить с помощью SQL?

[igamity]

Я не против SQL, как такового, да и не говорю, что в данной задаче он не применим… В задачах, которые я уже с его помощью решал, приходилось много работы перекладывать на приложение, т. к. быстрых SQL-решений найти не удалось. Исходя из этого и появилась идея о том, что возможно есть другие движки хранилищ данных, которые бы лучше справились с задачами.

Самое сложное условие я даже предположить не могу ;) т. к. фактически мне требуется разработать набор базовых функций поиска по условию, а в дальнейшем данные функции могут комбинироваться в произвольные конструкции. Из чего следует, что базовые функции должны быть максимально быстрыми, а так же поддерживать оптимизацию в сочетаниях друг с другом, так чтобы итоговый алгоритм выполнялся в ограниченное время. Тем более, что показанный в топике числовой ряд будет далеко не единственным.

Answer 2

[pomme]

Похоже на биржевые котировки :)

Сложно советовать вслепую, не зная вида Ваших запросов, но Ваша структура называется «временные ряды» (time series). Список софта по работе с ними есть, например, здесь: ces.stat.ucla.edu/software/time-series-analysis. Вам же, думаю, не только искать по ним придется, но и преобразовывать — масштабировать, накладывать фильтры, убирать шумы и т.п.

Comments

[igamity]

Да, это биржевые котировки, только у нас собственные алгоритмы и матстат не требуется. Собственно наши фильтры будут строится на взаимных отношениях котировок в зависимости от их положения во времени. Т. е. скорее потребуются всевозможные варианты поиска по условиям и перебор вариантов, но хотелось бы часть работы, видимо поиск, переложить на движок БД.

[pomme]

Я бы все-таки рекомендовал свой велосипед.
Дело в том, что в ваших условиях как минимум два предиката неравенства: i < j && X_i < Y_j, а, значит, вам понадобится мерджить индексы и операция, которую вы, как я понял, ожидаете мгновенной, сведется как минимум к index scan.
Правда, если вы будете часто сравнивать не две произвольные точки из ряда, а, например, одна из них будет близко к концу, то этот index scan будет быстрым.
То есть получается либо а) велосипед, либо б) sql storage. Гибкости sql вам вполне хватит, а сильно эффективнее вряд ли можно сделать — index scan будет все равно.
NoSQL вообще не советовал бы рассматривать — для вас критично умение стораджа реализовывать разные методы слияния индексов и умный оптимизатор — а в обоих вещах тот же InnoDB даст NoSQL стораджам большую фору.

[igamity]

NoSQL подкупает объектами. Например, если взять локальные экстремумы, их было бы достаточно найти один раз, после чего добавить к соответствующему объекту ряда данных метку или параметр. В принципе и в SQL можно объект запихнуть, но вот работать потом с ними придется на уровне приложения.

[pomme]

Дык и с объектами на уровне приложения — оно же должно знать структуру хранимого объекта. Вообще, даже в sql никто не мешает вам ограничиться всего одним строковым полем на таблицу и сказать, что в нем находится сериализованный объект (удобство sql, кстати, как раз в том, что он этого НЕ делает). Так что это скорее синтаксический сахар, а мы с Вами говорили об эффективности.
Да, конечно, можно и нужно хранить предрасчитанные данные. И если четко ограничить круг запросов, которые будут в системе, то можно сделать крайне эффективное кеширование, заточенное исключительно на эти запросы и работающее очень быстро. Но это вопрос бизнес-логики, а не БД — если понятна структура этого кеша, то уже неважно, в каком сторадже он будет реализован, эффективность дает в первую очередь именно строго специализированный кеш, а не движок стораджа.

[pietrovich]

Например, если взять локальные экстремумы, их было бы достаточно найти один раз, после чего добавить к соответствующему объекту ряда данных метку или параметр.

Ну так метку(читай колонку) и в обычной таблице можно поставить. А экстремумы определять при вставке, триггером или еще на этапе подготовки, или периодически после нескольких вставок. Индекс по маркеру позволит получить неплохую скорость выборок, если, конечно, там будут более-менее подходящие частоты для эффективной работы индеков.

Answer 3

[simplecode]

считаю, что не принципиально… грамотное умение составлять SQL запросы рулит…

Comments

[igamity]

Грамотное умение составлять — всегда рулит, но, имхо, SQL, как раз и не подходит. Не представляю каким образом, скажем в мускуле, найти ближайшее максимальное значение, относительно текущего, индексы которого меньше индекса текущего… Извернуться, конечно, можно, но уж больно нетривиально будет.

Answer 4

[Анатолий]

Для таких простых таблиц можете так же взглянуть на nosql решения. Возможно они себя лучше проявят при таких данных и условиях.

Comments

[igamity]

Не вопрос, просто не знаю на что смотреть. Первое, что приходит на ум — Монга, но т. к. я с ней не работал, не уверен, что в ней можно это реализовать и насколько это будет удобно, потому и появился данный топик.

[Анатолий]

Как раз в монго это реализовать элементарно, но Вам стоит поискать среди решений key=value, они на много быстрей, и если есть выборка по ключам (этого я не знаю) то они подойдут лучше.

[Анатолий]

не по ключам, по значениям =)

[igamity]

А не подскажете, есть ли примеры реализации чего-нибудь подобного на Монге? Из key=>value, я, если честно, только memcached знаю, в смысле работал с ним, и если брать именно его, получается вся выборка будет происходить в приложении, а хотелось бы переложить эту задачу на движок базы. Или я отстал от жизни? ;)

[Анатолий]

Я не понял что значит «хотелось бы переложить эту задачу на движок базы», но Xi+1 > Xi > Xi-1 может выбирать любая база, на то и есть запросы =)
По монго: www.mongodb.org/display/DOCS/Aggregation?focusedCommentId=3637279#comment-3637279

Answer 5

[VBart]

Для такой формализованной задачи, если нужны максимальные скорости можно и свой велосипед смастерить на том же Си, например, благо задача весьма простая.

Comments

[igamity]

Велосипед — не вариант.

[igamity]

как минимум — писать некому. Я реалист, понятное дело, что выбрав движок хранилища мне придется смириться с его недостатками (у любого варианта будут свои плюсы и минусы), но все же не придется базовый функционал изобретать.

Answer 6

[Пума Тайланд]

Для таких задач куда правильнее будет хранить данные в памяти и скидывать их скажем на диск время от времени чтобы не потерять. Особых применений что sql, что nosql решений не вижу.

Answer 7

[Федор Индутный]

Riak и вычислять все с помощью distributed MapReduce

Answer 8

[Bonart]

Oracle может подойти — там есть специальная поддержка для скользящих окон в синтаксисе и собственно движке запросов