The UNION ALL set operator is useful for combining data from multiple sources. With the emergence of big data ecosystems in which data is typically stored on multiple systems, UNION ALL has become even more important. In this paper, we present optimization techniques implemented in Teradata Database for join queries with UNION ALL. Instead of spooling all branches of UNION ALL before performing join operations, we propose cost-based pushing of joins into branches. Join pushing not only addresses the prohibitive cost of spooling all branches, but also helps in exposing more efficient join methods (e.g., direct hash-based joins) which, otherwise, would not be considered by the query optimizer. The geography of relations being pushed to UNION ALL branches is also adjusted to avoid unnecessary redistributions and duplications of data. We conclude the paper with a performance study that demonstrates the impact of the proposed optimization techniques on query performance.

Benchmarking Big Data solutions has been gaining a lot of attention from research and industry. BigBench is one of the most popular benchmarks in this area which was adopted by the TPC as TPCx-BB. BigBench, however, has key shortcomings. The structured component of the data model is the same as the TPC-DS data model which is a complex snowflake-like schema. This is contrary to the simple star schema Big Data models in real life. BigBench also treats the semi-structured web-logs more or less as a structured table. In real life, web-logs are modeled as key-value pairs with unknown schema. Specific keys are captured at query time - a process referred to as late binding. In addition, eleven (out of thirty) of the BigBench queries are TPC-DS queries. These queries are complex SQL applied on the structured part of the data model which again is not typical of Big Data workloads. In this paper1, we present BigBench V2 to address the aforementioned limitations of the original BigBench. BigBench V2 is completely independent of TPC-DS with a new data model and an overhauled workload. The new data model has a simple structured data model. Web-logs are modeled as key-value pairs with a substantial and variable number of keys. BigBench V2 mandates late binding by requiring query processing to be done directly on key-value web-logs rather than a pre-parsed form of it. A new scale factor-based data generator is implemented to produce structured tables, key-value semistructured web-logs, and unstructured data. We implemented and executed BigBench V2 on Hive. Our proof of concept shows the feasibility of BigBench V2 and outlines different ways of implementing late binding.

The Unified Data Architecture (UDA) of Teradata is an inclusive multisystem data analytics solution. A key challenge for query optimization under the UDA is to find optimal plans for queries that access data on heterogeneous remote data stores. The challenge comes primarily from the lack of statistics for data stored on remote systems. In this paper, we present techniques implemented in Teradata Database for dynamically collecting statistics on data fetched from a remote system and feeding these statistics back to the query optimizer during query execution. We demonstrate the performance impact of dynamic statistics collection and feedback with experiments conducted on a system that consists of Teradata Database and a remote Hadoop server.

The importance of temporal data management is evident by the temporal features recently released in major commercial database systems. In Teradata, the temporal feature is based on the TSQL2 specification. In this paper, we present Teradata's implementation approach for temporal query processing. There are two common approaches to support temporal query processing in a database engine. One is through functional query rewrites to convert a temporal query to a semantically-equivalent non-temporal counterpart, mostly by adding time-based constraints. The other is a native support that implements temporal database operations such as scans and joins directly in the DBMS internals. These approaches have competing pros and cons. The rewrite approach is generally simpler to implement. But it adds a structural complexity to original query, which can pose a potential challenge to query optimizer and cause it to generate sub-optimal plans. A native support is expected to perform better. But it usually involves a higher cost of implementation, maintenance, and extension. We discuss why and describe how Teradata adopted the rewrite approach. In addition, we present an evaluation of our approach through a performance study conducted on a variation of the TPC-H benchmark with temporal tables and queries.

There is a tremendous interest in big data by academia, industry and a large user base. Several commercial and open source providers unleashed a variety of products to support big data storage and processing. As these products mature, there is a need to evaluate and compare the performance of these systems.

This paper introduces a new tool that recommends an optimized partitioning solution called Multi-Level Partitioned Primary Index (MLPPI) for a fact table based on the queries in the workload. The tool implements a new technique using a greedy algorithm for search space enumeration. The space is driven by predicates in the queries. This technique fits very well the Teradata MLPPI scheme, as it is based on a general framework using general expressions, ranges and case expressions for partition definitions. The cost model implemented in the tool is based on the Teradata optimizer, and it is used to prune the search space for reaching a final solution. The tool resides completely on the client, and interfaces the database through APIs as opposed to previous work that requires optimizer code extension. The APIs are used to simplify the workload queries, and to capture fact table predicates and costs necessary to make the recommendation. The predicate-driven method implemented by the tool is general, and it can be applied to any clustering or partitioning scheme based on simple field expressions or complex SQL predicates. Experimental results given a particular workload will show that the recommendation from the tool outperforms a human expert. The experiments also show that the solution is scalable both with the workload complexity and the size of the fact table.

This paper complements our previous results in the context of effectively and efficient designing Parallel Relational Data Warehouses (PRDW) over heterogeneous database clusters, which are represented by the proposal of a methodology called Fragmentation & Allocation (F& A). The main merit of F& A is that of combining the fragmentation and the allocation phases simultaneously, which are instead performed separately by traditional approaches. In this paper, we prove the practical impact and the reliability of F& A on a real-life parallel processing database system.

Recursive queries were introduced as part of ANSI SQL 99 to support processing of hierarchical data typical of air flight schedules, bill-of-materials, data cube dimension hierarchies, and ancestor-descendant information (e.g. XML data stored in relations). Recently, recursive queries have also found extensive use in web data analysis such as social network and click stream data. Teradata implemented recursive queries in V2R6 using static plans whereby a query is executed in multiple iterations, each iteration corresponding to one level of the recursion. Such a static planning strategy may not be optimal since the demographics of intermediate results from recursive iterations often vary to a great extent. Gathering feedback at each iteration could address this problem by providing size estimates to the optimizer which, in turn, can produce an execution plan for the next iteration. However, such a full feedback scheme suffers from lack of pipelining and the inability to exploit global optimizations across the different recursion iterations. In this paper, we propose adaptive optimization techniques that avoid the issues with static as well as full feedback optimization approaches. Our approach employs a mix of multi-iteration pre-planning and dynamic feedback techniques which are generally applicable to any recursive query implementation in an RDBMS. We also validated the effectiveness of our proposed techniques by conducting experiments on a prototype implementation using a real-life social network data from the FriendFeed online blogging service.

Query processing in a DBMS typically involves two distinct phases: compilation, which generates the best plan and its corresponding execution steps, and execution, which evaluates these steps against database objects. For some queries, considerable resource savings can be achieved by skipping the compilation phase when the same query was previously submitted and its plan was already cached. In a number of important applications the same query, called a Parameterized Query (PQ), is repeatedly submitted in the same basic form but with different parameter values. PQ's are extensively used in both data update (e.g. batch update programs) and data access queries. There are tradeoffs associated with caching and re-using query plans such as space utilization and maintenance cost. Besides, pre-compiled plans may be suboptimal for a particular execution due to various reasons including data skew and inability to exploit value-based query transformation like materialized view rewrite and unsatisfiable predicate elimination. We address these tradeoffs by distinguishing two types of plans for PQ's: generic and specific plans. Generic plans are pre-compiled plans that are independent of the actual parameter values. Prior to execution, parameter values are plugged in to generic plans. In specific plans, parameter values are plugged prior to the compilation phase. This paper provides a practical framework for dynamically deciding between specific and generic plans for PQ's based on a mix of rule and cost based heuristics which are implemented in the Teradata 12.0 DBMS.

The trade-offs between the required storage space and the validity of answers produced by probabilistic question-answering (PQA) systems are studies. If the correct answer to a given query is "yes" and the system, instead, issues the estimate that the query has a probability\piof being true, then the economic loss to the user can be measured by a distortion function that decreases monotonically with\pi. A system will be called elastic if a drastic memory saving may be achieved by tolerating a small level of average distortion. The main result reported is that for a large class of distortion measures (i.e., measures exceeding(1-\pi)^{\alpha}with\alpha>0), if a binary QA system (true-false answers) is inelastic then the corresponding probabilistic QA system must also be inelastic. This result implies, for example, that a PQA system that is designed to answer all binary questions on an arbitrary dataset is inelastic. Similarly a PQA system admitting singly conjunctive questions such as "Are bothxandyin the dataset?" is also inelastic.

An improved analysis for an information system is described in which the input and output alphabets consist of (equiprobable) ordered lists of m items, with two distortion criteria: 1) the fraction of item-pairs found out of order and 2) the fraction of items found in wrong positions. For the former it is shown that, asm \rightarrow \infty, the rate-distortion functionR_{1} (D)is equivalent tomG(D)with, for smallD,G(D)=\log (2/D)-2+ O(D). For the latter,R_{2} (D) = m \log m(1 - D) + m(l - D)[\log(1 - D) - 1] + o(m).

A question-answering (QA) system answers queries from a given set about data sets drawn from a given ensemble. Shannon's rate-distortion functionR(D)provides the minimum amount of memory that a QA system must employ in order to achieve an average distortion less thanD(the distortion can, for example, be the average proportion of erroneous answers produced by the system). The ability of a system to convert an amountDof distortion into a saving in memory is measured by the ratioR(D)/R(0). A system will be called elastic if this ratio goes to zero asM, the size of the data set ensemble, tends to infinity. The asymptotic bounds toR(D)are derived, giving rise to elasticity conditions which involve only general system parameters.

It has been conjectured that error-allowance could improve dramatically the performance of data processing systems. This hypothesis is tested in the framework of question-answering (QA) systems with storage requirements as a complexity measure. Shannon's rate distortion functionR(D)represents the minimum amount of memory a system must employ in order to achieve an average distortion less thanD(the distortion can be, for example, the average proportion of erroneous answers produced by the system). The ability of a system to convert an amountDof distortion into memory savings is measured by the ratioR(D)/R(O). A system will be called elastic if this ratio goes to zero as the size of the dataset ensemble goes to infinity. Asymptotic bounds toR(D)are derived giving rise to elasticity conditions invoking the structure of the distortion matrix associated with the system. The bounds established represent a marked Improvement over former results by narrowing the gap between the necessary and sufficient conditions for elasticity. Moreover, conditions are established under which the amount of computation required for testing elasticity can be substantially reduced.