{'fraction_non_alphanumeric': 0.022317457750464946, 'fraction_numerical': 0.004851621250101076, 'mean_word_length': 4.353208527215669, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 1, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Multi Query Optimization in GLADE

SQL-on-Hadoop systems, query optimization, data distribution over multiple nodes and parallelization techniques are few of the areas under extreme research these days. Big names like Amazon, Google, Microsoft and many more are working on implementing systems for faster access of data from multiple nodes reducing data mobility and increasing the parallelization. Queries are retrieved and reviewed by the database systems in an efficient way in the least amount of time by the introduction of various parallelization techniques by running the same query in parallel over different nodes carrying the data. Apart from multi-threading parallelization, there is another way of parallelization that can be performed in order to further reduce retrieval time hence improving the efficiency of the system; parallelization on user queries on top of a DBMS/RDBMS. In this paper, we will study one such technique of how multiple queries can run simultaneously on a system in order to increase the efficiency by reducing the data retrieval from the storage. Maximum sharing of workload has been performed by generating optimal and ubiquitous join plans for a set of queries and then fed them to GLADE (Generalized Linear Aggregate Distribution Engine), a scalable distributed system for large scale data analytics. Our main work is centered on generating GLADE join plans for a Multi-Query satisfying maximum number of queries in order to maximize data sharing and minimize data retrieval for each individual query.


SQL and DBMS
Programming lanuages or machine languages helps us interact with machines.
There are different types of programming languages in order to communicate with the machine and pass instructions to get our work done in an efficient way. We have static and dynamic programming languages, which are then further breakdown into weak and strong languages (the detail of this is beyond the scope of this paper). While we are talking to machines in different languages instructing them to perform our tasks, we need some type of storage buffer, where we can store data in order to fetch it later on, when needed. This DATABASE system is a place where the data is stored, in a structured or unstructured format, organized or randomly spread, depending upon the type and need of data. The data, if stored in a structured manner in the database, is stored in the form of tables. When there is a need of storing a data in the form of database, there came the need of implementing a system, which can provide the user or the customers to interact with the database engine, where data is stored, and perform different tasks on the user stored data. Such systems are called Database Management Systems (DBMS).
DBMS provide the user to interact with the computer via some environment which can be a GUI (graphical user interface) or the form of passing the commands and talking to the computer using some special syntax. This special syntax is actually a designated language assigned to communicate with the database, and is called Structured Query Language or SQL. Via SQL, we have full control of our database and can fetch or add more data, update the existing data and so on.
There are different types of existing DBMS's like Oracle, IBM DB2, Microsoft SQL server, Access, MySQL, Sybase and many more. On the other hand, SQL is further categorized into 3 different types of command sets, namely data definition language, data manipulation language, and data control language. The most standard SQL commands with which one can almost communicate completely with the database system are CREATE, INSERT, SELECT, UPDATE, DROP and DELETE.

RDBMS
RDBMS stands for relational DBMS, which is a DBMS that contains data stored in form of tables and the tables are being related to each other through some attribute(s).
The power of RDBMS is its property of relation among the tables, because of which we can break down bigger tables into smaller tables with some common relation between them. As the size of the data is growing exponentially, the need of RDBMS is increasing, since we don't end up having such a huge amount of memory at one place, hence we cannot store all the data at one place. So the ease provided by RDBMS gets handy here. We will talk about GLADE in this paper shortly and explain how the testing is being done in GLADE using RDBMS.

SQL-on-Hadoop Hype
In the previous section, we talked about structured query language. In this section, we will put some light on Hadoop and then SQL-on-Hadoop systems. Hadoop or Apache Hadoop is an open source software framework that lets you store your data in large amount (of the order of 10 15 and more) over a distributed system with multiple clusters, and then later on let you process such big data using simple programming models. It comes in handy when the data is extremely large and you cannot store it on a single machine. Hadoop distributed file system (HDFS) is an extremely fault tolerant and low cost file system that provides scalable and reliable data storage and control on your stored data. The data stored is in terabytes to petabytes in size and even more.
So what is the hype about systems with SQL on top of Hadoop or HDFS? These days, companies are increasingly inclining towards using Apache Hadoop as the underlying system to store their data. On the other hand, to manage the data, they deeply rely on SQL because of the familiarity and ease of using SQL. As a result over the past few decades, by supporting familiar SQL queries, SQL processing over HDFS is getting more and more attention, and number of enterprise developers and business analysts providing such SQL-on-Hadoop functionality in their architecture is increasing exponentially, GLADE being one of them. GLADE used to work on a different M4 language format for the queries, but we will get to that later on in the paper on how SQL support is being introduced in GLADE.
Clearly, next generation of big data is coming in full bloom to help enterprises and Business Intelligence (BI) to store, process and analyze big data more effectively and efficiently.

GLADE Introduction
GLADE is an acronym for Generalized Linear Aggregate (GLA) Distributed Engine and is a scalable distributed framework for large scale data analytics. All the implementation of the algorithms in the paper are done in GLADE and all the queries were tested in GLADE too. We will discuss in depth about the architecture of GLADE and how it works in Chapter 4. GLADE, a relational execution engine, basically consists of a simple user interface to create user defined functions, here we call them GLA's, the heart of GLADE, and a distributed system that executes these GLA's in parallel. We will discuss more about how different type of parallelism is used in GLADE. It is derived from DataPath [2] which is an extremely efficient multi-query processing framework.

Problem Formulation
Query execution in a distributed system is one of the hot topic these days. BI are working on making their systems more efficient trying to execute queries as fast as possible and as parallel as possible to achieve lesser time and process more data. One mundane way of achieving faster data retrieval is parallelization among the nodes. In this paper, we will consider another rather less common but more efficient way of parallelization on queries, on top on node parallelization. We call it as Multi Query Optimization, which is discussed in detail in Chapter 5.

Solution Analysis
In this paper, we will show that how parallelization is achieved by running the same query on all the nodes having the data, and how same execution plan runs on each node to extract data. All the nodes passes the data back to one master node, where the data aggregation is done and the results are passed back to the user. This is one of the monotonous way of query execution. In this paper, we will consider another way of parallelization on queries. In that case, our system will create chunks of queries and call each chunk as a Multi Query (MQ).
A MQ consists of a set of queries, where each query contains certain distinct tables.
There is only one constraint on how each MQ is defined, and that is there has to be one query in a MQ, that consists of all the tables used in all the other queries collectively. Each MQ is processed to generate a single shared GLADE join plan, which is a graph with multiple exit points. Each exit point correspond to each query in a MQ. The whole graph is executed on all the nodes to generate results for all the queries simultaneously.
The main idea behind this algorithm is to achieve faster retrieval of data from the underlying system without the need of accessing it multiple number of times. This redundancy is simply removed by pairing the same set of queries sharing the same tables.
For example if we have a MQ with q number of queries, and say ( ') corresponds to the worst case cost of the query containing all the tables for this particular MQ, then the overall cost for all the queries collectively as a MQ is upper bounded by ⌈ ( ') ⌉. The main algorithm will be discussed in the Chapter 5 and we will show how this algorithm is derived from [1].

Existing solutions and their limitations
There has been a lot of work going on in the area of MQ optimization. BI are trying to optimize their distributed systems by implementing various algorithms, trying to reduce the retrieval time and get the results as fast as possible. The fight for creating a perfect distributed system that generates millions and millions of tuples within microseconds is real. [1], [3] and [4] have done a lot of work on optimizing the cost of running multiple queries. In this paper, we will discuss about a new technique of parallelization, parallelization of queries which we named as Multi Query Optimization. The idea is somewhat similar to [1] but with modifications and considering sharing of queries in a different way, by incorporating satisfied and unsatisfied queries while generating GLADE join plans.

Contributions
GLADE has already been on the play from past 5 years and advancements are being carried on in it. The main contributions we brought into GLADE are providing support to handle multiple queries at a time. We also provide the support for SQL queries in GLADE, which was previously working on M4 format. We introduce the keyword MULTIQUERY in GLADE's dictionary of SQL (more detail on that in Chapter 5) and performed different tests for different set of MQ's in GLADE. To abridge, here is the list of all the contributions in this paper that we have introduced in GLADE:  Integrate SQL query parser, query compiler and query optimizer in GLADE.
 Implement support for SQL queries into GLADE by converting SQL text to GLADE execution plans.
 Implement support for multi-queries in GLADE using Yacc.

Report Timeline
The report is divided into 6 chapters. We have already discussed the introduction chapter. In the next chapter, we will discuss about query planning and query execution in general, how GLADE plans are generated and what are different components of query planner. In chapter 3, we will discuss how we incorporated query optimization in GLADE to generate execution plans to run on GLADE nodes and how we provided SQL support in GLADE. In chapter 4, we will discuss about GLADE and its architecture in general.
Chapter 5 finally talks about multi query optimization algorithm in GLADE on top of simple query optimizer, which is a variant of [1]. Chapter 6 concludes our paper.

Introduction
Database management systems helps us to interact with the database where the data is stored somewhere in the underlying memory. This is a big picture, and in order to understand what is happening at a lower level, we need to get inside on how queries are being processed inside the engine and what is the most optimal way to retrieve the data from the storage. Query planner tells us how a relational DBMS evaluates and processes the queries, how different components of DBMS work together to take a query from a user and parse it, generate join plans consisting of joins of the tables from which the data is to be fetched, and eventually execute those join plans to generate tuples for the user.
There are 4 basic steps in which a query is being processed in GLADE:  Query Parsing Let's look into the depth of how each of these components work and then look at an example of how these steps are implemented in GLADE. We will talk about query execution in detail in next chapter, when we explain how execution plans are converted to graph and waypoint files.

Query Parsing
When a SQL query is first submitted by the user, it is passed through a parser which translates the query into its equivalent relational algebra expression. The first step in query parsing is Tokenization. The query text is converted into its tokenize representation by the query lexer. We had already defined a set of rules which define how to scan a query and what action to perform against each token. This tokenize representation of each part of a query is in a form of a tree and is required by the parser for further Semantics Validation.  involves determination of the validity of the query, like if all the tables are present in the   database, the table attributes are valid and are present in the corresponding tables and other grammatical and structural validation. This step is necessary since we need to confirm that the format and all the variables of the query are correct.
In GLADE, we have used Lex/Yacc for tokenizing and finding the hierarchical structure for the query. We have predefined the tokens and the production rules which defines how to understand the input query language and what action to take for each statement the lexer has generated for parsing. Once the query passes all the parsing checks, it is then passed on to the query optimizer.
In order to understand how parser works, consider following query: SELECT DISTINCT c_name, c_address, c_acctbal FROM region, nation, customer, orders WHERE o_custkey = c_custkey AND c_nationkey = n_nationkey AND n_regionkey = r_regionkey AND r_regionkey < 5 Here, we have 4 relations/tables namely region, nation, customer and orders. The benchmark we have used throughout our project for testing was TPCH. The first step in parsing is to check if the structure of the query is correct or not. We see that the query has all the necessary clauses (SELECT, FROM, WHERE) and in the right order. We have defined these tokens in the parser dictionary already. The structure of a query in GLADE is break down into following:

DISTINCT
Here is the tree constructed for this example:

Query Optimization
Query optimizer is the heart of the query planner which generates the optimal join plan to be eventually compiled and executed. Before we get into the optimizer, we need to understand the relational algebra operators, scan, select and join.
The most basic relational algebra operator is a SCAN operator, which can read the contents of an entire relation, say R. In our case, the whole relation is stored arbitrarily in the memory and it can be in any order, so in order to respond to any user query, we have there are more than one relations in a query, then there is a JOIN operator corresponding to a join between two relations upon a certain attribute. This information can be found in the WHERE clause of the query too.
Other than these 3 operators, there are more operators which we will discuss more in detail in the next section. The main goal of query optimizer is to determine a realistic efficient join strategy of the operators for executing the query. There are 2 forms of query optimization:  Rule Based Optimization  Cost Based Optimization

Rule Based Optimization
Rule Based or Heuristic optimization technique comprise of generating the optimal join plan based on certain heuristic rules. The optimality of the join order is defined by the efficiency of the heuristic function. This method is beyond the scope of this paper since we worked on cost based query optimization in GLADE for generation of query plans which is explained below.

Cost Based Optimization Algorithm
On the other hand in Cost Based Optimization (CBO), each operator is assigned a cost which be any statistics collected from the database or any hardware parameters. We used the cardinality of each table to define the cost of the operator. This cardinality is determined using Flajolet-Martin algorithm (the detail of which is beyond the scope of this paper). At a bottom level, when defining the costs to each SCAN/SELECT operator, no optimization is required. Whereas at a higher level when we have multiple JOIN operators, we need to apply cost based optimization to get optimal join plans. This is the technique we used in our project and will be dicussed in the rest of the paper. The algorithms we used for CBO are defined under.

Algorithm
The dynamic program for a query using CBO algorithm is:  // This algorithm generates the next permutation lexicographically // provided a given permutation.

Example Explanation
In order to understand the algorithm, consider the same example we saw in the previous section: SELECT DISTINCT c_name, c_address, c_acctbal FROM region, nation, customer, orders WHERE o_custkey = c_custkey AND c_nationkey = n_nationkey AND n_regionkey = r_regionkey AND r_regionkey < 5 For simplicity, we will use the following

SCAN
In the preprocessing stage of the algorithm, the first step is to initialize the data structure. This is the implementation of a SCAN operator, which scans tuples from each

Push-down Selection
The next step is to implement a SELECT operator, if any. In other words we need to update the size of each relation based on any selectivity in the query. This is called push down selection. Push down selections basically help in reducing the size of a relation and is an efficient approach in query optimization which pushes the selections down in the tree as far as we can. This is one of the most powerful tool of query optimizer since we apply the selections before the JOIN operator (that's the furthest it can be pushed down). By doing so guarantees that when the JOIN operator is applied, we don't get an inundation of tuples, hence reducing the size of the relation by a large factor at an early stage just before applying a giant operator (JOIN).
In order to estimate the size reduced by a SELECTregion operator, there are following possible cases, when: i. An attribute is equated to a constant using equality operator, in which case the size is reduced by a factor of total number of distinct elements for that attribute.
= If T(R) represents size of a relation R, and if we assume that we had the case r_regionkey = 5 instead in the example above, then size after selectivity would be given by: where r_regionkey = 5 is the selectivity on the attribute and V(X, Y) shows the number of distinct elements in relation X over attribute Y.
ii. An attribute is compared to a constant using greater or less than operator.
[5] and [6] explains how more problematic it gets when the selection involves comparison, just as in case of this example. Most of the databases stores data in columnar format and the data follows a highly skewed distribution, for example Zipfian Distribution or Normal Distribution. On average, in every comparison operator, we can assume that half of tuples can satisfy the comparison operator. So T(R)/2 would be a good estimate for for the relation. But this is not a good heuristic in every scenario.
Mostly, more than half of tuples lie below or above the given constant just as in the case of negatively skewed or positively skewed distributions. So a better heuristic would be to estimate that the selectivity would return somewhere around one third of the total tuples and not half. In case of our example, the size of the selectivity would be given by: The cost would, however, remain zero, since no relations are joined yet. So in the case of our example, after applying push-down selections, we get the following output: iii. An attribute is not equal to a constant. This is rather a very rare case and is very rarely used in the queries. A selection of type r_regionkey ≠ 5 would essentially return almost the same amount of tuples. Hence we estimate in this case as: Alternatively, we can also use the fact that we have one tuple less than the tuple we are comparing the relation with, so in that case we will have: which is slightly less than the total number of tuples, but in the case of extremely large database, this would not matter much. So we estimate that in the case of inequality, the selectivity factor is 1.

JOIN
The next step in the algorithm is to make pairs of all the relations.  Preserving attributes: Consider a third attribute P which is not a join attribute and which is present is R but not in S and we are to join R and S. Then the attribute P will not loose its values after the join is encountered. In other words: Hence which says that the estimated number of tuples after a JOIN is applied between two relations/tables is equal to the Cartesian product of the number of tuples from each relation (after applying push down selections) times the probability that each such pair shares the same attribute. The join order of this pair is going to be 01 and the cost of this pair is still zero. This is because of the fact that if we were to stop the algorithm at the first stage of the JOIN, then that can be the case only when there are only 2 tables to be joined. In that case, the algorithm will only generate one pair and that one pair is going to be the optimal join order for that query. So we do not worry about cost at this stage. On the other hand, if the algorithm generates more than one pair of joins, then we have more than 2 tables, so the initial join cost for the individual pairs does not matter. It is the cost of the next level of JOIN with more than 2 tables involved.
Following the same pattern and generating all the pairings, we would get the following pairs: According to the algorithm: In the case of 012, the algorithm will generate the permutations "012, 021, 102, 120, 201, 210". Each single permutation is associated with a unique cost calculated by the algorithm.

Greediness of the Algorithm:
The approach the algorithm aplies for finding the optimal order at every level is greedy because we consider one decision at one time about the order of joins and never backtrack or consider altering the decision we already made. The greediness is based on the fact that we need to keep the statespace as small as possible.
Hence we keep discarding join orders with higher cost and only consider the one with the least cost and move to the next level.
Consider a sub-string 012. In the first step of the first iteration, the algorithm will first pick 0 as a left node and 12 as the right node from the list of previously observed nodes, and calculate a cost of joining 0 with 12. Then in the next step, it will pick up 01 as a left node and 2 as a right node and again calculate the cost for the order 012. The process repeats for all the permutations for 012 and in the end the cost of which ever join order is least will be stored in the map along with its respective JOIN size and along with the JOIN order. The JOIN order is calculated using parenthesis, which indicates a JOIN, for example, The structure of JOIN node in the form of tree looks like: The final join order containing all tables is guaranteed to have the least join cost.
As a rule of thumb, any relation with fewer number of tuples becomes the right node in the tree. The final join order tree for this query, represented by ( (01)2)3 is shown below:

Complexity
The time complexity of the whole CBO algorithm described in 2.1.1.3 is solely determined by the complexity of the lexicographical order algorithm. The worst case time complexity of lexicographical algorithm is ( 2 * !), where x is the size of the string array.
For total of n number of relations/tables to be scaned, where n > 2, the overall time complexity of the algorithm turns out to be:

Query Compilation
After the initial optimal join order tree is generated by the Query Optimizer, the next step in query planning is to constrct a complete query execution tree by implementing the rest of relational algebra operators in the query (if any). The first step in that is to generate the execution tree following the join order created by the optimizer.
A single execution node in our project consists of a left pointer to the left node, a right pointer to the right node, a parent pointer to the parent node and the name of the node (SCAN, JOIN etc). A dynamic program of the algorithm is given below: If we consider the same example as we considered in the last section, the algorithm generates the the following execution tree:

Simple Queries
In case of a simple SELECT-FROM-WHERE queries, there are two cases. We can either have just a projection or finding distinct number of elements in the query.

PROJECT:
The PROJECT operator is performed at the top of the query execution tree. It performs the projection on each tuple coming out of the execution tree based on the attribute in the SELECT clause of the query. So every simple query has a PROJECT at the top of the tree depending on how many attributes we have in the SELECT clause. The way how tuples are projected depends on the algorithm we use for joining the tables.
In case of our sample example, there are 3 attribute, c_name, c_address, c_acctbal.

Aggregate Queries
Queries involving an aggregate function are more complicated than a simple query.
There can be many user defined aggregate functions (UDAF) depending upon the user need. In GLADE, we call these UDAF as GLA and they are discussed in Chapter 4. For the testing purpose, we only considered 2 default aggregate functions, which will be The way how GROUP BY works is that it creats groups based on the attribute in the GROUP BY clause and then perform the aggregate function on each group based on the attribute in the SUM clause (the aggregate function can be a sum, count, min or max from the grouping attribute, but we are only considering 'sum' for our testing purposes). In case of this example, it will keep a running sum of c_acctbal and create groups according the c_name. A complete query execution tree for this query will look like: processing is to be done at each node at the tuple level. They are explained below in detail.

Graph File
For generation of graph and waypoint files, we have only worked with simple SELECT-FROM-WHERE queries. Aggregate queries are left for future work. Consider the simple version of the same query we had discussed in the previous section: SELECT c_name, c_address, c_acctbal FROM region, nation, customer, orders WHERE o_custkey = c_custkey AND c_nationkey = n_nationkey AND n_regionkey = r_regionkey AND r_regionkey < 5 The graph file generated for this query is shown below. We will learn in the next chapter that GLADE consists of 2 main type of nodes, a coordinator node and a worker node. The job of coordinator is to assign and define worker nodes which works on tuple level to join data according to the query execution plan. The graph file indicates that there are 4 tables to be scanned and we need 5 worker nodes for this. All the tables to be scanned are at leaf nodes and the 5 worker nodes are the intermediate node, out of which one is going to be the root node which will pass the data back to coordinator, which in turn returns it to the user. It defines the links between any nodes in the same way as it was defined in the execution tree we saw in the previous chapter. The PRINT node is the root node and always stays at the top, whose job is to terminate the process after final tuples are merged and then returns the results back to the user. How each of the node works and how the code is executed on each node is explained in the next section.

Waypoint File
The waypoint generated for the same query is shown below. At a high level, how this works is simple. All the threads are initialized using the Init routine (we will discuss these routines in detail in next chapter). The table scaners tells us which attributes we will be looking for in each table. Once everything is initialized, the chunks start to accumulate. This is done in the Accumulate routine. Once each worker is done accumulating chunks and its job is done, it passes the data to its parent node. At this point, two cases can happen. If this worker is a leaf node, its only job is to serialize the data and send to its parent node. If its an internal node, it first receives the data coming from the underlying nodes, deserializes the data, merge the data with the data it contains (this is done in the Merge routine) and finally serializes the data and pass it to its parent node.
During merge phase, the join waypoints have the information about which attributes from the left and right side will be arriving, which attributes from this node will we use to join and eventually which attributes we need to prune and which attributes we need to pass to the parent node. In the end, when all the merging is finalized, the PRINT node is executed which performs any final merging and then terminate the process by calling the Terminate routine and passes the results back to the user.

GLADE Architecture
GLADE is short for Generalized Linear Aggregate (GLA) Distributed Engine, which is a scalable and distributed system for analyzing big data. This chapter put some light on the GLADE [7], [8] architecture in general and how query execution is implemented in GLADE.

Architecture
GLADE is scalable distributed system for the execution of analytical data by providing an engine to execute user defined aggregate functions at multiple levels inside a single node. The system is responsible for generating the execution tree and moving data within the network from storage to client. The data resides in the memory in a columnoriented format and the storage system itself is a relational execution engine which is derived from DataPath [2]. DataPath works as a shared-memory single node processing system, while GLADE on the other hand has a shared-nothing cluster architecture and is a multi-node distributed system. The architecture of GLADE is shown below. GLADE has currently nine clusters, one master node and other eight as a binary tree. Every node can run multiple threads to run GLA's. GLA is executed on a thread if its available and once a GLA has finished its job, it is ready to join a pool of free GLA's.    It is the job of the user to identify in these methods that which variables need to be serialized and how to do that. The way how this works is when a worker finishes the job, it will serialize the GLA and move it to the parent node. At the same time, the deserializer works at the parent node, whose job is to receive and retrieve the GLA. These serialize and deserialize functions needed to implemented in a proper way so that the GLAs can be transferred and retrieved accordingly.

Implementation in GLADE
We have seen in Chapter 3 that how execution tree is generated and how it is

Introduction
The MQO algorithm is derived from [1] and   GLADE is derived from Datapath [2] which is a purely push based database system.

Previous Work
This means that queries do not request data, data is instead pushed automatically into the nodes for processing. It deals with analytical queries over multi terabyte data with no indexing or no tunable partitioning. The ultimate goal of [2] is data-centric query processing rather than compute-centric query processing. The flow of data should control the computation rather than the other way around.

Many-Query Join or MQJoin [3] is a novel technique for sharing of join operators
while generating plans to effectively deal with hundreds of simultaneousl queries. Their main focus is on minimizing redundant query processing by making efficient use of main memory bandwidth and multi core architechture. While most of the work is done on the impact of sharing on main-memory joins, they used the simple build-probe phased multijoin technique to achieve higher throughput and stable response times.

Multi Query Planner
MQ planner just like the single query planner discussed in Chapter 2 works on the same technique. Instead of taking a single query, it takes a Multi Query. It also consists of a query parser, optimizer and compiler. The structure of MQ planner is shown in the figure above. In order to understand how MQ planner works, we first need to take a look at the schema of a Multi Query. This is a single MQ. It starts with the keyword "MULTIQUERY", ends with "END" and inside the block, each query is separately defined starting with a distinct name of the query followed by a colon.

Boundry Conditions
Before we explain each part for MQ planner, we need to explain the limitations or bounds of the system. The MQO algorithm works under only one bound, that while we create batches of queries or Multi Queries, the following condition must satisfy: In other words there has to be atleast one query which contains all the distinct tables that are present in all other queries collectively for the same MQ.

Query Parser
In the case of MQ planner, we use the same LEX/YACC query parser but with slight modification. The structure of a single MQ in GLADE has:  A query name.
 Query data, which is the actual query. Inside query data, we have Select List, Table   List and And List for each query.
 A pointer pointing to the next query block.
The way how parser works is that it generates the parse trees in the same way as it generates for a single query, but it is being called n number of times, where n is the total number of queries in a MQ. Parser generates a linked list of parsed queries along with their names and at the same time, doing 2 other things:  Semantics Validation in the same way as done earlier.
 Generates a list of all distinct attributes and all distinct tables being used in all the queries collectively.

Multi Query Optimizer
We saw that how query optimizer works for single queries. The cost based optimization approach for generation of a JOINs is very efficient and is definite to generate an optimal join order for all the relational algebra operators with least cost. In case of a single query, we only have one exit point to the user which defines the end of a query. The results are returned to the user via that exit point. However in case of MQ, the scenario is completely different for 2 reasons. First, the query optimizer is not certain if all the queries in a MQ are coming from a single user. Second, there are more than one query to answer regardless of that fact that they are coming from one user or not. So for each query, there has to be a (different) endpoint defined so that in the execution phase, when all tuples are being collected from the database, they can exit via their respective exit points for each query in a MQ. That is why instead of a JOIN tree, we get a JOIN graph with multiple exits, where each exit corresponds to a different query.

Algorithms
Like the cost based optimization algorithm we discussed in Chapter 2, we apply the same strategy on a MQ. A modified dynamic program of CBO with greedy approach is as follows: for all the queries in MQ do // Make a pair of two tables, say T1 and T2, sort ascending T1, T2 (no need // to have entries for (T1, T2) and (T2, T1) because of commutativity. // Estimate cardinality of join using distinct values from Catalog and join // predicates. This is called selectivity. This algorithm is different from the CBO algorithm we learned in Chapter 2 in 2 aspects. First we are considering all the queries in MQ. Second we have new added details for our data structures: number of satisfied queries and the list of satisfied queries. The basic idea behind doing this is to optimize the whole process by pruning as much computation as we can. If we have a list of all the satisfied queries for every order, we need not to test the same order again for the same query.
Lets look at how the algorithm works. In the same way as we did in CBO algorithm, we run a loop over all the tables for this MQ and keep a record of the order, size of the  If there are more than one queries, we pick up the highest of them and update the order in the map. The idea behind picking up the highest is that since our ultimate goal is to generate a single join plan for all the queries. To understand this, consider the case when query A generates n tuples and query B generates m tuples after the selectivity is being performed. Now lets assume that n > m. The total number of tuples generated by the two queries all together will be n + m if they were to run indivitually. But since we are generating a single join plan, we will pick n number of tuples since we have n > m, so all m tuples will be present in n and if we pick the maximum of (n, m), we can answer both queries with a single selection, hence increasing the overall efficiency.
After performing the selectivity, we continue to follow the same CBO approach and generate a pair for each table. This is slightly different too from actualy CBO algorithm. In case of a MQ, we first pick up a pair of tables and then check that pair of tables across the whole MQ. If there is any query that has a JOIN between these 2 tables, we calculate the selectivity in exact same way as we calculated in CBO for different scenarios we discussed earlier. We keep a list of all the queries that consists of a JOIN of any two tables. At the end of this inner loop, after we calculate all the selectivities for a single pair, we pick the largest selectivity and use that to estimate the size of this JOIN.
The same idea is used as discussed above when calculating push down selections. Since we are generating a single join plan, we need to pick max( selectivity array (T1, T2)). After calculating the selectivity, we need to now check if this JOIN satisfies any query in a MQ (we will do this step every time we generated any new plan at any level). If this is true, then we need to add 1 the number of queries satisfied by the each individual plan: ( 1 , 2 ) = { 1 + 2 + 1 and do the same thing for the list of satisfied queries for this new JOIN order: and insert this new entity in the map with the new size for this JOIN.
If this is false, we don't have any JOIN of ( 1 , 2 ) in any query in the MQ. The selectivity in that case would be just 1 and the total size of that JOIN will be very expensive and will be equal to the Cartesian product of the cardinalities of individual tables.
After generating all the pairs, the next permutation algorithm is called to create a full state space for all the permutations for all the tables in the MQ. The algorithm is given below: After this algorithm is completed, the next step is to find out the best possible plan so far from a list of prospective optimal plans. At this stage, we can encounter 2 types of cases which needed to be solved separately. One case will straight generate the final graph file. The other also generates the graph file for the entire MQ but is also responsible for accepting more queries at run time and fitting them to the already existed and running JOIN plan. Before we go into them, lets look at a sample example for each case and explain the further process.

Example Explanation (Case 1)
Consider the given MQ. We will pass the query first through query parser to  // For the current unsatisfied query, we need to check 2 things: // 1. Either the best plan we found has all the tables in it, in that case // we need to add more operators only by duplicating the tables (Case 1) // 2. Either the best plan we found has less than total number of tables, // in that case we need to add more joins on top of that by joining that // with more tables which are missing (Case 2 in next section) switch (q) case 1: addMoreJoins (q, p) case 2: addMoreTables(q, p) end switch sharedOptimizedPlan ( _mq, p) We can see that Algorithm 4 picked 2 possible options which satisfy maximum number of queries. We picked the one with least cost, and the join order contains all the distinct tables in it. It could be the case (we will discuss in the next example) that the algorithm picks up the join order which will have less tables in it. We will see that case in the next section and see what are the benefits of that algorithm. We will consider the first algorithm here.
The shared optimized plan generation algorithm performs a random walk on the unsatisfied queries and picks a random numbered unsatisfied query from the pool of unsatisfied queries and apply the cases on that selected query. Since in the case of this MQ, we only are left with one unsatisfied query, so the algorithm will pick that query. The algorithm starts with generating an optimization tree for a single query. Since this query is not satisfied by the optimal join order plan, the optimal join plan for this query will most certainly not satisfy the join plan either. The next step in graph generation is the graph initiation. If this is the first time the program has entered this loop, then we have not started generating the graph yet. So the initial optimization tree is generated for the optimal join order in the exact same way as we generated in Chapter 2. For the case of our example MQ, we have the optimal join order as 0(((12)3)4) which satisfies 3 queries, Query1, 2 and 4. The only query it does not satisfy is Query3. We have Query3 as: SELECT l_discount FROM customer, orders, lineitem WHERE c_custkey = o_custkey AND o_orderkey = l_orderkey AND c_name = 'Customer#000070919' AND l_quantity > 30 AND l_discount < 0.03 We pass this query to the CBO and it generated the optimization tree for this query.
The optimal join order for this query comes out to be 0(34), which is shown by the following optimization tree: informarion about all the subnodes from that level, number of parents and information about parent nodes and if any particular node is an exit point or not. We pass this graph and the above tree for the unsatisfied query to the recursive sub tree checking routine, which checks if the small tree or any sub tree of that is another sub tree of large graph file, and if it is, find the spot where to affix it.
Recursive sub tree checking routine recursively splits the tree and check in the graph file if it is a sub tree of the graph file. In order to get a better idea about this, consider the example MQ. We have the tree as 0(34) and the graph as 0(( (12)3)4). This recursive sub tree checking routine splits 0(34) into two parts: left (0) and right (34). We go to the right first and see that 34 is not a sub tree of the graph 0(( (12)3)4 optimized plan generation) loops back again and finds out that now, total number of queries satisfied by the current plan is equal to the total number of queries. Hence the MQO algorithm terminates with the graph file shown above as the final single optimal join plan to satisfy all the queries in the MQ. This graph file is then passed on to the query compiler for further generation of graph and waypoint files needed to be executed by GLADE to start generating tuples for this MQ.

Example Explanation (Case 2)
We discussed in Shared optimized plan generation algorithm that there can be 2 cases which can arise when deciding for the best possible join order we get from Generate All Partition routine. We have already discussed Case 1 when the best join plan has all the tables included. Now consider this MQ which will generate a different case scenario. Again in the same way, we will pass the query first through query parser to generate parse trees and to perform semantics validation and to get a list of all total number of tables in it. We will go through all the steps exactly in the same way as above to find out what we get in the end and how it is different from Case 1 and how to tackle Case 2.

END
Now in this case, when selecting best plan, the algorithm picks 0(34) join order which satisfies 4 queries. This join order contains three tables only, whereas total number of tables are five. We need to add more tables on top of this join order for all the unsatisfied queries. The algorithm for that is "add more tables" routine, which is defined here:

Algorithm 6: Adding Missing Tables in Optimization Tree
Function addMoreTables ( Query q, OptimalJoinPlan p) if graph is not created then graphGenerator(p.JoinOrder) end if // Find the list of tables missing in the join order from this query. // For each table in list, insert in into a new map along with all the details // and treat the join order as a single relation, say r and insert it into the map too. // Then run the CBO algorithm on this new map and replace the final best plan with p. for all tables in q do if table is not in p then new_map.insert (table size from catalog, 0, table name, 0, { }) end if end for new_map.insert (p) CBO (new_map) new_p = new_map.find (best join plan) old_map.replace (p with new_p) exits.insert (q) return The first step in this algorithm is to generate a graph from the join order if it has not been generated yet. This will create all the exit points for all the satisfying queries at the current stage. After that, the algorithm finds all the tables that are missing from this join order, creates a new map and inserts all of those tables in the map with initial cost and sizes and any satisfied queries, if exists. The next step is to transform the current join order into a single relation or treat it as a view, where all the details are hidden underneath it. Insert that view into the new map too. Now we have a single map with single enteties and we can run our CBO algorithm on it, treating it as a simple query. The only difference will be that the starting cost of this join order in the form of a view will be the actual cost of the join order generated by MQ optimizer.
Let us follow the example to have a better picture of the algorithm. The optimal join order is 0(34) which satisfies Query 1, 3, 4 and 5. The only unsatisfied query is Query2.
Running this algorithm starting with Query2 and the join order 0(34), the algorithm creates a list of missing tables, which are (1,2). We treat 0(34) as a virtual view, we call it v with join order as 0(34) and satisfying 4 queries. The starting map will look like: The last step is to insert this exit in the list of exits as we have found another satisfying query in the graph which corresponds to another exit point in the grap. This now terminates our algorithm and the program loops back to Shared Optimized Plan Genration algorithm and then finds out that now total number of queries are equal to the plan p, hence it terminates the algorithm with final join order of the graph as (12)(0(34)) with 5 exits points, each corresponding to a single query. The graph representation of the whole process is shown below:

Query2
The biggest advantage of using our MQO algorithm is that it can tackle the incoming queries at run time from the user. Consider a scenario where a user has submitted a batch of queris and the MQO generated a single shared plan for it. In the mean time, user submits more queries from the same pool of tables as the actual MQ have. We can fix new incoming quries into the already generated plan by passing the graph file and the pool of unsatisfied new queries to MQO. If the graph does not satisfy any of the queries, Case 1 will eventually run adding more JOIN operators to fit the queries in the graph. Now consider the second case if the new incoming queries consists of some new tables than the original MQ have but the boundry conditions are satisfied. In this case, Case 2 will run adding more tables on top of the graph and still able to generate a new plan at run time.

Chapter 6 Conclusion
In this paper, we have discussed about Multi Query Optimization which is an extended version of Shared Workload Optimization [1]. The main focus of the study was to generate a single plan with maximum sharing and least join cost. The join plans were implemented in GLADE [7]. In addition, we have provided an interface to submit SQL queries into GLADE, which are converted into graph and waypoint files executable on GLADE nodes. The greedy approach of cost based query optimization is used to generate optimal join plans which are then translated into GLADE execution plans, which runs on the GLAs. User can submit a pool of queries, which are then converted into batches or Multi Queries. Each Multi Query is parsed and optimized to produce a single JOIN plan, which is then compiled and executed in GLADE to return the results to the user for a batch of queries at the same time. The biggest achievement of the algorithm is its tendency to incorporate more queries from the user at run time while running the execution plan for the previously submitted batch of queries.
The testing was performed on the master cluster of GLADE and the benchmark used was TPCH. For our testing purposes, we have considered only simple SELECT-FROM-WHERE queries for generation of GLADE plans for both single and Multi Queries and also for the generation of graph and waypoint files. For future work, the same approach can be extended for the case of aggregate queries and queries involving GLAs.