Что такое выбор Big-O для SQL?

Ответ 1

Поскольку вы не контролируете выбранный алгоритм, невозможно напрямую узнать. Однако без индексов SELECT должен быть O (n) (сканирование таблицы должно проверять каждую запись, что означает, что она будет масштабироваться с размером таблицы).

С индексом SELECT, вероятно, O (log (n)) (хотя это будет зависеть от алгоритма, используемого для индексирования, и свойств самих данных, если это верно для любой реальной таблицы). Чтобы определить ваши результаты для любой таблицы или запроса, вам необходимо прибегнуть к профилированию данных реального мира.

INSERT без индексов должен быть очень быстрым (близко к O (1)), в то время как UPDATE нужно сначала найти записи, и поэтому будет медленнее (немного), чем SELECT, который доставит вас туда.

INSERT с индексами, вероятно, снова окажется в шаге O (log (n ^ 2)), когда дерево индексов необходимо перебалансировать, ближе к O (log (n)) в противном случае. Такое же замедление произойдет с UPDATE, если оно повлияет на индексированные строки, помимо затрат SELECT.

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

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

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

Ответ 2

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

Однако, если вы являетесь пользователем MS SQL Server, вы можете ознакомиться с оценочным планом выполнения в Query Analyzer (2000) или Management Studio (2005+). Это дает вам много информации, которую вы можете использовать для анализа.

Ответ 3

Все зависит от того, как (ну) вы пишете свой SQL и насколько хорошо ваша база данных предназначена для выполняемой вами операции. Попытайтесь использовать функцию плана объяснения, чтобы увидеть, как вещи будут выполняться db.. Вы можете вычислить большой-O