logarithmic time count (*) запрос диапазона в любой СУБД

Question

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

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

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

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

Answer 1

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

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

Не уверен, но этот вопрос выглядит связанным с этим question on SO.

Answer 2

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

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

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