DBMS Inner Join 최적화에서의 논리적 버그 탐지를 위한 집합론적 접근 방식

쿼리 옵티마이저(query optimizer)는 주어진 쿼리에 대해 대안적인 쿼리 계획(query plans)을 평가함으로써 가장 효율적인 실행 전략을 결정하는 데이터베이스 관리 시스템(DBMS)의 핵심 구성 요소입니다. 옵티마이저의 작업 중 조인 최적화(join optimization)는 다중 테이블 쿼리에서 조인의 순서가 실행 성능에 상당한 영향을 미칠 수 있기 때문에 중심적인 역할을 합니다. 그러나 조인 최적화의 내재적인 복잡성으로 인해 논리적 버그(logical bugs)는 불가피하며 종종 탐지하기 어렵습니다. 기존의 퍼징(fuzzing) 도구들이 크래시(crash) 및 성능 관련 오류를 찾아내는 데 주목할 만한 성과를 보여주었지만, 시스템이 잘못된 쿼리 결과를 생성하는 경우인 논리적 버그를 효과적으로 식별하는 것은 여전히 미해결 과제로 남아 있습니다. 본 논문에서는 집합론(set theory)의 관점을 통해 INNER JOIN 최적화와 관련된 DBMS 버그를 탐지하기 위한 변형 테스트(metamorphic testing) 접근 방식을 제안합니다. 각 테스트 케이스에 대해, 기본 집합 연산인 교집합(intersection)과 세 가지 의미 보존 변환 규칙, 즉 대칭 조인 변환(symmetric join transformation), 비대칭 차집합 변환(asymmetric difference transformation), 대칭 차집합 변환(symmetric difference transformation)을 기반으로 동등한 쿼리들을 생성합니다. 이 규칙들은 단순한 NATURAL/INNER JOIN 쿼리를 의미론적으로는 동일하지만 더 복잡한 형태로 재작성합니다. 우리는 이러한 설계를 JoinEquiv로 구현하였으며, 이는 원본 쿼리와 변환된 쿼리의 결과를 비교함으로써 DBMS 쿼리 처리 과정에서의 논리적 불일치를 체계적으로 찾아내는 테스트 오라클(testing oracle) 역할을 합니다. JoinEquiv를 사용하여 우리는 주요 DBMS(MySQL, TiDB, DuckDB, Percona)에서 이전에 알려지지 않았던 29개의 문제를 발견하였으며, 그 중 27개가 공식적으로 확인되었습니다. JoinEquiv는 DBMS 옵티마이저와 실행기(executor)의 깊은 논리적 결함을 드러내며, DBMS의 견고성(robustness)을 향상시키는 데 있어 그 가치를 강조합니다.