{"action":"created","comment":{"url":"https://api.github.com/repos/pivotal/blog/pulls/comments/78680464","id":78680464,"diff_hunk":"@@ -0,0 +1,330 @@\n+---\n+authors:\n+- narmenatzoglou\n+- krajaraman\n+- shardikar\n+- chasseur\n+- frahman\n+- caragea\n+- vraghavan\n+- addison\n+- xzhang\n+categories:\n+- GREENPLUM DATABASE\n+- QUERY EXECUTION\n+- CODE GENERATION\n+date: 2016-09-02T10:43:19-04:00\n+draft: false\n+short: |\n+  A code generation based solution inside the GPDB execution engine.\n+title: Improving Query Execution Speed via Code Generation\n+---\n+\n+## Overhead of a Generalized Query Execution Engine\n+\n+\n+To handle the full range of SQL queries and data type, [GPDB](http://greenplum.org/)’s execution engine is designed with high levels of complexity such as function \n+pointers and control flow statements. Making these decisions for each tuple adds up to significant overhead, and prevents efficient usage of modern CPUs, with deep \n+pipelines. \n+\n+\n+## Code Generation \n+\n+To address this problem of ineffective CPU utilization and poor execution time, several state-of-the-art commercial and academic query execution engines have explored \n+a Code Generation (CodeGen) based solution. This approach exploits the metadata about the underlying schema and plan characteristics already available at \n+query execution time, to produce native code. To elaborate consider the following use case in Postgres-based engine like GPDB. In the code snippet from `ExecEvalScalarVar`, \n+we retrieve the 5th attribute of a tuple.\n+```c\n+switch (variable->varno)\n+{  \n+     case INNER:\n+          slot = econtext->ecxt_innertuple;\n+   \t   break;\n+     case OUTER:\n+   \t   slot = econtext->ecxt_outertuple;\n+          break;\n+     default:\n+          slot = econtext->ecxt_scantuple;\n+   \t   break;\n+}\n+attnum = variable->varattno;\n+return slot_getattr(slot, attnum);\n+```\n+\n+At runtime, from the query plan we know for function `ExecEvalScalarVar` the `variable->varno` is neither `INNER` nor `OUTER`, thus we can generate code that passes the \n+value of `econtext->ecxt_scantuple` (default case) as an argument to `slot_getattr` function directly. Similarly, based on the plan we can initialize the `attnum` \n+value to a constant. A handwritten, and more efficient, code for the above snippet would look like the following: \n+\n+```c\n+return slot_getattr(slot_getattr(econtext->ecxt_scantuple, 5);\n+```\n+\n+This code consists of much less instructions and branches, thus its execution time is significantly less than the execution time of original code. \n+In a successful application of code generation, the time needed to generate, compile, and execute this code is significantly less than the execution of the original code. \n+```\n+Code_Generation_Time + Compilation_Time + Codegened_Code_Execution_Time < Original_Code_Execution_Time\n+```\n+\n+## CodeGen Approach in Literature: Holistic vs. Hotspots\n+\n+In literature, there are two major approaches in doing code generation namely (1) holistic macro approach, and (2) hotspot based micro specialization. \n+In the holistic approach the execution looks at optimization opportunities across the whole query plan [1][2]. This may include but not restricted to\n+merging query operators, converting pull-based execution pattern to push-based model, etc. Alternatively, the hotspot based micro specialisation strategy generates code \n+for frequently exercised code paths only [4]. Figure below depicts the CodeGen approach followed in numerous commercial databases. \n+ \n+\n+{{< figure src=\"/images/codegen/commercial.png\" class=\"center\">}}\n+\n+\n+To incrementally deliver value to our customers, we decided to follow the hotspot based methodology in implementing CodeGen and revisit the holistic approach in the near future.\n+\n+\n+## GPDB Hotspots\n+\n+When we ran [TPCH](http://www.tpc.org/tpch/) queries, the top 10 functions with respect to time spent is shown below. Note that the remaining functions are bundled in a category called “Others”.\n+\n+{{< responsive-figure src=\"/images/codegen/profiling.png\" >}}\n+\n+Based on the results, the following hotspots are prime candidates for code generation: \n+\n+- Deforming a tuple (see `_slot_getsomeattrs` function)\n+- Expression evaluation (see `ExecProject`, `agg_hash_initial_pass`, `ExecEvalScalarVar`)\n+- Aggregate functions\n+\n+\n+## Which programming language to use to generate code: C/C++ vs. Java vs. LLVM?\n+\n+There are several ways to generate code at runtime, (1) C/C++, (2) Java, (3) Directly in Machine Code and (4) LLVM, to name a few. Given that GPDB code base is in C and C++,\n+adding Java does not make much sense. Assembly code is also not a good candidate since it is both hard to write as well as maintain. Generating C/C++ code is more developer \n+friendly, but optimizing and compiling C/C++ is shown to be slow [2]. \n+\n+In contrast, [LLVM](http://llvm.org/) is ideal for generating code as it provides a collection of modular as well as reusable compiler and toolchain technologies. \n+LLVM provides a C++ API for writing code into an intermediate representation (IR), which at runtime can be optimized and turned into native code efficiently.\n+LLVM IR is a low-level programming language similar to assembly language, which is type-safe, target machine-independent, and supports RISC-like instructions and unlimited \n+registers. GPDB inherits all of the LLVM code optimizations. Below you can see the equivalent LLVM IR code for our example.\n+                                                                            \n+ ```                                                                         \n+llvm::Value* res = ir_builder()->CreateCall(llvm_slot_getattr_func, {llvm_econtext_ecxt_scantuple, 5});\n+ir_builder()->CreateRet(res);\n+```\n+\n+Commercial databases leverage both approaches. For instance, [Redshift](https://aws.amazon.com/redshift/) compiles C++ code [6], while \n+[Impala](https://www.cloudera.com/products/apache-hadoop/impala.html) \n+utilizes LLVM [8]. [MemSQL](http://www.memsql.com/) emits a high-level language, called [MPL](http://docs.memsql.com/docs/code-generation), when preparing the query, and then compiles the HLL to emit LLVM IR [7].  ","path":"content/post/codegen-gpdb-qx.md","position":113,"original_position":113,"commit_id":"04f83991993e5514878353afbdb727b61c608764","original_commit_id":"04f83991993e5514878353afbdb727b61c608764","user":{"login":"craig-chasseur","id":8863297,"avatar_url":"https://avatars.githubusercontent.com/u/8863297?v=3","gravatar_id":"","url":"https://api.github.com/users/craig-chasseur","html_url":"https://github.com/craig-chasseur","followers_url":"https://api.github.com/users/craig-chasseur/followers","following_url":"https://api.github.com/users/craig-chasseur/following{/other_user}","gists_url":"https://api.github.com/users/craig-chasseur/gists{/gist_id}","starred_url":"https://api.github.com/users/craig-chasseur/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/craig-chasseur/subscriptions","organizations_url":"https://api.github.com/users/craig-chasseur/orgs","repos_url":"https://api.github.com/users/craig-chasseur/repos","events_url":"https://api.github.com/users/craig-chasseur/events{/privacy}","received_events_url":"https://api.github.com/users/craig-chasseur/received_events","type":"User","site_admin":false},"body":"Not a commercial offering, but interesting recent research you might also want to cite is this paper: https://infoscience.epfl.ch/record/218087/files/how-to-architect-a-query-compiler.pdf\r\n\r\nIt basically starts with Scala and does a number of lowering steps (including hand-written tuned C implementations of a couple of important data structures) until it gets down to C and then machine code.","created_at":"2016-09-14T03:10:42Z","updated_at":"2016-09-14T03:10:42Z","html_url":"https://github.com/pivotal/blog/pull/108#discussion_r78680464","pull_request_url":"https://api.github.com/repos/pivotal/blog/pulls/108","_links":{"self":{"href":"https://api.github.com/repos/pivotal/blog/pulls/comments/78680464"},"html":{"href":"https://github.com/pivotal/blog/pull/108#discussion_r78680464"},"pull_request":{"href":"https://api.github.com/repos/pivotal/blog/pulls/108"}}},"pull_request":{"url":"https://api.github.com/repos/pivotal/blog/pulls/108","id":84558174,"html_url":"https://github.com/pivotal/blog/pull/108","diff_url":"https://github.com/pivotal/blog/pull/108.diff","patch_url":"https://github.com/pivotal/blog/pull/108.patch","issue_url":"https://api.github.com/repos/pivotal/blog/issues/108","number":108,"state":"open","locked":false,"title":"Post on Code Generation in GPDB's execution engine","user":{"login":"armenatzoglou","id":9626616,"avatar_url":"https://avatars.githubusercontent.com/u/9626616?v=3","gravatar_id":"","url":"https://api.github.com/users/armenatzoglou","html_url":"https://github.com/armenatzoglou","followers_url":"https://api.github.com/users/armenatzoglou/followers","following_url":"https://api.github.com/users/armenatzoglou/following{/other_user}","gists_url":"https://api.github.com/users/armenatzoglou/gists{/gist_id}","starred_url":"https://api.github.com/users/armenatzoglou/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/armenatzoglou/subscriptions","organizations_url":"https://api.github.com/users/armenatzoglou/orgs","repos_url":"https://api.github.com/users/armenatzoglou/repos","events_url":"https://api.github.com/users/armenatzoglou/events{/privacy}","received_events_url":"https://api.github.com/users/armenatzoglou/received_events","type":"User","site_admin":false},"body":"","created_at":"2016-09-08T21:34:37Z","updated_at":"2016-09-14T03:10:42Z","closed_at":null,"merged_at":null,"merge_commit_sha":"0a4061786fc86f6df2f99c9d6d92461d198858de","assignee":null,"assignees":[],"milestone":null,"commits_url":"https://api.github.com/repos/pivotal/blog/pulls/108/commits","review_comments_url":"https://api.github.com/repos/pivotal/blog/pulls/108/comments","review_comment_url":"https://api.github.com/repos/pivotal/blog/pulls/comments{/number}","comments_url":"https://api.github.com/repos/pivotal/blog/issues/108/comments","statuses_url":"https://api.github.com/repos/pivotal/blog/statuses/04f83991993e5514878353afbdb727b61c608764","head":{"label":"armenatzoglou:codegen_post","ref":"codegen_post","sha":"04f83991993e5514878353afbdb727b61c608764","user":{"login":"armenatzoglou","id":9626616,"avatar_url":"https://avatars.githubusercontent.com/u/9626616?v=3","gravatar_id":"","url":"https://api.github.com/users/armenatzoglou","html_url":"https://github.com/armenatzoglou","followers_url":"https://api.github.com/users/armenatzoglou/followers","following_url":"https://api.github.com/users/armenatzoglou/following{/other_user}","gists_url":"https://api.github.com/users/armenatzoglou/gists{/gist_id}","starred_url":"https://api.github.com/users/armenatzoglou/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/armenatzoglou/subscriptions","organizations_url":"https://api.github.com/users/armenatzoglou/orgs","repos_url":"https://api.github.com/users/armenatzoglou/repos","events_url":"https://api.github.com/users/armenatzoglou/events{/privacy}","received_events_url":"https://api.github.com/users/armenatzoglou/received_events","type":"User","site_admin":false},"repo":{"id":67249078,"name":"blog","full_name":"armenatzoglou/blog","owner":{"login":"armenatzoglou","id":9626616,"avatar_url":"https://avatars.githubusercontent.com/u/9626616?v=3","gravatar_id":"","url":"https://api.github.com/users/armenatzoglou","html_url":"https://github.com/armenatzoglou","followers_url":"https://api.github.com/users/armenatzoglou/followers","following_url":"https://api.github.com/users/armenatzoglou/following{/other_user}","gists_url":"https://api.github.com/users/armenatzoglou/gists{/gist_id}","starred_url":"https://api.github.com/users/armenatzoglou/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/armenatzoglou/subscriptions","organizations_url":"https://api.github.com/users/armenatzoglou/orgs","repos_url":"https://api.github.com/users/armenatzoglou/repos","events_url":"https://api.github.com/users/armenatzoglou/events{/privacy}","received_events_url":"https://api.github.com/users/armenatzoglou/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/armenatzoglou/blog","description":"Pivotal Engineering Blog","fork":true,"url":"https://api.github.com/repos/armenatzoglou/blog","forks_url":"https://api.github.com/repos/armenatzoglou/blog/forks","keys_url":"https://api.github.com/repos/armenatzoglou/blog/keys{/key_id}","collaborators_url":"https://api.github.com/repos/armenatzoglou/blog/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/armenatzoglou/blog/teams","hooks_url":"https://api.github.com/repos/armenatzoglou/blog/hooks","issue_events_url":"https://api.github.com/repos/armenatzoglou/blog/issues/events{/number}","events_url":"https://api.github.com/repos/armenatzoglou/blog/events","assignees_url":"https://api.github.com/repos/armenatzoglou/blog/assignees{/user}","branches_url":"https://api.github.com/repos/armenatzoglou/blog/branches{/branch}","tags_url":"https://api.github.com/repos/armenatzoglou/blog/tags","blobs_url":"https://api.github.com/repos/armenatzoglou/blog/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/armenatzoglou/blog/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/armenatzoglou/blog/git/refs{/sha}","trees_url":"https://api.github.com/repos/armenatzoglou/blog/git/trees{/sha}","statuses_url":"https://api.github.com/repos/armenatzoglou/blog/statuses/{sha}","languages_url":"https://api.github.com/repos/armenatzoglou/blog/languages","stargazers_url":"https://api.github.com/repos/armenatzoglou/blog/stargazers","contributors_url":"https://api.github.com/repos/armenatzoglou/blog/contributors","subscribers_url":"https://api.github.com/repos/armenatzoglou/blog/subscribers","subscription_url":"https://api.github.com/repos/armenatzoglou/blog/subscription","commits_url":"https://api.github.com/repos/armenatzoglou/blog/commits{/sha}","git_commits_url":"https://api.github.com/repos/armenatzoglou/blog/git/commits{/sha}","comments_url":"https://api.github.com/repos/armenatzoglou/blog/comments{/number}","issue_comment_url":"https://api.github.com/repos/armenatzoglou/blog/issues/comments{/number}","contents_url":"https://api.github.com/repos/armenatzoglou/blog/contents/{+path}","compare_url":"https://api.github.com/repos/armenatzoglou/blog/compare/{base}...{head}","merges_url":"https://api.github.com/repos/armenatzoglou/blog/merges","archive_url":"https://api.github.com/repos/armenatzoglou/blog/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/armenatzoglou/blog/downloads","issues_url":"https://api.github.com/repos/armenatzoglou/blog/issues{/number}","pulls_url":"https://api.github.com/repos/armenatzoglou/blog/pulls{/number}","milestones_url":"https://api.github.com/repos/armenatzoglou/blog/milestones{/number}","notifications_url":"https://api.github.com/repos/armenatzoglou/blog/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/armenatzoglou/blog/labels{/name}","releases_url":"https://api.github.com/repos/armenatzoglou/blog/releases{/id}","deployments_url":"https://api.github.com/repos/armenatzoglou/blog/deployments","created_at":"2016-09-02T19:24:45Z","updated_at":"2016-09-02T19:24:46Z","pushed_at":"2016-09-13T00:03:29Z","git_url":"git://github.com/armenatzoglou/blog.git","ssh_url":"git@github.com:armenatzoglou/blog.git","clone_url":"https://github.com/armenatzoglou/blog.git","svn_url":"https://github.com/armenatzoglou/blog","homepage":"http://engineering.pivotal.io/","size":18830,"stargazers_count":0,"watchers_count":0,"language":"CSS","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"pivotal:master","ref":"master","sha":"8dfae3a02f5415b609f83f13cd0b4ad54f95c09b","user":{"login":"pivotal","id":9148,"avatar_url":"https://avatars.githubusercontent.com/u/9148?v=3","gravatar_id":"","url":"https://api.github.com/users/pivotal","html_url":"https://github.com/pivotal","followers_url":"https://api.github.com/users/pivotal/followers","following_url":"https://api.github.com/users/pivotal/following{/other_user}","gists_url":"https://api.github.com/users/pivotal/gists{/gist_id}","starred_url":"https://api.github.com/users/pivotal/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pivotal/subscriptions","organizations_url":"https://api.github.com/users/pivotal/orgs","repos_url":"https://api.github.com/users/pivotal/repos","events_url":"https://api.github.com/users/pivotal/events{/privacy}","received_events_url":"https://api.github.com/users/pivotal/received_events","type":"Organization","site_admin":false},"repo":{"id":41665610,"name":"blog","full_name":"pivotal/blog","owner":{"login":"pivotal","id":9148,"avatar_url":"https://avatars.githubusercontent.com/u/9148?v=3","gravatar_id":"","url":"https://api.github.com/users/pivotal","html_url":"https://github.com/pivotal","followers_url":"https://api.github.com/users/pivotal/followers","following_url":"https://api.github.com/users/pivotal/following{/other_user}","gists_url":"https://api.github.com/users/pivotal/gists{/gist_id}","starred_url":"https://api.github.com/users/pivotal/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pivotal/subscriptions","organizations_url":"https://api.github.com/users/pivotal/orgs","repos_url":"https://api.github.com/users/pivotal/repos","events_url":"https://api.github.com/users/pivotal/events{/privacy}","received_events_url":"https://api.github.com/users/pivotal/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/pivotal/blog","description":"Pivotal Engineering Blog","fork":false,"url":"https://api.github.com/repos/pivotal/blog","forks_url":"https://api.github.com/repos/pivotal/blog/forks","keys_url":"https://api.github.com/repos/pivotal/blog/keys{/key_id}","collaborators_url":"https://api.github.com/repos/pivotal/blog/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/pivotal/blog/teams","hooks_url":"https://api.github.com/repos/pivotal/blog/hooks","issue_events_url":"https://api.github.com/repos/pivotal/blog/issues/events{/number}","events_url":"https://api.github.com/repos/pivotal/blog/events","assignees_url":"https://api.github.com/repos/pivotal/blog/assignees{/user}","branches_url":"https://api.github.com/repos/pivotal/blog/branches{/branch}","tags_url":"https://api.github.com/repos/pivotal/blog/tags","blobs_url":"https://api.github.com/repos/pivotal/blog/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/pivotal/blog/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/pivotal/blog/git/refs{/sha}","trees_url":"https://api.github.com/repos/pivotal/blog/git/trees{/sha}","statuses_url":"https://api.github.com/repos/pivotal/blog/statuses/{sha}","languages_url":"https://api.github.com/repos/pivotal/blog/languages","stargazers_url":"https://api.github.com/repos/pivotal/blog/stargazers","contributors_url":"https://api.github.com/repos/pivotal/blog/contributors","subscribers_url":"https://api.github.com/repos/pivotal/blog/subscribers","subscription_url":"https://api.github.com/repos/pivotal/blog/subscription","commits_url":"https://api.github.com/repos/pivotal/blog/commits{/sha}","git_commits_url":"https://api.github.com/repos/pivotal/blog/git/commits{/sha}","comments_url":"https://api.github.com/repos/pivotal/blog/comments{/number}","issue_comment_url":"https://api.github.com/repos/pivotal/blog/issues/comments{/number}","contents_url":"https://api.github.com/repos/pivotal/blog/contents/{+path}","compare_url":"https://api.github.com/repos/pivotal/blog/compare/{base}...{head}","merges_url":"https://api.github.com/repos/pivotal/blog/merges","archive_url":"https://api.github.com/repos/pivotal/blog/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/pivotal/blog/downloads","issues_url":"https://api.github.com/repos/pivotal/blog/issues{/number}","pulls_url":"https://api.github.com/repos/pivotal/blog/pulls{/number}","milestones_url":"https://api.github.com/repos/pivotal/blog/milestones{/number}","notifications_url":"https://api.github.com/repos/pivotal/blog/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/pivotal/blog/labels{/name}","releases_url":"https://api.github.com/repos/pivotal/blog/releases{/id}","deployments_url":"https://api.github.com/repos/pivotal/blog/deployments","created_at":"2015-08-31T08:51:11Z","updated_at":"2016-08-24T01:06:29Z","pushed_at":"2016-09-13T00:03:29Z","git_url":"git://github.com/pivotal/blog.git","ssh_url":"git@github.com:pivotal/blog.git","clone_url":"https://github.com/pivotal/blog.git","svn_url":"https://github.com/pivotal/blog","homepage":"http://engineering.pivotal.io/","size":19259,"stargazers_count":23,"watchers_count":23,"language":"CSS","has_issues":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":52,"mirror_url":null,"open_issues_count":14,"forks":52,"open_issues":14,"watchers":23,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/pivotal/blog/pulls/108"},"html":{"href":"https://github.com/pivotal/blog/pull/108"},"issue":{"href":"https://api.github.com/repos/pivotal/blog/issues/108"},"comments":{"href":"https://api.github.com/repos/pivotal/blog/issues/108/comments"},"review_comments":{"href":"https://api.github.com/repos/pivotal/blog/pulls/108/comments"},"review_comment":{"href":"https://api.github.com/repos/pivotal/blog/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/pivotal/blog/pulls/108/commits"},"statuses":{"href":"https://api.github.com/repos/pivotal/blog/statuses/04f83991993e5514878353afbdb727b61c608764"}}}}
{"actor":{"display_login":"craig-chasseur"}}