[SQL_Q] 3421. Find Students Who Improved

https://leetcode.com/problems/find-students-who-improved/description/

문제

Table: Scores

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| student_id  | int     |
| subject     | varchar |
| score       | int     |
| exam_date   | varchar |
+-------------+---------+
(student_id, subject, exam_date) is the primary key for this table.
Each row contains information about a student's score in a specific subject on a particular exam date. score is between 0 and 100 (inclusive).
Write a solution to find the students who have shown improvement. A student is considered to have shown improvement if they meet both of these conditions:

Have taken exams in the same subject on at least two different dates
Their latest score in that subject is higher than their first score
Return the result table ordered by student_id, subject in ascending order.

The result format is in the following example.

 

Example:

Input:

Scores table:

+------------+----------+-------+------------+
| student_id | subject  | score | exam_date  |
+------------+----------+-------+------------+
| 101        | Math     | 70    | 2023-01-15 |
| 101        | Math     | 85    | 2023-02-15 |
| 101        | Physics  | 65    | 2023-01-15 |
| 101        | Physics  | 60    | 2023-02-15 |
| 102        | Math     | 80    | 2023-01-15 |
| 102        | Math     | 85    | 2023-02-15 |
| 103        | Math     | 90    | 2023-01-15 |
| 104        | Physics  | 75    | 2023-01-15 |
| 104        | Physics  | 85    | 2023-02-15 |
+------------+----------+-------+------------+
Output:

+------------+----------+-------------+--------------+
| student_id | subject  | first_score | latest_score |
+------------+----------+-------------+--------------+
| 101        | Math     | 70          | 85           |
| 102        | Math     | 80          | 85           |
| 104        | Physics  | 75          | 85           |
+------------+----------+-------------+--------------+
Explanation:

Student 101 in Math: Improved from 70 to 85
Student 101 in Physics: No improvement (dropped from 65 to 60)
Student 102 in Math: Improved from 80 to 85
Student 103 in Math: Only one exam, not eligible
Student 104 in Physics: Improved from 75 to 85
Result table is ordered by student_id, subject.

어렵지 않은 문제지만
두 번의 JOIN을 하지 않으면 풀기 어려운 문제.
다중 JOIN을 할 때 어떻게 하면 좋을지 고민을 하다보니 시간을 많이 썼다.

내 쿼리

with dates as (
    SELECT student_id,subject, MIN(exam_date) s1, MAX(exam_date) s2
    FROM Scores 
    GROUP BY student_id, subject
)
select d.student_id, d.subject, 
s1.score as first_score, 
s2.score as latest_score
FROM dates d join Scores s1
on s1.student_id = d.student_id
and s1.subject = d.subject
and s1.exam_date = d.s1
JOIN Scores s2
on s2.student_id = d.student_id
and s2.subject = d.subject
and s2.exam_date = d.s2
where s1.score < s2.score
order by student_id, subject

✅ 장점

• MIN, MAX는 그룹화 연산에서 상대적으로 빠름 (특히 인덱스 사용 시)

• JOIN 조건이 명확하고 인덱스를 타기 좋음

• 정렬(ORDER BY)이 없다면 정렬 비용 없음

• 정렬 없이 추출 가능 → 큰 이점

❌ 단점

• Scores를 두 번 JOIN → I/O 비용 증가

• MIN, MAX는 같은 subject 내 중복 날짜가 있으면 첫/마지막 점수를 정확히 식별 못할 가능성 (단, 이 문제는 exam_date가 고유하므로 문제 없음)

다른 사람 쿼리

with ranked_scores as (
    SELECT student_id, subject, score, exam_date,
    row_number() over(
        partition by student_id, subject 
        order by exam_date) as rn_asc,
    row_number() over(
        partition by student_id, subject 
        order by exam_date DESC) as rn_desc
    FROM Scores
)
SELECT s1.student_id, s1.subject,
s1.score as first_score,
s2.score as latest_score
FROM ranked_scores s1 JOIN ranked_scores s2
on s1.rn_asc =1
and s2.rn_desc =1
and s1.student_id = s2.student_id
and s1.subject= s2.subject
and s1.score < s2.score
and s1.exam_date < s2.exam_date

✅ 장점

• SELF JOIN을 사용하여 코드가 명확함

• ROW_NUMBER()로 최초/최신 score 중복 방지 가능 (중복 exam_date가 있어도 정확히 추출 가능)

• 여러 시험이 있는 복잡한 시나리오 확장 용이

❌ 단점 (대용량에서 치명적)

• ROW_NUMBER()는 내부적으로 정렬이 필요 → 대용량에서는 정렬 비용이 상당함
• PARTITION BY + ORDER BY 조합은 특히 메모리 부족 시 임시 디스크 공간 사용 (디스크 정렬)
• index가 없으면 매우 느려짐
  • exam_date, student_id, subject에 복합 인덱스 필수

대용량 환경 기준 결론

기준	사용자 쿼리 (MIN/MAX)	다른 사람 쿼리 (ROW_NUMBER)
정렬 비용	❌ 없음	✅ 있음 (큰 부담)
인덱스 활용	✅ 가능 (subject + exam_date)	✅ 필요 (window 정렬용)
JOIN 비용	❌ 2중 JOIN (I/O 큼)	✅ SELF JOIN (같은 테이블 내)
확장성	❌ 제한적 (2개 시험에 최적화)	✅ 다회 시험 등 확장 쉬움
대용량 최적화	✅ 효율적	❌ 정렬 병목 가능

대용량에서는 일반적으로 MIN/MAX 기반 쿼리가 더 빠를 가능성이 큼,
단, 아래 조건이 함께 만족되면 ROW_NUMBER()도 실용적임:

• exam_date 정렬을 위한 인덱스(student_id, subject, exam_date)가 있음

• exam_date에 중복 값이 존재하여 정확한 정렬이 필요한 시나리오

• exam_date에 따른 분석/확장성이 더 중요함 (e.g. 중간 점수도 고려해야 하는 경우)

---

대용량 환경이라는 가정 하에 index의 여부가 매우 중요하다.

쿼리별 성능 비교 (인덱스 있는 상황 기준)

항목	사용자 쿼리 (MIN/MAX)	다른 사람 쿼리 (ROW_NUMBER)
인덱스 활용	✅ GROUP BY student_id, subject 후 MIN/MAX(exam_date)는 PK 인덱스로 커버 가능	✅ PARTITION BY student_id, subject ORDER BY exam_date → 정렬에 인덱스 사용 가능
정렬 필요 여부	❌ 없음 (MIN/MAX는 정렬 없이 동작 가능)	✅ 있음 (ROW_NUMBER는 내부 정렬 필수)
디스크 I/O	✅ Scores 3회 접근 (하지만 효율적인 조건 JOIN)	✅ Scores 1회 접근, 그러나 정렬된 윈도우 함수 수행
메모리 사용량	✅ 낮음 (정렬 없음)	❌ 높음 (ROW_NUMBER() 정렬은 메모리 또는 디스크 사용)
속도 예측 (수백만 행 기준)	✅ 빠름 (정렬 없는 2-way JOIN)	❌ 느림 (정렬 병목 가능성 존재)

---

구체적으로: 왜 MIN/MAX 방식이 빠른가?

사용자 쿼리

SELECT student_id, subject,
       MIN(exam_date), MAX(exam_date)
FROM Scores
GROUP BY student_id, subject

• 이 GROUP BY + MIN/MAX는 인덱스가 있으면 정렬 없이도 O(1) 또는 O(logN)으로 실행
• 이후 Scores 테이블을 exam_date 기준으로 다시 JOIN할 때도 인덱스 타기 용이
  → 이 쿼리는 정렬 비용이 거의 없음

다른 사람 쿼리 핵심

ROW_NUMBER() OVER (PARTITION BY student_id, subject ORDER BY exam_date)

• ROW_NUMBER()는 내부적으로 정렬이 필수
• 비록 인덱스가 student_id, subject, exam_date 순으로 걸려 있어도, DB는 정렬된 결과를 materialize해서 메모리에 적재하려 함
• 특히 exam_date가 고유하지 않거나, 데이터가 수천만 건이라면 디스크 TEMP 정렬 발생 가능
  → 대용량에서 병목 가능성 ↑