Ch.11 사례 - 매 요청마다 정렬하는 API¶
< 환경 세팅 | Binary Search와 B-Tree >
앞에서 자료구조 선택이 검색 성능을 수천 배 바꾼다는 걸 봤다. 이번에는 정렬이다. 정렬은 검색의 전제 조건이기도 하고, 그 자체로 가장 자주 보이는 성능 함정이기도 하다.
11-1. 사례 설명¶
주니어 개발자가 상품 목록 API를 만들고 있다. 가격순 정렬 기능이 필요하다.
@app.get("/products")
async def get_products(sort_by: str = "price"):
products = db.query("SELECT * FROM products") # 10만 건
if sort_by == "price":
products.sort(key=lambda p: p["price"])
elif sort_by == "name":
products.sort(key=lambda p: p["name"])
return products[:20] # 상위 20개만 반환
10만 건을 전부 가져와서, 전부 정렬하고, 상위 20개만 반환한다. 매 요청마다. 코드를 본 시니어가 한숨을 쉬는 그림이다.
개발 환경에서는 데이터가 1,000건이라 빠르다. 운영에 10만 건이 쌓이면? 점심 시간에 트래픽 몰리면? 같은 코드인데 운영에서만 터지는 흔한 패턴이다.
(이 코드는 단순한 정렬 한 줄짜리 함정이 아니다. 안에는 세 가지 다른 문제가 겹쳐 있다. 첫째, 필요 없는 데이터를 DB에서 다 가져온다. 둘째, 가져온 데이터를 애플리케이션에서 다시 정렬한다. 셋째, 정렬된 결과의 0.02%만 쓰고 나머지를 버린다. 하나씩 풀어본다.)
11-2. 결과 예측¶
여러분이 면접관이고 이 코드를 봤다고 하자. 어떤 질문을 던질 것인가?
- 10만 건 정렬의 시간 복잡도는?
- Python의
sort()는 어떤 알고리즘을 쓰는가? ORDER BY price LIMIT 20을 DB에서 직접 하면 얼마나 빠를까?- DB에 인덱스가 있다면 추가로 얼마나 빨라지는가?
- 상위 20개만 필요한데 10만 건을 다 정렬할 필요가 있는가?
마지막 질문이 핵심이다. "정렬을 한다"와 "Top-N을 뽑는다"는 시간 복잡도 자체가 다르다.
11-3. 결과 분석¶
Python의 list.sort()는 Tim Sort를 사용한다. 평균/최악 O(n log n)이다.
10만 건을 정렬하면 비교 횟수가 대략 100,000 * log2(100,000) ≈ 1,660,000번이다. 백만 단위 비교 연산은 Python 인터프리터 입장에서 가볍지 않다.
| 방식 | 시간 복잡도 | 10만 건 기준 |
|---|---|---|
| 애플리케이션에서 전체 정렬 | O(n log n) | 약 166만 번 비교 |
| Top-N Sort (heapq.nsmallest) | O(n log k) | 약 43만 번 비교 (k=20) |
| DB ORDER BY + LIMIT (인덱스 없음) | O(n log n) | DB에서 정렬 (네트워크 절약) |
| DB ORDER BY + LIMIT (인덱스 있음) | O(log n + k) | 인덱스에서 20건만 추출 |
같은 "상위 20개"인데 시간 복잡도가 4개 단계로 나뉜다.
sorted() vs heapq.nsmallest()¶
Python에서 "상위 N개만 필요하다"고 명시적으로 알려주는 방법이 heapq.nsmallest다. 전체를 정렬하지 않고 크기 N짜리 힙(heap)만 유지하면서 한 번 스캔한다.
import heapq
# 전체 정렬 후 슬라이싱: O(n log n)
top20 = sorted(products, key=lambda p: p["price"])[:20]
# Top-N Sort: O(n log k)
top20 = heapq.nsmallest(20, products, key=lambda p: p["price"])
10만 건에서 측정한 결과 (Python 3.12, M2 Pro, 단일 측정 평균값):
11-2에서 예측했으면, 아래를 펼쳐 실제 결과와 비교하자.
해답 펼쳐보기
| 방식 | 평균 실행 시간 | 배율 |
|---|---|---|
sorted()[:20] |
약 38 ms | 1.0x |
heapq.nsmallest(20, ...) |
약 11 ms | 3.5x |
(측정 환경: MacBook Pro M2 Pro, Python 3.12.3, 10만 건 dict 리스트, key 함수 동일. timeit 5회 평균. 환경마다 절대값은 다르지만 배율은 비슷하게 나온다.)
3배 차이는 작아 보일 수 있다. 그런데 RPS 1,000짜리 API에서 38ms와 11ms 차이는 그대로 P99 레이턴시에 꽂힌다. 부하 시점에 더 벌어진다.
그래도 진짜 문제는 따로 있다¶
위 두 방식 다 "10만 건을 메모리에 올린다"는 전제는 그대로다. 네트워크로 10만 건을 옮기고, Python 객체로 디코드하고, GC가 정리한다. 이게 정렬보다 더 비싸다.
DB에서 ORDER BY price LIMIT 20으로 내리면 네트워크엔 20건만 흐른다. 거기에 인덱스까지 있으면 정렬 자체가 사라진다.
이 문제의 핵심은 "정렬을 누가 더 잘하는가"가 아니라 "정렬을 할 필요가 있는가"다.
11-4. 코드 설명¶
# 단계 1: 가장 나쁜 코드
products = db.query("SELECT * FROM products") # 10만 건 전체를 메모리로
products.sort(key=lambda p: p["price"]) # O(n log n) 정렬
return products[:20] # 20개만 사용
# 단계 2: Top-N Sort로 개선 (그래도 메모리 문제는 남음)
import heapq
products = db.query("SELECT * FROM products")
return heapq.nsmallest(20, products, key=lambda p: p["price"])
# 단계 3: DB에 떠넘기기 (네트워크/메모리 절약)
products = db.query("SELECT * FROM products ORDER BY price LIMIT 20")
# 단계 4: 인덱스 추가 (정렬 자체가 사라짐)
# CREATE INDEX idx_products_price ON products(price);
# → ORDER BY price LIMIT 20이 O(log n + 20)
단계 1과 단계 4의 차이는 자릿수가 다르다. 같은 응답을 내놓는데 한쪽은 10만 건을 다 만지고, 다른 쪽은 20건만 만진다.
"이 작업 정말 정렬이 필요한가?" 체크리스트¶
코드에 sort()나 ORDER BY를 쓰기 전에 스스로에게 던질 질문이다.
- 결과가 정말 정렬 순서대로 필요한가, 아니면 그냥 N개만 있으면 되나?
- "랜덤 10개" 같은 요구면 정렬이 아예 불필요하다.
- 정렬 키가 한 가지인가, 사용자가 고를 수 있는가?
- 사용자 선택형이면 정렬 키마다 인덱스를 검토해야 한다.
- 데이터가 자주 바뀌는가, 거의 고정인가?
- 거의 고정이면 미리 정렬해서 캐시(Materialized View, Redis Sorted Set 등)에 둘 수 있다.
- 전체를 정렬해야 하는가, 상위 N개만 보면 되는가?
- 상위 N개면 Top-N Sort 또는
LIMIT을 쓴다. - 정렬 기준 컬럼에 인덱스가 있는가?
- 없다면 추가 비용을 감수하고 인덱스를 거는 게 거의 항상 이득이다 (쓰기 비용 < 읽기 비용일 때).
이 다섯 질문을 통과 못한 정렬은 대부분 잘못 쓴 정렬이다.
정렬 알고리즘 자체를 외워야 하는가¶
면접에서 Quick Sort, Merge Sort, Heap Sort를 비교하라는 질문은 흔하다. 그런데 실무에서 직접 정렬 알고리즘을 구현하는 일은 거의 없다. 표준 라이브러리(Python sort, Java Arrays.sort)가 이미 Tim Sort나 그 변형이고, 일반 데이터에서 충분히 빠르다.
실무에서 중요한 건 "정렬을 누가, 언제, 얼마나 자주 하는가"이다. 알고리즘 비교는 그 판단의 도구일 뿐이다.
(이 강의에서 Quick Sort 코드를 한 줄도 안 쓰는 이유다. 외운 것보다 "정렬을 안 해도 되게 만드는 법"이 중요하다.)
그런데 왜 인덱스가 있으면 더 빠른가? B-Tree가 이미 정렬된 상태를 유지하기 때문이다. 다음에서 Binary Search와 B-Tree를 본다.