Coding Interview Prep · レッスン

上位N行を確実に返す

Q: 「上位N行を確実に返す」レッスンは無料ですか？

はい。「上位N行を確実に返す」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

Q: 「上位N行を確実に返す」で何を学びますか？

タイブレーカーがない場合、ORDER BYとLIMITの結果が不定になる理由を学びます。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Q: Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。

Q: 「上位N行を確実に返す」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

Q: このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

タイブレーカーがない場合、ORDER BYとLIMITの結果が不定になる理由を学びます。

「上位N行を確実に返す」はCoddyKit上の無料Coding Interview Prepレッスンです。これはレッスン3/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

Top-Nクエリに潜む隠れたバグ

「給与が最も高い従業員を上位5人取得してください」という依頼は簡単に思えます。ORDER BY salary DESC LIMIT 5とすればよいからです。しかし、面接官は罠を仕掛けてきます。境界で6人の給与が同じだったらどうでしょうか。多くの行が同順位だったらどうでしょうか。

本質的な問題は決定性です。並べ替えキーに同じ値があると、LIMITは任意に行を切り捨てるため、返される行が実行ごとに変わる可能性があります。このレッスンでは、Top-Nの結果を信頼できるものにします。

ORDER BY + LIMITが非決定的になる理由

順位4位、5位、6位の給与がすべて50000だとします。ORDER BY salary DESC LIMIT 5は必ず5行を返す必要があるため、同順位の3行のうち2行を残し、1行を除外します。ただし、どの2行になるかは未定義です。

クエリを2回実行した場合や、オプティマイザーが実行計画を変更した場合、異なる人が返される可能性があります。この非決定性こそ、面接官が見抜いてほしいバグです。

SELECT name, salary
FROM employees
ORDER BY salary DESC
LIMIT 5;

修正1：一意な同順位時の判定を追加する

最も簡単な修正は、一意な列（通常は主キー）を追加して、並べ替え順を完全なものにすることです。これで完全なキーが同じ行はなくなるため、どこで切り取られるかが決定的になり、結果を再現できるようになります。

これによって返される給与の範囲は変わりませんが、同順位の行からどれを選ぶかが実行ごとに安定します。

SELECT id, name, salary
FROM employees
ORDER BY salary DESC, id ASC
LIMIT 5;

修正2：WITH TIESですべての同順位を含める

要件によっては、ちょうどN行ではなく、「境界で同順位になった人を全員含める」ことが求められます。標準SQLとSQL ServerにはWITH TIESがあり、最後の行のORDER BY値と一致する行を追加で返します。

5番目の給与が3人で同じ場合、この方法では7行が返されます。なお、WITH TIESにはORDER BYが必要です。

SELECT name, salary
FROM employees
ORDER BY salary DESC
FETCH FIRST 5 ROWS WITH TIES;

まず要件を明確にする

コーディングの前に、面接官へ次のように確認してください。「境界で同順位の行がある場合、ちょうどN行が必要ですか、それとも同順位の行をすべて含めますか」この1つの確認だけでも、上級者らしさを示せます。

ちょうどN行で、結果を安定させる：一意な同順位時の判定を追加します。
同順位の行をすべて含める：WITH TIESまたはRANKを使います。
異なる値を対象にする：DENSE_RANKを使います。

移植性の高いウィンドウ関数アプローチ

WITH TIESに対応していないエンジンも多くあります。移植性が高く強力なパターンでは、サブクエリまたはCTE内でランキング用のウィンドウ関数を使い、その後で順位によって絞り込みます。ROW_NUMBERを使うと、決定的な並べ替えキーに基づいてちょうどN行を取得できます。

ウィンドウ関数をWHEREで直接参照することはできないため、サブクエリなどで囲む必要があります。

SELECT name, salary
FROM (
  SELECT name, salary,
         ROW_NUMBER() OVER (ORDER BY salary DESC, id ASC) AS rn
  FROM employees
) ranked
WHERE rn <= 5;

RANKで同順位を保持する

同順位の行をすべて残し、順位に欠番を作りたい場合は、ROW_NUMBERをRANKに置き換えます。3行が4位で同順位の場合、すべて4位になり、次の順位は7位になります。

rank <= 5で絞り込むと、同順位を含め、給与順位の上位5位に入るすべての行が返されます。

SELECT name, salary
FROM (
  SELECT name, salary,
         RANK() OVER (ORDER BY salary DESC) AS rnk
  FROM employees
) ranked
WHERE rnk <= 5;

Top-Nの異なる値にはDENSE_RANK

「給与の水準上位3つ」（上位3人ではありません）という場合は、異なる値を対象にします。DENSE_RANKは同順位に同じ順位を割り当て、番号を飛ばしません。そのため、dense_rnk <= 3では、異なる給与のうち上位3つのいずれかを受け取る全員が返されます。

どの表現にどのランキング関数を使うべきかを理解していることは、典型的な差別化ポイントです。

SELECT name, salary
FROM (
  SELECT name, salary,
         DENSE_RANK() OVER (ORDER BY salary DESC) AS drnk
  FROM employees
) ranked
WHERE drnk <= 3;

Top-1の特殊ケース

最上位の1行だけを取得する場合、ORDER BY ... LIMIT 1で動作しますが、それでも同順位の問題が残ります。最大値を持つすべての行が必要なら、最大値を求めるサブクエリと比較するか、RANK() = 1を使います。

最大値のサブクエリを使う形式は簡潔で、どのSQL方言でも実行できます。

SELECT name, salary
FROM employees
WHERE salary = (SELECT MAX(salary) FROM employees);

アプローチの比較

信頼できるTop-Nを取得するために、各手段を使う場面をまとめます。

LIMIT + 一意な同順位時の判定：ちょうどN行、安定、最も簡単
FETCH ... WITH TIES：ちょうどN行に境界の同順位を追加、標準SQL
ROW_NUMBER：ちょうどN行、決定的、完全に移植可能
RANK：同順位をすべて含む上位N順位
DENSE_RANK：上位N個の異なる値

グループごとのTop-N（プレビュー）

ウィンドウ関数を使う方法は、簡単に一般化できます。PARTITION BYを追加すると、各グループ内の上位N件を取得できます。たとえば、部署ごとの高給者上位2人を取得できます。パーティション分割の後に、同じrn <= nの条件で絞り込みます。

このグループごとのTop-Nは、実際の面接で非常によく出る問題の1つで、今学んだパターンそのものを基礎としています。

SELECT department, name, salary
FROM (
  SELECT department, name, salary,
         ROW_NUMBER() OVER (PARTITION BY department
                            ORDER BY salary DESC, id ASC) AS rn
  FROM employees
) ranked
WHERE rn <= 2;

確認問題

要件と適切な関数を対応させてください。

まとめ

Top-Nを信頼できる形で返すには：

並べ替えキーに同じ値がある場合、ORDER BY ... LIMITだけでは非決定的になります。
安定したちょうどN件の結果には、一意な同順位時の判定を追加してください。
境界の同順位を保持するには、WITH TIESまたはRANKを使います。
上位N個の異なる値には、DENSE_RANKを使います。
面接官がちょうどN行を求めているのか、それとも同順位をすべて含めたいのかを、必ず確認してください。

よくある質問