Prior to mid-2000s, the space of data analytics was mainly confined within the area of decision support systems . It was a long era of isolated enterprise data ware houses curating information from live data sources and of business intelligence software used to query such information. Most data sets were small enough in volume and static enough invelocity to be segregated in warehouses for analysis. Data analysis was not ad-hoc; it required pre-requisite knowledge of underlying data access patterns for the creation of specialized access methods (e.g. covering indexes, materialized views) in order to efficiently execute a set of few focused queries.

Real-time analytics on massive datasets has become a very common need in many enterprises. These applications require not only rapid data ingest, but also quick answers to analytical queries operating on the latest data. MemSQL is a distributed SQL database designed to exploit memory-optimized, scale-out architecture to enable real-time transactional and analytical workloads which are fast, highly concurrent, and extremely scalable. Many analytical queries in MemSQL's customer workloads are complex queries involving joins, aggregations, sub-queries, etc. over star and snowflake schemas, often ad-hoc or produced interactively by business intelligence tools. These queries often require latencies of seconds or less, and therefore require the optimizer to not only produce a high quality distributed execution plan, but also produce it fast enough so that optimization time does not become a bottleneck. In this paper, we describe the architecture of the MemSQL Query Optimizer and the design choices and innovations which enable it quickly produce highly efficient execution plans for complex distributed queries. We discuss how query rewrite decisions oblivious of distribution cost can lead to poor distributed execution plans, and argue that to choose high-quality plans in a distributed database, the optimizer needs to be distribution-aware in choosing join plans, applying query rewrites, and costing plans. We discuss methods to make join enumeration faster and more effective, such as a rewrite-based approach to exploit bushy joins in queries involving multiple star schemas without sacrificing optimization time. We demonstrate the effectiveness of the MemSQL optimizer over queries from the TPC-H benchmark and a real customer workload.

Network communication is the slowest component of many operators in distributed parallel databases deployed for large-scale analytics. Whereas considerable work has focused on speeding up databases on modern hardware, communication reduction has received less attention. Existing parallel DBMSs rely on algorithms designed for disks with minor modifications for networks. A more complicated algorithm may burden the CPUs, but could avoid redundant transfers of tuples across the network. We introduce track join, a novel distributed join algorithm that minimizes network traffic by generating an optimal transfer schedule for each distinct join key. Track join extends the trade-off options between CPU and network. Our evaluation based on real and synthetic data shows that track join adapts to diverse cases and degrees of locality. Considering both network traffic and execution time, even with no locality, track join outperforms hash join on the most expensive queries of real workloads.

Many workloads for analytical processing in commercial RDBMSs are dominated by snowstorm queries, which are characterized by references to multiple large fact tables and their associated smaller dimension tables. This paper describes a technique for bushy join tree optimization for snowstorm queries in Oracle database system. This technique generates bushy join trees containing subtrees that produce substantially reduced sets of rows and, therefore, their joins with other subtrees are generally much more efficient than joins in the left-deep trees. The generation of bushy join trees within an existing commercial physical optimizer requires extensive changes to the optimizer. Further, the optimizer will have to consider a large join permutation search space to generate efficient bushy join trees. The novelty of the approach is that bushy join trees can be generated outside the physical optimizer using logical query transformation that explores a considerably pruned search space. The paper describes an algorithm for generating optimal bushy join trees for snowstorm queries using an existing query transformation framework. It also presents performance results for this optimization, which show significant execution time improvements.

Lightweight computing devices are becoming ubiquitous and an increasing number of applications are being developed for these devices. Many of these applications deal with significant amounts of data and involve complex joins and aggregate operations, which necessitate a local database management system on the device. This is a challenge as these devices are constrained by limited stable storage and main memory. Hence new storage models that reduce storage costs are needed and a storage scheme should be selected based on data characteristics, nature of queries, and updates. Also, query execution plan should be chosen depending on the amount of available memory and the underlying storage scheme; memory should be optimally allocated among the database operators involved in the query. To achieve these goals, we utilize a novel storage model, ID based storage, which reduces storage costs considerably. We present an exact algorithm for allocating memory among the database operators. Because of its high complexity, we also propose a heuristic solution based on the benefit of an operator per unit memory allocation.

Computation platforms have extended to small intelligent devices like cellphones, sensors, smartcards, PDAs, etc. As new functionalities and features are being added to these devices, increasing number of applications are being developed, many of them dealing with significant amounts of data leading to the need of embedded database support on these devices [1]. The queries go beyond simple Select-Project-Join queries but still have to be locally executed on the device [4]. Most of the modern day cellphones are being equipped with increasing memory which means more data centric applications are being developed for them. Sensor networks are also proliferating and these collect data from the environment and subject them to various queries. Most of these queries need to be executed on the device itself to reduce communication costs. Applications for PDAs execute complicated join and aggregate queries on the device resident data. Thus, there is an increasing need to facilitate the execution of complex queries locally on a variety of lightweight computing devices. However, scaling down the database footprint poses challenges since these lightweight devices come with very limited computing resources. While the amount of main memory and stable storage available in such devices is relatively small, the devices are not uniformly endowed with resources. For example, the computing capability and main memory of a cellphone differs from that of a PDA. It is essential that the available resources be utilized optimally for a database system that is developed for such devices. The already limited stable storage has to accommodate the operating system as well as the database system code, which means even less storage is available to store the data. Storage Models designed for such database systems should reduce storage cost to a minimum to be able to store more data. Limited stable storage usually precludes the creation and use of any additional index structures, hence the storage models should try to incorporate some index information in the data model itself. Ideally, index structures which can speed up query processing at no additional storage cost should be maintained. Different storage models have different storage and update costs. The selection of the best storage model for a data attribute in a relation depends on the size of the relation, selectivity and length of the attribute, frequency of updates, and the nature of queries. As far as the choice of query processing techniques is concerned, RAM is perhaps the most critical resource in these devices. Existing approaches use minimum memory algorithms for every operator. This can lead to poor performance for complex queries involving several joins and aggregates. Query execution time for complex