Какова сложность поиска медианы и подсчета в MySQL? - PullRequest
Новая
       16

Какова сложность поиска медианы и подсчета в MySQL?

1 голос
/ 20 февраля 2009

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

SELECT count(*) FROM tbl WHERE col1 > 10 ORDER BY col1;

Другой случай касается медианной операции. Под медианой я подразумеваю поиск значения строки (int) n / 2, где n - количество строк в таблице. Примером этого может быть следующий (опять же есть индекс на col1): 

SELECT median(col1) FROM tbl ORDER BY col1;

Какова сложность этих случаев в худшем случае?

1 Ответ

2 голосов
/ 20 февраля 2009

Пункты ORDER BY не нужны - или сбивают с толку, или оба.

SELECT COUNT(*) вернет одну строку (обычно). Поскольку у вас есть критерий поиска, оптимизатору может потребоваться выполнить сканирование индекса col1 (если есть индекс с col1 в качестве ведущего столбца индекса) или сканирование таблицы. Это операция O (N), где N - количество строк в таблице.

SELECT MEDIAN(col1) также вернет одну строку (обычно). Это будет операция O (N), опять же с использованием сканирования индекса или сканирования таблицы.

Квалификатор 'normal' есть, потому что я не совсем уверен, что оптимизатор будет делать с предложениями ORDER BY. Одна возможность состоит в том, что оптимизатор определит, что он является избыточным, и проигнорирует его. Другая возможность состоит в том, что он каким-то образом добавит col1, который вы ORDER BY, к столбцам проекции, включит его в другие операции и затем удалит его, прежде чем возвращать результаты. Однако это приведет к нарушению смешивания агрегатов и неагрегатов без предложения GROUP BY, поэтому я думаю, что оптимизатор проигнорирует его или отклонит запрос. Однако я не проводил эксперимент с MySQL.

FWIW, IBM Informix Dynamic Server (IDS) выдает ошибку -19828: в этом контексте столбец или выражение ORDER BY должны находиться в списке SELECT.

Без предложений ORDER BY приведенный выше анализ достаточно точен. Обратите внимание, что для SELECT COUNT (*) без критериев сервер часто может использовать метаданные, которые он хранит в таблице, для ответа на запрос в O (1) раз.

...