Артём Клименко: Так прежде чем приступить к поиску по таблице (ну и по индексу в том числе), postgresql ищет ту самую таблицу по CHECK, а потом уже работает с родительской и партицией. В ANALYZE видно, что поиск происходит по родительской таблице Offer и партиции Offer-4793. Родительская таблица Offer пуста, а в таблице Offer-4793 всего одно значение для bid, по которому идёт поиск. А так в тесте вообще всего одна запись.
Melkij: У меня очень много данных, по которым должна быть быстрая вставка и быстрый поиск. А так как для этого нужен индекс, скорость вставки при росте таблицы экспоненциально снижается. Поэтому я решил избавится от индексирования по одному полю, сделав на каждое значение этого поля по таблице.
По поводу партиционных индексов. Это походу то что надо! Про партицирование таблиц я знал. О партицировании индексов догадывался, но беглым поиском ничего не нашёл. Спасибо за ссылку, буду изучать.
А какая тут алгоритмическая сложность? Вроде как я где-то читал, что O(log(n)). Но судя по результатам, она экспоненциальная. Если судить самому, то планировщику необходимо проверить условие в каждой партиции, следовательно сложность должна быть линейной.
Каждый раз, когда на Reduce шаге мне попадается элемент, у которого есть и ребёнок и родитель, это означает, что есть цепочка длинной более одной связи. Есть счётчик, который подсчитывает это дело.
SeptiM: Так проблема то в том, что в MapReduce мы не можем видеть больше двух рёбер одновременно. В моём алгоритме с каждой итерацией сокращается количество цепочек с длиной больше 1. И тот момент, когда это количество прекращает сокращаться, означает, что остались только петли
Да, мой алгоритм по разбору в худшем случае O(nlogn), в лучшем O(n)
Что делать... Надо разрывать цикл. Начиная от рандомного элемента цепочки, заканчивая анализом всей цепочки, и по результатам анализа разрывать.
Про little step - big step знаю как "Fast step - Slow step"
Ваш алгоритм имеет сложность между O(nlogn) и O(n^2). С такой сложностью у меня тоже есть несколько. Но вот хочется что-то ближе к O(n).
Юрий Ярош: Ничего не понял из первого абзаца ответа.
Когда разбирался с Hadoop, все эти примеры изучил.
У меня то вопрос -- откуда берутся несуществующие данные. Можно, конечно, выяснить это дебагом. Но это довольно долго, поэтому я интересуюсь, не сталкивался ли кто-нибудь с этой проблемой.
По поводу ScyllaDB. Она вышла совсем недавно и очень меня порадовала. Но она же должна быть ещё совсем сырой. Рано пока её использовать в продакшн.
Начал работу с Hadoop. Адаптер ColumnFamilyInputFormat почему-то присылает много (10%) несуществующих данных. Ключ есть, а полей нет. И в БД не существует записей под этими ключами. Что это может быть?
Юрий Ярош: Я же писал в описании вопроса, что храню прайс-листы. Т. е. сущность -- товар. Cassandra пока очень устраивает. Если появятся причины, по которым она будет не подходить, начну рассматривать другие варианты. А пока с точки зрения горизонтального масштабирования преград никаких нет.
Посмотрел тарантул. Штука прикольная, но для продакшн надо её сильно допиливать -- писать разные обёртки для клиентов (официальные очень слабенькие) итд
