LQRS: Learned Query Re-optimization Framework for Spark SQL

본 논문은 실행 중 생성된 런타임 관측치를 활용하여 동적 계획 수정을 가능하게 하는 'LQRS'라는 학습 기반 쿼리 재최적화 프레임워크를 제안하며, 이를 통해 Spark SQL 환경에서 기존 학습 기반 최적화 기법 대비 최대 90% 의 실행 시간 단축을 달성함을 보여줍니다.

핵심

🍳 비유: "현장에서 레시피를 즉석으로 수정하는 천재 요리사"

1. 기존 방식의 문제점: "예상만 믿는 요리사"

기존의 데이터베이스 (Spark SQL) 나 최신 학습형 최적화기 (Lero 등) 는 마치 미리 정해진 레시피대로만 요리하는 요리사와 같습니다.

• 문제: 요리 시작 전에 "양파가 5 개 정도 들어갈 거야"라고 예상하고 레시피를 짭니다. 하지만 실제 요리 도중 양파가 50 개나 들어오거나, 재료가 생각보다 훨씬 적게 나올 수 있습니다.
• 결과: 레시피가 틀렸는데도, 요리사가 "아, 내 예상대로야"라고 믿고 계속 잘못된 순서로 요리를 진행합니다. 결국 요리가 늦어지거나, 재료가 넘쳐서 냄비가 터지는 (메모리 부족) 상황이 발생합니다.

2. LQRS 의 혁신: "실시간 관찰과 즉석 수정"

LQRS 는 이 문제를 해결하기 위해 실시간으로 상황을 보고 레시피를 수정하는 천재 요리사를 도입했습니다.

• 핵심 아이디어: "요리하기 전에 계획을 세우되, 요리하는 도중에도 재료가 어떻게 나오는지 보고 계획을 바꿀 수 있어!"
• 예시:
  • 상황: 1 단계 요리 (첫 번째 재료를 다지는 것) 를 해보니, 예상과 달리 양파가 1 개만 나왔습니다.
  • 기존 방식: "아, 레시피대로 2 단계로 넘어가자." (계속 잘못된 경로)
  • LQRS 방식: "어? 양파가 하나밖에 없네? 그럼 이걸 먼저 다른 재료와 섞는 게 훨씬 빠르겠다!"라고 즉석에서 조리 순서를 바꿉니다.

3. LQRS 가 어떻게 작동하나요? (3 단계 과정)

① 관찰 (눈을 뜨다)
요리사가 재료를 다지는 동안, LQRS 는 옆에서 **"어? 지금 재료가 5 개밖에 안 나왔네?"**라고 실시간으로 관찰합니다. 기존 시스템은 요리가 끝날 때까지 이 사실을 모릅니다.

② 학습 (경험을 쌓다)
LQRS 는 **강화 학습 (Reinforcement Learning)**이라는 기술을 사용합니다. 마치 바둑이나 체스 AI 가 수만 번의 게임을 통해 "이 수를 두면 이긴다"를 배우는 것처럼, LQRS 도 수많은 쿼리 실행을 통해 **"이런 상황에서는 저렇게 순서를 바꾸면 빨라진다"**는 것을 스스로 배웁니다.

• 교과서 학습 (Curriculum Learning): 처음엔 쉬운 결정 (예: "이 재료 먼저 섞기") 만 배우고, 점점 어려운 상황 (예: "여러 재료를 섞는 순서 바꾸기") 을 배워갑니다.

③ 수정 (계획 변경)
배운 지식을 바탕으로, 요리가 진행되는 중간 중간에 레시피를 수정합니다.

• 플러그인 (Planner Extension): LQRS 는 Spark SQL 이라는 큰 주방 시스템에 별도의 보조 요리사처럼 끼워 넣습니다. 이 보조 요리사는 주방장이 (Spark) 요리를 멈추지 않고도, "지금 이 순서로 바꾸면 더 빨라요!"라고 조언하고 즉시 실행합니다.

4. 왜 이것이 중요한가요? (성과)

이 논문은 LQRS 를 다양한 테스트 (JOB, TPC-H 등) 에 적용해 보았습니다. 결과는 놀라웠습니다.

• 최대 90% 속도 향상: 다른 최신 시스템보다 훨씬 빠르게 쿼리를 처리했습니다.
• 실패 감소: 잘못된 계획을 고집하다가 실패하는 경우가 줄었습니다.
• 유연성: 데이터의 양이나 종류가 변해도, 실시간으로 관찰해서 적응하므로 기존 시스템보다 훨씬 똑똑하게 대처합니다.

💡 한 줄 요약

"LQRS 는 요리가 끝날 때까지 기다리지 않고, 요리하는 도중 재료가 어떻게 나오는지 실시간으로 확인하며 레시피를 수정하는 '현명한 요리사'입니다. 덕분에 요리 (쿼리 실행) 시간이 획기적으로 단축됩니다."

이 시스템은 데이터가 너무 많거나 복잡해져서 기존 방식으로는 처리가 느려지는 현대의 빅데이터 환경에서, 실시간 지능을 통해 속도와 효율을 극대화하는 획기적인 해결책입니다.

기술 요약

1. 문제 정의 (Problem)

현대 데이터베이스 관리 시스템 (DBMS) 의 핵심 구성 요소인 쿼리 옵티마이저는 효율적인 실행 계획을 선택하는 역할을 합니다. 기존 비용 기반 옵티마이저 (Cost-Based Optimizer, CBO) 는 수동으로 설계된 공식을 사용하여 비용을 추정하지만, 이는 실제 실행 비용과 괴리가 있어 비최적의 실행 계획을 생성하는 경우가 많습니다.

이를 해결하기 위해 머신러닝을 활용한 **학습 기반 쿼리 옵티마이저 (Learned Query Optimizer, LQO)**가 제안되었으나, 다음과 같은 근본적인 한계가 존재합니다:

• 실행 전 최적화 (Pre-execution Optimization) 의 한계: 대부분의 LQO(예: Lero, AutoSteer) 는 실행 전 통계 정보에 기반하여 정적 실행 계획을 수립합니다.
• 런타임 관측의 부재: 쿼리 실행 중에 발생하는 중요한 런타임 관측치 (예: 실제 카디널리티, 중간 결과 크기 등) 를 활용하여 계획을 동적으로 재최적화하지 못합니다.
• 예측의 불확실성: 집계 키의 값 분포나 복잡한 술어의 선택도 같은 특성은 실제 데이터 처리가 이루어져야만 명확해지는데, 실행 전 모델은 이를 정확히 예측하기 어렵습니다.

따라서, 런타임 관측치를 수집하여 쿼리 실행 중에도 동적으로 실행 계획을 재최적화할 수 있는 학습 기반 프레임워크가 필요합니다.

2. 방법론 (Methodology)

저자들은 **LQRS (Learned Query Re-optimization Framework)**를 제안하여 Spark SQL 환경에서 실행 시간 최적화를 실현했습니다. LQRS 는 Spark SQL 의 적응형 쿼리 실행 (Adaptive Query Execution, AQE) 인프라를 기반으로 하며, 다음과 같은 핵심 메커니즘을 가집니다.

2.1. 학습 기반 재최적화 (Learned Re-optimization)

• 동적 계획 수정: 실행 전 계획 수립뿐만 아니라, 쿼리 실행 중 (In-execution) 에도 실제 런타임 피드백을 받아 계획을 수정합니다.
• 강화 학습 (Reinforcement Learning): 쿼리 실행을 에이전트와 환경의 상호작용으로 모델링합니다.
  • 상태 (State): 부분적으로 실행된 계획과 AQE 를 통해 수집된 실제 카디널리티 및 데이터 크기 통계.
  • 행동 (Action): 계획 초기화 전략 선택 (init), 리프 노드 교환 (swap), 특정 테이블을 먼저 조인하도록 유도 (lead), 브로드캐스트 조인 강제 (broadcast), 행동 없음 (no-op) 등 5 가지 행동 공간.
  • 보상 (Reward): 최종 실행 시간 단축을 목표로 하되, 중간 단계에서 발생하는 불필요한 셔플 (reshuffle) 비용을 패널티로 부과하여 안정적인 학습을 유도합니다.

2.2. 아키텍처 구성

1. 의사 결정 모델 (Decision Model):

   • TreeCNN 기반: 쿼리 계획 트리를 벡터화하여 처리하는 TreeCNN 아키텍처를 사용합니다.
   • Actor-Critic 프레임워크:
     • Actor: 현재 상태 (부분 실행 계획) 를 기반으로 최적의 최적화 행동 (예: 조인 순서 변경) 을 선택합니다.
     • Critic: Actor 의 행동이 장기적으로 얼마나 유익한지 평가하여 보상을 제공합니다.
   • 커리큘럼 학습 (Curriculum Learning): 학습 초기에는 단순한 행동 (계획 초기화) 만 허용하고, 점차 복잡한 런타임 조정 행동으로 난이도를 높여 학습 안정성을 확보합니다.

2. 플래너 확장 (Planner Extension):

   • Spark SQL 의 AQE 인터페이스를 확장하여 구현된 플러그 앤 플레이 모듈입니다.
   • 인터셉션: 쿼리 스테이지가 완료될 때마다 실제 통계 정보를 추출하여 의사 결정 모델에 전달합니다.
   • 주입 (Injection): 모델이 제안한 최적화 행동 (예: 조인 순서 변경) 을 실행 중인 계획에 적용하고, AQE 엔진에 다시 전달하여 실행을 계속합니다.
   • 안전성: 수정된 계획이 원래 계획과 의미적 동등성을 유지하는지 AQE 의 검증 메커니즘을 통해 보장합니다.

3. 주요 기여 (Key Contributions)

1. LQRS 프레임워크 개발: Spark SQL 의 AQE 와 강화 학습을 결합하여 실행 전 및 실행 중 최적화를 모두 지원하는 최초의 학습 기반 쿼리 옵티마이저를 구현했습니다.
2. TreeCNN 기반 의사 결정 모델: 실제 카디널리티와 바이트 크기를 입력 특징으로 사용하여, 단순한 아키텍처로 높은 성능을 달성하는 모델을 설계했습니다.
3. 플러그 앤 플레이 플래너 확장: Spark SQL 의 확장성 인터페이스를 활용하여 런타임 중 온라인 계획 수정을 가능하게 하는 모듈을 설계했습니다. 이는 실행을 중단하지 않고도 동적 재최적화 (예: Bushy Join 탐색) 를 지원합니다.
4. 커리큘럼 학습 전략: 학습 안정성을 높이기 위해 단순한 결정에서 복잡한 결정으로 점진적으로 학습을 진행하는 전략을 도입했습니다.

4. 실험 결과 (Results)

저자는 JOB, ExtJOB, STACK, TPC-H 등 4 개의 공개 벤치마크를 사용하여 LQRS 를 평가했습니다.

• 성능 향상: LQRS 는 다른 학습 기반 옵티마이저 (Lero, AutoSteer) 및 기존 재최적화 방법 (SSA) 대비 최대 90% 까지 엔드 - 투 - 엔드 실행 시간을 단축했습니다.
  • Spark SQL 대비 4 개 벤치마크에서 16.3% ~ 73.3% 의 실행 시간 감소를 기록했습니다.
• 비교 분석:
  • Lero 대비: 런타임 관측을 활용하여 Lero 와 유사한 품질의 계획을 달성하면서도, Lero 가 겪는 과도한 계획 열거 및 평가 오버헤드를 피했습니다.
  • SSA 대비: 강화 학습 기반의 의사 결정 과정이 단기 비용과 장기 이득을 균형 있게 고려하여, SSA 보다 더 안정적이고 큰 성능 개선을 보였습니다.
• 동적 적응성: 데이터 분포 변화 (IMDb 데이터의 과거 버전 vs 전체 버전) 및 워크로드 변경에 대해 LQRS 는 높은 견고성 (Robustness) 을 보였습니다.
• 오버헤드: LQRS 는 최적화 오버헤드가 가장 낮게 측정되었습니다. 불필요한 계획 수정을 방지하는 no-op 행동과 런타임 기반의 정밀한 의사 결정 덕분입니다.

5. 의의 및 결론 (Significance)

이 논문은 학습 기반 쿼리 최적화와 **적응형 쿼리 처리 (Adaptive Query Processing)**를 통합한 새로운 패러다임을 제시합니다.

• 패러다임 전환: "최적화 후 실행 (Optimize-then-Execute)"의 한계를 넘어, "실행 중 최적화 (Optimize-during-Execution)"를 가능하게 함으로써 런타임 관측치의 가치를 극대화했습니다.
• 실용성: Spark SQL 과 같은 대규모 데이터 처리 시스템에 직접 통합 가능한 플러그인 형태의 설계를 통해, 이론적 모델을 실제 산업 환경에 적용하는 가능성을 보여주었습니다.
• 미래 방향: LQRS 는 런타임 피드백을 활용한 동적 계획 수정이 쿼리 성능 향상에 결정적인 역할을 할 수 있음을 입증하였으며, 향후 더 복잡한 쿼리 패턴과 다양한 DBMS 에 대한 확장을 위한 기초를 마련했습니다.

결론적으로, LQRS 는 실행 시간 동안 수집된 실제 데이터를 기반으로 쿼리 계획을 지속적으로 정제함으로써, 기존 옵티마이저가 달성하지 못했던 높은 성능을 달성한 획기적인 프레임워크입니다.