Efficient Query Rewrite Rule Discovery via Standardized Enumeration and Learning-to-Rank(extend)

이 논문은 표준화된 템플릿 열거와 학습 기반 랭킹을 결합하여 검색 공간을 대폭 축소하고 100 만 개 이상의 자동 생성된 재작성 규칙을 확보함으로써 복잡한 쿼리 최적화를 가능하게 하는 확장성 있는 시스템 SLER 을 제안합니다.

핵심

🚀 SLER: 데이터베이스를 위한 '스마트 규칙 발견가'

이 논문은 데이터베이스가 훨씬 더 빠르게 작동하도록 돕는 새로운 시스템 SLER을 소개합니다. 기존 방식이 가진 한계를 깨고, 훨씬 더 복잡하고 정교한 질문 (쿼리) 들을 처리할 수 있게 해주는 혁신적인 방법입니다.

이 내용을 일반인도 쉽게 이해할 수 있도록 마법 같은 요리사와 도서관의 비유로 설명해 드리겠습니다.

---

1. 문제: 왜 기존 방식은 지쳤을까? (기존의 'WeTune' 시스템)

데이터베이스는 수많은 데이터를 저장하고 찾는 곳입니다. 사용자가 "지난달에 5 만 원 이상 연봉을 받은 직원의 부서 ID 를 찾아줘"라고 질문하면, 데이터베이스는 이를 최적화해서 빠르게 답을 찾아야 합니다. 이를 위해 **규칙 (Rule)**이라는 요리 레시피를 사용합니다.

• 기존 방식 (WeTune):
  • 마치 모든 가능한 요리 레시피를 일일이 손으로 적어보는 요리사 같습니다.
  • 문제는 레시피가 너무 많다는 것입니다. 간단한 레시피 (4 단계 이하) 는 만들 수 있지만, 복잡한 레시피 (5 단계 이상) 를 만들려고 하면 시간이 수년이 걸립니다.
  • 게다가 만든 레시피 100 개 중 90 개는 이미 있는 것과 똑같은 '중복'이거나, 아무런 도움이 안 되는 '하찮은' 것들입니다.
  • 결과: 복잡한 질문이 들어오면, 이 시스템은 "어, 이거 어떻게 해?"라며 멈춰버립니다.

2. 해결책: SLER 의 등장 (스마트한 규칙 발견가)

이 논문이 제안한 SLER은 단순히 레시피를 무작위로 찾는 게 아니라, 세 가지 지능적인 전략을 사용합니다.

🧩 전략 1: "표준화된 템플릿" (요리 재료 정리하기)

• 비유: 요리할 때 재료를 다듬지 않고 그대로 넣으면 요리가 꼬입니다. SLER 은 먼저 모든 레시피를 표준화된 형태로 정리합니다.
• 원리: "필터"와 "프로젝트" 같은 연산자 순서가 조금만 달라도 다른 레시피로 보일 수 있는데, SLER 은 이를 같은 것으로 간주합니다.
• 효과: 불필요한 레시피를 아예 만들지 않아서, 탐색할 공간이 기하급수적으로 줄어듭니다. 마치 도서관에서 책 제목만 보고 중복된 책을 미리 제거하는 것과 같습니다.

🗑️ 전략 2: "RTP 알고리즘" (중복 쓰레기 수거)

• 비유: 새로운 레시피를 만들 때마다, "이거 이미 있잖아?"라고 확인하는 과정이 필요합니다. 기존 방식은 모든 레시피를 다 확인하느라 시간이 걸렸지만, SLER 은 생성하는 순간 중복을 찾아냅니다.
• 원리: 두 개의 템플릿 (시작과 끝) 쌍을 기준으로, 이미 알려진 규칙과 겹치는지 즉시 체크합니다.
• 효과: 쓸데없는 확인 작업을 대폭 줄여서, 복잡한 5~6 단계 이상의 레시피도 만들 수 있게 되었습니다.

🏆 전략 3: "학습된 랭킹 (Learning-to-Rank)" (최고 요리사 선발)

• 비유: 수만 개의 레시피가 생겼을 때, 다 쓸 수 없죠. SLER 은 **AI(머신러닝)**를 훈련시켜 "어떤 레시피가 실제로 요리 시간을 단축해 줄까?"를 예측합니다.
• 원리: 과거의 실제 데이터 (실제 SQL 쿼리) 를 학습시켜, 가장 효과가 좋은 규칙을 상위 100 개로 먼저 뽑아냅니다.
• 효과: 모든 규칙을 다 검증할 필요 없이, 가장 유망한 규칙들만 집중적으로 검증합니다. 덕분에 7 단계 이상의 아주 복잡한 규칙도 찾아낼 수 있게 되었습니다.

---

3. SLER 의 놀라운 성과

이 시스템을 실제로 테스트한 결과는 다음과 같습니다.

• 규칙의 양: 기존 시스템이 만들 수 없었던 100 만 개 이상의 새로운 규칙을 찾아냈습니다. (기존의 4 단계 제한을 깨고 6 단계, 심지어 10 단계까지!)
• 속도: 작은 규칙을 찾는 속도는 기존보다 3 배 이상 빠르며, 복잡한 규칙을 찾는 것은 기존에는 불가능했던 일입니다.
• 실제 효과: 복잡한 질문 (예: 여러 테이블을 여러 번 조인하고 서브쿼리가 겹친 경우) 을 처리할 때, 기존 방식은 아예 답을 못 찾거나 비효율적인 답을 줬지만, SLER 은 최적의 답을 한 번에 찾아냅니다.

4. 요약: 왜 이것이 중요한가요?

지금까지 데이터베이스는 간단한 질문만 잘 처리할 수 있었습니다. 하지만 요즘은 AI 나 복잡한 앱들이 만들어내는 질문들이 너무 복잡해져서 기존 시스템이 따라가지 못했습니다.

SLER은 마치 지능적인 비서처럼, 방대한 규칙 중에서 가장 효율적인 것들만 골라내어 데이터베이스가 더 빠르고 똑똑하게 작동하도록 도와줍니다.

• 기존: "모든 것을 다 찾아보자" (시간이 너무 오래 걸림, 실패함)
• SLER: "표준화해서 정리하고, AI 가 좋은 것만 골라내자" (빠르고, 정확함, 복잡한 일도 해결함)

이 기술은 앞으로 우리가 사용하는 모든 데이터 기반 서비스 (은행, 쇼핑, SNS 등) 가 더 빠르게 반응하는 데 기여할 것입니다.

기술 요약

1. 문제 정의 (Problem Definition)

데이터베이스 성능 최적화의 핵심인 쿼리 재작성 (Query Rewriting) 분야에서 기존 자동화 방법론은 다음과 같은 심각한 한계에 직면해 있습니다.

• 기존 방식의 비효율성: 최신 기술 (SOTA) 인 WeTune 과 같은 도구는 모든 가능한 쿼리 계획 템플릿 쌍을 무차별 대입 (Brute-force) 방식으로 탐색합니다. 이로 인해 탐색 공간이 기하급수적으로 증가하여 계산 비용이 매우 높습니다.
• 확장성 부족: WeTune 은 4 개 이하의 노드 (연산자) 를 가진 템플릿만 처리할 수 있습니다. 그러나 실제 업무 환경 (PostgreSQL 등) 에서는 5~8 개, 복잡할 경우 10 개 이상의 노드를 가진 쿼리가 빈번하게 발생합니다. 5 개 노드 규칙을 생성하는 데 6 개월, 6 개 노드는 10 년 이상의 시간이 소요될 수 있어 실용적이지 않습니다.
• 중복 및 비효율성: 생성된 규칙의 90% 이상이 중복이며, 나머지 중 50% 이상은 최적화 가치가 없는 사소한 규칙들입니다.
• 효과성 한계: 복잡한 패턴 (예: ORM 이 생성한 중첩 서브쿼리) 에 대한 유효한 재작성 규칙이 부족하여, 기존 최적화기가 복잡한 쿼리를 단순화하지 못합니다.

2. 제안 방법론 (Methodology: SLER)

저자들은 **SLER (Scalable Learning-to-Rank based Rule Discovery)**라는 새로운 시스템을 제안합니다. 이는 **표준화된 템플릿 열거 (Standardized Enumeration)**와 **학습 기반 랭킹 (Learning-to-Rank)**을 결합하여 효율성과 효과성을 동시에 해결합니다.

A. 표준화된 규칙 열거 (Standardized Rule Enumeration)

• 표준화 템플릿 (Standardized Templates): 쿼리 계획의 구조적 중복을 제거하기 위해 연산자 (Project, Filter, Join 등) 의 위치를 일정한 규칙 (예: Projection 이 Join 아래에 오도록) 으로 정렬하거나 불필요한 연산자를 제거하는 '표준화' 과정을 도입합니다.
• 중복 제거: 구조적으로 동일하지만 연산자 순서만 다른 템플릿 쌍을 사전에 필터링하여, 불필요한 검증 (SMT Solver 호출 등) 을 줄입니다. 이를 통해 검증 복잡도를 지수 시간에서 다항 시간으로 낮춥니다.
• 알고리즘:
  • Operator Removal: 단일 입력 노드 중 불필요한 것을 제거.
  • Operator Swapping: 연산자의 우선순위에 따라 위치를 교환하여 정규화된 구조로 만듦.

B. RTP 기반 중복 제거 (RTP-based Deduplication)

• Reduce by Template Pair (RTP) 알고리즘: 규칙 생성 단계에서 템플릿 쌍 (Source, Destination) 단위로 중복을 즉시 제거합니다.
• 작동 원리: 생성된 규칙이 기존 규칙 집합과 동등한 결과를 내는지 확인하고, 중복되면 즉시 폐기합니다. 이는 전체 규칙 집합을 생성한 후 일괄 제거하는 방식보다 훨씬 효율적입니다.

C. 학습 기반 랭킹 (Learning-to-Rank)

• LambdaMART 모델 적용: 수천 개의 실제 SQL 쿼리 데이터를 기반으로 학습된 랭킹 모델을 사용하여, 어떤 템플릿 쌍이 성능 향상에 기여할 가능성이 높은지 예측합니다.
• 특징 추출: 템플릿의 구조적 거리 (L2 Distance), 코사인 유사도, 표현식 복잡도 (연산자 수, 중첩 깊이 등) 를 특징으로 사용합니다.
• Top-k 필터링: 모든 규칙을 검증하는 대신, 랭킹 모델이 예측한 점수가 높은 상위 $k$개의 템플릿 쌍만 선별하여 규칙을 생성합니다. 이를 통해 7 개 이상의 노드를 가진 복잡한 템플릿도 확장 가능하게 다룰 수 있습니다.

3. 주요 기여 (Key Contributions)

1. 효율성 극대화: "작은 것에서 큰 것으로 (Small-to-Large)" 규칙을 조합한다는 가설이 대부분의 복잡한 규칙에 적용되지 않음을 실험적으로 증명하고, 이를 대신하여 표준화된 템플릿을 통한 직접 열거 방식을 제안했습니다. 이를 통해 4 노드 규칙 생성 시간을 WeTune 대비 약 34% 수준으로 단축했습니다.
2. 확장성 확보: 5~6 노드 규칙 생성을 가능하게 했으며, 랭킹 모델을 통한 선별적 열거를 통해 7 노드 이상 (최대 10 노드) 의 복잡한 규칙도 탐색할 수 있는 체계를 마련했습니다.
3. 대규모 규칙 데이터베이스 구축: 오픈소스 및 상용 워크로드의 11,000 개 이상의 SQL 쿼리를 분석하여 100 만 개 이상의 유효한 재작성 규칙을 자동으로 생성했습니다. 이는 현재까지 실험적으로 검증된 가장 큰 규칙 라이브러리입니다.
4. 효과성 입증: 기존 WeTune 이 처리하지 못했던 복잡한 쿼리 (q1, q4, q7 등) 를 한 단계로 최적화하거나, WeTune 이 불가능했던 5~9 노드 구조의 패턴을 성공적으로 재작성했습니다.

4. 실험 결과 (Results)

• 성능 (Efficiency):
  • 생성 시간: 4 노드 규칙 생성 시 WeTune(67 시간 4 분) 대비 SLER(20 시간 49 분) 로 약 3 배 이상 빠릅니다.
  • 중복 제거 시간: 4 노드 기준 WeTune(20 일 19 시간) 대비 SLER(9 분 57 초) 로 약 300 배 이상 단축되었습니다.
  • 확장성: 5 노드 규칙 생성은 30 일, 6 노드는 395 일 소요되지만, 랭킹 필터링 (Top-k) 을 적용하면 10 노드 규칙도 523 분 내에 5,000 개 이상의 유효 규칙을 발견할 수 있습니다.
• 효과성 (Effectiveness):
  • 규칙 수: WeTune 의 4 노드 규칙 집합 대비 약 98 배 더 큰 (679,316 개) 규칙 집합을 구축했습니다.
  • 최적화 품질: SLER 규칙을 적용한 쿼리는 WeTune 대비 더 높은 최적화 비율을 보였으며, 특히 WeTune 이 최적화하지 못했던 복잡한 쿼리에서 획기적인 성능 개선 (최대 98.6% 향상) 을 달성했습니다.
  • 랭킹 정확도: 생성된 규칙 중 상위 500 개 규칙이 전체 성능 향상의 98.6% 를 담당하여, 랭킹 모델이 고가치 규칙을 정확히 선별함을 입증했습니다.

5. 의의 및 결론 (Significance & Conclusion)

• 차세대 옵티마이저의 기반: SLER 는 수동으로 규칙을 정의하는 전통적인 방식의 한계를 넘어, 데이터베이스가 스스로 복잡한 쿼리 패턴을 학습하고 최적화 규칙을 발견할 수 있는 토대를 마련했습니다.
• 실무 적용 가능성: ORM 이 생성하는 비효율적인 SQL, 중첩 서브쿼리 등 현대 웹 애플리케이션의 복잡한 쿼리를 효과적으로 처리할 수 있어, 실제 상용 데이터베이스 (Tencent, Yashan DB 등) 에 적용 시 큰 성능 향상을 기대할 수 있습니다.
• 확장성: 현재는 기본 관계형 연산자에 국한되었으나, 집계 (Aggregate), 그룹화 (Group-by), 윈도우 함수 등으로 표준화 템플릿을 확장하면 OLAP 워크로드까지 적용 가능한 유연한 프레임워크입니다.

요약하자면, SLER 는 **표준화 (Standardization)**를 통한 중복 제거와 **머신러닝 (Learning-to-Rank)**을 통한 지능형 선별을 결합하여, 기존에는 계산 비용 때문에 불가능했던 대규모 쿼리 재작성 규칙의 자동 발견을 실현한 획기적인 연구입니다.