요약

  • 1979년의 System R 옵티마이저는 고려한 대안들 중 추정 비용이 가장 낮은 플랜을 선택했다. 이 비용은 추정된 페이지 읽기 횟수와 저장소 인터페이스 호출을 결합한 것이었으며, 사전에 경과 시간을 측정하거나 상상 가능한 모든 플랜에 대해 전역 최적임을 증명하지 않았다.
  • 선택도 추정치가 카디널리티 추정치를 결정하고, 이는 접근 경로, 조인 순서, 연산자 선택을 형성한다. "흥미로운 순서"는 국소적으로 더 비싼 경로가 나중의 정렬을 피하거나 다른 조인을 돕는다면 보존할 가치가 있는 이유를 설명한다.
  • Selinger는 Morton Astrahan, Donald Chamberlin, Raymond Lorie, Thomas Price와 함께 기념비적인 팀 기여를 조직했다. 그들의 가장 오래 지속된 성과는 가정을 검증하고, 수정하고, 감시할 수 있는 명시적인 결정 아키텍처였다.

약속이 이루어질 때 플랜은 아직 존재하지 않는다

주문, 고객, 지역을 조인하고 최근 기간으로 필터링하며 시장별로 그룹화해 가장 큰 열 개의 합계를 반환하는 쿼리를 생각해 보자. 관계형 결과는 쿼리에 의해 정의된다. 올바른 구현은 테이블을 스캔하든 인덱스를 따르든, 고객을 먼저 조인하든 지역을 마지막으로 미루든 동일한 조건을 만족하는 행과 집계를 반환해야 한다.

물리적 경험은 완전히 다를 수 있다. 한 경로는 좁은 인덱스를 읽어 소수의 행에 도달하고 그룹화에 유용한 순서를 보존한다. 다른 경로는 큰 릴레이션을 스캔해 과도하게 큰 중간 결과를 만들고 조인 후에 이를 정렬한다. 두 경로 모두 의미상 동등할 수 있지만, 운영 규모에서 견딜 수 있는 것은 하나뿐일 수 있다.

그러나 첫 페이지를 읽기 전에 데이터베이스는 이 특정 실행의 런타임을 관찰할 수 없다. 카탈로그 통계, 술어 가정, 연산자 공식, 하드웨어 가중치, 그리고 경계가 정해진 대안 탐색 같은 설명에 근거해 선택해야 한다. 따라서 옵티마이저의 가장 저렴한 플랜은 모델 아래에서 만들어진 예측이다. 실행이 나중에 그 판정을 내린다.

이 구분은 운영 언어가 그것을 지워 버리기 전까지는 자명해 보인다. 팀은 옵티마이저가 어떤 플랜이 가장 저렴한지 "안다"고 말한다. 대시보드는 추정 비용을 밀리초인 것처럼 표기한다. 선택된 플랜이 화면에 표시된 숫자가 가장 낮다는 이유로 성능 저하가 묻힌다. 이러한 각 표현은 비교적 추정치를 미래 실행에 관한 사실로 바꿔 버린다.

System R의 원본 연구는 그那样的 민담보다 더 신중했다. 불확실성이 남아 있는 상태에서 선택하는 체계적인 방법을 만들었고, 저자들은 절대적 비용 예측이 부정확할 수 있음을 공개적으로 보고했다. 그 아키텍처가 중요한 이유는 바로 불확실한 선택을 명시적으로 만들기 때문이다.

선언적 SQL은 새로운 제어 문제를 만들었다

SQL의 비절차적 약속은 경로를 선택하는 주체를 바꾼다. 사용자는 저장소 연산의 순서를 지정하지 않고 원하는 정보가 무엇인지를 서술한다. 이 분리는 이식성을 높이고, 인덱스·테이블 크기·분포가 바뀌어도 데이터베이스가 적응하게 한다. 동시에 옵티마이저에게 지연 시간, 용량, 신뢰성에 직접 영향을 미치는 결정에 대한 권한을 준다.

1979년 논문Access Path Selection in a Relational Database Management System은 그 권한을 4단계 순서 안에 배치했다. 파싱은 문장을 내부 표현으로 바꾸고, 최적화는 접근 명세를 선택하고, 코드 생성은 그 명세를 실행 가능한 기계 장치로 번역하며, 실행은 이를 수행한다. 이 순서가 핵심 사실이다. 최적화는 해당 실행이 실제 자원 사용을 드러내기 전에 일어난다.

접근 명세는 쿼리 의미의 또 다른 서술이 아니다. 그것은 물리적 선택을 기록한다. 어느 릴레이션을 먼저 접근할까? 세그먼트 스캔과 인덱스 중 어느 것이 적절한가? 조인은 어떤 순서로 일어나야 하는가? 기존의 순서를 보존할 만큼 가치 있는가? 코드 생성과 실행이 진행되면 이러한 계획 선택은 실제 읽기, 호출, 비교, 버퍼, 중간 행이 된다.

따라서 의미적 정확성과 물리적 경제성은 서로 다른 층에 놓인다. 플랜은 정확하면서도 느릴 수 있다. 두 플랜은 똑같이 정확하면서도 비용이 극단적으로 다를 수 있다. 한 데이터셋에서의 빠른 결과는 그 플랜이 일반적으로 최선임을 입증하지 못한다. 수학적으로 낮은 추정치는 다음 버퍼 상태, 매개변수 값, 동시 실행되는 워크로드 아래에서 더 낮은 경과 시간을 보장하지 않는다.

카탈로그는 현실의 압축된 시각이었다

System R은 행을 어떻게 읽을지 결정하면서 모든 행을 검사하지 않았다. 카탈로그 통계를 사용했다. 논문은 릴레이션의 튜플 수인NCARD, 점유된 페이지 수인TCARD, 페이지 점유도 척도인P, 인덱스의 서로 다른 키 수인ICARD, 인덱스 페이지 수인NINDX같은 값을 기술한다.

이 수치들은 데이터베이스의 압축된 설명을 제공했다. 동시에 경계도 부과했다. 통계는UPDATE STATISTICS연산으로 초기화되고 주기적으로 새로 고쳐졌다. 저자들은 데이터 변경마다 모든 통계를 유지하는 방식을 카탈로그 갱신과 잠금이 감당할 수 없는 비용을 추가한다는 이유로 명시적으로 거부했다.

이 절충은 우연이 아니라 본질적이다. 계획 요약은 유지 비용이 충분히 싸면서 선택을 안내할 만큼 풍부해야 한다. 관련된 모든 현실의 완벽하고 지속 동기화되는 복사본이라면, 그것을 얻는 비용이 그것이 지원하는 쿼리 결정보다 더 클 수 있다. 반대로 너무 거칠거나 낡으면 플랜이 잘못된 순위를 매길 수 있다.

현대 용어는 "낡은 통계"를 종종 유지보수 결함으로 취급한다. 때로는 그렇다. 그러나 더 깊은 문제는 경제적이다. 관찰에는 대가가 따른다. 시스템은 무엇을 샘플링할지, 얼마나 자주, 어떤 세밀기준으로, 어떤 가정 아래에서 결정한다. 따라서 모든 옵티마이저는 데이터의 완전한 미래 행동이 아니라 구성된 데이터상(形象)을 본다.

선택도는 신념이고, 카디널리티는 그 결과다

각 술어에 대해 System R은 통과할 것으로 기대되는 튜플의 비율인 선택도 계수를 부여했다. 인덱스가 있는 등식은 서로 다른 인덱스 키의 개수를 사용할 수 있었다. 다른 술어는 단순한 기본값에 의존했다. 논문은 인덱스 없는 등식에 10분의 1, 열린 범위에 3분의 1, 닫힌 범위에 4분의 1을 제시하고, 이 수치들이 대략적인 순서 매기기를 넘어서는 의미가 없다고 명시한다.

이 문장은 흔한 역사적 오류를 막는다. 그 기본값들은 데이터베이스의 발견된 상수가 아니었다. 더 나은 근거가 없을 때 대안을 순위 매기기 위해 사용된 실용적인 신념이었다.

AND로 결합된 술어는 선택도 계수를 곱할 수 있었다. 곱셈은 편리하지만 조건들의 효과가 독립적이라고 다룬다. 실제 데이터는 자주 그 가정을 거부한다. 우편번호는 도시와 상관하고, 제품군은 가격과, 계좌 유형은 잔액과, 날짜는 상태와 상관한다. 상관된 술어를 독립 필터로 곱하면 작은 선택도 오류가 큰 카디널리티 오류가 될 수 있다.

카디널리티는 릴레이션, 조인 또는 중간 연산자에서 몇 개의 행이 나오는지를 묻는다. 논문의 단순화된QCARD추론은 기저 릴레이션의 카디널리티와 적용 가능한 선택도 계수를 결합한다. 그 행 수 예측은 이후 비용 공식의 입력이 된다. 초기 조인을 과소 추정하면, 모델이 외부 행이 몇 개 안 된다고 상상하기 때문에 중첩 루프 경로가 저렴해 보일 수 있다. 런타임에는 수천 또는 수백만 개의 행이 반복 작업을 몰아넣을 수 있다. 필터를 과대 추정하면 옵티마이저는 실제로 아주 적은 데이터만 건드릴 인덱스 경로를 거부할 수 있다.

선택도와 카디널리티는 관련되어 있지만 서로 바꿔 쓸 수 없다. 선택도는 비율 또는 확률 같은 추정치다. 카디널리티는 그것과 입력 크기에서 파생된 개수다. 작은 테이블에서 1% 오류는 사소하지만, 같은 상대 오류가 여러 조인을 거쳐 전파되면 물리적 플랜 전체를 바꿀 수 있다.

이후의 평가들은 반복적으로 이 지점으로 돌아왔다. Leis와 공동 저자들은 2015년에 카디널리티 추정 오류가 일반적으로 비용 공식의 작은 부정확성보다 플랜 품질을 더 크게 훼손한다는 것을 발견했다. 그들의 2025년 회고는 카디널리티 추정을 계속되는 불안정성의 원천으로 기술하고 견고성과 적응성을 미완의 과제로 강조한다. 이것이 1979년 설계를 낡은 것으로 만들지는 않는다. 그 결정 사슬이 어디에서 가장 노출되어 있는지를 보여줄 뿐이다.

비용은 스톱워치가 아니라 순위 매기는 통화였다

System R의 공개된 공식은 간결했다.

COST = PAGE FETCHES + W × (RSI CALLS)

페이지 읽기는 I/O를, Research Storage Interface에 대한 호출은 프로세서 작업을 근사했다. 가중치W는 둘의 상대적 가격을 표현했다. 이것은 I/O만 보는 시각을 넘어선 의도된 조치였다. CPU 작업도 중요했기 때문이다. 그럼에도 결과는 여전히 모델 점수였다.

이 점수는 가정된 환율을 통해 서로 다른 양을 결합했다. 초 단위의 경과 시간을 예측하지 않고도 두 후보를 순위 매길 수 있었다. 실행 전에 알기 어려운 효과들 — 필요한 페이지가 이미 메모리에 있는지, 읽기가 얼마나 순차적인지, 경합이 얼마나 있는지, 중간 결과가 넘치는지, 프로세서가 어떻게 동작하는지, 다른 워크로드가 캐시에 무엇을 하는지, 그리고 데이터의 얼마나가 결국 클라이언트에 소비되는지 — 는 생략되거나 단순화되었다.

더 낮은 점수를 "더 저렴하다"고 부르는 것은 모델 안에서 타당하다. "더 빠르다"고 부르는 것은 가설이다. "최적"이라고 부르려면 두 가지 추가 자격이 필요하다. 어떤 목적에 대한 최적인가, 그리고 어떤 탐색된 대안 안에서인가?

PostgreSQL 문서는 같은 구분을 현대적 형태로 보존한다. 플래너의 비용 단위는 관례적이고 플랫폼 의존적이며, 밀리초가 아니다. 일반EXPLAIN은 문장을 실행하지 않고 추정치만 보여준다.EXPLAIN ANALYZE는 문장을 실행하고 실제 행 수와 시간을 더해준다. 이 쌍은 Selinger 아키텍처가 만든 경계 — 먼저 추정하고, 나중에 관찰한다 — 의 거의 실험실 시연이다.

접근 경로, 연산자, 조인 순서는 별개의 선택이다

"플랜을 선택한다"는 표현은 여러 결정을 숨길 수 있다.

접근 경로는 기저 릴레이션에 어떻게 도달하는지를 결정한다. 예를 들어 페이지를 스캔하거나 적용 가능한 인덱스를 사용한다. 물리적 연산자는 작업이 어떻게 수행되는지를 결정한다. 특정 조인이나 정렬 메커니즘은 자체 입력 요구 사항과 자원 프로필을 가진다. 조인 순서는 어느 릴레이션이 먼저 결합되는지, 따라서 중간 결과의 크기와 속성을 결정한다.

이 결정들은 상호작용한다. 인덱스는 행을 필터하면서 유용한 순서를 전달할 수도 있다. 이른 선택적 조인은 이후 모든 단계의 입력을 줄일 수 있다. 작은 외부 입력에 뛰어난 조인 방법은 추정 카디널리티가 틀리면 재앙이 될 수 있다. 한 요구 사항을 충족하기 위해 삽입된 정렬은 나중 단계를 더 싸게 만들 수 있고, 연산자가 파괴한 순서는 또 다른 정렬을 강제할 수 있다.

결과의 정확성은 대안을 구분하지 않는다. 관계형 동등성은 옵티마이저가 널, 중복, 집계 같은 언어 규칙의 의미를 조건으로 논리식을 변환하게 한다. 물리적 계획은 어느 동등한 실현을 사용할지를 묻는다. 이 두 질문을 섞으면 진단이 나빠진다. 틀린 답은 정확성 버그이고, 너무 늦게 도착하는 올바른 답은 계획, 추정 또는 실행 문제다.

"흥미로운 순서"는 절제된 선택지를 보존했다

논문의 가장 오래 지속된 아이디어 중 하나가 "흥미로운 순서"다. 어떤 인덱스 경로가 당장의 릴레이션에 대해서는 스캔보다 비용이 더 들 수 있다. 그러나 그것이 조인 키, 그룹화 키 또는 쿼리의 최종ORDER BY에 따라 정렬된 튜플을 반환한다면, 미래의 정렬을 피하거나 더 나은 이후 조인을 가능하게 할 수 있다. 국소적으로 가장 싸지 않다는 이유로 버리면 전역 플랜이 더 나빠진다.

따라서 System R은 부분 결과에 대해 하나보다 많은 승자를 유지했다. 가장 싼 무순서 플랜과 각 관련 흥미로운 순서에 대해 가장 싼 플랜을 함께 두었다. 같은 릴레이션 부분집합을 같은 유용한 순서 속성으로 전달하는 플랜들은 비교를 위한 실용적 동등 클래스를 형성했다.

이것은 비용 기반 최적화의 예외가 아니다. 단계 전반에 걸쳐 비용 산정을 일관되게 만드는 것이 바로 이것이다. 중간 결과가 운반하는 속성에는 선택 가치가 있다. 지금 더 내는 것이 나중 작업을 줄일 수 있다. 물리적 속성이 없는 플랜 점수는 당장의 가격과 총 결과를 혼동한다.

흥미로운 순서는 동등성의 의미도 날카롭게 한다. 두 부분 플랜은 같은 행을 만들면서 같은 이후 비용에서 대체 가능하지 않을 수 있다. 논리적 출력은 일치하지만 물리적 약속은 다르다. 옵티마이저는 두 시각을 동시에 필요로 한다.

조인 순서는 탐색 자체를 비싸게 만들었다

릴레이션이 여러 개면 조인 순서는 조합적으로 성장한다. 모든 순열의 순진한 나열은 계승적으로 증가한다. 그러면 최적화가 너무 많은 시간과 메모리를 소비해 실행 시간 절약이 탐색을 정당화하지 못하게 된다.

System R은 동적 계획법을 사용했다. 릴레이션 부분집합에 대한 플랜을 만들고, 각 부분집합과 흥미로운 순서에 대한 최선 대표를 저장하고, 조인을 확장할 때 재사용했다. 어설픈 접근법은 카르테시안 곱을 요구되지 않는 한 미루었다. 관련 없는 릴레이션을 이른 시점에 결합하면 보통 큰 중간 결과가 만들어지기 때문이다.

논문은 모든 원시 순열 대신 릴레이션 부분집합과 흥미로운 순서로 경계가 정해진 탐색을 기술하고, 8테이블 조인을 IBM 370/158에서 수 초 내에 최적화할 수 있었다고 보고한다. 이것은 놀라운 공학적 성과였다. 동시에 제약이기도 했다. 옵티마이저는 어떤 플랜 형태와 속성이 후보가 되고, 어떤 부분 플랜이 버려지고, 어떤 것이 유지될 가치가 있는지를 의도적으로 정의했다.

탐색 공간의 가지치기는 무작위 추측을 의미하지 않는다. 다룰 수 있는 표현 안에서 정의된 최적화 문제를 푼다는 뜻이다. 동적 계획법도 데이터베이스 설계자가 상상할 수 있는 모든 연산자, 조인 트리, 물리적 속성, 변환에 걸쳐 전역 최선 플랜을 증명하지 않는다. 실제 구현된 열거기, 비용 모델, 가지치기 규칙 아래에서 최선의 후보를 식별한다.

따라서 최적화 시간과 실행 시간은 같은 대장에 기록되지만 서로 다른 양으로 남는다. 더 큰 탐색은 모든 쿼리를 지연시키면서 더 좋은 플랜을 찾을 수 있다. 더 작은 탐색은 빠르게 적당한 플랜을 만들지만 가치 있는 대안을 놓칠 수 있다. 준비된 문장은 또 다른 층을 더한다. 일반 플랜은 반복되는 계획 작업을 절약할 수 있지만 최선 경로가 매개변수 값에 크게 의존할 때는 성능이 나쁠 수 있다.

저자들은 모델의 한계를 숨기지 않았다

1979년 논문은 예측 비용이 절대값으로는 종종 부정확했다고 결론 내린다. 또한 모델이 다수의 사례에서 실제로 최선이었던 테스트된 접근 경로를 선택했다고 보고하고 추가 검증을 요청한다. 이 두 진술은 양립한다. 보정이 불완전해도 순위 매기기는 유용할 수 있다. 일기 예보가 비가 정확히 몇 분에 시작할지 지정하지 않으면서 위험의 순서를 매길 수 있는 것과 같다.

Mackert와 Lohman의 1986년 R* 옵티마이저 평가가 이후의 실증적 압력을 제공했다. 추정 자원이 실제 사용과 비교되었다. I/O 모델링의 많은 부분은 작동했지만 프로세서 비용의 세부는 개선이 필요했다. 버퍼 가정이 중요했다. 조인 카디널리티, 외부 카디널리티, 가용 페이지가 상호작용하기 때문에 중첩 루프 비용은 특히 어려웠다.

이 검증은 제도적으로 중요하다. 비용 모델은 수학적 외양으로 보호되지 않는다. 실행과 비교할 수 있는 주장을 한다. 불일치가 어디에 집중되는지에 따라 설계자는 통계, 공식, 연산자 가정 또는 피드백을 개선할 수 있다. 추정은 반증 가능하기 때문에 관리 가능해진다.

IBM의 이후 적시 통계 작업도 같은 논리를 따랐다. 독립적으로 수집된 통계가 없거나 낡을 때, 옵티마이저는 중요한 관찰이 부족하다는 것을 발견하고 계획 시점에 목표 데이터를 요청할 수 있다. 대응은 불확실성이 사라진 것처럼 가장하는 것이 아니다. 기대되는 계획 이익이 비용을 정당화하는 곳에서 더 나은 정보를 사는 것이다.

Patricia Selinger는 팀 단위 설계를 이끌었다

Patricia G. Selinger는 1975년 IBM Research에 합류했다. IBM의 역사 기록은 그녀가 System R 옵티마이저 작업과 이후 R* 분산 데이터베이스 작업을 이끌었다고 기술하며, 그녀는 1994년 IBM Fellow가 되었고, 1999년 미국의 National Academy of Engineering에 선출되었으며, 2018년 IBM에서 은퇴했다. 이러한 영예는 한 편의 논문을 넘어선 경력을 반영한다.

옵티마이저 자체는 집단적 공로로 인정되어야 한다. 1979년 논문은 P. Griffiths Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price가 저술했다. Chamberlin은 Computer History Museum 구술 역사에서 Selinger가 최적화 작업과 기념비적 논문을 조직했으며, Lorie, Price, Astrahan을 중요한 기여자로 명시적으로 언급했다고 회상한다. IBM의 더 넓은 역사 기록은 이 작업을 Edgar Codd의 관계형 모델, Chamberlin과 Raymond Boyce의 SQL 작업, Lorie의 컴파일러 작업, 훨씬 더 큰 System R 프로그램과 함께 배치한다.

여기서 리더십은 홀로 이루어진 발명을 의미하지 않았다. Selinger의 독특한 역할은 최적화 문제를 구현 가능한 계약으로 조직한 것이었다. 통계로부터의 입력, 후보 접근 경로, 선택도와 카디널리티 추정, 가중치가 적용된 비용, 유용한 물리적 속성, 경계가 정해진 열거 절차가 그 계약을 이루었다. 팀은 선언적 언어를 우아한 인터페이스에서 범용 시스템이 경제적으로 실행할 수 있는 것으로 만들었다.

그 작업을 "AI"라고 부르는 것은 그 구체성을 평평하게 만든다. 논문은 명시적인 통계, 규칙, 공식, 동적 계획법을 기술한다. 그 중요성은 유행하는 레이블을 필요로 하지 않는다. 그것은 쿼리가 무엇을 요청하는지와 기계가 그것을 어떻게 시도하는지 사이에 오래 지속되는 제어 층을 만들었다.

그 경계는 정직했기에 살아남았다

비용 기반 최적화는 때때로 그 성과가 유일한 참된 경로를 찾는 것인 양 기술된다. 더 중요한 성과는 더 좁고 더 강하다. 의미와 방법을 분리하고, 물리적 선택을 비교 가능하게 만들고, 쿼리를 바꾸지 않고 새로운 근거가 결정을 바꿀 수 있는 자리를 보존한 것이다.

이 설계가 살아남은 이유는 개정을 기대하기 때문이다. 통계는 더 풍부해질 수 있다. 카디널리티 추정기는 상관을 모델링할 수 있다. 비용 가중치는 하드웨어에 적응할 수 있다. 열거기는 새로운 조인 형태를 수용할 수 있다. 런타임 피드백은 재계획을 촉발할 수 있다. 그 어떤 변화도 사용자가 모든 선언적 쿼리를 물리적 프로그램으로 다시 쓰기를 요구하지 않는다.

이 적응성은 경계를 명확히 유지하는 데 달려 있다. 선택된 플랜은 승인된 예측이다. 그것은 이미 현실에 의해 입증되었기 때문이 아니라 구현된 비교에서 이겼기 때문에 실행을 받을 자격이 있다. 실행이 시작되면 실제 행, I/O, 프로세서 작업, 메모리 압력, 경과 시간이 근거가 된다. 성숙한 시스템은 두 기록을 모두 남기고 그 격차로부터 배운다.

참고 자료