15. Query Compilation and Code Generation (Bigdata and Knowledge Management Systems 2, SNU GSDS)

서울대학교 데이터사이언스대학원 정형수 교수님의 "빅데이터 및 지식 관리 시스템 2" 강의를 필기한 내용입니다.

• 목차

완성되지 않은 강의록

• 사진이랑 보충 설명을 더 넣을 예정입니다.

Query Plan §

• Query plan 에서의 goal 은
  • instruction count 를 줄이고: 이것은 보통 DBMS implementation 에 영향을 받는다.
  • cycle per instruction 도 줄이고
  • parallel 하게 하고
  • 당연한 얘기지만, 10배 빨라지기 위해서는 instruction 의 양을 90% 줄여아 한다.

Interprete, Compile, JIT §

• Interpretation: 코드를 그때그때 parsing 해서 그에 맞는 pre-implemented function 을 call 하는 것.
• Compilation: Native code (executable) 로 바꾸는 것.
• Transpilation (Source-to-source compilation): 다른 언어로 바꾸는 것.
• Just-In-TIme (JIT): 그때그때 compilation 하면서 native query processing code 전체 혹은 일부를 생성하는 것.

Pull-based Execution §

• Pull-based, volcano model 에서는
  • 모든 node 는 emit() 과 getNext() 를 구현하고 있고, 상위 node 에서 getNext() 를 이용해 하위 node 에서 emit() 으로 뱉은 데이터를 pull 해온다.
  • Predicate 에서는 pred() 로 검사를 한다.
  • Join 에서는 probe() 로 hashtable 등에서 match 되는지 확인한다.
    • Join 에서 만약 hashtable 을 사용하기로 했다면, probe 전에 한쪽의 table 로 build_hash_table() 로 만든다.
• 근데 Predicate evaluation (pred()) 은 절대 가볍지 않다.
  • Input 으로 들어온 predicate 의 피연산자에 대해, 어떤 type 인지를 catalog 를 통해 확인하고 이 type 이 이 연산자로 연산이 가능한가 확인하는 등등의 작업을 해야 하기 때문이다.
  • 근데 native code 에서 predicate 을 처리하는 것은 이것보다는 훨씬 간단하기 때문에 이런것들을 native code 로 generate 하여 처리하는 것이 더 효율적이다.

Query Transpilation and JIT §

• 위에서 말한 대로, query execution 을 할 때 predicate evaluation 에서 interprete 방식을 사용하는 것보다 native code 로 compile 해서 실행하는 것이 더 빠르다.
• 그래서, query plan 에 대해 이놈을 실행할 C, C++ 코드를 동적으로 생성하는 Query Transpilation 접근 방식을 취하거나, 이놈을 실행할 IR 을 동적으로 생성하는 Query JIT Compilation 방식을 취하게 된다.
  • 가령, DBMS 에서는 SQL query 를 parsing 하여 AST 를 바꾼 뒤 미리 준비된 각 AST node 에 대응되는 C, C++ (Transpilation 을 한다고 했을 때) 혹은 LLVM (LLVM JIT Compilation 을 한다고 했을 때) code block 으로 이것을 다 치환한다.
  • 참고로 Oracle 에서는 Proc-C 라는 Domain Specific Language (DSL) 로 바꾼 뒤 native code 를 생성한다고 한다.
• 그 다음에 이것을 compile 해서 shared library (.so 파일) 형태의 native code 로 바꾸게 되고, 이것을 동적으로 load 해서 실행하게 된다.

HIQUE (ICDE’10) §

• Transpilation 접근법이 처음 등장한 것이 이 Hique 논문 (Holistic code generation, ICDE’10) 이다.
• 이 논문에서는 모든 query plan node 대해 C, C++ 로 변환해주는 코드를 짰다.
  • 이것을 Templated Plan 이라고 하는데,
  • 위 그림에서 보이는 것 처럼 일단 Template code 가 있고 여기에서 변수들은 전부 macro definition 으로 주입받는다.
  • 가령 catalog 에 있는 tuple size 나 user 가 넘겨주는 parameter value 같은 것들을 macro definition 으로 만들어서 이 template 에 붙여주면 정상적으로 작동하는 C, C++ code 가 되는 것.
• 실행시에는 위에서 말한 것과 유사하게 compile 한 다음 shared lib 을 load 하는 방식으로 작동한다.
• 추가적으로 접근해야되는 데이터들을 array access 형태로 만들어서 compilation 에 SIMD instruction 으로 compile 되도록 하는 최적화도 되어 있다고 한다.

• 그 결과가 위와 같다.
  • Generic Iterator: 기존의 interprete 방식
    • 즉, query 에 사용되는 data 가 어떤 type 인지 모른다고 가정하고, query 실행시에 catalog 를 보면서 확인하며 interprete 방식으로 실행하는 것.
  • Optimized Iterator: 위의 generic iterator 와 동일한데, type 정보같은 것들을 미리 주입하는 (예를 들어 int type 만 사용한다고 가정하고 type checking 같은것들을 전부 hard-coded 로 바꿔버린) 등의 조작을 한 것.
  • Generic Handcoded: 사람이 query execution code 를 직접 짜되, 모든 type 에 대응할 수 있도록 generic 하게 짠 것.
  • Optimized Handcoded: 위의 generic handcoded 와 동일한데, 마찬가지로 type 정보는 hardcoded 해놓는 등의 최적화를 한 것.
• 보면 HIQUE 와 optimized handcoded 와 유사한 성능으로 가장 좋은 성능을 보여주는 것을 알 수 있다.
  • 이 말은, 이런 transpilation 이 효과적이라는 것과 HIQUE 가 정확하게 구현되어 있다는 의미이다.
  • 보다시피 여기서 가장 성능이 많이 좋아지는 부분은 intruction exec (predicate evaluation) 이다.

• 근데 문제는 실제 query execution time 보다 query compile 하는데에 더 오래걸리는 문제가 있다.
  • 즉, C/C++ code parsing overhead 가 있는 것.
  • 이 parsing overhead 를 줄이기 위해 C code 가 아닌 IR 로 하자는 게 JIT compilation 접근이다.

HyPer (VLDB’11) §

• HyPer 가 이 solution 의 이름은 아니고 기존의 Thomas Neumann 교수님의 HyPer 에 접목을 한것이다.
• 여기서는 query 를 IR 로 바꾸고, IR 을 machine code 로 바꾸어서 Hique 에서의 parsing overhead 를 없앴다.

• 또한, push-based execution 으로 pipelining 을 해서 성능을 높였다.
  • 기존의 Pull-based execution 에서는 getNext() 를 호출하면 다음 node 에서 exec 을 시작하는 것이었는데,
  • Push-based 에서는 각 operator 들이 계속해서 operation 들을 수행하고 있고, 그 결과를 materialize 시켜 놓으며 쌓아두면 상위 node 가 그것들을 필요할 때마다 가져가는 형태
  • 따라서 모든 operator 들이 계속 돌고 있고, pipelining 이 된다.
    • 즉, intra-query, inter-operator parallelism 이다.

Real-world Implementation §

• Stored proc: 어차피 application 이 DBMS 에 날리는 query 는 정해져있기 떄문에 이런 query 는 미리 procedure 로 만들어서 parsing overhead 를 줄인다.
  • 미리 IR 로 만들어놓는것
  • 그래서 application 에서는 실제로 SQL 이 아닌 parameter 만 보내기도 한다.
• AWS Redshift 같은곳에서는 query fragment 들을 C++ code 로 바꿔둔 뒤 local caching 하여 이 바꿔둔 template code 들을 재활용한다.
  • 또한, 만약에 local cache 에 없다면 다른 사람들이 query planning 할 때 생성했던 template code 들을 global hashtable 로 만들어놓아서 이후 query 가 들어왔을 때 이 hashtable 을 보고 있으면 바로 그 template code 를 사용하기도 한다.
• TUM UMBRA: 여기서는 custom IR 을 사용해서 더 빠르게 했다고 한다.
• Singlestore: 모든 들어온 query 를 parameterize 해서 유사한 query 가 들어오면 이 parameterized 한 것을 바로 사용하는 방식을 취한다고 한다.