Query optimization

For the SQL interface, we provide a cost-based query optimizer. The optimizer parses SQL, and decides on the best join order and parallelism for each component. It aims to minimize latency and the number of machines used, and to maximize throughput. The optimizer automatically assigns operators to components, specifies the connection between components, and assigns the parallelism for each component. The key ideas are:

• Universal producer-consumer balance (the speed balance holds among any two communicating machines) and
• Application-level batching (we programmatically set the batch sizes and we find a sweet spot between latency and throughput).

The optimizer applies various optimizations on the query plan, which includes pushing down selections and projections. For convenience, we also provide versions of the optimizer in which a user can specify manually parallelism and/or join ordering.

Implementation

We have implemented several query optimizers. Two major types are: INDEX and NAME optimizers. The INDEX ones are quite simple, and they add projection operators after query plan is fully created. The NAME ones are more sophisticated, as each component decides on its output schema. A component sends only expressions (rather than the columns), if only these expressions are used down the hierarchy. In that case, we can easily implement pushing up selections and projections. The NAME optimizers also use cardinality estimation to assign parallelism to components.

There are two INDEX optimizers:

• INDEX_SIMPLE: It generates lefty plans in the exactly the same order as specified in SQL query JOIN ON syntax. No projections except on the very last component.
• INDEX_RULE_BUSH: It generates bushy plans using heuristics.

In both cases, parallelism is generated using the position of a component in the hierarchy, and not by using cardinality information.

There are several NAME optimizers:

• NAME_MANUAL_PAR_LEFTY: Both query plan and parallelism is manually specified.
• NAME_MANUAL_COST_LEFTY: Query plan is explicitly specified, as well as total parallelism for spouts.
• NAME_RULE_LEFTY: Query plan is built such that the smallest component which can be joined is joined first. Total parallelism of sources also has to be specified.
• NAME_COST_LEFTY: Query plan is built using a Selinger-style (dynamic programming) optimization, which requires cardinality estimation. Pruning is based on minimum number of workers necessary for the same subplan. A user specifies the total parallelism of data sources.
• NAME_MANUAL_BATCHING: Query plan is optimizer for latency. Batch size for each component is set by the optimizer.

Supported features

Currently, the SQL interface recognizes ANSI SQL syntax, and it instantiates hash joins with full-history semantics.

---

---

The pre-bundled sql queries are just examples - you can write your own queries in your own schema by providing a statistics file similar to the TPC-H statistics. You can use arbitrary optimizer with any sql file, the only thing that changes is the configuration file (example is https://github.com/epfldata/squall/blob/master/test/squall/confs/local/0_01G_hyracks_ncl).

pointers to optimizers

---

\noindent\textbf{Query optimizer.} %query Squall's optimizer generates a physical plan from the logical plan. % CURRENTLY the optimizer only uses the hash joins: consisting of novel database operators. The optimizer maximizes throughput and minimizes latency and the number of machines used. It starts from the data sources and adds the operators one after another, %automatically pushing selections and projections as close as possible to the data sources. Where possible, the optimizer collocates operators to components to minimize network transfers. Further, it assigns the right parallelism to each component, such that a component is neither overloaded nor mostly idle. We refer to this as universal producer-consumer balance. % WHY WE CAN TALK ABOUT PARALLELISM without saying how we do it (part of the query optimizer) % Each plan must have component parallelism; we must say something about it; without component parallelism, it's useless to have query optimizer (wrong parallelism leads to terrible performance) % We did not say how we do it; elasticity is an option, but we don't mention elasticity, because we don't implement it % It's heuristics in the same way as the join order The optimizer uses heuristics to find an optimal join order and component parallelism.

---

Squall is mainly concerned with aggregation queries. It supports a wide range of SQL queries, including equi and non-equi joins, and it also supports some features which are outside SQL Standard:

Specifying GROUP BY (for example in an aggregation) is possible not only by column, but also as a Projection over a tuple
DISTINCT can operate on multiple fields

Squall recognizes ANSI SQL syntax. Regarding UDFs, we have YearFromDate pre-built. For the others, the source code needs to be changed.