49장. 유전자 쿼리 데이터베이스 시스템의 최적화

마틴 우테쉬자동제어연구소
        광업기술대학교
                 독일 프라이베르크

                    1997년 2월 10일

1.) 복잡한 최적화 문제로서의 쿼리 처리
===================================================

   모든 관계 연산자 중에서 가장 처리하기 어려운 것은
최적화는 JOIN입니다. 질의에 응답하기 위한 대체 계획의 수
포함된 JOIN의 수에 따라 기하급수적으로 증가합니다. 더 나아가
최적화 노력은 다양한 *JOIN 지원으로 인해 발생합니다.
방법*(예: 중첩 루프, 인덱스 스캔, Postgres의 병합 조인)
개별 JOIN 및 다양한 *인덱스*(예: r-트리,
b-트리, Postgres의 해시)를 관계에 대한 액세스 경로로 사용합니다.

   현재 Postgres 최적화 구현은 *near-
대체 전략의 공간에 대한 철저한 검색*. 이 쿼리
최적화 기술은 데이터베이스 애플리케이션을 지원하기에 부적절합니다.
인공적인 쿼리와 같이 광범위한 쿼리가 필요한 도메인
지능.

   광업 대학의 자동 제어 연구소 및
독일 프라이베르크의 기술 회사는 설명된 문제에 직면했습니다.
사람들은 Postgres DBMS를 결정을 위한 백엔드로 사용하기를 원했습니다.
전기 유지 관리를 위한 지식 기반 시스템 지원
전력망. 대규모 JOIN 쿼리를 처리하는 데 필요한 DBMS
지식 기반 시스템의 추론 기계.

   가능한 쿼리 공간 탐색 시 성능 문제
계획에 따라 새로운 최적화 기술이 개발되어야 한다는 요구가 생겼습니다.

   다음에서는 *Genetic 구현을 제안합니다.
데이터베이스 쿼리 최적화 문제에 대한 옵션인 알고리즘*.

2.) 유전 알고리즘(GA)
===========================

   GA는 다음을 통해 작동하는 경험적 최적화 방법입니다. 
결정된 무작위 검색. 가능한 솔루션 세트
최적화 문제는 *개인*의 *인구*로 간주됩니다.
개인이 환경에 적응하는 정도가 지정됩니다.
*피트니스*로 말이죠.

   검색공간에 개인의 좌표가 표시됩니다.
*염색체*, 본질적으로 문자열 세트로 구성됩니다. *유전자*는
단일 매개변수의 값을 암호화하는 염색체의 하위 섹션
최적화 중입니다. 유전자의 일반적인 인코딩은 *이진* 또는
*정수*.

   진화 작업 *재조합*의 시뮬레이션을 통해,
*돌연변이* 및 *선택* 새로운 세대의 검색 포인트가 발견됩니다.
조상보다 더 높은 평균 체력을 보여줍니다.

   "comp.ai.genetic" FAQ에 따르면 이 역시 강조할 수 없습니다.
GA는 문제에 대한 해결책을 찾기 위한 순수한 무작위 검색이 아니라는 점을 강력히 확신합니다.
문제. GA는 확률론적 프로세스를 사용하지만 결과는 뚜렷하게 다릅니다.
무작위가 아님(무작위보다 좋음) 

GA의 구조적 다이어그램:
--------------

P(t) 시점 t의 조상 세대
P''(t) 시점 t의 후손 세대

+========================================+
| 알고리즘 GA <<<<<<<<<<<<<|
+========================================+
| 초기화 t := 0 |
+========================================+
| P(t) 초기화 |
+========================================+
| P(t)의 적합성 평가 |
+========================================+
| STOPPING CRITERION이 아닌 동안 |
|   +-------------------------+
|   | P'(t) := 재결합P(t) |
|   +-------------------------+
|   | P''(t) := MUTATIONP'(t) |
|   +-------------------------+
|   | P(t+1) := SELECTIONP''(t) + P(t) |
|   +-------------------------+
|   | P''(t)의 적합성 평가 |
|   +-------------------------+
|   | t := t + 1 |
+===+=====================================+

3.) PostgreSQL의 GEQO(유전자 쿼리 최적화)
==================================================

   GEQO 모듈은 쿼리 솔루션을 위한 것입니다.
여행하는 세일즈맨 문제(TSP)와 유사한 최적화 문제입니다.
가능한 쿼리 계획은 정수 문자열로 인코딩됩니다. 각 문자열
쿼리의 한 관계에서 다음 관계까지의 JOIN 순서를 나타냅니다.
예를 들어 쿼리 트리 /\
                      // 2
                     // 3
                    4 1은 정수 문자열 '4-1-3-2'로 인코딩됩니다.
이는 먼저 관계 '4'와 '1'을 결합한 다음 '3'을 결합하고
그런 다음 '2'입니다. 여기서 1, 2, 3, 4는 PostgreSQL의 렐리드입니다.

   GEQO 모듈의 일부는 D. Whitley의 Genitor에서 채택되었습니다.
알고리즘.

   PostgreSQL에서 GEQO 구현의 특정 특성
다음과 같습니다:

o *정상 상태* GA 사용(최소 적합도 대체)
   전체 세대의 교체가 아닌 인구 내 개인)
   향상된 쿼리 계획으로 빠르게 수렴할 수 있습니다. 이것은
   합리적인 시간 내에 쿼리를 처리하는 데 필수적입니다.

o 특히 적합한 *에지 재결합 크로스오버* 사용
   GA를 통해 TSP 솔루션에 대한 에지 손실을 낮게 유지합니다.

o 유전 연산자로서의 돌연변이는 더 이상 사용되지 않으므로 복구할 수 없습니다.
   합법적인 TSP 투어를 생성하려면 메커니즘이 필요합니다.

   GEQO 모듈은 PostgreSQL DBMS에 다음과 같은 이점을 제공합니다.
Postgres 쿼리 최적화 프로그램 구현과 비교:

o 비완전한 검색을 통해 대규모 JOIN 쿼리 처리

o 더 이상 쿼리 계획의 비용 크기 근사치가 개선되지 않았습니다.
   계획 병합이 필요합니다(GEQO 모듈은
   개인별 쿼리 계획).

참고자료
==========

J. Heitk"otter, D. Beasley:
--------------
   "진화 계산에 대한 히치하이커를 위한 안내서",
   'comp.ai.genetic' FAQ,
   'ftp://ftp.Germany.EU.net/pub/research/softcomp/EC/Welcome.html'

Z. 퐁:
--------
   "Postgres 쿼리 최적화 프로그램의 설계 및 구현",
   'postgres-papers' 배포판의 'planner/Report.ps' 파일

R. 엘마스리, S. 나바테:
----------
   "데이터베이스 시스템의 기초",
   벤자민/커밍스 출판사, Inc.

=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
* PostgreSQL에 대해 남은 작업 *
= 유전자 쿼리 최적화(GEQO) =
* 모듈 구현 *
=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
* Martin Utesch * 자동 제어 연구소 *
= = 광업 기술 대학 =
* utesch@aut.tu-freiberg.de * 독일 프라이베르크 *
=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=

1.) 기본 개선
=============================================================

a) 쿼리가 이미 처리된 경우 메모리 해제를 개선합니다.
------------------------------------------------
대규모 JOIN 쿼리의 경우 유전자 쿼리에 소요되는 컴퓨팅 시간
최적화는 Postgres 시간의 *일부분*에 불과한 것 같습니다.
'MemoryContextFree' 루틴을 통해 메모리를 해제해야 합니다.
파일 '백엔드/utils/mmgr/mcxt.c';
디버깅을 통해 루틴 루프에 갇힌 것으로 나타났습니다.
'OrderedElemPop', 파일 'backend/utils/mmgr/oset.c';
일반 쿼리를 사용할 때 긴 쿼리에서도 동일한 문제가 발생합니다.
Postgres 쿼리 최적화 알고리즘;

b) 유전 알고리즘 매개변수 설정을 개선합니다.
------------------------------------------------
파일 'backend/optimizer/geqo/geqo_params.c', 루틴
'gimme_pool_size' 및 'gimme_number_세대';
매개변수 설정에 대한 절충안을 찾아야 합니다.
두 가지 경쟁 요구를 충족하려면:
1. 쿼리 계획의 최적화
2. 컴퓨팅 시간

c) 정수 오버플로에 대한 더 나은 솔루션을 찾습니다.
--------------------------------
'backend/optimizer/geqo/geqo_eval.c' 파일, 루틴
'geqo_joinrel_size';
MAXINT 오버플로에 대한 현재 해킹은 Postgres 정수를 설정하는 것입니다.
'rel-size' 값을 로그로 변환합니다.
'backend/nodes/relation.h'의 'struct Rel'을 수정하면
확실히 전체 PostgreSQL 구현에 심각한 영향을 미칠 것입니다.

d) 소진된 메모리에 대한 해결책을 찾습니다.
-------------------------
쿼리에 포함된 10개 이상의 관계에서 발생할 수 있는
'backend/optimizer/geqo/geqo_eval.c' 파일, 루틴
재귀적으로 호출되는 'gimme_tree';
어쩌면 올바르게 해제해야 할 것을 잊어버렸을 수도 있지만 무엇인지는 모르겠습니다.
물론 JOIN의 'rel' 데이터 구조는 계속해서 성장하고 있으며
성장할수록 더 많은 관계가 그 안에 담겨집니다.
제안을 환영합니다 :-(

2.) 추가 개선 사항
=============================================================
PostgreSQL 내에서 부시 쿼리 트리 처리를 활성화합니다.
쿼리 계획의 품질이 향상될 수 있습니다.