The last decade has seen a remarkable rise in specialized database systems. Systems for transaction processing, data warehousing, time series analysis, full-text search, data lakes, in-memory caching, document storage, queuing, graph processing, and geo-replicated operational workloads are now available to developers. A belief has taken hold that a single general-purpose database is not capable of running varied workloads at a reasonable cost with strong performance, at the level of scale and concurrency people demand today. There is value in specialization, but the complexity and cost of using multiple specialized systems in a single application environment is becoming apparent. This realization is driving developers and IT decision makers to seek databases capable of powering a broader set of use cases when looking to adopt a new database. Hybrid transaction and analytical (HTAP) databases have been developed to try to tame some of this chaos.

Advances in modern hardware, such as increases in the size of main memory available on computers, have made it possible to analyze data at a much higher rate than before. In this paper, we demonstrate that there is tremendous room for improvement in the processing of analytical queries on modern commodity hardware. We introduce BIPie, an engine for query processing implementing highly efficient decoding, selection, and aggregation for analytical queries executing on a columnar storage engine in MemSQL. We demonstrate that these operations are interdependent, and must be fused and considered together to achieve very high performance. We propose and compare multiple strategies for decoding, selection and aggregation (with GROUP BY), all of which are designed to take advantage of modern CPU architectures, including SIMD. We implemented these approaches in MemSQL, a high performance hybrid transaction and analytical processing database designed for commodity hardware. We thoroughly evaluate the performance of the approach across a range of parameters, and demonstrate a two to four times speedup over previously published TPC-H Query 1 performance.

The basic architecture of SQL Server, as well as other major database systems, goes back to a time when main memories were (very) small, data lived on disk, machines had a single (slow) processor, and OLTP was the only workload that mattered. This is not an optimal design for today's environment with large main memories, plenty of cores, and where transactional and analytical processing are equally important. To adapt to these trends and take advantage of the opportunities they offer SQL Server has added support for column store indexes and in-memory tables over the last two releases. The two features are aimed at dramatically improving performance on analytical and transactional workloads, respectively. This paper gives an overview of the design of the two features and the performance improvements they provide.

Over the last two releases SQL Server has integrated two specialized engines into the core system: the Apollo column store engine for analytical workloads and the Hekaton in-memory engine for high-performance OLTP workloads. There is an increasing demand for real-time analytics, that is, for running analytical queries and reporting on the same system as transaction processing so as to have access to the freshest data. SQL Server 2016 will include enhancements to column store indexes and in-memory tables that significantly improve performance on such hybrid workloads. This paper describes four such enhancements: column store indexes on in-memory tables, making secondary column store indexes on disk-based tables updatable, allowing B-tree indexes on primary column store indexes, and further speeding up the column store scan oper ator.

Apache Hive is a widely used data warehouse system for Apache Hadoop, and has been adopted by many organizations for various big data analytics applications. Closely working with many users and organizations, we have identified several shortcomings of Hive in its file formats, query planning, and query execution, which are key factors determining the performance of Hive. In order to make Hive continuously satisfy the requests and requirements of processing increasingly high volumes data in a scalable and efficient way, we have set two goals related to storage and runtime performance in our efforts on advancing Hive. First, we aim to maximize the effective storage capacity and to accelerate data accesses to the data warehouse by updating the existing file formats. Second, we aim to significantly improve cluster resource utilization and runtime performance of Hive by developing a highly optimized query planner and a highly efficient query execution engine. In this paper, we present a community-based effort on technical advancements in Hive. Our performance evaluation shows that these advancements provide significant improvements on storage efficiency and query execution performance. This paper also shows how academic research lays a foundation for Hive to improve its daily operations.

SQL Server 2012 introduced two innovations targeted for data warehousing workloads: column store indexes and batch (vectorized) processing mode. Together they greatly improve performance of typical data warehouse queries, routinely by 10X and in some cases by a 100X or more. The main limitations of the initial version are addressed in the upcoming release. Column store indexes are updatable and can be used as the base storage for a table. The repertoire of batch mode operators has been expanded, existing operators have been improved, and query optimization has been enhanced. This paper gives an overview of SQL Server's column stores and batch processing, in particular the enhancements introduced in the upcoming release.

The SQL Server 11 release (code named Denali) introduces a new data warehouse query acceleration feature based on a new index type called a column store index. The new index type combined with new query operators processing batches of rows greatly improves data warehouse query performance: in some cases by hundreds of times and routinely a tenfold speedup for a broad range of decision support queries. Column store indexes are fully integrated with the rest of the system, including query processing and optimization. This paper gives an overview of the design and implementation of column store indexes including enhancements to query processing and query optimization to take full advantage of the new indexes. The resulting performance improvements are illustrated by a number of example queries.

Presents a structure that can be used both for trigger condition testing and view materialization in active databases, along with a study of techniques for optimizing the structure. The structure presented is known as a discrimination network. The type of discrimination network introduced and studied in this paper is a highly general type of discrimination network which we call the Gator network. The structure of several alternative Gator network optimizers is described, along with a discussion of optimizer performance, output quality and accuracy. The optimizers can choose an efficient Gator network for testing the conditions of a set of triggers or optimizing maintenance of a set of views, given information about the structure of the triggers or views, database size, predicate selectivity and update frequency distribution. The efficiency of optimized Gator networks relative to alternatives is analyzed. The results indicate that, overall, Gator networks can be optimized effectively and can give excellent performance for trigger condition testing and materialization of views.

Current database trigger systems have extremely limited scalability. This paper proposes a way to develop a truly scalable trigger system. Scalability to large numbers of triggers is achieved with a trigger cache to use the main memory effectively, and a memory-conserving selection predicate index based on the use of unique expression formats called expression signatures. A key observation is that if a very large number of triggers are created, many will have the same structure, except for the appearance of different constant values. When a trigger is created, tuples are added to special relations created for expression signatures to hold the trigger's constants. These tables can be augmented with a database index or main-memory index structure to serve as a predicate index. The design presented also uses a number of types of concurrency to achieve scalability, including token (tuple)-level, condition-level, rule action-level and data-level concurrency.

Describes the design and implementation of the Ariel DBMS and its tightly-coupled forward-chaining rule system. The query language of Ariel is a subset of POSTQUEL (the POSTGRES QUEry Language), extended with a new production-rule sublanguage. Ariel supports traditional relational database query and update operations efficiently, using a System R-like query processing strategy. In addition, the Ariel rule system is tightly coupled with query and update processing. Ariel rules can have conditions based on a mix of selections, joins, events and transitions. For testing rule conditions, Ariel makes use of a discrimination network composed of a special data structure for testing single-relation selection conditions efficiently, and a modified version of the TREAT algorithm, called A-TREAT, for testing join conditions. The key modification to TREAT (which could also be used in the Rete algorithm) is the use of virtual /spl alpha/-memory nodes which save storage since they contain only the predicate associated with the memory node instead of copies of data matching the predicate. In addition, the notions of tokens and /spl alpha/-memory nodes are generalized to support event and transition conditions. The rule-action executor in Ariel binds the data matching a rule's condition to the action of the rule at rule fire time, and executes the rule action using the query processor.

Abstract The EXODUS database toolkit, and in particular the E persistent programming language, have been used in two substantial database system implementation efforts by the authors, the Ariel database rule system and the Triton nested relation DBMS. An important advantage of using a persistent programming language for database system implementation is that it is easy to implement special‐purpose persistent objects used by the DBMS such as catalogs, rule indexes, and nested relational structures. Support for transactions built into a persistent programming language greatly reduces the effort required to implement a database system. A disadvantage observed is that it is not possible to map the type system of the DBMS to the type system of the underlying programming language while still retaining good performance for ad hoc queries. Also, software engineering difficulties arise when a persistent language makes a distinction between database types and main‐memory types.

The authors present the results of a simulation comparing the performance of the two most widely used production rule condition testing algorithms, Rete and TREAT, in the context of a database rule system. The results show that TREAT almost always outperforms Rete. TREAT requires less storage than Rete, and is less sensitive to optimization decisions than Rete. Based on these results, it is concluded that TREAT is the preferred algorithm for testing join conditions of database rules. Since Rete does outperform TREAT in some cases, this study suggests a next step which would be to develop a hybrid version of Rete and TREAT with an optimizer that would decide which strategy to use based on the rule definition and statistics about the data and update patterns.>

This paper describes testing of rule conditions and execution of rule actions in Ariel active DBMS. The Ariel rule system is tightly coupled with query and update processing. Ariel rules can have conditions based on a mix of patterns, events, and transitions. For testing rule conditions, Ariel makes use of a discrimination network composed of a special data structure for testing single-relation selection conditions efficiently, and a modified version of the TREAT algorithm, called A-TREAT, for testing join conditions. The key modification to TREAT (which could also be used in the Rete algorithm) is the use of virtual α-memory nodes which save storage since they contain only the predicate associated with the memory node instead of copies of data matching the predicate. The rule-action executor in Ariel binds the data matching a rule's condition to the action of the rule at rule fire time, and executes the rule action using the query processor.

Article Free Access Share on Experiences in DBMS implementation using an object-oriented persistent programming language and a database toolkit Authors: Eric N. Hanson Artificial Intelligence Technology Office (WL/AAA-1), Air Force Wright Laboratory, Wright-Patterson AFB, OH and Wright State University Artificial Intelligence Technology Office (WL/AAA-1), Air Force Wright Laboratory, Wright-Patterson AFB, OH and Wright State UniversityView Profile , Tina M. Harvey 7th Communications Group/DOWI, The Pentagon, Washington DC and Department of Electrical and Computer Engineering, Air Force Institute of Technology 7th Communications Group/DOWI, The Pentagon, Washington DC and Department of Electrical and Computer Engineering, Air Force Institute of TechnologyView Profile , Mark A. Roth Department of Electrical and Computer Engineering (AFIT/ENG), Air Force Institute of Technology, Wright-Patterson AFB, OH Department of Electrical and Computer Engineering (AFIT/ENG), Air Force Institute of Technology, Wright-Patterson AFB, OHView Profile Authors Info & Claims OOPSLA '91: Conference proceedings on Object-oriented programming systems, languages, and applicationsNovember 1991 Pages 314–328https://doi.org/10.1145/117954.117978Published:01 November 1991Publication History 4citation718DownloadsMetricsTotal Citations4Total Downloads718Last 12 Months19Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Forward-chaining rule systems must test each newly asserted fact against a collection of predicates to find those rules that match the fact. Expert system rule engines use a simple combination of hashing and sequential search for this matching. We introduce an algorithm for finding the matching predicates that is more efficient than the standard algorithm when the number of predicates is large. We focus on equality and inequality predicates on totally ordered domains. This algorithm is well-suited for database rule systems, where predicate-testing speed is critical. A key component of the algorithm is the interval binary search tree (IBS-tree). The IBS-tree is designed to allow efficient retrieval of all intervals (e.g. range predicates) that overlap a point, while allowing dynamic insertion and deletion of intervals. The algorithm could also be used to improve the performance of forward-chaining inference engines for large expert systems applications.

A database procedure is a collection of queries stored in the database. Several methods are possible for processing queries that retrieve the value returned by a database procedure. The conventional algorithm is to execute the queries in a procedure whenever it is accessed. A second strategy requires caching the previous value returned by the database procedure. If the cached value is valid at the time of a query, the value is returned immediately. If the cached value has been invalidated by an update, the value is recomputed, stored back into the cache, and then returned. A third strategy uses a differential view maintenance algorithm to maintain an up-to-date copy of the value returned by the procedure. This paper compares the performance of these three alternatives. The results show that which algorithm is preferred depends heavily on the database environment, particularly, the frequency of updates and the size of objects retrieved by database procedures.

The rule subsystem that is being implemented in the POSTGRES DBMS is explained. It is novel in several ways. First, it gives users the capability of defining rules as well as data. Moreover, depending on the scope of each rule defined, optimization is handled differently. This leads to good performance both when there are many rules each of small scope and when there are a few rules each of large scope. In addition, rules provide either a forward-chaining or a backward-chaining control flow, and the system chooses the control mechanism that optimizes performance whenever possible. Priority rules can be defined, allowing a user to specify rule systems that have conflicts. This use of exceptions seems necessary in many applications. Database services such as views, protection, integrity constraints, and referential integrity can be obtained simply by applying the rules system in the appropriate way. Consequently, no special-purpose code need be included in POSTGRES to handle these tasks.>

This paper explains the rules subsystem that is being implemented in the POSTGRES DBMS. It is novel in several ways. First, it gives to users the capability of defining rules as well as data to a DBMS. Moreover, depending on the scope of each rule defined, optimization is handled differently. This leads to good performance both in the case that there are many rules each of small scope and a few rules each of large scope. In addition, rules provide either a forward chaining control flow or a backward chaining one, and the system will choose the control mechanism that optimizes performance in the cases that it is possible. Furthermore, priority rules can be defined, thereby allowing a user to specify rules systems that have conflicts. This use of exceptions seems necessary in many applications. Lastly, our rule system can support an implementation of views, protection and integrity control, simply by applying the rules system in a particular way. Consequently, no special purpose code need be included to handle these tasks.

The conventional way to process commands for relational views is to use query modification to translate the commands into ones on the base relations. An alternative approach has been proposed recently, whereby materialized copies of views are kept, and incrementally updated immediately after each modification of the database. A related scheme exists, in which update of materialized views is deferred until just before data is retrieved from the view. A performance analysis is presented comparing the cost of query modification, immediate view maintenance, and deferred view maintenance. Three different models of the structure of views are given a simple selection and projection of one relation, the natural join of two relations, and an aggregate (e.g. the sum of values in a column) over a selection-projection view. The results show that the choice of the most efficient view maintenance method depends heavily on the structure of the database, the view definition, and the type of query and update activity present.

This paper suggests that more powerful database systems (DBMS) can be built by supporting database procedures as full-fledged database objects. In particular, allowing fields of a database to be a collection of queries in the query language of the system is shown to allow the natural expression of complex data relationships. Moreover, many of the features present in object-oriented systems and semantic data models can be supported by this facility. In order to implement this construct, extensions to a typical relational query language must be made, and considerable work on the execution engine of the underlying DBMS must be accomplished. This paper reports on the extensions for one particular query language and data manager and then gives performance figures for a prototype implementation. Even though the performance of the prototype is competitive with that of a conventional system, suggestions for improvement are presented.

This paper explores the use of commands in a query language as an abstract data type (ADT) in data base management systems Basically, an ADT facility allows new data types, such as polygons, lines, money, time, arrays of floating point numbers, bit vectors, etc, to supplement the built-in data types in a data base system. In this paper we demonstrate the power of adding a data type corresponding to commands in a query language We also propose three extensions to the query language QUEL to enhance its power in this augmented environment.