次の2つの操作の複雑さを知りたいです。最初のケースは、インデックスが設定されている列で並べ替えて、次のように特定の数値より下または上のすべての値のカウントを要求するカウントです。
SELECT count(*) FROM tbl WHERE col1 > 10 ORDER BY col1;
もう1つのケースは、中央値演算に関するものです。中央値とは、（int）n / 2の行の値を見つけることを意味します。ここで、nはテーブル内の行数です。この例は次のようになります（ここでもcol1にインデックスがあります）。
SELECT median(col1) FROM tbl ORDER BY col1;
これらのケースの最悪の場合の複雑さは何ですか？
ORDER BY句は不要です-または紛らわしい、あるいはその両方。
SELECT COUNT(*)（通常は）単一の行を返します。検索に基準があるため、オプティマイザはcol1のインデックススキャン（インデックスの先頭列がcol1のインデックスがある場合）またはテーブルスキャンを実行する必要がある場合があります。これはO（N）操作です。ここで、Nはテーブルの行数です。
SELECT MEDIAN(col1)また、（通常は）単一の行を返します。これもO（N）操作であり、これもインデックススキャンまたはテーブルスキャンを使用します。
ORDER BYオプティマイザが句をどのように処理するかが完全にはわからないため、「通常」の修飾子があります。1つの可能性は、オプティマイザーがそれが冗長であると判断し、それを無視することです。他の可能性は、それが何らかの形col1であなたORDER BYを投影列に追加し、それを他の操作に含め、そして結果を返す前にそれを削除することです。ただし、それは句なしで集計と非集計を混合するというファウルを実行しGROUP BYます-したがって、オプティマイザーはそれを無視するか、クエリを拒否すると思います。ただし、MySQLでの実験は行っていません。
FWIW、IBM Informix Dynamic Server（IDS）はエラー-19828を生成します。このコンテキストでは、ORDERBY列または式がSELECTリストに含まれている必要があります。
ORDER BY句がない場合、上記の分析は十分に正確です。基準のないSELECTCOUNT（*）の場合、サーバーはテーブルに関して保持しているメタデータを使用して、O（1）時間でクエリに応答できることがよくあります。