This repository has been archived by the owner on May 12, 2021. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 3
/
architecture-overview.html
667 lines (639 loc) · 46.5 KB
/
architecture-overview.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
<!DOCTYPE html>
<!--
Generated by Apache Maven Doxia at 2015-12-08
Rendered using Reflow Maven Skin 1.1.1 (http://andriusvelykis.github.io/reflow-maven-skin)
-->
<html xml:lang="en" lang="en">
<head>
<meta charset="UTF-8" />
<title>Apache Trafodion Architecture Overview</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="description" content="" />
<meta http-equiv="content-language" content="en" />
<link href="http://netdna.bootstrapcdn.com/bootswatch/2.3.2/cerulean/bootstrap.min.css" rel="stylesheet" />
<link href="http://netdna.bootstrapcdn.com/twitter-bootstrap/2.3.1/css/bootstrap-responsive.min.css" rel="stylesheet" />
<link href="./css/bootswatch.css" rel="stylesheet" />
<link href="./css/reflow-skin.css" rel="stylesheet" />
<link href="http://yandex.st/highlightjs/7.5/styles/default.min.css" rel="stylesheet" />
<link href="./css/lightbox.css" rel="stylesheet" />
<link href="./css/site.css" rel="stylesheet" />
<link href="./css/print.css" rel="stylesheet" media="print" />
<!-- Le HTML5 shim, for IE6-8 support of HTML5 elements -->
<!--[if lt IE 9]>
<script src="http://html5shim.googlecode.com/svn/trunk/html5.js"></script>
<![endif]-->
</head>
<body class="page-architecture-overview project-trafodion" data-spy="scroll" data-offset="60" data-target="#toc-scroll-target">
<div class="navbar navbar-fixed-top">
<div class="navbar-inner">
<div class="container">
<a class="btn btn-navbar" data-toggle="collapse" data-target="#top-nav-collapse">
<span class="icon-bar"></span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
</a>
<a class="brand" href="index.html">Apache <span class="color-highlight">Trafodion</span></a>
<div class="nav-collapse collapse" id="top-nav-collapse">
<ul class="nav pull-right">
<li ><a href="download.html" title="Download">Download</a></li>
<li class="dropdown">
<a href="#" class="dropdown-toggle" data-toggle="dropdown">About <b class="caret"></b></a>
<ul class="dropdown-menu">
<li ><a href="index.html" title="Project Overview">Project Overview</a></li>
<li ><a href="new-features.html" title="New Features">New Features</a></li>
<li ><a href="roadmap.html" title="Roadmap">Roadmap</a></li>
<li ><a href="performance.html" title="Performance">Performance</a></li>
<li ><a href="http:divider" title=""></a></li>
<li ><a href="team-list.html" title="Team">Team</a></li>
<li ><a href="presentations.html" title="Presentations">Presentations</a></li>
<li ><a href="mail-lists.html" title="Mailing List">Mailing List</a></li>
<li ><a href="http:divider" title=""></a></li>
<li ><a href="source-repository.html" title="Source Repository">Source Repository</a></li>
<li ><a href="issue-tracking.html" title="Issue Tracking">Issue Tracking</a></li>
<li ><a href="license.html" title="License">License</a></li>
</ul>
</li>
<li class="dropdown">
<a href="#" class="dropdown-toggle" data-toggle="dropdown">Using <b class="caret"></b></a>
<ul class="dropdown-menu">
<li ><a href="quickstart.html" title="Quick Start">Quick Start</a></li>
<li ><a href="download.html" title="Download">Download</a></li>
<li ><a href="install.html" title="Install">Install</a></li>
<li ><a href="management.html" title="Managing Trafodion">Managing Trafodion</a></li>
<li ><a href="http:divider" title=""></a></li>
<li ><a href="documentation.html" title="Documentation">Documentation</a></li>
<li ><a href="faq.html" title="FAQ">FAQ</a></li>
<li ><a href="release-notes.html" title="Release Notes">Release Notes</a></li>
</ul>
</li>
<li class="dropdown active">
<a href="#" class="dropdown-toggle" data-toggle="dropdown">Features <b class="caret"></b></a>
<ul class="dropdown-menu">
<li class="active"><a href="" title="Architecture Overview">Architecture Overview</a></li>
<li ><a href="http:divider" title=""></a></li>
<li ><a href="https://blueprints.launchpad.net/trafodion/+spec/security-ansi-schemas" title="ANSI Schema Support" class="externalLink">ANSI Schema Support</a></li>
<li ><a href="https://blueprints.launchpad.net/trafodion/+spec/ustat-automation" title="Automated Update Statistics" class="externalLink">Automated Update Statistics</a></li>
<li ><a href="https://blueprints.launchpad.net/trafodion/+spec/bulkunload" title="Bulk Unload" class="externalLink">Bulk Unload</a></li>
<li ><a href="https://wiki.trafodion.org/wiki/index.php/Trafodion_Manageability#Logging_Events" title="Event Handling" class="externalLink">Event Handling</a></li>
<li ><a href="https://blueprints.launchpad.net/trafodion/+spec/hybrid-query-cache" title="Hybrid Query Cache" class="externalLink">Hybrid Query Cache</a></li>
<li ><a href="https://blueprints.launchpad.net/trafodion/+spec/identity-column" title="Identity Column" class="externalLink">Identity Column</a></li>
<li ><a href="https://wiki.trafodion.org/wiki/index.php/Creating_Statistics_During_Bulk_Load" title="Immediate Update Statistics" class="externalLink">Immediate Update Statistics</a></li>
<li ><a href="https://blueprints.launchpad.net/trafodion/+spec/lob-support" title="Large Object (LOB)" class="externalLink">Large Object (LOB)</a></li>
<li ><a href="https://blueprints.launchpad.net/trafodion/+spec/ddl-query-invalidation" title="Metadata Query Invalidation" class="externalLink">Metadata Query Invalidation</a></li>
<li ><a href="https://cwiki.apache.org/confluence/display/TRAFODION/Cmp-divisioning" title="Multi-Temperature Data" class="externalLink">Multi-Temperature Data</a></li>
<li ><a href="https://blueprints.launchpad.net/trafodion/+spec/access-external-hbase-tables" title="Native HBase Tables" class="externalLink">Native HBase Tables</a></li>
<li ><a href="docs/Trafodion_odb_User_Guide.pdf" title="ODB">ODB</a></li>
<li ><a href="https://blueprints.launchpad.net/trafodion/+spec/sql-query-cancel" title="Query Cancel" class="externalLink">Query Cancel</a></li>
<li ><a href="https://blueprints.launchpad.net/trafodion/+spec/security-privilege-updates" title="Privilege Checking" class="externalLink">Privilege Checking</a></li>
<li ><a href="https://wiki.trafodion.org/wiki/index.php/Trafodion_Manageability" title="Repository" class="externalLink">Repository</a></li>
<li ><a href="https://blueprints.launchpad.net/trafodion/+spec/enable-get-statistics-thru-rms" title="Runtime Management System" class="externalLink">Runtime Management System</a></li>
<li ><a href="https://blueprints.launchpad.net/trafodion/+spec/sequence-numbers" title="Sequence Numbers" class="externalLink">Sequence Numbers</a></li>
<li ><a href="https://blueprints.launchpad.net/trafodion/+spec/skew-buster" title="Skew Buster" class="externalLink">Skew Buster</a></li>
<li ><a href="https://wiki.trafodion.org/wiki/index.php/Tutorial:_The_object-oriented_UDF_interface" title="Table-Oriented UDF" class="externalLink">Table-Oriented UDF</a></li>
<li ><a href="https://wiki.trafodion.org/wiki/index.php/Data_Loading#Trickle_Loading_Data_Into_Trafodion_Tables" title="Trickle Load" class="externalLink">Trickle Load</a></li>
<li ><a href="http:divider" title=""></a></li>
<li ><a href="https://wiki.trafodion.org/wiki/index.php/Backup_and_Restore" title="Backup/Restore Utility" class="externalLink">Backup/Restore Utility</a></li>
<li ><a href="https://wiki.trafodion.org/wiki/index.php/Metadata_Cleanup" title="Metadata Cleanup Utility" class="externalLink">Metadata Cleanup Utility</a></li>
</ul>
</li>
<li class="dropdown">
<a href="#" class="dropdown-toggle" data-toggle="dropdown">Contributing <b class="caret"></b></a>
<ul class="dropdown-menu">
<li ><a href="contribute.html" title="Contribute">Contribute</a></li>
<li ><a href="advocate.html" title="Advocate">Advocate</a></li>
<li ><a href="develop.html" title="Develop">Develop</a></li>
<li ><a href="testing.html" title="Test">Test</a></li>
<li ><a href="merge.html" title="Merge">Merge</a></li>
<li ><a href="release.html" title="Release">Release</a></li>
<li ><a href="http:divider" title=""></a></li>
<li ><a href="create-dev-environment.html" title="Create Dev Environment">Create Dev Environment</a></li>
<li ><a href="manage-dev-environment.html" title="Manage Dev Environment">Manage Dev Environment</a></li>
<li ><a href="setup-build-environment.html" title="Setup Build Environment">Setup Build Environment</a></li>
<li ><a href="build.html" title="Build Trafodion">Build Trafodion</a></li>
<li ><a href="http:divider" title=""></a></li>
<li ><a href="code.html" title="Modify Code">Modify Code</a></li>
<li ><a href="tests.html" title="Modify Tests">Modify Tests</a></li>
<li ><a href="document.html" title="Modify Documentation">Modify Documentation</a></li>
<li ><a href="website.html" title="Modify Web Site">Modify Web Site</a></li>
<li ><a href="wiki.html" title="Modify Wiki Pages">Modify Wiki Pages</a></li>
<li ><a href="http:divider" title=""></a></li>
<li ><a href="cplusplus-coding-guidelines.html" title="C++ Coding Guidelines">C++ Coding Guidelines</a></li>
</ul>
</li>
<li class="dropdown">
<a href="#" class="dropdown-toggle" data-toggle="dropdown">Apache <b class="caret"></b></a>
<ul class="dropdown-menu">
<li ><a href="http://incubator.apache.org/projects/trafodion.html" title="Status Page" target="_blank" class="externalLink">Status Page</a></li>
<li ><a href="http://www.apache.org/foundation/how-it-works.html" title="Apache Foundation" target="_blank" class="externalLink">Apache Foundation</a></li>
<li ><a href="http://www.apache.org/licenses/" title="Apache License" target="_blank" class="externalLink">Apache License</a></li>
<li ><a href="http://www.apache.org/security/" title="Apache Security" target="_blank" class="externalLink">Apache Security</a></li>
<li ><a href="http:divider" title=""></a></li>
<li ><a href="http://www.apache.org/foundation/sponsorship.html" title="Sponsorship" target="_blank" class="externalLink">Sponsorship</a></li>
<li ><a href="http://www.apache.org/foundation/thanks.html" title="Thanks" target="_blank" class="externalLink">Thanks</a></li>
</ul>
</li>
</ul>
</div><!--/.nav-collapse -->
</div>
</div>
</div>
<div class="container">
<!-- Masthead
================================================== -->
<header>
<div class="jumbotron subhead">
<div class="row" id="banner">
<div class="span12">
<div class="pull-left">
<a href="index.html" id="bannerLeft"><h1>Apache <span class="color-highlight">Trafodion</span></h1></a>
<p class="lead">Transactional SQL-on-Hadoop Database</p>
</div>
<div class="pull-right">
</div>
</div>
</div>
</div>
<div>
<ul class="breadcrumb">
<li><a href="index.html" title="Trafodion">Trafodion</a></li>
<li class="divider">/</li>
<li>Architecture Overview</li>
</ul>
</div>
<hr class="toc-separator" />
<div id="toc-bar" class="navbar" data-spy="affix" data-offset-top="250">
<div class="navbar-inner">
<div id="toc-scroll-target" class="container">
<a class="btn btn-navbar" data-toggle="collapse" data-target="#toc-nav-collapse">
<span class="icon-bar"></span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
</a>
<div class="nav-collapse collapse" id="toc-nav-collapse">
<ul id="toc" class="nav">
<li class="toplevel"><a href="#introduction" title="Introduction">Introduction</a></li>
<li class="divider-vertical"></li>
<li class="toplevel"><a href="#process_architecture" title="Process Architecture">Process Architecture</a></li>
<li class="divider-vertical"></li>
<li class="toplevel"><a href="#connectivity" title="Connectivity">Connectivity</a></li>
<li class="divider-vertical"></li>
<li class="toplevel"><a href="#transactions" title="Transactions">Transactions</a></li>
<li class="divider-vertical"></li>
<li class="dropdown">
<a href="#compiler_architecture" title="Compiler Architecture" class="dropdown-toggle" role="button" data-toggle="dropdown" data-target="#">Compiler Architecture <b class="caret"></b></a>
<ul class="dropdown-menu" role="menu">
<!-- Repeat the item, otherwise it is not clickable as the dropdown root -->
<li><a href="#compiler_architecture" title="Compiler Architecture">Compiler Architecture</a></li>
<li class="divider"></li>
<li><a href="#Parser" title="Parser">Parser</a></li>
<li><a href="#Binder" title="Binder">Binder</a></li>
<li><a href="#Normalizer" title="Normalizer">Normalizer</a></li>
<li><a href="#Optimizer" title="Optimizer">Optimizer</a></li>
<li><a href="#Pre-Code_Generator" title="Pre-Code Generator">Pre-Code Generator</a></li>
<li><a href="#Generator" title="Generator">Generator</a></li>
<li><a href="#Heap_Management" title="Heap Management">Heap Management</a></li>
<li><a href="#Error_Management" title="Error Management">Error Management</a></li>
</ul>
</li>
<li class="divider-vertical"></li>
<li class="dropdown">
<a href="#executor_architecture" title="Executor Architecture" class="dropdown-toggle" role="button" data-toggle="dropdown" data-target="#">Executor Architecture <b class="caret"></b></a>
<ul class="dropdown-menu" role="menu">
<!-- Repeat the item, otherwise it is not clickable as the dropdown root -->
<li><a href="#executor_architecture" title="Executor Architecture">Executor Architecture</a></li>
<li class="divider"></li>
<li><a href="#Relational_Operators" title="Relational Operators">Relational Operators</a></li>
<li><a href="#Scalar_Expressions" title="Scalar Expressions">Scalar Expressions</a></li>
<li><a href="#Interprocess_Communication" title="Interprocess Communication">Interprocess Communication</a></li>
<li><a href="#Call_Level_Interface" title="Call Level Interface">Call Level Interface</a></li>
<li><a href="#Heap_Management" title="Heap Management">Heap Management</a></li>
<li><a href="#Error_Management" title="Error Management">Error Management</a></li>
<li><a href="#Statistics_Reporting" title="Statistics Reporting">Statistics Reporting</a></li>
</ul>
</li>
</ul>
</div>
</div>
</div>
</div>
</header>
<div class="main-body">
<div class="row">
<div class="span12">
<div class="body-content">
<!-- Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License. -->
<p>This page provides information about the Trafodion architecture.</p>
<div class="page-header">
<h1 id="introduction">Introduction</h1>
</div>
<p>Trafodion provides an operational SQL engine on top of Hadoop – a solution targeted toward operational workloads in the Hadoop Big Data environment. Included are:</p>
<ul>
<li>Fully functional ANSI SQL language support</li>
<li>Full ACID support for read/write queries including distributed transaction protection for multiple rows, tables and statements</li>
<li>Heterogeneous storage engine access including native access to data stores</li>
<li>Enhanced High Availability support for client applications</li>
<li>Support for large data sets using optimized intra-query parallelism</li>
<li>Performance improvements for OLTP workloads via compile and runtime optimizations</li>
</ul>
<p>Transaction management features include:</p>
<ul>
<li>Transaction serializability using the HBase-Trx implementation of Multi-Version Concurrency Control</li>
<li>Transaction recovery to achieve database consistency</li>
<li>Thread-aware transaction management support to work with multi-threaded SQL clients</li>
<li>Non-transactional/direct access to HBase tables</li>
</ul>
<h1 id="process_architecture">Process Architecture</h1>
<p>The following figure depicts the Trafodion process architecture:</p>
<p><img src="images/process-architecture.png" alt="Trafodion Process Architecture" /></p>
<p>The figure above should be interpreted as follows:</p>
<ul>
<li>Client Applications talk to Trafodion via a JDBC or ODBC interface. The Trafodion drivers implement these interfaces, using an optimized Trafodion-specific wire protocol to talk to the Master Executor process in the SQL layer. The diagram shows a JDBC Type-4 driver configuration.</li>
<li>The Master Executor is the root process for executing SQL statements submitted via JDBC or ODBC. It contains a copy of the SQL compiler code. Most SQL statements are compiled within this process. The root of any compiled query plan is also executed in the Master Executor.</li>
<li>A few SQL statements (for example, DDL and some utilities) require a second instance of the compiler code; this is the CMP process in the diagram.</li>
<li>Trafodion supports several forms of execution-time parallelism. When a query plan requires parallelism, a set of ESP (Executor Server Processes) is dynamically spawned (if not already available). Each ESP executes a fragment of the query plan.</li>
<li>The DTM (Distributed Transaction Management) process manages distributed transactions. This includes log management and transaction coordination.</li>
<li>The Storage Engine layer consists of HBase and Hadoop processes. Trafodion allows SQL access to native HBase tables. Trafodion reads HBase metadata in order to process these tables. Trafodion also offers its own implementation of SQL table, stored as an HBase table, for applications that need a more efficient OLTP representation. Trafodion generates its own metadata for such tables, and stores that in HBase.</li>
</ul>
<h1 id="connectivity">Connectivity</h1>
<p>The Database Connectivity Services (DCS) framework enables applications developed for ODBC/JDBC APIs to access a Trafodion SQL database server. DCS is a distributed service. It uses the underlying HBase ZooKeeper instance for its definition of a cluster. <a class="externalLink" href="http://zookeeper.apache.org/" title="Zookeeper website">Apache ZooKeeper</a> is a centralized service for maintaining configuration information, naming, providing distributed synchronization, and providing group services. All participating nodes and clients need to be able to access the running ZooKeeper.</p>
<p>DCS is a collection of components:</p>
<ul>
<li><b>ODBC/JDBC Drivers</b>: Provide a standard programming language middle-ware API for accessing database management systems (DBMS).</li>
<li><b>DCS Master Process</b>: The DCS Master server is responsible for monitoring all server instances in the cluster. It assigns an ODBC/JDBC client connection request to a Master Executor (MXOSRVR) process. It also has a backup process that takes over the Master Executor role during failures.</li>
<li><b>DCS Server Process</b>: This process is responsible for starting and keeping a Master Executor (MXOSRVR) server process executing. There is one DCS Server process per node in the cluster.</li>
<li><b>Master Executor Process</b>: This is the database server that provides database access to ODBC/JDBC clients. There is a one-to-one relationship between an ODBC/JDBC client connection and a database server process. The Master Executor performs all SQL queries on behalf of its client’s requests. It will perform all required SQL calls to execute a SQL query through the Executor to access HBase tables. The Master Executor is often referred to as MXOSRVR.</li>
</ul>
<h1 id="transactions">Transactions</h1>
<p>Trafodion supports distributed ACID transaction semantics using the Multi-Version Concurrency Control (MVCC) model. The transaction management is built on top of a fork of the <i>HBase-trx</i> project implementing the following changes:</p>
<ul>
<li>Upgraded it to work on HBase version 0.98.1 (for CDH 5.1) or 0.98.0 (for HDP 2.1).</li>
<li>Added support for parallel worker processes doing work on behalf of the same transaction.</li>
<li>Added support for global transactions, that is, transactions that can encompass resources (regions/HTables) across an HBase cluster.</li>
<li>Added transaction recovery after server failure.</li>
</ul>
<p>There is on Distributed Transaction Manager (DTM) process per node in a cluster running Trafodion. The DTM process owns and keeps track of all transactions that were started on that node. (In HBase-trx, transactions were tracked in the library code of each client, which meant that after a server failure, there was no way to restart the transaction manager for in-doubt transactions.)</p>
<p>When a Trafodion client begins a SQL statement, it checks in with the Transaction Manager (TM) to begin the transaction. The TM returns a cluster-unique transaction ID. This transaction ID in turn is propagated by the Trafodion Executor to any processes that work on some fragment of that SQL statement. This transaction ID propagation occurs courtesy of a Trafodion messaging layer, which keeps track, for example, of whether a process death has occurred.</p>
<p>When a Trafodion Executor process issues an HBase call, the modified client-side HBase-trx library can deduce which TM owns the transaction from the transaction ID, and registers itself with that TM if it has not already done so. Thus, at any given moment in time, a TM is aware of what processes are participating in a transaction.</p>
<p>The original HBase-trx library worked by extending certain Java classes in the region server. Our implementation has for the most part changed to execute this library in co-processors. This allows better extensibility at the HBase level. With a class extension approach, only one feature could extend the HBase code. With co-processors, it is possible to host several extensions. Endpoint and observer co-processors perform the resource manager role in transaction processing.</p>
<p>For additional details, please refer to the <a href="presentations/dtm-architecture.pdf">Trafodion Distributed Transaction Management</a> presentation.</p>
<h1 id="compiler_architecture">Compiler Architecture</h1>
<p>The Trafodion Compiler translates SQL statements into query plans that can then be executed by the Trafodion execution engine, commonly called the Executor.</p>
<p>The Compiler is a multi-pass compiler. Each pass transforms a representation of the SQL statement into a new or augmented representation which is input to the next pass. The sections below give more detail on each pass. The logic that calls each pass is in the CmpMain class, method CmpMain::compile. You can find that logic in file $MY_SQROOT/sql/sqlcomp/CmpMain.cpp.</p>
<p>A copy of the compiler code runs in the Master process, which avoids inter-process message passing between the Compiler and Executor. At the moment the compiler code is not re-entrant, but it is a serially reusable resource within the Master. Some processing is recursive. For example, the execution logic for DDL statements is packaged with the compiler code. When we execute a DDL statement, the Executor spawns a separate Compiler process to execute that logic. For another example, the UPDATE STATISTICS utility dynamically generates SQL SELECT statements to obtain statistical data. Since we are not re-entrant, we spawn a separate Compiler process for this recursive processing.</p>
<p>The compiler is written in C++.</p>
<div class="section">
<h2 id="Parser">Parser</h2>
<p>The parser pass performs lexical and syntactic analysis, transforming the SQL statement into a parse tree. Trafodion uses a hand-coded scanner for lexical analysis of UCS2 strings. (UTF-8 encoding for SQL statement text is supported but is translated to UCS2 internally). </p>
<p>The parser grammar is implemented as a set of Bison rules. The output of the parser is a tree of objects of class RelExpr, representing relational operators. Scalar expressions are represented by trees of ItemExpr objects, which are contained in the nodes of the RelExpr tree. This common model to represent a query is used throughout the compilation process.</p>
</div>
<div class="section">
<h2 id="Binder">Binder</h2>
<p>The binder pass takes the parse tree and decorates it with metadata information. All references to SQL objects (tables, views, columns and so on) are bound to their respective metadata. The binder also performs type synthesis. At this stage, errors such as the wrong data type being passed to a function call or that a column reference doesn’t belong to any of the tables in scope are detected.</p>
<p>The binder also manages a cache of query plans. If the binder detects that the new SQL statement is similar to one previously compiled, it simply reuses the earlier query plan (modifying parameters as needed), bypassing subsequent compiler passes. This can be significant as optimization is often the most expensive compilation phase.</p>
</div>
<div class="section">
<h2 id="Normalizer">Normalizer</h2>
<p>The SQL language is rich in redundancy. Many concepts can be expressed in multiple ways. For example, sub-queries can be expressed as joins. The DISTINCT clause can be transformed into GROUP BY. The normalizer pass removes this redundancy, transforming the parse tree into a normalized representation in the following steps.</p>
<ul>
<li><b>Predicate Pull-Up</b>: Predicates are pulled up the tree as high as is semantically possible. Then equivalence classes (Value Equivalence Groups or VEGs) are created for columns and values that are subject to equality predicates. References to such columns and values are then replaced with a reference to the equivalence class (VEG). Similarly equality predicates themselves are replaced with a predicate that simply points to the equivalence class. Predicate pull-up is how we achieve transitive closure.</li>
<li><b>Normalization</b>: Predicates are pushed back down again, performing some optimizations. For example, if we have the query, select * from t1 join t2 on t1.a = t2.b where t1.a = 5, we can infer the predicate t2.b = 5 and push that down into the t2 scan operator.</li>
<li><b>Semantic Query Optimization</b>: We perform unconditional transformations that depend on uniqueness or cardinality constraints.</li>
</ul>
</div>
<div class="section">
<h2 id="Optimizer">Optimizer</h2>
<p>The Trafodion optimizer is a rule-based, cost-driven optimizer based on the Cascades Framework. By “rule-based”, we mean that plan transformation is based on a set of rules coded within the Optimizer. (We don’t mean syntax-driven optimization based on hints in the SQL statement text.) By “cost-driven”, we mean that cost estimates are used to bound the search space.</p>
<p>It is a top-down optimizer; that is, it generates an initial feasible plan for the query, then using rules, transforms that plan into semantically equivalent alternatives. The optimizer computes the cost of each plan, and uses these costs to bound its search for additional plans using a branch-and-bound algorithm. This is in contrast to classical, dynamic programming-style optimizers, that build up a set of plans “bottom-up”, by first considering all one-table plans, then joins of two tables, then joins of three tables and so on.</p>
<p>The optimizer itself is multiple passes, some of which can be bypassed depending on the optimization level chosen for the compile. The first pass simply generates the initial feasible plan. Subsequent passes apply successively richer sets of rules to traverse the search space. For example, we first consider only hash joins, and in later passes introduce the possibility of nested or merge joins.</p>
<p>The optimizer makes a distinction between logical and physical expressions. A logical expression considers the semantics of an operator, for example, a join. Certain aspects of a plan pertain to logical expressions, for example estimated output row count. A physical expression considers the implementation of an operator, for example, a nested join. Certain aspects of a plan pertain to physical expressions, for example estimated message counts. Rules transform logical expressions into other logical expressions or into physical expressions. So, for example, join order would be permuted at the logical expression level, then join method considered as we implement the operator with a physical expression.</p>
<p>Search spaces in general are exponential in size. So the optimizer is rich in heuristics to limit where it searches. The optimizer also takes into account variation: Estimations of cost for individual relational operators will be imperfect; the optimizer tries to pick plans that degrade gracefully if estimates are off the mark.</p>
<p>Another factor the optimizer takes into account is that traversal can wrap back to a previously visited plan. The optimizer remembers plans previously visited in a “memo” structure (class CascadesMemo). Plans are hashed for quick lookup.</p>
</div>
<div class="section">
<h2 id="Pre-Code_Generator">Pre-Code Generator</h2>
<p>The pre-code generator performs unconditional transformations after the optimization phase. References to elements of an equivalence class are replaced with the most efficient alternatives. </p>
<p>For example, an equivalence class (VEG) containing { T1.A, T2.B, 5 }, in the context of a T2 scan operator results in the predicate T2.B = 5.</p>
</div>
<div class="section">
<h2 id="Generator">Generator</h2>
<p>The generator pass transforms the chosen optimized tree into a query plan which can then be executed by the Executor. Low-level optimizations of scalar expressions take place here. Many scalar expressions are generated in native machine code using the open source LLVM infrastructure. For those scalar operators where we have not yet implemented native expression support, we instead generate code that is interpreted at run time.</p>
</div>
<div class="section">
<h2 id="Heap_Management">Heap Management</h2>
<p>In order to make heap management efficient, the Compiler uses heap classes, NAHeap, that it shares with the executor. One heap, the Statement heap, is used for objects that are particular to a given SQL statement’s compilation, for example, parse tree nodes. At the end of statement compilation, we simply destroy the heap instead of calling “delete” on each of possibly thousands of objects. Another heap, the Context heap, is used for objects that may be reused across SQL statements. For example, metadata is cached within the compiler. As one can imagine, considerable care goes into selecting which heap to use when creating a given object, to avoid dangling references and other resource leaks. For example, access to a given file must be encapsulated in an object on the global heap, since on the statement heap we cannot count on execution of the destructor to close the file.</p>
</div>
<div class="section">
<h2 id="Error_Management">Error Management</h2>
<p>The Compiler captures error information into a ComDiagsArea object. The style of programming is to return on errors rather than throw exceptions. Calling logic then checks for the presence of errors before continuing. So, for example, the main logic that invokes each compiler pass checks for errors before proceeding to the next pass.</p>
<h1 id="executor_architecture">Executor Architecture</h1>
<p>The Trafodion Executor implements a data-flow architecture. That is, each relational operator is implemented as a set of tasks which are scheduled for execution. Operators communicate with each other using queues.</p>
</div>
<div class="section">
<h2 id="Relational_Operators">Relational Operators</h2>
<p>A query plan consists of a collection of fragments, each fragment being a portion of the query plan executed in a given process. Each fragment in turn is a tree of relational operators. A relational operator may in turn be decorated with additional scalar expressions. Relational operators in the query plan are represented by two class hierarchies, ex_tdb and ex_tcb. The ex_tdb (tdb = “task descriptor block”) hierarchy contains the compiler-generated state for the operator. The ex_tcb (tcb = “task control block”) hierarchy contains the run-time state for the operator. So, for example, the queue objects are pointed to by ex_tcb objects.</p>
</div>
<div class="section">
<h2 id="Scalar_Expressions">Scalar Expressions</h2>
<p>Scalar expressions are evaluated by an expression evaluator. If the expression could be compiled into native machine code, the expression evaluator simply invokes this code. Otherwise, the expression evaluator implements an interpreter. For historical reasons, there are actually two interpreters. The first (and oldest) is a high level clause-based expression evaluator: each clause roughly corresponds to a scalar operator in the original SQL text. The second (and newest) is a PCODE-based evaluator, implementing a lower-level machine-like instruction set. Most expressions that cannot be generated as native machine code are generated as PCODE; those few expressions that PCODE cannot cover are generated as clause expressions. For debugging purposes, it is possible to force the Compiler to generate PCODE instead of native machine code, or clause-based expressions instead of either native machine code or PCODE.</p>
</div>
<div class="section">
<h2 id="Interprocess_Communication">Interprocess Communication</h2>
<p>An IPC layer, shared with other components such as the compiler, abstracts the (asynchronous) communication of objects across process boundaries. The sorts of things that flow are query plan objects, data rows, and error objects (ComDiagsArea).</p>
</div>
<div class="section">
<h2 id="Call_Level_Interface">Call Level Interface</h2>
<p>At the highest level of the Executor is the Call Level Interface (CLI) layer. This layer implements an ODBC-like interface to the Executor. Connectivity code communicates to the Executor using this interface. The CLI layer keeps track of such abstractions as SQL statements and cursors. It also provides an interface to retrieve SQL diagnostics.</p>
</div>
<div class="section">
<h2 id="Heap_Management">Heap Management</h2>
<p>The Executor also uses the NAHeap classes for heap management. Again, there are statement heaps for objects local to a given SQL statement, and a global heap for objects that exist across statements.</p>
</div>
<div class="section">
<h2 id="Error_Management">Error Management</h2>
<p>The Executor too uses the ComDiagsArea classes for error management. Like the Compiler, the programming style relies on returns rather than exceptions; calling code is expected to check for the existence of errors and respond appropriately.</p>
</div>
<div class="section">
<h2 id="Statistics_Reporting">Statistics Reporting</h2>
<p>The Executor also collects statistics concerning the execution of a particular query. These statistics are available at the CLI interface at the conclusion of statement execution.</p>
</div>
</div>
</div>
</div>
</div>
</div><!-- /container -->
<!-- Footer
================================================== -->
<footer class="well">
<div class="container">
<div class="row">
<div class="span2 bottom-nav">
<ul class="nav nav-list">
<li class="nav-header">About</li>
<li >
<a href="index.html" title="Project Overview">Project Overview</a>
</li>
<li >
<a href="new-features.html" title="New Features">New Features</a>
</li>
<li >
<a href="roadmap.html" title="Roadmap">Roadmap</a>
</li>
<li >
<a href="performance.html" title="Performance">Performance</a>
</li>
<li >
<a href="http:divider" title=""></a>
</li>
<li >
<a href="team-list.html" title="Team">Team</a>
</li>
<li >
<a href="presentations.html" title="Presentations">Presentations</a>
</li>
<li >
<a href="mail-lists.html" title="Mailing List">Mailing List</a>
</li>
<li >
<a href="http:divider" title=""></a>
</li>
<li >
<a href="source-repository.html" title="Source Repository">Source Repository</a>
</li>
<li >
<a href="issue-tracking.html" title="Issue Tracking">Issue Tracking</a>
</li>
<li >
<a href="license.html" title="License">License</a>
</li>
</ul>
</div>
<div class="span2 bottom-nav">
<ul class="nav nav-list">
<li class="nav-header">Using</li>
<li >
<a href="quickstart.html" title="Quick Start">Quick Start</a>
</li>
<li >
<a href="download.html" title="Download">Download</a>
</li>
<li >
<a href="install.html" title="Install">Install</a>
</li>
<li >
<a href="management.html" title="Managing Trafodion">Managing Trafodion</a>
</li>
<li >
<a href="http:divider" title=""></a>
</li>
<li >
<a href="documentation.html" title="Documentation">Documentation</a>
</li>
<li >
<a href="faq.html" title="FAQ">FAQ</a>
</li>
<li >
<a href="release-notes.html" title="Release Notes">Release Notes</a>
</li>
</ul>
</div>
<div class="span2 bottom-nav">
<ul class="nav nav-list">
<li class="nav-header">Features</li>
<li class="active">
<a href="#" title="Architecture Overview">Architecture Overview</a>
</li>
<li >
<a href="http:divider" title=""></a>
</li>
<li >
<a href="https://blueprints.launchpad.net/trafodion/+spec/security-ansi-schemas" title="ANSI Schema Support" class="externalLink">ANSI Schema Support</a>
</li>
<li >
<a href="https://blueprints.launchpad.net/trafodion/+spec/ustat-automation" title="Automated Update Statistics" class="externalLink">Automated Update Statistics</a>
</li>
<li >
<a href="https://blueprints.launchpad.net/trafodion/+spec/bulkunload" title="Bulk Unload" class="externalLink">Bulk Unload</a>
</li>
<li >
<a href="https://wiki.trafodion.org/wiki/index.php/Trafodion_Manageability#Logging_Events" title="Event Handling" class="externalLink">Event Handling</a>
</li>
<li >
<a href="https://blueprints.launchpad.net/trafodion/+spec/hybrid-query-cache" title="Hybrid Query Cache" class="externalLink">Hybrid Query Cache</a>
</li>
<li >
<a href="https://blueprints.launchpad.net/trafodion/+spec/identity-column" title="Identity Column" class="externalLink">Identity Column</a>
</li>
<li >
<a href="https://wiki.trafodion.org/wiki/index.php/Creating_Statistics_During_Bulk_Load" title="Immediate Update Statistics" class="externalLink">Immediate Update Statistics</a>
</li>
<li >
<a href="https://blueprints.launchpad.net/trafodion/+spec/lob-support" title="Large Object (LOB)" class="externalLink">Large Object (LOB)</a>
</li>
<li >
<a href="https://blueprints.launchpad.net/trafodion/+spec/ddl-query-invalidation" title="Metadata Query Invalidation" class="externalLink">Metadata Query Invalidation</a>
</li>
<li >
<a href="https://cwiki.apache.org/confluence/display/TRAFODION/Cmp-divisioning" title="Multi-Temperature Data" class="externalLink">Multi-Temperature Data</a>
</li>
<li >
<a href="https://blueprints.launchpad.net/trafodion/+spec/access-external-hbase-tables" title="Native HBase Tables" class="externalLink">Native HBase Tables</a>
</li>
<li >
<a href="docs/Trafodion_odb_User_Guide.pdf" title="ODB">ODB</a>
</li>
<li >
<a href="https://blueprints.launchpad.net/trafodion/+spec/sql-query-cancel" title="Query Cancel" class="externalLink">Query Cancel</a>
</li>
<li >
<a href="https://blueprints.launchpad.net/trafodion/+spec/security-privilege-updates" title="Privilege Checking" class="externalLink">Privilege Checking</a>
</li>
<li >
<a href="https://wiki.trafodion.org/wiki/index.php/Trafodion_Manageability" title="Repository" class="externalLink">Repository</a>
</li>
<li >
<a href="https://blueprints.launchpad.net/trafodion/+spec/enable-get-statistics-thru-rms" title="Runtime Management System" class="externalLink">Runtime Management System</a>
</li>
<li >
<a href="https://blueprints.launchpad.net/trafodion/+spec/sequence-numbers" title="Sequence Numbers" class="externalLink">Sequence Numbers</a>
</li>
<li >
<a href="https://blueprints.launchpad.net/trafodion/+spec/skew-buster" title="Skew Buster" class="externalLink">Skew Buster</a>
</li>
<li >
<a href="https://wiki.trafodion.org/wiki/index.php/Tutorial:_The_object-oriented_UDF_interface" title="Table-Oriented UDF" class="externalLink">Table-Oriented UDF</a>
</li>
<li >
<a href="https://wiki.trafodion.org/wiki/index.php/Data_Loading#Trickle_Loading_Data_Into_Trafodion_Tables" title="Trickle Load" class="externalLink">Trickle Load</a>
</li>
<li >
<a href="http:divider" title=""></a>
</li>
<li >
<a href="https://wiki.trafodion.org/wiki/index.php/Backup_and_Restore" title="Backup/Restore Utility" class="externalLink">Backup/Restore Utility</a>
</li>
<li >
<a href="https://wiki.trafodion.org/wiki/index.php/Metadata_Cleanup" title="Metadata Cleanup Utility" class="externalLink">Metadata Cleanup Utility</a>
</li>
</ul>
</div>
<div class="span2 bottom-nav">
<ul class="nav nav-list">
<li class="nav-header">Contributing</li>
<li >
<a href="contribute.html" title="Contribute">Contribute</a>
</li>
<li >
<a href="advocate.html" title="Advocate">Advocate</a>
</li>
<li >
<a href="develop.html" title="Develop">Develop</a>
</li>
<li >
<a href="testing.html" title="Test">Test</a>
</li>
<li >
<a href="merge.html" title="Merge">Merge</a>
</li>
<li >
<a href="release.html" title="Release">Release</a>
</li>
<li >
<a href="http:divider" title=""></a>
</li>
<li >
<a href="create-dev-environment.html" title="Create Dev Environment">Create Dev Environment</a>
</li>
<li >
<a href="manage-dev-environment.html" title="Manage Dev Environment">Manage Dev Environment</a>
</li>
<li >
<a href="setup-build-environment.html" title="Setup Build Environment">Setup Build Environment</a>
</li>
<li >
<a href="build.html" title="Build Trafodion">Build Trafodion</a>
</li>
<li >
<a href="http:divider" title=""></a>
</li>
<li >
<a href="code.html" title="Modify Code">Modify Code</a>
</li>
<li >
<a href="tests.html" title="Modify Tests">Modify Tests</a>
</li>
<li >
<a href="document.html" title="Modify Documentation">Modify Documentation</a>
</li>
<li >
<a href="website.html" title="Modify Web Site">Modify Web Site</a>
</li>
<li >
<a href="wiki.html" title="Modify Wiki Pages">Modify Wiki Pages</a>
</li>
<li >
<a href="http:divider" title=""></a>
</li>
<li >
<a href="cplusplus-coding-guidelines.html" title="C++ Coding Guidelines">C++ Coding Guidelines</a>
</li>
</ul>
</div>
<div class="span4 bottom-description">
<blockquote><a href="http://trafodion.apache.org/">Apache Trafodion</a> is a webscale SQL-on-Hadoop solution enabling transactional or operational
workloads on Hadoop. <br /><br />The name "Trafodion" (the Welsh word for transactions, pronounced
"Tra-vod-eee-on") was chosen specifically to emphasize the differentiation that
Trafodion provides in closing a critical gap in the Hadoop ecosystem.<br /><br />
Trafodion builds on the scalability, elasticity, and flexibility of Hadoop. Trafodion extends
Hadoop to provide guaranteed transactional integrity, enabling new kinds of big data
applications to run on Hadoop.</blockquote>
</div>
</div>
</div>
</footer>
<div class="container subfooter">
<div class="row">
<div class="span12">
<p class="pull-right"><a href="#">Back to top</a></p>
<p class="copyright">Copyright ©2015 <a href="http://www.apache.org">Apache Software Foundation</a>. All Rights Reserved.</p>
<hr/>
<div class="row span16">
<span>Disclaimer: Apache Trafodion is an effort undergoing incubation at the Apache Software Foundation (ASF), sponsored by the Apache Incubator PMC.
Incubation is required of all newly accepted projects until a further review indicates that the infrastructure, communications, and decision making
process have stabilized in a manner consistent with other successful ASF projects. While incubation status is not necessarily a reflection of the
completeness or stability of the code, it does indicate that the project has yet to be fully endorsed by the ASF.</span>
<br/>
<br/>
<span>Apache, Apache Maven, Apache Maven Fluido Skin, the Apache feather logo, the Apache Maven project logo and the Apache Incubator project logo
are trademarks of The Apache Software Foundation.</span>
<br/>
<br/>
<span>
<a target="_blank" href="http://www.apache.org">
<img id="asf-logo" alt="Apache Software Foundation" src="images/logos/feather-small.gif"/>
</a>
<a target="_blank" href="http://incubator.apache.org/">
<img id="incubator-logo" alt="Apache Incubator" src="images/logos/egg-logo.gif"/>
</a>
</span>
</div> </div>
</div>
</div>
<!-- Le javascript
================================================== -->
<!-- Placed at the end of the document so the pages load faster -->
<script src="http://ajax.googleapis.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
<script src="http://netdna.bootstrapcdn.com/twitter-bootstrap/2.3.2/js/bootstrap.min.js"></script>
<script src="./js/lightbox.min.js"></script>
<script src="./js/reflow-scroll.js"></script>
<script src="http://yandex.st/highlightjs/7.5/highlight.min.js"></script>
<script src="./js/reflow-skin.js"></script>
</body>
</html>