O(1) オーダー
- テーブルから任意の1行を取り出す
SELECT TOP 1 * FROM table;
O(log N) オーダー
- インデックスが張られた列に対してのWHERE句による抽出
O(log N)なので、テーブルサイズが大きくなっても、あまり時間計算量は増えない
O(N) オーダー
以下の場合は、行数に対して線形的に時間計算量が増加する
- 全行SELECTする
- WHERE句を使用して抽出する。※インデックスがない場合にO(N)
- count(*)でテーブルの行数をカウントする
O(N log N) オーダー
- ORDER BY句によるソート
O(N2) オーダー
以下の場合は、行数に対して多項式的に時間計算量が増加する（激増する）。
- テーブルの結合
- テーブルAの各行に対して、テーブルBの各行を結合させるため
但し、結合のアルゴリズムによっては以下の計算量になる。
- ハッシュ結合
- O(M+N)
- マージ結合
- O(M+N)
- O(M log M + N log N)
- O(M + N log N)
- ネストされた結合
- O(N2)
参考
How To Write Better SQL Queries: The Definitive Guide – Part 2
