PostgreSQL 미드레벨 코딩·알고리즘 면접

DISTINCT ON은 정렬 후 첫 번째 행만 선택하는 방식으로 O(n log n) 정렬 비용이 발생하지만 메모리 사용이 적습니다. ROW_NUMBER는 전체 파티션을 윈도우 함수로 처리하므로 O(n log n) 정렬과 추가 메모리가 필요하며, WHERE 절에서 rn <= 3 필터링이 외부 쿼리에서 발생해 비효율적입니다. Lateral Join은 각 고객마다 서브쿼리를 실행하는 방식으로, 인덱스가 (customer_id, order_date DESC)로 구성되어 있으면 각 고객당 O(1) Index Scan으로 상위 3개만 조회하므로 전체 O(m)의 시간 복잡도를 가집니다. 이 시나리오에서는 Lateral Join이 인덱스를 최대한 활용하여 불필요한 정렬을 피하므로 가장 효율적이며, 실행 계획에서 Nested Loop + Index Scan으로 나타납니다.

WITH RECURSIVE를 사용해 base case로 1단계 친구를 선택하고, recursive case에서 depth < 2 조건으로 제한합니다. 순환 참조 방지를 위해 path 배열(INTEGER[])에 방문한 user_id를 누적하고, NOT (next_friend = ANY(path)) 조건으로 이미 방문한 노드를 제외합니다. 양방향 관계이므로 UNION을 사용해 user_id와 friend_id를 모두 탐색하되, 최종 결과에서 본인과 1단계 친구를 NOT IN 서브쿼리로 제외합니다. 시간 복잡도는 평균 친구 100명 기준 O(100²) = O(10,000)이며, 배열 연산이 추가되어 실제로는 더 높습니다. 최적화를 위해 (user_id, friend_id)와 (friend_id, user_id) 양방향 인덱스를 생성하고, DISTINCT를 사용해 중복 경로를 조기에 제거하며, LIMIT으로 추천 수를 제한하여 불필요한 탐색을 줄입니다. 대규모 네트워크에서는 재귀 CTE 대신 애플리케이션 레벨에서 BFS 알고리즘을 구현하거나 그래프 데이터베이스를 고려해야 합니다.

COUNT(DISTINCT user_id)는 각 시간대 그룹마다 해시 테이블을 생성하여 중복을 제거하므로 O(n) 시간과 O(k) 공간(k는 고유 사용자 수)이 필요하며, work_mem 설정에 따라 디스크 정렬이 발생할 수 있습니다. Window Function과 DENSE_RANK는 전체 데이터를 (event_time, user_id)로 정렬한 후 순위를 매기는 방식으로 O(n log n) 시간과 추가 메모리가 필요하며, 실행 계획에서 WindowAgg 노드가 나타납니다. 두 단계 집계는 먼저 (date_trunc('hour', event_time), user_id)로 중복 제거한 후 시간대별 COUNT하는 방식으로, DISTINCT 서브쿼리가 중간 결과를 줄여 메모리 효율적이지만 두 번의 집계 연산이 필요합니다. HyperLogLog는 O(1) 공간으로 근사 카운팅을 제공하며 오차율 2% 이내로 매우 큰 카디널리티에서 유리하지만, 정확한 값이 필요한 경우 사용할 수 없습니다. 1억 건 규모에서는 (event_time, user_id) 복합 인덱스와 함께 두 단계 집계 방식이 중간 결과 크기를 최소화하여 가장 효율적이며, 실시간성이 중요하고 근사치로 충분하다면 HyperLogLog가 최선입니다.