LLM 에이전트가 조인 순서 최적화를 잘할까요?

서론

Databricks 인텔리전스 플랫폼에서는 엔진 성능을 개선하고 사용자 경험을 단순화하기 위해 새로운 AI 기술을 정기적으로 탐색하고 활용합니다. 여기서는 가장 오래된 데이터베이스 과제 중 하나인 조인 순서 지정(join ordering)에 최첨단 모델을 적용한 실험 결과를 소개합니다.

이 블로그는 UPenn과의 연구 협력의 일환입니다.

문제: 조인 순서 지정

관계형 데이터베이스의 쿼리 최적화 프로그램은 처음부터 SQL 쿼리에 대한 좋은 조인 순서를 찾는 데 어려움을 겪어왔습니다. 조인 순서 지정의 어려움을 설명하기 위해 다음 쿼리를 고려해 보겠습니다.

Sony가 제작하고 Scarlett Johansson이 출연한 영화는 몇 편입니까?

다음 스키마에서 이 쿼리를 실행한다고 가정해 보겠습니다.

Actor, Company, Movie 엔티티 테이블은 Produces 및 Stars 관계 테이블(예: 외래 키를 통해)을 통해 연결됩니다. SQL에서 이 쿼리의 한 가지 버전은 다음과 같을 수 있습니다:

논리적으로는 간단한 조인 연산을 수행하고자 합니다: Actor ⋈ Stars ⋈ Movie ⋈ Produces ⋈ Company. 하지만 물리적으로는 이러한 각 조인이 교환적이고 결합적이기 때문에 많은 옵션이 있습니다. 쿼리 최적화 프로그램은 다음 중 하나를 선택할 수 있습니다:

1. 먼저 Scarlett Johansson이 출연한 모든 영화를 찾은 다음, Sony가 제작한 영화만 필터링합니다.
2. 먼저 Sony가 제작한 모든 영화를 찾은 다음, Scarlett Johansson이 출연한 영화를 필터링합니다.
3. Sony 영화와 Scarlett Johansson 영화를 병렬로 계산한 다음, 교집합을 취합니다.

어떤 계획이 최적인지는 데이터에 따라 달라집니다. 만약 Scarlett Johansson이 출연한 영화가 Sony가 제작한 영화보다 훨씬 적다면, 첫 번째 계획이 최적일 수 있습니다. 불행히도, 이 수량을 추정하는 것은 (일반적으로) 쿼리 자체를 실행하는 것만큼 어렵습니다. 설상가상으로, 가능한 계획의 수는 테이블 수에 따라 기하급수적으로 증가하기 때문에 일반적으로 선택할 수 있는 계획은 3개보다 훨씬 많으며, 분석 쿼리는 일반적으로 20-30개의 다른 테이블을 조인합니다.

오늘날 조인 순서 지정은 어떻게 작동할까요? 전통적인 쿼리 최적화 프로그램은 세 가지 구성 요소로 이 문제를 해결합니다. 첫째, 서브쿼리의 크기를 빠르게 추정하도록 설계된 카디널리티 추정기(예: Sony가 제작한 영화 수를 추정), 둘째, 다양한 잠재적 계획을 비교하는 비용 모델, 셋째, 기하급수적으로 큰 공간을 탐색하는 검색 절차입니다. 카디널리티 추정은 특히 어려우며, 다양한 접근 방식을 사용하여 추정 정확도를 개선하려는 광범위한 연구로 이어졌습니다 [A].

이러한 모든 솔루션은 쿼리 최적화 프로그램에 상당한 복잡성을 더하며, 통합, 유지 관리 및 상용화에 상당한 엔지니어링 노력이 필요합니다. 하지만 프롬프팅을 통해 새로운 도메인에 적응하는 능력을 가진 LLM 기반 에이전트가 이 수십 년 된 문제 해결의 열쇠를 쥐고 있다면 어떨까요?

에이전트 기반 조인 순서 지정

쿼리 최적화 프로그램이 잘못된 조인 순서¹를 선택하면, 인간 전문가는 문제를 진단(종종 잘못 추정된 카디널리티)하고 쿼리 최적화 프로그램에 다른 순서를 선택하도록 지시하여 이를 해결할 수 있습니다. 이 과정은 종종 여러 차례의 테스트(예: 쿼리 실행)와 중간 결과의 수동 검사를 필요로 합니다.

쿼리 최적화 프로그램은 일반적으로 수백 밀리초 내에 조인 순서를 선택해야 하므로, LLM을 쿼리 최적화 프로그램의 핵심 경로(hot path)에 통합하는 것은 잠재적으로 유망하지만 오늘날에는 불가능합니다. 그러나 인간 전문가가 몇 시간을 들여야 할 수도 있는 쿼리 조인 순서 최적화의 반복적이고 수동적인 프로세스는 LLM 에이전트를 통해 자동화될 수 있습니다! 이 에이전트는 수동 튜닝 프로세스를 자동화하려고 시도합니다.

이를 테스트하기 위해 프로토타입 쿼리 최적화 에이전트를 개발했습니다. 이 에이전트는 단일 도구에 접근할 수 있으며, 이 도구는 쿼리에 대한 잠재적인 조인 순서를 실행하고 해당 조인 순서의 런타임(원래 쿼리 런타임의 타임아웃 포함)과 각 계산된 서브플랜의 크기(예: EXPLAIN EXTENDED plan)를 반환합니다.

저희는 에이전트가 50회 반복 실행되도록 하여, 에이전트가 다양한 조인 순서를 자유롭게 시도할 수 있도록 했습니다. 에이전트는 이 50회 반복을 사용하여 유망한 계획을 테스트하거나("활용"), 위험하지만 유익한 대안을 탐색("탐색")할 수 있습니다. 그 후, 에이전트가 테스트한 가장 성능이 좋은 조인 순서를 수집하여 최종 결과로 삼습니다. 하지만 에이전트가 유효한 조인 순서를 선택했는지 어떻게 알 수 있을까요? 정확성을 보장하기 위해 각 도구 호출은 구조화된 모델 출력을 사용하여 조인 순서를 생성하며, 이는 모델의 출력이 유효한 조인 재정렬만 허용하도록 지정된 문법과 일치하도록 강제합니다. 이는 쿼리 최적화 프로그램의 "핵심 경로(hot path)"에서 LLM에게 즉시 조인 순서를 선택하도록 요청하는 이전 연구 [B]와는 다릅니다. 대신 LLM은 마치 사람이 수동으로 조인 순서를 튜닝하는 것처럼, 많은 후보 계획을 시도하고 관찰된 결과로부터 학습하는 오프라인 실험자처럼 행동합니다.

DBR에서 에이전트를 평가하기 위해 최적화하기 어렵게 설계된 쿼리 세트인 Join Order Benchmark (JOB)를 사용했습니다. JOB에서 사용된 IMDb 데이터셋은 약 2GB에 불과하여 Databricks가 좋지 않은 조인 순서도 상당히 빠르게 처리할 수 있었기 때문에, 각 행을 10번 복제하여 데이터셋의 규모를 늘렸습니다 [C].

저희는 조인 순서 벤치마크의 113개 모든 쿼리에 대해 에이전트가 쿼리당 15개의 조인 순서(롤아웃)를 테스트하도록 했습니다. 각 쿼리에서 찾은 최상의 조인 순서에 대한 결과를 보고합니다. 최첨단 모델을 사용했을 때, 에이전트는 쿼리 지연 시간을 1.288배(기하 평균) 개선할 수 있었습니다. 이는 완벽한 카디널리티 추정(실제로는 다루기 힘듦), 더 작은 모델, 그리고 최근의 BayesQO 오프라인 최적화 프로그램(BayesQO는 Databricks가 아닌 PostgreSQL용으로 설계되었지만)을 사용하는 것보다 뛰어난 성능입니다.

실제로 인상적인 개선은 분포의 꼬리 부분에서 나타나며, P90 쿼리 지연 시간이 41% 감소했습니다. 아래에서는 표준 Databricks 최적화 프로그램("기본")과 저희 에이전트("에이전트")에 대한 전체 CDF를 그렸습니다. 쿼리 지연 시간은 Databricks 최적화 프로그램의 중앙값 지연 시간으로 정규화되었습니다(즉, 1에서 파란색 선은 0.5의 비율에 도달합니다).

저희 에이전트는 테스트된 각 계획(때로는 롤아웃이라고도 함)을 통해 워크로드를 점진적으로 개선하여, 더 큰 시간 예산을 더 나은 쿼리 성능으로 전환할 수 있는 간단한 "언제든지 알고리즘(anytime algorithm)"을 만듭니다. 물론, 결국 쿼리 성능은 더 이상 개선되지 않을 것입니다.

저희 에이전트가 발견한 가장 큰 개선 사항 중 하나는 쿼리 5b에서였습니다. 이 쿼리는 1994년을 참조하는 메모와 함께 2010년 이후 영화를 VHS로 출시한 미국 제작사를 찾는 간단한 5방향 조인입니다. Databricks 옵티마이저는 먼저 미국 VHS 제작사를 찾는 데 중점을 두었습니다(이는 실제로 선택적이며 12개의 행만 생성합니다). 에이전트는 1994년을 참조하는 VHS 릴리스를 먼저 찾는 계획을 발견했으며, 이는 훨씬 더 빠른 것으로 나타났습니다. 이는 쿼리가 VHS 릴리스를 식별하기 위해 LIKE 술어를 사용하기 때문인데, 이는 카디널리티 추정기에게 매우 어려운 작업입니다.

저희 프로토타입은 데이터베이스 쿼리를 자율적으로 수정하고 개선하는 에이전트 시스템의 가능성을 보여줍니다. 이 작업은 에이전트 설계에 대한 몇 가지 질문을 저희에게 던졌습니다.

1. 에이전트에게 어떤 도구를 제공해야 할까요? 현재 접근 방식에서는 에이전트가 후보 조인 순서를 실행할 수 있습니다. 에이전트가 특정 카디널리티 쿼리(예: 특정 서브플랜의 크기 계산) 또는 데이터에 대한 특정 가정을 테스트하는 쿼리(예: 1995년 이전에 DVD 릴리스가 없었음을 확인)를 발행하도록 하는 것은 어떨까요?
2. 이 에이전트 최적화는 언제 트리거되어야 할까요? 물론 사용자는 문제가 있는 쿼리를 수동으로 표시하여 개입할 수 있습니다. 하지만 정기적으로 실행되는 쿼리에 이 최적화를 선제적으로 적용할 수도 있을까요? 쿼리에 최적화 “잠재력”이 있는지 어떻게 판단할 수 있을까요?
3. 개선 사항을 자동으로 이해할 수 있을까요? 에이전트가 기본 옵티마이저가 찾은 것보다 더 나은 조인 순서를 찾으면, 이 조인 순서는 기본 옵티마이저가 최적이 아닌 순서를 선택하고 있다는 증거로 볼 수 있습니다. 에이전트가 기본 옵티마이저의 체계적인 오류를 수정한다면, 이를 발견하고 옵티마이저를 개선하는 데 사용할 수 있을까요?

물론 쿼리 최적화를 위한 LLM의 잠재력에 대해 생각하는 것은 저희만이 아닙니다 [D]. Databricks는 LLM의 일반화 능력을 활용하여 데이터 시스템 자체를 개선할 가능성에 대해 기대하고 있습니다.

이 주제에 관심이 있다면, 저희의 후속 UCB 블로그인 "LLM 에이전트는 SQL 조인 순서를 어떻게 생각할까요?"도 참조하십시오.

저희와 함께하세요

앞으로 AI가 데이터베이스 최적화를 어떻게 형성할 수 있는지에 대한 한계를 계속 확장하게 되어 기쁩니다. 차세대 데이터베이스 엔진 구축에 열정이 있다면, 저희와 함께하세요!

¹ Databricks는 런타임 필터와 같은 기술을 사용하여 잘못된 조인 순서의 영향을 완화합니다. 여기 제시된 결과에는 이러한 기술이 포함됩니다.

참고

A. 카디널리티 추정 기법에는 예를 들어, 적응형 피드백, 심층 학습, 분포 모델링, 데이터베이스 이론, 학습 이론, 그리고 요인 분해가 있습니다. 이전 연구에서는 또한 기존 쿼리 옵티마이저 아키텍처를 심층 강화 학습, 다중 팔 밴딧, 베이지안 최적화, 또는 더 고급 조인 알고리즘으로 완전히 대체하려는 시도가 있었습니다.

B. 예를 들어, RAG 기반 접근 방식은 “핫 경로의 LLM” 시스템을 구축하는 데 사용되었습니다.

C. 비록 조잡하지만, 이 접근 방식은 이전 연구에서 사용되었습니다.

D. 다른 연구자들은 RAG 기반 쿼리 복구 시스템, LLM 기반 쿼리 재작성 시스템, 심지어 LLM이 합성한 전체 데이터베이스 시스템을 제안했습니다.

(이 글은 AI의 도움을 받아 번역되었습니다. 원문이 궁금하시다면 여기를 클릭해 주세요)