запрос диапазона логарифмического подсчета времени (*) в любой СУБД

Предположим, что имеется таблица T со столбцом C, индексированным B-деревом, и заданная константа k. Предположим, что результатом следующего запроса будет n:

select count(*) from T where C > k;

Я попробовал такой запрос в MySQL (InnoDB) со столбцом C, индексированным B-деревом, и понял, что чем больше значение n, тем медленнее запрос. На большом столе (Гб) мне приходится ждать даже минуты. Итак, я предполагаю, что временная сложность линейна по отношению к n. Но я знаю, можно ли хранить совокупную информацию о внутренних узлах B-Tree, что можно сделать за логарифмическое время по отношению к размеру таблицы.

Может ли кто-нибудь предложить любую СУБД с реализованным логарифмическим решением или какой-либо трюк для сокращения времени запроса в MySQL?


sql database algorithm b-tree-index aggregates
person Hamid Alaei    schedule 26.09.2014    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Ничего не скажешь, пока не увидишь план выполнения. По крайней мере, в Oracle у вас также должна быть гистограмма в столбце C, чтобы иметь разные планы выполнения для разных значений C.

Также глубина индекса обычно составляет 3-5. Основание логарифма ОЧЕНЬ большое. Также имейте в виду, что многие базы данных обманывают при удалении строк из таблицы, обычно конечные узлы могут указывать на строки, которые уже были удалены. Не стоит усилий по поддержанию агрегированных значений в B-дереве, это не будет хорошо масштабироваться.

Если вы ищете базу данных с различными модными опциями индексации, обратите внимание на PostreSQL.

person ibre5041    schedule 26.09.2014
comment
Благодарю. Я знаю, что контроль параллелизма усложняет ситуацию. Но в конкретном случае, который меня интересует в данный момент, у меня не так много обновлений, и меня не очень волнует блокировка всей таблицы при вставке строки. Как насчет этого? - person Hamid Alaei; 26.09.2014
comment
Боюсь, вам придется смириться с тем, что базы данных предназначены для разных целей. Индексы не имеют агрегатов в узлах дерева, потому что их обслуживание в большинстве случаев было бы слишком дорогим. Но сначала вы действительно должны проверить план выполнения запроса. - person ibre5041; 26.09.2014

arrow_upward
0
arrow_downward

Да, все СУБД поддерживают индексы. Убедитесь, что все поля K проиндексированы, и, к сожалению, насколько я знаю, это единственное, что вы можете сделать.

Этот ссылка предназначена для SQL Server, но она должна работать (с очень небольшими изменениями) с MySql.

Не уверен, но этот вопрос выглядит связанным с этим вопросом на ТАК.

person Ciprian Khlud    schedule 26.09.2014
comment
Единственный способ индексации в логарифмическом порядке — использовать index. Я также рекомендую вам эту страницу (но у СУБД есть небольшие отличия в синтаксисе): Использовать индекс Луки - person Ciprian Khlud; 26.09.2014
comment
Пожалуйста, прочитайте еще раз мой вопрос. Я уже использовал index. при всем уважении, вы неправильно поняли мой вопрос. - person Hamid Alaei; 26.09.2014