Self-tuning Database Systems: A Systematic Literature Review of Automatic Database Schema Design and Tuning

Automated physical schema tuning in SQL databases is well-studied, and there is a large number of related articles (cf. Section 5). In contrast, research on automatic schema tuning in NoSQL databases started only in 2010, hence less research has been conducted so far (cf. Section 6). While there exist several surveys on automatic schema tuning for SQL and NoSQL databases, none of these studies provides an in-depth overview, classification, or comparison of existing approaches from multiple facets. To the best of our knowledge, our work is the first substantial effort to explore automatic schema tuning approaches in both SQL and NoSQL databases, as well as the first work to propose a taxonomy for evaluating and comparing different schema tuning solutions. This survey helps to investigate the gap between the motivations and capabilities of current solutions, and consequently to identify areas for future research.

This survey concentrates on the following four research questions:

Answering this question allows us to identify the distribution of the publications across publishers and publication types as well as periods when the topic was particularly attractive to researchers.

The purpose of this question is to identify which level of representation (conceptual, logical, and physical) is considered in the schema design process, and which schema structures or models are designed at the respective level.

This question explores the various solutions that have been presented for addressing the schema design problem, and whether the proposed methods support fully automatic schema tuning.

Presenting a classification and taxonomy reveals a comprehensive understanding of significant facets of the schema design problem and helps to position existing works in the research landscape. This also facilitates the development of new approaches.

This is the most vital stage of the process and defines data sources, search strategy, and the selection criteria for the primary publications. We used electronic indexing systems, such as IEEE, Springer, Science Direct, ACM, Citeseer, Web of Science, and Scopus to find candidates for primary studies. The search was carried out using search strings derived from the research questions and combined with Boolean operators following the guidelines of Spanos and Angelis [212]. According to [212], the determination of search keywords is an iterative procedure. It begins with trial searches using different keywords, considering an initial set of articles that is known to belong to the research field of the review. The procedure ends when the initial set of articles is found. In our case, we used the following primary keywords: “NoSQL databases”, “relational databases”, “schema design”, “modeling”, “schema tuning”, “schema configuration”. To search academic works related to the structures or models of schema design, the keywords “index”, “materialized view”, “partitioning”, “clustering”, “graph model”, “document model”, “column model”, “key-value model” were used. Furthermore, an in-depth analysis was conducted to identify more representative keywords and maximize the candidate set of primary studies. Finally, these keywords are combined using Boolean ANDs and ORs, yielding our search string shown in Figure 2.

Next, the following inclusion and exclusion criteria were applied:

To find candidates for primary studies, we use the search string shown in Figure 2 in the electronic indexing systems IEEE, Springer, Science Direct, ACM, Citeseer, Web of Science, and Scopus. For completeness, a manual search was carried out in Google Scholar with the aim of finding additional works on automatic database schema design. Our search strategy was based on finding literature published as book, book chapter, journal, conference article, thesis, or technical report in the period from 1st January 1970 to 31st December 2021. As a result, we obtained 8,275 candidates of primary studies.

This step applies the inclusion and exclusion criteria in order to filter out academic works that are not relevant to our study. We first applied the exclusion criteria EC5–EC8, and as a result 1,824 studies remained. Then, the other inclusion and exclusion criteria (EC1–EC4, IC1–IC2) were applied. Finally, 142 academic works related to SQL databases and 98 academic works related to NoSQL databases remained for a more detailed study.

In addition to the inclusion and exclusion criteria, it is important to ensure that the primary studies have a high quality. According to Kitchenham [130], the quality assessment of the primary studies is complex and depends on various factors. We adopted the following criteria for our study: (a) availability of the publication, including information on how to access them, e.g., URLs, DOIs, or databases; (b) detailed description and documentation of the presented methods and models for schema design; and (c) comprehensive presentation of the results. Based on these criteria, the academic works were subjected to thorough text-reading, leaving 114 works related to SQL databases and 72 works related to NoSQL databases for this survey. An overview of the identified primary studies is given in Table 1. The table shows the statistics with respect to publication type and year of publication. Symposia and workshop publications are considered as conferences. We can see that research on automated physical design in SQL databases covers the entire period of our study, whereas research works on schema design in NoSQL databases have appeared only starting from 2010.

In this stage, we analyze the primary studies in order to answer the research questions. For this, we extracted the following main features:

Stand-alone approaches build an external cost model outside of the DBMS for comparing alternative design configurations. Stonebraker [214] and Schkolnick [202] presented a probabilistic model that considers statistical properties of the transactions as input parameters, e.g., the probability that a particular column appears in a query. These approaches are not practical since maintaining the statistics is expensive and the required amount of storage is very high. Thus, they work in special restricted cases, but not in the general case. Hammer and Chan [102] used an exponential smoothing technique, which is a forecasting model in the derivation of parameters for the cost model. Another approach adopts rule-based expert systems [63, 80, 195]. They formalize the knowledge of human experts as rules, and use these rules to generate a good physical design configuration. [105] introduced a simple linear cost model for estimating the number of rows in a table that a query is expected to process. Similarly, [126] developed an analytical cost model to predict the impact of data correlations on the performance of secondary index look-up. The work in [234] uses an approximate mean value analysis to estimate the cost of executing a configuration with a workload. Finally, the studies in [16, 21, 24, 57, 78, 95, 120, 157, 192, 224, 225, 226] use I/O based cost models to calculate the total workload cost, which is measured in terms of number of page or block accesses, or as a weighted sum of I/O and CPU operations.

Approaches based on external cost models suffer from serious drawbacks. They cannot guarantee that the proposed storage scheme will be used to its full potential by the optimizer. Moreover, the tool becomes obsolete whenever the optimizer changes.

Instead of an external cost model, the pioneering work in [81] uses the cost model of the query optimizer, which maintains statistics about the queries’ execution cost. Such an approach has significant advantages compared to external cost models. The generated physical schemes are based on information extracted from the optimizer, and thus will be used by the optimizer to its full potential. Moreover, they remain synchronized if the optimizer evolves over time. A shortcoming of this approach is that creating statistics by traditional full scan techniques for very large databases with many columns was impractical.

The Auto-admin project initiated by Microsoft in 1997 extends a “what-if” interface to the optimizer for simulating hypothetical physical structures [46]. These structures are not materialized, instead, they are simulated inside the optimizer by adding metadata and statistical information to the system catalog. This interface allows physical design tools to stay in-sync with the optimizer and consider a large space of alternative physical designs without materializing them. Similar “what-if” interfaces were subsequently adopted by other commercial DBMSs, for instance HypoPG,¹ which allows to create hypothetical indices in PostgreSQL and see their impact on the optimizer. Large problem instances imply a very high number of what-if optimization calls, which dramatically increases the cost of physical structure tuning. To tackle this problem, several studies [38, 68, 181, 203] propose fast what-if optimization techniques, which execute fewer what-if calls and significantly reduce the cost of index tuning.

Other studies, such as [56, 58, 59], are based on a combination of an optimizer-based and a knowledge-based approach to reap the benefits of both techniques.

As pointed out in [143, 181], invoking the optimizer to estimate the cost of queries under various configurations is costly, and good configurations might be missed due to erroneous cardinality estimates. Therefore, recent research has studied the use of machine learning techniques, especially deep neural networks and reinforcement learning, to estimate cost models [26, 136, 146, 176, 179, 184, 185, 187, 197, 231]. The goal is to develop a tuning strategy that does not require prior knowledge of a cost model. Instead, the cost model is learned. Oracle’s cloud-based autonomous DBMS [176] is one notable example of augmenting an existing DBMS with machine learning agents. Instead of augmenting an existing DBMS, other works [184, 185] have looked into creating new DBMS architectures, which use different ML algorithms to predict the cost and benefit of deploying configuration components.

Early works use exact approaches based on an analytical model to find an optimal physical configuration [16, 128, 178, 202, 214]. Exact solutions find an optimal set of physical structures by considering all possible design choices. Since the physical structure selection problem is NP-complete [188], an exhaustive search strategy is impractical and not scalable. Therefore, the above approaches made many simplifying assumptions. General problems with analytical approaches include: (1) significant simplifications have to be made, and (2) if the query processing strategy or other modeled aspects of the DBMS change, the model becomes obsolete.

To tackle the complexity of exact approaches, approximate solutions have been investigated. The most widely used technique is to use heuristic search methods to prune the search space of design models and to choose a near-optimal configuration. Most of the works use heuristic solutions [21, 23, 24, 30, 56, 57, 58, 59, 63, 80, 81, 82, 102, 103, 195, 211, 217, 224, 229], greedy approaches [6, 45, 96, 97, 105, 127], evolutionary algorithms like genetic algorithms [137, 172, 191, 232], branch-and-bound algorithms [171, 186, 234], relaxation-based approaches [35, 36, 37], or hybrid approaches [233]. Other studies exploit combinatorial optimization techniques to choose an optimal set in potentially exponential time, or find an near-optimal solution along with a distance bound to the optimal solution. The works in [40, 41, 68, 126, 180, 192] adopt an Integer Linear Programming (ILP) formulation of the problem and employ a commercial ILP solver, such as branch-and-bound, Lagrangian relaxation, or column generation. In [78, 95, 119, 120], a polynomial time approximation algorithm is used to solve the index selection problem, which is formulated as a knapsack optimization problem. The work in [237] models the index and materialized view selection problem as a variant of the knapsack problem, followed by a random-swapping algorithm.

The approaches described above lack a mechanism to learn about the goodness of the recommended set of physical structures. Their quality can be improved by learning from the effects of deployed actions, e.g., adding an index. Recent advances in (deep) reinforcement learning inspired researchers to move toward learning-based approaches. For instance, [140, 197, 210] demonstrate how deep reinforcement learning can be used for index selection. The works in [26] and [179] specify a general reinforcement learning approach for automated and dynamic database indexing. Liang et al. [150] investigate how to use deep reinforcement learning for selecting materialized views and improve the performance of OLAP workloads. Yuan et al. [231] solve the view selection problem by first modeling it as an ILP problem, then modeling the ILP as a Markov Decision Process (MDP), and finally using a deep reinforcement learning technique to solve it.

The physical design problem has been studied since the early 70’s, initially focusing on the index selection problem for files [16, 128, 178, 202, 214]. These early works adopt an analytical approach, using a probabilistic cost model of the transactions, to derive an exact solution, i.e., optimal set of indices. These exact approaches suffer from performing a complete enumeration of all possible index sets. Other works use approximate solutions and deal with a limited number of physical structures instead of all possible subsets, e.g., indexes [21, 24, 30, 56, 57, 58, 59, 63, 78, 81, 82, 102, 107, 108, 120, 195, 224, 234], partitioning [103, 169, 170, 195, 234], and multi-dimensional clustering [153]. Finally, exist also some approximate solutions for materialized views or index selection, which are specifically tailored for OLAP/Data Cubes [23, 96, 97, 105, 139, 211, 217, 229, 232]. Notice that none of the above works developed physical design tools for commercial DBMSs.

The AutoAdmin project² started in 1996 at Microsoft Research with the aim at making RDBMSs self-tuning. A primary focus was automating the physical database design. In 1998, the first physical database design tool was released, called Index Tuning Wizard (ITW), which shipped with Microsoft SQL Server 7.0 and is based on techniques presented in [45]. A key feature of this tool is an extension of the query optimizer to support a “what-if” interface [46]. In the SQL Server 2,000 release, ITW was enhanced with integrated recommendations for indexes and materialized views in the context of multidimensional (OLAP) databases [7].

Horizontal and vertical partitioning are other important aspects of physical database design with significant impact on performance and manageability. Horizontal partitioning allows tables, indexes and materialized views to be partitioned into disjoint sets of rows, which are separately stored and accessed. Vertical partitioning allows a table to be partitioned into disjoint sets of columns. In [8] a scalable solution to the integrated physical design problem of indexes, materialized views, vertical and horizontal partitioning for both performance and manageability was presented. In the Microsoft SQL Server 2005, the functionality of ITW was replaced by a full-fledged application, called the Database Engine Tuning Advisor (DTA) [6]. It significantly increased the scope and usability of ITW. DTA provides integrated recommendations for indexes, indexed views, indexes on indexed views, and horizontal range partitioning. It scales to large databases and workloads using techniques, such as workload compression and reduced statistics creation. ITW and DTA employ a “candidate selection” step to identify a set of likely configurations in a cost-based manner by consulting the query optimizer.

The ITW and DTA tools assume that the DBA knows when to invoke a physical design tuning tool. In this regard, DBAs face two main challenges. First, changes in data distributions and workloads might lead to the current configuration becoming sub-optimal. Thus, DBAs must continuously invoke the tuning tool to recommend changes in the current configuration. Second, only if the current configuration is no longer optimal, it is necessary to run a tuning tool and change the configuration, since running a tuning tool causes an overhead. Therefore, the work in [36] introduced a more lightweight tool, called Alerter, which identifies when a physical design tool should be invoked. Finally, the work in [37] introduced an online index selection approach that continuously monitors changes in the workload and in the data, and modifies the physical design as needed. It was prototyped inside the Microsoft SQL Server engine.

Since an crucial requirement for a self-tuning database system is the ability to efficiently monitor the database and identify potential performance threats, the AutoAdmin project developed also a SQL Continuous Monitoring engine (SQLCM) [44]. It enables continuous monitoring inside the database system and has the capability to automatically take actions based on the monitoring.

Physical database schema tuning can be carried out in three different modes: manual, semi-automatic, and full-automatic. Manual (or offline) approaches are invoked by the DBA when expected to be necessary and recommend a physical configuration to the DBA to improve the DBMS performance. Semi-automatic techniques use the DBA in the loop by recommending a physical configuration that requires feedback from the DBA. Full-automatic approaches, known as online physical design tuning, continuously tune the configuration as the workload or database state changes without the need for any DBA intervention.

Manual Mode. Manual tools for physical design tuning in commercial database systems other than the Microsoft SQL Server are IBM DB2 Design Advisor [219, 236, 237] and the SQL Access Advisor in Oracle 10g [64]. The DB2 Design Advisor [237] recommends indexes and materialized views for a given workload. As of DB2 version 8.2 [236], the Design Advisor provides integrated recommendations for physical design features, including indexes, materialized views, partitioning, and multi-dimensional clustering. It adopts a hybrid algorithm that efficiently searches through the large solution space while taking into consideration the interactions of related features. This approach allows to break the implementation of different features into smaller components. The implementation details can be found in [151, 191, 237]. For instance, a knapsack algorithm followed by a random-swapping phase is proposed for index and materialized view selection [219, 237], and a rank-based search and a genetic algorithm were proposed for partitioning [191]. The SQL Access Advisor in Oracle 10g [64] recommends indexes and materialized views for a given workload. It receives as input a workload and a set of candidates (created on a per-query basis by the Automatic Tuning Optimizer) and outputs a recommendation for the overall workload. In Oracle 11g [28, 138], the advisor was extended to make recommendations also for partitioning.

The index selection approach in [203] recursively applies a greedy selection that effectively accounts for index interactions. The approach decreases the number of “what-if” optimizer calls by employing caching and workload information, and thus can scales for large problems.

The work in [192] presents a physical design tool for C-store [215], a clustered column-store RDBMS. This tool builds an optimal candidate set consisting of materialized views and clustering indexes for OLAP workloads. The work in [233] provides a hybrid evolutionary approach, combining the advantages of heuristic and evolutionary algorithms to select materialized views in a data warehouse, whereas [98] presents a simple greedy heuristic for selecting views. The cost model in these studies is calculated in terms of query processing and view maintenance.

In [127], the authors investigate how to effectively integrate index compression techniques into physical database design. The presented index selection approach considers compressed alternatives for each index based on a given memory budget. The optimizer’s cost model is extended to handle compressed indexes in the configurations. The work in [193] jointly optimizes different configuration decisions (compression, index, and ordering) using linear programming to determine the best runtime performance for a given workload and memory budget.

Finally, there exist a number of state-of-the-art offline approaches for suggesting vertical and horizontal partitions [124, 171, 186] and multidimensional hierarchical Clustering of OLAP data [159].

Semi-automatic or Full-automatic Mode. The work in [205] proposes a semi-automatic index tuning technique, which adapts its recommendations to changes in the workload and feedback from the DBA. Fully-automatic approaches become popular in the form of database cracking [113, 114], continuous monitor-and-tune approaches [13, 14, 37, 88, 111, 112, 122, 147, 198, 204, 227], and machine learning-based approaches [26, 76, 135, 136, 146, 150, 179, 184, 185, 187, 210, 231]. Database cracking is an online index selection approach, where indexes are created and continuously refined as part of query processing. In this approach, each query is interpreted not only as a request for a particular result set, but also as an advice to crack the physical database store into smaller pieces. There is a large body of work on extending and improving database cracking [90, 91, 92, 93, 100, 110, 115, 189, 206, 207]. A comparative study of different cracking techniques is presented in [208].

Continuous monitor-and-tune approaches [13, 14, 37, 88, 111, 112, 122, 147, 198, 204, 227] monitor changes in the workload in a continuous way, collect statistics and make online decisions automatically to perform changes to the physical design as needed. The work in [204] and [198] share similar goals as [37], but differ in the design. The authors of [198] have developed the earliest online index selection solution, called the QUIET framework and implemented on top of DB2. It aims at creating indexes automatically at runtime, while considering a DBA-defined space budget. In comparison to [37], this approach requires multiple additional calls to the optimizer to obtain information about candidate indexes. The work in [204] developed a self-tuning framework, called COLT, that continuously monitors the workload of a database system and enriches the existing physical design with a set of effective indexes. COLT has been implemented inside PostgreSQL, extending the optimizer with a “what-if” interface. In contrast to [37], it is not fully integrated in the query optimizer. The authors of [227] have developed an autonomic tuning expert for IBM DB2 and evaluated it under changing workloads and system states. The approach stores DBA experts’ tuning knowledge for the autonomic management process.

A online DBMS-independent framework for automatic index tuning was introduced in [14], which can be used with different DBMSs. It is based on heuristics that run continuously to guide decisions on the current physical database configuration in order to react to workload changes. In [13], a model-driven approach was developed to support tuning decisions by different heuristics. A instantiation of the model is the database self-tuning task for physical design tuning, including indexes and materialized views. In this model, a database tuning requester can be a human agent, such as a DBA, or a computational agent, such as a monitoring tool. The work in [147] employs an online approach to monitor database queries. It collects statistical information in order to detect performance trends and to make decisions for automatic re-partitioning. In [111, 112], the authors presented a method for automatically deriving database configurations by evaluating an objective functions. The proposed self-management logic provides a continuous monitoring and light-weight analysis of the workload and database state, compares it against goals (e.g., response times, throughput, CPU or disk space usages, availability, and operation costs) defined by a DBA, and starts a reconfiguration analysis when there is a risk of missing the goals. Multi-objective optimization techniques are used to automatically derive database configurations that meet these goals. Additionally, this approach stores an explicit workload model to identify patterns in the workload that allow to predict workload shifts. Finally, an online technique to recommend indexes for high-dimensional databases was introduced in [88]. This approach uses a control feedback to monitor the query workload and to detect when the query pattern changes and corresponding adjustments to the index set are recommended.

There are numerous studies [26, 76, 135, 136, 140, 146, 150, 179, 184, 185, 187, 210, 231] that have leveraged machine learning techniques for automated tuning of DBMSs. They extract the state and performance metrics from a DBMS and use this data to train models for choosing tuning features that will benefit the most. Some studies [135, 136, 146, 184, 185] propose autonomous (self-managing) database systems, which leverage machine learning techniques for workload modeling and forecasting, fully automated physical design, and other configuration components. Thus, they do not focus on one particular configuration aspect and take a holistic view, which considers combinations of various configuration components.

The authors of [184] present the first self-driving RDBMS, called Peloton (later NoisePage [185]), which automatically configures and optimizes various aspects (e.g., indexes, materialized views, data partitioning, knobs) as the database and the workload evolve over time. It supports hybrid workloads, OLTP and OLAP, and predicts future workloads based on past arrival rates [156] so that the system can adapt itself. NoisePage uses behavior models generated by different ML algorithms to predict the cost and benefit of deploying configuration components. Based on these cost/benefit estimates, NoisePage adopts tree-based optimization methods (e.g., Monte Carlo tree search (MCTS) or RL methods) to select actions that improve the system’s target objective function.

The authors in [135, 136] proposed a framework for self-driving database systems that automatically tune various configuration features, such as physical database design, knob configurations, or hardware resources. The framework is able to predict future workloads and to deliver configurations based on these predictions. They also propose a linear programming (LP) model to tune the multiple dependent features in a recursive way. Additionally, an approach for adaptive cost estimation is suggested, which can be obtained by applying linear regressions, gradient boosting regressors, or neural networks. The proposed framework is integrated into the research DBMS Hyrise [74], which is a relational columnar store for transactional and analytical transaction processing (HTAP).

In [146], the authors built an autonomous database framework and integrated ML techniques into the open-source database system openGauss [175]. They proposed learning-based models for developing learned optimizers and advisors, such as learned cost estimation, learned knob tuning, learned database diagnosis, and a learned view/index advisor. For the latter, a deep reinforcement learning model to select high-quality indexes and materialized views is proposed.

Other researchers have developed learning approaches to solve the problem of automatically indexing a database [26, 140, 179, 187, 197, 210], materialized view selection [150, 231], and partitioning [76] using reinforcement learning or deep reinforcement learning.

Finally, we would like to mention some autonomous features in commercial databases, including Oracle Autonomous database [176], Alibaba self-driving database [12, 145], and fully-automated indexing in Microsoft Azure SQL Database [67].

Forward Engineering (or schema-first) approaches start from a conceptual model or a relational database and transform it into a NoSQL data model. In this process, workloads may be considered to optimize the proposed schema. Thus, we can distinguish two categories of approaches: workload-agnostic and workload-driven approaches.

Workload-agnostic Approaches. These approaches define a set of conversion rules that transform a relational or conceptual schema into a NoSQL schema. They largely ignore workloads as well as the evaluation of alternative designs. In this context, the authors of [1] provide a set of mapping rules that transform a UML conceptual model into different NoSQL physical models (column, document or graph). They provide a generic intermediate logical model that describes data according to the features of NoSQL models and support a sufficient degree of independence, so as to enable the mapping to several platforms. The work in [65] presents a set of mappings from conceptual schemas expressed in UML/OCL into logical schemas (data store specific models) and integrate them in a unique multi-data store design method. This approach embeds three transformations, each specific to a data store: UmlToSQL, UmlToGraphDB, and UmlToDocumentDB. Some authors propose transformations for column store databases [144, 149] and document databases [104, 174]. For the mapping of conceptual schemas to graph databases, the works in [5, 11, 66] have transformed a UML model, relational and RDF schemas, and extended ER model to a graph model. Additionally, data modeling for document-oriented and graph-based databases have been investigated in [125]. The study in [15] has investigated the process of transforming a relational database schema into various NoSQL database schemas, namely document-based, column-based, and graph-based.

The studies in [25, 89] proposed a modeling language for data modeling in hybrid polystores, which involve a combination of relational and NoSQL databases. The language provides mapping rules between the conceptual schema of a polystore according to the Entity-Relationship model and the underlying physical schemas.

Finally, it is worth mentioning contributions related to modeling and implementing data warehouses in NoSQL databases [10, 51, 52, 53, 54, 72, 73, 209, 230]. These approaches define a set of mapping rules that transform a multidimensional conceptual data model into NoSQL models.

Workload-driven Approaches. Workload-driven schema design considers the workload when optimizing the schema, i.e., the schema design is based on the analysis of the workload queries. The workload-driven approach is suitable when the queries and data structure are known beforehand. Approaches in this area often rely on schema denormalization and data redundancy to optimize the schema and improve query performance.

The works in [29, 218] use denormalization to optimize the database schema for read queries. By analyzing read queries, [218] employs foreign key constraints in the conceptual schema to generate all possible denormalized relations for each query, whereas [29] uses secondary indexes to identify all feasible table variants that could answer each read query via a single read request. A cost function is used to select the schema with the minimal cost.

Rafik et al. [177] present a set of conversion rules to support the schema conversion of an existing relational database into HBase. To obtain a proper design, the conversion rules depend on an analysis of the most frequent access patterns and of the heavy queries that are frequently run.

Mior [163] developed an approach, called NoSE, for automated schema generation in extensible record stores. This cost-based approach uses a novel binary integer programming (BIP) formulation to map a conceptual model to a NoSQL schema. NoSE receives a conceptual model and workload as input, and then formulates the schema optimization problem as a BIP, which selects a set of column families that minimize the execution cost of the entire workload. This approach has been implemented for the Cassandra extensible record store [164].

The works in [50] and [71] consider workload information to select an optimized logical schema for read queries by reducing the number of accesses to the database. In [50], a big data modeling tool, called KDM, is presented, which automates Cassandra database schema design for queries defined in an application workflow. It starts with a query-driven mapping from a conceptual data model to a logical data model and ends with a logical-to-physical mapping. In [71], the researchers defined mapping rules that guide a workload-driven transition from a conceptual schema to a logical schema and its physical implementation for NoSQL document stores.

Imam et al. [118] presented a long list of NoSQL modeling guidelines for the logical and physical design of document-store databases with the aim at facilitating the data modeling process and improving developers’ modeling skills. In another work [117], the authors presented a schema suggestion model for NoSQL document stores. The model suggests a schema based on system requirements and parameters, such as list of entities and Create, Read, Update and Delete (CRUD) statements. This model aims at balancing significant system requirements, such as consistency, availability, and scalability. An extension of the model, called DSP model [116], focuses on performance and describes how the model supports query complexities. For this, a binary integer formulation was used to map the conceptual data model to a database schema.

The work in [70] presents a framework for the automatic design of NoSQL databases (column family model and document model), which takes a conceptual data model and access queries as inputs. It includes the definition of a set of rules to transform the conceptual data model first to a logical model and then to the final implementation in the target NoSQL database.

Physical design guidelines for graph databases with the aim at improving the query execution time are presented in [123]. In this work, indexes, path materialization, and query rewriting are considered as guidelines for the physical design in Neo4j.

CONST loop [167] is the first online NoSQL schema design approach. It adopts a self-tuning feedback control loop for continuous workload monitoring and analysis, as well as optimized schema design in wide column stores, and has been implemented in Apache Cassandra. This loop describes a design pattern for the self-tuning feature, which automatically modify the current schema design reacting to changes in the application’s workload. Details of the architecture of the monitor and analyze phases are described in [166].

Noguera and Lucrédio [173] attempted to implement a schema-independent way to specify and execute NoSQL queries, which means the developer is not free to change the data schema in which the data is stored without prior adaptation of the data access code (queries). This work employed a generative approach to simplify the writing of queries independently from the actual data structure in which the data is stored. It uses different mapping information between the ER model and the NoSQL document-oriented databases, and automatically transforms ER-based queries into actual native code for a specific NoSQL database. It generates a more flexible schema and allows changes to be made in a NoSQL database schema without causing changes in all related queries. But it requires effort beforehand to correctly create the mapping information.

Several metamodels have been proposed to represent multi-model NoSQL schemas. SOS [19] is a metamodel to represent schemas for aggregate-based NoSQL stores (i.e., key/value, column, and document), supporting application development by hiding the specific details of the various databases systems. Later, SOS evolved to the NoSQL Abstract Data Model (NoAM) [18], which is an intermediate system-independent data model to support a design methodology for aggregate-based NoSQL databases. The design methodology uses aggregate design (a group of related objects), which is mainly driven by data access patterns of the application, as well as by scalability and consistency needs. Mali et al. [158] describe an optimization process to generate a platform-independent, generic logical model used to generate five target models (relational & NoSQL models). They apply a transformation heuristic to reduce the search space of the model generation. This work did not address mapping rules for transforming the generic logical model to physical models. In another work, Li and Chen [148] proposed a query-oriented data modeling approach, called QODM, to generate a platform-independent data model for NoSQL databases based on query requirements, which can be transformed to a specific NoSQL database. The QODM approach includes key-value stores, document stores, and extensible record stores; graph databases are not supported.

The research efforts in [31, 42, 109, 199, 228] introduce methods to design NoSQL schemas with the goal of enhancing the performance of OLAP queries. For document warehouses (DocW), Messaoud et al. [161, 162] propose an approach for transforming a document warehouse model into a column-oriented or document-oriented NoSQL model.

Most NoSQL data stores are schema-less, that is, data can be stored without a previous formal definition of its structure. The flexibility of these data models allows the user to easily incorporate new data without making changes in the data model (evolution of data over time). However, to express queries there is still a need to know how data is structured. Therefore, for processing data without explicit schema information, reverse engineering can be used, which allows to generate the data model from an existing database. This is important to facilitate the understanding, the documentation, and the schema visualization of the data.

In [131] a schema extraction approach has been introduced that generates a JSON schema from collections of JSON documents. This approach is based on an earlier approach for XML schema extraction from XML documents [165]. Similarly, [20, 121, 221] deal with the problem of inferring schemas from JSON sources by using hierarchical data structures to summarize the structural information of JSON documents. Some studies [2, 3, 4, 32, 33, 55, 61, 196] present an MDE-based reverse engineering approach for extracting the data model from schema-less NoSQL databases. Model-Driven Engineering (MDE) techniques provide a formal framework for automatic model transformation, i.e., mapping one input model into an output model. This transformation process defines a set of transformation rules to be applied between source and target models.

Frozza et al. [84] present an approach for extract a schema from a JSON or Extended JSON document collection stored in a MongoDB database. This work combines hierarchical structures and MDE-based processes. Additionally, aggregation operations are considered to improve the performance of the schema extraction task. The authors present also a method for schema extraction in JSON document schema format from graph [85] and columnar models [83].

Other works, such as [106, 141], present property graph schema inference methods from graph databases that are based on the property graph data model that is used in Neo4j. Some works focus only on extracting the physical or logical model from the data stored in NoSQL databases [4, 20, 33, 83, 84, 85, 106, 131, 141, 196, 221], while others address the extraction of the conceptual model from the NoSQL physical schema [2, 3, 32, 55] or the stored data [61, 121].

Regarding multi-model databases, a Tensor-based Data Model (TDM) [142] was defined to support logical data independence in polystore systems. TDM subsumes various data models (relational, NoSQL, etc.) and proposes a set of operators for defining views (virtual or materialized views) that can dynamically transform data into appropriate data structures. Reverse mappings from relational, key/value, wide-column, and graph models to TDM were presented.

There exist also some approaches for directly executing OLAP queries on NoSQL data sources [60, 86, 101]. The works in [60] and [86] focus on extracting multidimensional schemas (facts and hierarchies) from document stores. The work in [101] proposes a pay-as-you-go approach, which enables OLAP queries against a polystore supporting relational, document, and column data models by hiding heterogeneity behind a dataspace layer.

Roundtrip engineering (RTE) represents one aspect of model-driven engineering (MDE) techniques and combines forward and reverse engineering. Since code and model are interrelated, changing code will change the model and vice versa. Akoka and Comyn-Wattiau [9] present a framework describing a roundtrip engineering process for graph databases, which was the first RTE approach of NoSQL databases. As pointed out in this work, roundtrip engineering allows a bi-transformation between the model and the source code. The authors of [168] first present the process of extracting the physical schema from the data stored in MongoDB, which captures characteristics, such as existing indexes, data organization, and statistical features, and then propose a bidirectional transformation between logical and physical models.

Candel et al. [39] propose a logical unified metamodel, termed U-Schema, which represents logical schemas for a multi-model database supporting relational and the most popular NoSQL systems (columnar, document, key–value, and graph). The U-Schema metamodel has been defined with the Ecore metamodeling language of the Eclipse Modeling Framework (EMF) [213]. A MapReduce operation is performed on the database to infer the logical data model for each NoSQL paradigm. Next, a round-trip strategy is defined, consisting of forward mapping to a mapping from the inferred logical schema to U-Schema, and reverse mapping to a mapping in the opposite direction.

Static tuning approaches recommend an efficient schema for a given workload to the DBA. While they are helpful to decrease the time required to tune a database, they leave several important decisions to DBAs, such as the continuous monitoring of the database in order to detect changes and re-tune the schema design. Static tuning approaches are designed to be invoked manually when expected to be necessary. Thus, they require a lot of human intervention and do not meet the requirements of an autonomic database. Besides, a shortcoming of these approaches is that they can only be used when the workload of the system is known and stable. Most studies for SQL [6, 45, 64, 98, 192, 203, 233, 236] and NoSQL [29, 50, 70, 71, 117, 164, 177, 218] databases generally take an offline approach to the schema design problem.

In dynamic environments where workloads are unknown, unstable, and change over time, offline schema tuning is far from ideal. Instead, dynamic approaches are able to track changes in both the workload and the database state and perform decisions online to reconfigure the current schema design as needed. Such approaches provide fully automated solutions that meet the requirements of an autonomic database system and reduce the maintenance overhead for DBAs. The topic of the on-line physical tuning of SQL databases raised to popularity in the form of database cracking [113, 114], continuous monitor-and-tune approaches [13, 14, 37, 88, 111, 112, 122, 147, 198, 204, 227], and machine learning-based approaches [26, 76, 135, 136, 146, 150, 179, 184, 185, 187, 210, 231]. For NoSQL databases, the CONST [167] approach is the only online NoSQL schema design approach, which is a self-tuning feedback control loop for continuous workload monitoring, analysis and optimized schema design in wide column stores.

To be fully autonomic, a DBMS must be able to predict future workloads based on historical data in order to select proper configurations in a timely manner. Since database systems are often exposed to unanticipated events, it is difficult to anticipate future workloads. Therefore, robustness is a crucial component for self-tuning DBMSs, and it comes with facets. The first facet of robustness regards the tuning decisions in the presence of reconfiguration costs. It might happen that a reconfiguration of the database schema produces only a minor performance improvement. To avoid such situations, the cost of the reconfiguration need to be considered in the optimization. The second facet of robustness refers to how workload changes affect the system’s performance. Robust configurations aim at providing an acceptable performance for most workload scenarios so that small changes do not have a large impact [135]. To obtain robust configurations, not only the current workload but also information about the distribution of potential future workloads must be incorporated. Robust workload forecasting models are essential since the workload may deviate significantly from the past. Some approaches explicitly incorporate these robustness aspects [111, 135, 136, 156, 185].

Within dynamic tuning approaches, we identify two sub-facets: reactive/proactive tuning when approaches adapt to changes in the data/workload, and internal/external tuning that expresses if approaches are internal or external to a system.

Reactive/Proactive Tuning. This category specifically deals with the time point when dynamic approaches apply the tuning process. In the reactive mode, systems respond to a change when it already happened. In the proactive mode, systems predict when changes are expected to occur (e.g., predict periodic changes in the workload), and therefore they can adapt the DBS configuration beforehand. For example, a self-tuning database system chooses its configurations proactively according to the expected workload patterns in the future. For SQL databases, there are numerous dynamic tuning approaches, which are either reactive [26, 37, 113, 114, 122, 147, 150, 179, 198, 204, 231] or proactive [111, 112, 136, 184, 185]. Currently, there are no proactive tuning approaches for NoSQL databases, and only one work [167] is reactive.

Internal/External Tuning. From a different perspective, dynamic tuning can be divided into two categories with respect to the separation of the tuning mechanism and database system. For internal approaches, the schema self-tuning process is integrated as a module in the DBMS engine. A DBMS internally monitors and analyzes the workload and database state. If it discovers that the database requires changes, the tuning component proceeds to recommend schema changes for better performance. The internal approach has some notable drawbacks. For instance, the system is costly to maintain or evolve, and it is often not scalable. Some works [37, 113, 114, 136, 184, 185, 204] present a dynamic internal approach for physical schema design in SQL databases. However, there is currently no work on the dynamic internal approach for NoSQL databases.

On the other hand, works such as [26, 76, 111, 112, 150, 179, 198, 231] for SQL and [167] for NoSQL databases, employ an external self-tuning manager. These approaches are based on an external self-tuning logic, which controls the reconfiguration decisions of the DBMS. A significant advantage of the external approach is the reusability of the tuning process with respect to different systems, which can be easily customized and configured for different applications.

As mentioned in Section 5.3, all major commercial database vendors ship automated physical design tools with relational databases, e.g., DTA in Microsoft SQL Server [6], DB2 Design Advisor [236, 237], and the SQL Access Advisor in Oracle [64]. There exist also several tools for database schema design in industrial applications, such as Hackolade,⁴erwin,⁵ and ER/Studio.⁶Hackolade is a multi-platform schema design tool for NoSQL databases, which offers graphical schema design, physical data modeling, and forward and reverse engineering. Currently supported databases include Apache Cassandra, Apache HBase, and ScyllaDB in column databases; MongoDB, Couchbase, CouchDB, Elasticsearch, Google Real time Firebase, and Google Cloud Fire store in document stores; Neo4j and TinkerPop in graph databases; and DynamoDB in key-value stores. The popular relational modeling tools erwin and ER/Studio are expanding toward NoSQL stores. erwin Data Modeler now supports Apache Cassandra, MongoDB, and Couchbase as target NoSQL databases, allowing schema forward and reverse engineering. The ER/Studio tool supports schema forward and reverse engineering for MongoDB.

Offline schema tuning approaches rely on DBAs, which is expensive and cannot adapt to cloud computing platforms because of their scale and complexity. Chaudhuri et al. [48] argue that expenses for DBAs are the key factor in the total cost of ownership. These costs can be further increased by a higher complexity of schema tuning tasks caused by non-stable workloads, a lack of domain knowledge and application context [67] in cloud environments. Therefore, fully automatic schema tuning for cloud platforms is an urgent research issue [67, 145, 146, 176, 185].

In large-scale systems with thousands of queries in the workload and hundreds of tables, schema selection approaches often face specific challenges, such as solution constraints (e.g., memory budget), reconfiguration costs, and prohibitive runtimes. Some studies presented scalable and efficient approaches for such systems. For example, DTA tool [6] scales to large databases and workloads using techniques such as workload compression and reduced statistics. The methods in [38, 68, 181, 203] significantly speedup what-if optimization by decreasing the number of what-if optimizer calls. The studies in [136, 146, 185] proposed autonomous database systems using machine Learning methods that are applicable for large-scale problems. There are only a few works [18, 20, 39] that investigate scalability requirements for schema design in NoSQL databases. For instance, the works in [20, 39] use MapReduce on tackle scalability issues.

The importance of automated schema design goes beyond SQL and NoSQL databases. For instance, schema extraction from a wide variety of heterogeneous data sources is a crucial element in data lakes, as the source data needs to be described by a data model to capture its semantics. To support the “load-first, schema-later” paradigm, the assessment of data quality and cleaning large volumes of heterogeneous data sources are essential tasks in unveiling the value of big data [79]. The quality of data can refer to the extension of the data (i.e., data values) or to the intension of the data (i.e., the schema) [27]. The schema extraction from raw data may be intertwined with the preparation for operations such as discovery, integration, and cleaning [79, 99, 182]. For example, CLAMS transforms heterogeneous data in a data lake into a unified data model and enforces quality constraints on this model for cleaning purposes [79]. Data quality verification and data cleaning methods are based on reverse engineering [190, 201].

As another example, [22] proposes an ontology driven meta-model to conceptualize data representation in heterogeneous databases, proposing a common conceptual abstraction on semantically enriched vocabularies for both NoSQL and SQL databases to generate logical or physical schemas.