Что такое Big-O for SQL select, для таблицы с n строк и для которых я хочу вернуть m результат?Что такое выбор Big-O для SQL?
И что такое Big-O для Update, или delete, или Create операция?
Я говорю о mysql и sqlite в целом.
Поскольку вы не контролируете выбранный алгоритм, невозможно напрямую узнать. Однако без индексов SELECT должен быть O (n) (сканирование таблицы должно проверять каждую запись, что означает, что она будет масштабироваться с размером таблицы).
С индексом SELECT, вероятно, является O (log (n)) (хотя это будет зависеть от алгоритма, используемого для индексирования, и свойств самих данных, если это верно для любой реальной таблицы). Чтобы определить ваши результаты для любой таблицы или запроса, вам нужно прибегнуть к профилированию данных реального мира.
INSERT без индексов должен быть очень быстрым (близко к O (1)), в то время как UPDATE необходимо сначала найти записи, и поэтому будет медленнее (немного), чем SELECT, который доставит вас туда.
INSERT с индексами, вероятно, снова окажется в шаге O (log (n^2)), когда дерево индексов необходимо перебалансировать, ближе к O (log (n)) в противном случае. Такое же замедление произойдет с UPDATE, если оно повлияет на индексированные строки, помимо затрат SELECT.
Все ставки отключены, как только вы говорите о JOIN в миксе: вам нужно будет профилировать и использовать инструменты оценки запросов баз данных, чтобы прочитать их. Также обратите внимание, что если этот запрос критичен по производительности, вы должны время от времени получать re, так как алгоритмы, используемые вашим оптимизатором запросов, будут меняться по мере изменения загрузки данных.
Еще одна вещь, о которой нужно помнить ... big-O не говорит вам о фиксированных расходах по каждой транзакции. Для небольших таблиц это, вероятно, выше фактических затрат на работу. В качестве примера: затраты на установку, срыв и связь кросс-сетевого запроса для одной строки, безусловно, будут больше, чем поиск индексированной записи в маленькой таблице.
Из-за этого я обнаружил, что возможность связывать группу связанных запросов в одной партии может иметь значительно большее влияние на производительность, чем любая оптимизация, которую я сделал для самой базы данных.
В соответствии с комментарием порядка выбора с соединением, помните что выбор с двойным соединением в таблицу может быть n^2. Например; выберите * из таблицы, где id> (выберите avg (id) из таблицы), вероятно, растет на одну запись без использования индексов. –
Я думаю, что реальный ответ может быть определен только в каждом конкретном случае (двигатель базы данных, дизайн таблицы, индексы и т. Д.).
Однако, если вы являетесь пользователем MS SQL Server, вы можете ознакомиться с оценочным планом выполнения в Query Analyzer (2000) или Management Studio (2005+). Это дает вам много информации, которую вы можете использовать для анализа.
Все зависит от того, как (хорошо) вы пишете свой SQL и насколько хорошо ваша база данных предназначена для выполняемой вами операции. Попытайтесь использовать функцию плана объяснения, чтобы увидеть, как вещи будут выполняться db. . Вы можете рассчитать big-O
duplicate: http://stackoverflow.com/questions/727719/database-query-time-complexity –