SQL의 재귀 CTE(Common Table Expression)는 복잡한 문제 해결에 강력한 도구가 될 수 있습니다. 특히, 스도쿠 퍼즐과 같이 탐색 및 백트래킹이 필요한 문제에 효율적으로 적용될 수 있습니다. 그러나 동일한 로직의 SQL 쿼리가 데이터베이스 시스템에 따라 전혀 다른 성능 특성을 보일 때가 있습니다. 본 글에서는 재귀 CTE를 사용하여 스도쿠를 해결하는 쿼리가 PostgreSQL에서는 매우 빠르게 실행되는 반면, DuckDB에서는 특정 조건에서 예상보다 오랜 시간이 걸리는 현상과 관련된 SQL 코드를 살펴보고 그 구성을 분석합니다.
제시된 스도쿠 해결 SQL 쿼리는 단일 행 데이터를 기반으로 654번의 재귀 CTE 반복을 수행합니다. 이 쿼리는 PostgreSQL에서는 1초 미만으로 실행되지만, DuckDB에서는 다중 스레드 환경에서 100밀리초 이상, 단일 스레드 환경에서는 7초 이상이 소요되는 성능 차이를 보였습니다.
아래는 스도쿠를 해결하기 위한 SQL 쿼리입니다. 이 쿼리는 숫자를 채워나가는 스도쿠의 논리를 SQL의 재귀 CTE로 구현한 것입니다.
WITH RECURSIVE
-- 스도쿠에 사용 가능한 숫자 (1-9) 생성
ValidNums(digit) AS MATERIALIZED (
SELECT val FROM generate_series(1, 9) AS t(val)
),
-- 스도쿠 그리드의 81개 칸에 대한 위치 정보 계산
-- idx: 전체 위치 (1-81), row_id: 행 (1-9), col_id: 열 (1-9), block_id: 3x3 블록 (1-9)
GridCoordinates(idx, row_id, col_id, block_id) AS MATERIALIZED (
SELECT
pos_val,
((pos_val - 1) // 9) + 1 AS row_id,
((pos_val - 1) % 9) + 1 AS col_id,
((pos_val - 1) // 9) // 3 * 3 + ((pos_val - 1) % 9) // 3 + 1 AS block_id
FROM generate_series(1, 81) AS pos_gen(pos_val)
),
-- 초기 스도쿠 퍼즐 데이터 전처리: 공백 제거, '?'를 '0'으로, 문자열을 정수 배열로 변환
InitialPuzzle(puzzle_id, original_string, current_board) AS (
SELECT
3 AS puzzle_id, -- 퍼즐 식별자 (예: ID 3)
E'800000000003600000070090200050007000000045700000100030001000068008500010090000400' AS original_string,
regexp_split_to_array(
regexp_replace(regexp_replace(
E'800000000003600000070090200050007000000045700000100030001000068008500010090000400',
'[\r\n\s]', '', 'g'
), '\?', '0', 'g'),
''
)::INTEGER[] AS current_board
),
-- 재귀적으로 스도쿠를 해결하는 핵심 CTE
SolverCore(puzzle_id, step_status, board_state, backtrack_stack, iteration_count) AS MATERIALIZED (
-- 재귀 초기 상태: 전처리된 스도쿠 보드 로드
SELECT
puzzle_id,
'시작' AS step_status,
current_board,
ARRAY[]::INTEGER[][], -- 빈 백트래킹 스택 초기화
0 AS iteration_count
FROM InitialPuzzle
UNION ALL
-- 재귀 본체: 다음 단계의 보드 상태 계산
SELECT
sc.puzzle_id,
next_step.status_msg,
next_step.new_board,
next_step.updated_backtrack_stack,
sc.iteration_count + 1
FROM SolverCore AS sc
CROSS JOIN LATERAL (
WITH
-- 현재 보드 상태와 그리드 위치 정보를 결합하여 각 셀의 상세 정보 생성
BoardCells(idx, row_id, col_id, block_id, cell_val) AS (
SELECT gc.idx, gc.row_id, gc.col_id, gc.block_id, sc.board_state[gc.idx]
FROM GridCoordinates AS gc
),
-- 빈 셀에 대해 유효한 후보 숫자 계산 (행/열/블록 중복 없음)
CandidateDigits(idx, row_id, col_id, block_id, digit) AS (
SELECT bc.idx, bc.row_id, bc.col_id, bc.block_id, vn.digit
FROM BoardCells AS bc
CROSS JOIN ValidNums AS vn
LEFT JOIN BoardCells AS bc_row ON bc_row.row_id = bc.row_id AND bc_row.cell_val = vn.digit
LEFT JOIN BoardCells AS bc_col ON bc_col.col_id = bc.col_id AND bc_col.cell_val = vn.digit
LEFT JOIN BoardCells AS bc_block ON bc_block.block_id = bc.block_id AND bc_block.cell_val = vn.digit
WHERE bc.cell_val = 0 -- 빈 셀
AND bc_row.row_id IS NULL -- 해당 행에 후보 숫자가 없음
AND bc_col.col_id IS NULL -- 해당 열에 후보 숫자가 없음
AND bc_block.block_id IS NULL -- 해당 블록에 후보 숫자가 없음
),
-- 유일하게 채울 수 있는 셀 또는 행/열/블록에서 유일한 후보 숫자 찾기
UniquePlacements(idx, row_id, col_id, block_id, digit) AS (
-- 셀 자체에서 유일한 후보
SELECT idx, row_id, col_id, block_id, MIN(digit)
FROM CandidateDigits GROUP BY idx, row_id, col_id, block_id HAVING COUNT(1) = 1
UNION ALL
-- 특정 행에서 유일한 후보
SELECT MIN(idx), row_id, MIN(col_id), MIN(block_id), digit
FROM CandidateDigits GROUP BY row_id, digit HAVING COUNT(1) = 1
UNION ALL
-- 특정 열에서 유일한 후보
SELECT MIN(idx), MIN(row_id), col_id, MIN(block_id), digit
FROM CandidateDigits GROUP BY col_id, digit HAVING COUNT(1) = 1
UNION ALL
-- 특정 블록에서 유일한 후보
SELECT MIN(idx), MIN(row_id), MIN(col_id), block_id, digit
FROM CandidateDigits GROUP BY block_id, digit HAVING COUNT(1) = 1
),
-- 보드 상태 유효성 검사 및 확정적 채움 여부 확인
ValidationResult(has_conflicts, has_definite_placements, has_unsolvable_empty_cells) AS (
SELECT
-- 확정된 채움에서 발생할 수 있는 충돌 (예: 동일 행/열/블록에 동일 숫자)
EXISTS (SELECT 1 FROM UniquePlacements GROUP BY row_id, digit HAVING COUNT(*) > 1) OR
EXISTS (SELECT 1 FROM UniquePlacements GROUP BY col_id, digit HAVING COUNT(*) > 1) OR
EXISTS (SELECT 1 FROM UniquePlacements GROUP BY block_id, digit HAVING COUNT(*) > 1) OR
EXISTS (SELECT 1 FROM UniquePlacements GROUP BY idx, digit HAVING COUNT(*) > 1) AS has_conflicts,
-- 확정적으로 채울 수 있는 칸이 있는지
EXISTS (SELECT 1 FROM UniquePlacements) AS has_definite_placements,
-- 빈 셀이 남아있지만 채울 수 있는 후보 숫자가 없는 경우 (더 이상 진행 불가)
(EXISTS (SELECT 1 FROM BoardCells WHERE cell_val = 0) AND NOT EXISTS (SELECT 1 FROM CandidateDigits)) AS has_unsolvable_empty_cells
),
-- 최종적으로 적용될 보드 (확정 채움 이후)
NextBoardState(board) AS (
SELECT
ARRAY(SELECT COALESCE(up.digit, sc.board_state[gc.idx]) ORDER BY gc.idx)
FROM GridCoordinates AS gc
LEFT JOIN UniquePlacements AS up ON gc.idx = up.idx
),
-- 추측에 사용할 '가장 적은 후보'를 가진 셀 찾기
GuessCandidate(best_guess_idx) AS (
SELECT idx FROM CandidateDigits GROUP BY idx ORDER BY COUNT(1), idx LIMIT 1
),
-- 선택된 추측 셀의 모든 후보 숫자
GuessOptions(guess_digit) AS (
SELECT cd.digit FROM CandidateDigits AS cd, GuessCandidate AS gc WHERE cd.idx = gc.best_guess_idx
),
-- 첫 번째 추측 시도 보드 (가장 작은 후보 숫자를 사용)
FirstGuessBoard(board) AS (
SELECT
sc.board_state[1 : (gc.best_guess_idx - 1)] || ARRAY[go.guess_digit] || sc.board_state[(gc.best_guess_idx + 1) : 81]
FROM GuessCandidate AS gc, GuessOptions AS go
ORDER BY go.guess_digit
LIMIT 1
),
-- 나머지 추측 시도 보드들을 백트래킹 스택에 추가
RemainingGuesses(boards_for_backtrack) AS (
SELECT ARRAY_AGG(board_arr)
FROM (
SELECT
sc.board_state[1 : (gc.best_guess_idx - 1)] || ARRAY[go.guess_digit] || sc.board_state[(gc.best_guess_idx + 1) : 81] AS board_arr
FROM GuessCandidate AS gc, GuessOptions AS go
ORDER BY go.guess_digit
OFFSET 1
) AS temp_boards
)
-- 분기 1: 확정 채우기 - 확정 칸이 있고 충돌이 없는 유효한 상태
SELECT '확정 채우기' AS status_msg, nbs.board AS new_board, sc.backtrack_stack AS updated_backtrack_stack
FROM NextBoardState AS nbs, ValidationResult AS vr
WHERE vr.has_definite_placements AND NOT vr.has_conflicts AND NOT vr.has_unsolvable_empty_cells
UNION ALL
-- 분기 2: 추측 채우기 - 확정 칸은 없지만 충돌이 없는 유효한 상태 (가장 적은 후보를 가진 칸에 추측 시도)
SELECT '추측 채우기' AS status_msg, fgb.board AS new_board, COALESCE(rg.boards_for_backtrack, ARRAY[]::INTEGER[][]) || sc.backtrack_stack AS updated_backtrack_stack
FROM ValidationResult AS vr, FirstGuessBoard AS fgb, RemainingGuesses AS rg
WHERE NOT vr.has_definite_placements AND NOT vr.has_conflicts AND NOT vr.has_unsolvable_empty_cells
AND EXISTS (SELECT 1 FROM GuessCandidate) -- 추측할 셀이 있는 경우에만 시도
UNION ALL
-- 분기 3: 백트래킹 - 충돌이 있거나 더 이상 채울 수 없는 빈 셀이 있는 유효하지 않은 상태
SELECT '백트래킹' AS status_msg, sc.backtrack_stack[1] AS new_board, sc.backtrack_stack[2:] AS updated_backtrack_stack
FROM ValidationResult AS vr
WHERE (vr.has_conflicts OR vr.has_unsolvable_empty_cells) AND array_length(sc.backtrack_stack, 1) > 0
) AS next_step
-- 재귀 중단 조건: 최대 반복 횟수 도달 또는 모든 셀이 채워지지 않은 상태 (0이 남아있음)
WHERE sc.iteration_count < 10000 AND sc.board_state @> ARRAY[0]
)
-- 최종 결과 출력: 해결된 스도쿠 보드를 9x9 문자열 형식으로 변환
SELECT
s.puzzle_id,
ip.original_string,
array_to_string(
ARRAY(SELECT CASE WHEN element_pos % 9 = 1 AND element_pos > 1 THEN E'\n' ELSE '' END || element_val::TEXT
FROM UNNEST(s.board_state) WITH ORDINALITY AS elem(element_val, element_pos)),
''
) AS solved_sudoku_result
FROM SolverCore AS s
JOIN InitialPuzzle AS ip ON s.puzzle_id = ip.puzzle_id
WHERE NOT s.board_state @> ARRAY[0] AND array_length(s.board_state, 1) = 81;
SQL 코드 분석
MATERIALIZED힌트: 일부 CTE에MATERIALIZED힌트가 사용되었습니다. 이는 CTE 결과를 물리적으로 저장하여 재사용함으로써 복잡한 쿼리의 성능을 향상시키는 데 도움이 될 수 있습니다. PostgreSQL에서는 옵티마이저가 자동으로 판단하지만, 명시적으로 힌트를 주어 동작을 유도할 수 있습니다. DuckDB에서도 이 힌트는 옵티마이저에게 가이드를 제공합니다.- 정수 나눗셈 연산자: DuckDB는 정수 나눗셈을 위해
//연산자를 사용합니다. PostgreSQL은 두 피연산자가 모두 정수일 때/연산자가 정수 나눗셈을 수행합니다. - 배열 슬라이싱: 백트래킹 스택을 관리할 때
sc.backtrack_stack[2:]와 같은 배열 슬라이싱 구문이 사용되었습니다. 이는 DuckDB에서 지원하는 간결한 문법입니다. PostgreSQL에서는sc.backtrack_stack[2:array_length(sc.backtrack_stack, 1)]와 같이 명시적으로 배열의 길이를 지정해야 합니다. - 재귀 로직:
InitialPuzzle: 초기 스도쿠 퍼즐 문자열을 정수 배열로 파싱합니다.ValidNums및GridCoordinates: 스도쿠의 기본 숫자 범위(1-9)와 9x9 그리드의 각 셀에 대한 위치 정보를 미리 계산하여 재귀 과정에서 효율적으로 사용합니다.SolverCore: 핵심 재귀 CTE로, 현재 스도쿠 보드 상태(board_state), 백트래킹을 위한 이전 보드 상태 스택(backtrack_stack), 반복 횟수 등을 관리합니다.BoardCells,CandidateDigits,UniquePlacements: 현재 보드 상태에서 빈 셀을 식별하고, 각 셀에 채울 수 있는 유효한 후보 숫자들을 찾아내며, 특정 셀, 행, 열, 또는 블록에서 유일하게 확정 가능한 숫자를 결정합니다.ValidationResult: 현재 보드 상태가 유효한지(충돌 없음), 확정적으로 채울 수 있는 칸이 있는지, 혹은 더 이상 진행할 수 없는 막다른 길인지 등을 판단합니다.- 확정 채우기, 추측 채우기, 백트래킹: 이 세 가지 분기를 통해 스도쿠를 해결합니다.
- 확정 채우기: 유일하게 채울 수 있는 칸이 있고 충돌이 없는 경우, 해당 숫자를 보드에 적용합니다.
- 추측 채우기: 확정적으로 채울 수 있는 칸이 없지만 유효한 상태일 때, 가장 적은 수의 후보를 가진 셀을 선택하여 첫 번째 후보 숫자를 채우고, 나머지 후보들은 백트래킹 스택에 저장합니다.
- 백트래킹: 충돌이 발생하거나 더 이상 채울 수 있는 칸이 없는 막다른 길에 도달했을 때, 백트래킹 스택에서 이전 보드 상태를 가져와 다시 시도합니다.
성능 차이 및 고려사항
이 쿼리가 PostgreSQL에서 더 빠르고 DuckDB에서 느리게 동작하는 원인은 여러 가지가 있을 수 있습니다. DuckDB는 OLAP(온라인 분석 처리) 워크로드에 최적화된 반면, 재귀 CTE는 복잡한 반복 로직과 작은 단위의 데이터 조작을 많이 포함하며, 특히 배열 연산과 LATERAL JOIN의 효율성에 따라 성능이 크게 달라질 수 있습니다. PostgreSQL은 OLTP(온라인 트랜잭션 처리) 및 복잡한 SQL 로직 처리에서 오랜 경험을 가지고 있어, 이러한 유형의 재귀 및 배열 기반 연산에 대한 최적화가 더 잘 이루어져 있을 가능성이 있습니다. 또한, DuckDB의 다중 스레드 처리가 이 특정 재귀 패턴에서 오버헤드를 발생시켜 단일 스레드보다 느리게 만들 수도 있습니다.
다음은 실제 실행 결과입니다.
postgres=# \i 1230/0112en.txt
id | pz | result
----+-----------------------------------------------------------------------------------+-----------
3 | 800000000003600000070090200050007000000045700000100030001000068008500010090000400 | 812753649+
| | 943682175+
| | 675491283+
| | 154237896+
| | 369845721+
| | 287169534+
| | 521974368+
| | 438526917+
| | 796318452
(1 row)
Time: 135.542 ms
DuckDB 다중 스레드 환경:
D .read 1230/0112ducken.txt
┌───────┬───────────────────────────────────────────────────────┬──────────────────────────────────────────────────────┐
│ id │ pz │ result │
│ int32 │ varchar │ varchar │
├───────┼───────────────────────────────────────────────────────┼──────────────────────────────────────────────────────┤
│ 3 │ 80000000000360000007009020005000700000004570000010003 │ 812753649\n943682175\n675491283\n154237896\n36984572 │
│ │ 0001000068008500010090000400 │ 1\n287169534\n521974368\n438526917\n796318452 │
└───────┴───────────────────────────────────────────────────────┴──────────────────────────────────────────────────────┘
Run Time (s): real 11.169 user 24.808297 sys 10.038441
DuckDB 단일 스레드 환경:
D set threads=1;
Run Time (s): real 0.007 user 0.011898 sys 0.000619
D .read 1230/0112ducken.txt
┌───────┬───────────────────────────────────────────────────────┬──────────────────────────────────────────────────────┐
│ id │ pz │ result │
│ int32 │ varchar │ varchar │
├───────┼───────────────────────────────────────────────────────┼──────────────────────────────────────────────────────┤
│ 3 │ 80000000000360000007009020005000700000004570000010003 │ 812753649\n943682175\n675491283\n154237896\n36984572 │
│ │ 0001000068008500010090000400 │ 1\n28716934\n521974368\n438526917\n796318452 │
└───────┴───────────────────────────────────────────────────────┴──────────────────────────────────────────────────────┘
Run Time (s): real 7.429 user 6.501462 sys 0.397789