Patent Publication Number: US-9418092-B2

Title: Index selection in a multi-system database management system

Description:
BACKGROUND 
     A database is a collection of stored data that is logically related and that is accessible by one or more users. A popular type of database is the relational database management system (RDBMS), which includes relational tables made up of rows and columns (also referred to as tuples and attributes). Each row represents an occurrence of an entity defined by a table, with an entity being a person, place, thing, or other object about which the table contains information. 
     To extract data from, or to update, a relational table in an RDBMS, queries according to a standard database-query language (e.g., Structured Query Language or SQL) are used. Examples of SQL include INSERT, SELECT, UPDATE, and DELETE. 
     As applications become increasingly sophisticated, and data storage needs become greater, higher performance database systems are used. One example of such a database system is the TERADATA® database management system from Teradata Corporation. The TERADATA® database system can be a parallel processing system capable of handling relatively large amounts of data. In some arrangements, a database system includes multiple nodes that manage access to multiple portions of data to enhance concurrent processing of data access and updates. Concurrent data processing is further enhanced by the use of virtual processors, sometimes referred to as access module processors (AMPs), to further divide database tasks. Each AMP is responsible for a logical disk space. In response to a query, one or more of the AMPs are invoked to perform database access, updates, and other manipulations. 
     A physical storage structure that is provided by some database management systems is an index. An index is a structure that provides relatively rapid access to the rows of a table based on the values of one or more columns. An index stores data values and pointers to the rows where those data values occur. An index can be arranged in ascending or descending order, so that the database management system can quickly search the index to find a particular value. The database management system can then follow the pointer to locate the row containing the value. 
     The advantage of having an index is that it speeds the execution of SQL statements with search conditions that refer to an indexed column or columns. Generally, it is desired to create an index for columns that are used frequently in search conditions (such as in the Where clause of a SELECT statement). 
     In a database management system, primary and secondary indexes can be defined for each table. In a database system having multiple access modules, such as AMPs in a TERADATA® database management system, the primary index is used for assigning a data row to a particular one of plural AMPs. In effect, the primary index determines the distribution of rows of a table across multiple AMPs of the database system. Secondary indexes are used by a database system to more quickly identify portions of tables that are to be accessed in response to a database query. 
     Proper selection of indexes (such as the primary and secondary indexes) is important for optimal database performance. This is also referred to as the index selection problem, which can be a difficult problem when applied to a sophisticated parallel database system. Conventionally, many database designers rely mostly on their application experience and intuition to manually make index design decisions. With the increasing complexity of some database applications (e.g., data warehousing applications, which contain thousands of tables, indexes, and complex queries), the ability of a database designer to effectively perform tuning of indexes becomes increasingly difficult. 
     The problem of selecting indexes is made even more complex in the context of a multi-system database management system that has multiple database systems. For example, due to the size and nature of multi-system database machines, the search space of candidate indexes becomes very large such that the computations associated with traditional search algorithms used by conventional index selection tools are prohibitively expensive. 
     SUMMARY 
     In general, according to an embodiment, an index selection subsystem performs index selection for a multi-system database management system having a plurality of database systems. The index selection subsystem merges and sorts sets of query information from respective database systems into a workload, and generates candidate indexes from the workload. The index selection subsystem selects a recommended index from the candidate indexes based on one or more criteria. 
     Other or alternative features will become apparent from the following description, from the drawings, and from the claims. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram of an exemplary multi-system database management system that includes a plurality of database systems, in which an embodiment of the invention is incorporated. 
         FIG. 2  is a flow diagram of a process of performing index selection for a multi-system database management system, according to an embodiment. 
     
    
    
     DETAILED DESCRIPTION 
     In accordance with some embodiments, index selection is performed by an index selection subsystem for a multi-system database management system that has multiple database systems. Here, a “database system” refers to a set of coordinated database nodes (or just a single node) and associated database software that perform database-related tasks in the database system. Each database system of a multi-system database management system can have a corresponding different configuration, such as number of database nodes, number of logical components such as access modules and parsing engines (described further below), database software version, data distribution scheme (based on hashing of a primary index, for example), and/or indexing scheme. 
     The multiple database systems of the multi-system database management system can be distributed over a wide geographic region. For example, the multi-system database management system can include a first database system located in a first city, a second database system located in a second city, and so forth. The multiple database systems of the multi-system database management system can provide redundancy by provided replications of data in one or more of the database systems. If one of the database systems were to go down, then the multi-system database management system can continue to operate (process received database queries) with the remaining functional database system(s). Also, as another example, one database system can be upgraded (e.g., database software upgrade) or maintained (e.g., to repair or replace components) while the remainder of the multi-system database management system can continue to operate. 
     The multiple database systems of the multi-system database management system provide flexibility in that each of the database systems can operate independently of other database systems when desired. Moreover, a database query submitted to the multi-system database management system can also be submitted to multiple ones of the database systems for processing to provide concurrency. 
     The index selection subsystem according to some embodiments is able to merge and sort multiple sets of query information corresponding to the multiple database systems of the multi-system database management system into one or more workloads. “Query information” can include the query statement, query plan, explain text, XML (Extensible Markup Language) version, and various statistics, such as CPU utilization, disk utilization, row count, average row size, block size, column statistics, table selectivity, row cardinality, spool usage, and so forth. 
     The index selection subsystem then can select candidate indexes based on each workload that contains merged and sorted sets of queries from the multiple database systems. Then, applying one or more criteria, the index selection subsystem is able to select a recommended index for a given table for a given system or set of multi-node systems. Note that a “recommended index” can include addition of an index or removal of an index. Note that the recommended index for the given table can be different for different database systems. For example, for a first database system, the index selection subsystem can select a first recommended index for the given table, while for a second database system, the index selection subsystem can select a second recommended index for a replica of the given table. 
       FIG. 1  illustrates an exemplary arrangement that includes a multi-system database management system  100  having multiple distinct database systems  102 A and  102 B. The database system  102 A includes multiple database nodes  104 A, which are interconnected by an interconnect network  106 A. Each database node  104 A can include a server computer and associated storage devices. 
     As depicted in  FIG. 1 , each database node  104 A includes database software  108 A that is executable on one or more central processing units (CPUs)  110 A of the node  104 A. The CPU(s)  110 A is (are) connected to memory  112 A. The database software  108 A includes a parsing engine  114 A, which receives database queries and parses such received database queries. The parsing engine  114 A includes an optimizer  116 A that generates query plans in response to a database query, where the optimizer  116 A selects the most efficient query plan from among multiple query plans. The query plan includes a number of steps for the query. 
     The parsing engine  114 A can send the steps of the query plan to one or more of multiple access modules  118 A, which are also part of the database software  108 A. Each access module  118 A is responsive to the steps received from the parsing engine  114 A to perform one or more of the following tasks: inserts, deletes, or modifies content of tables; creates, modifies, or deletes definitions of tables; retrieves information from definitions and tables; and locks databases and tables. In one example, each access module  118 A can be based on an access module processor (AMP) used in some TERADATA® database systems from Teradata Corporation. 
     Each access module  118 A manages access of data in respective storage modules  120 A. A storage module  120 A can be implemented with a physical storage device or with a logical storage device (e.g., a logical volume within one or more physical storage devices). The presence of multiple storage modules  120 A allows a table to be distributed across the storage modules, where the content of the distributed table can be accessed concurrently by the access modules  118 A. 
     The database system  102 B similarly includes multiple database nodes  104 B interconnected by an interconnect network  106 B. Each database node  104 B includes database software  114 B connected to respective storage modules  120 B. The database nodes  104 B can be arranged similarly as the database nodes  104 A, or alternatively, the database nodes  10413  can be different from the database nodes  104 A. Although not shown specifically, each of the database nodes  104 A and  104 B includes corresponding one or more CPUs. 
     As noted above, the configurations of the multiple database systems (e.g.,  102 A,  102 B) of a multi-system database management system can be different. For example, the database system  102 A can have a first configuration (number of database nodes  104 A, number of access modules  118 A in each database node, number of parsing engines  114 A, database software version, indexing scheme, data distribution scheme, etc.), while the database system  102 B can have a second configuration (number of database nodes  10413 , number of access modules  118 B, number of parsing engines  114 B, database software version, indexing scheme, data distribution scheme, etc.). 
     To provide coordination between the database systems  102 A and  102 B, the database systems  102 A and  102 B are connected by a network  120  (e.g., a wide area network to connect geographically dispersed database systems). In some cases, the database systems  102 A and  102 B can run independently of each other. In other cases, however, there may be some coordination among the database systems of the multi-system database management system  100  such that processing of a query may involve tasks being performed by two or more of the database systems. 
     Although just two database systems  102 A and  102 B are depicted in  FIG. 1 , it is noted that the multi-system database management system  100  can include more than two database systems. Moreover, even though each of the database systems  102 A,  102 B is depicted as having multiple database nodes, it is noted that in different embodiments, one or more of the database systems can include just one database node. 
     To provide redundancy, multiple copies of a particular table (e.g., table A) can be kept in the distinct database systems. For example, the database system  102 A can store a first copy of table A, while the database system  102 B stores a second copy of table A. 
     Due to different configurations of the database systems  102 A and  102 B, it may be desirable to use different indexes for the two different database systems  102 A,  102 B. Thus, in accordance with some embodiments, an index selection subsystem can potentially select different indexes to use for different copies of the same table maintained in different database systems. 
       FIG. 1  depicts an index selection subsystem implemented in a computer  130  that is separate from the database systems  102 A,  102 B. In an alternative implementation, note that the index selection subsystem can be implemented in one or more of the database systems in the multi-system database management system. The computer  130  is connected to the network  120  to communicate with the database systems of the multi-system database management system  100 . The computer  130  includes an index selection tool  132 , a parsing engine  133  that includes an optimizer  134 , and a target emulation tool  136  to emulate environments of the database systems in the multi-system database management system  100 . The computer  130  can include multiple parsing engines  133  and multiple index selection tools  132 . The index selection tool(s)  132 , optimizer(s)  134 , and target emulation tool  136  can be software tools executable on one or more CPUs  138  in the computer  130 . The CPU(s)  138  is (are) connected to a storage  140 . A workload  142  (or workloads) is (are) stored in the storage  140 , where the workload(s)  142  can include merged and sorted query information from the multiple database systems of the multi-system database management system  100 . It is noted that the computer  130  can be implemented with multiple computing nodes, such as a massively parallel system of computing nodes. 
     In other embodiments, the components  132 ,  134 , and  136  can actually be implemented with a farm of parsing engines in a database node (e.g., one of nodes  104 ). Note that each of the parsing engines includes a corresponding optimizer. The database node can be enabled to perform emulation of various database systems that are the target of index selection. 
     In some embodiments, the architecture of the computer  130  can be referred to as a “virtual regulator” architecture. The virtual regulator architecture allows multiple threads of the index selection tool  132  to be spawned to run in parallel thus increasing the performance of the index selection problem. Hundreds or thousands of parsing engines (with associated optimizers  134 ) can be configured to perform searching in parallel to avoid time delays. 
     In the ensuing discussion, reference is made to a workload (in the singular sense) that contains merged and sorted query information from multiple database systems. However, it is noted that embodiments are applicable to scenarios where there are multiple workloads that each contains merged and sorted query information from multiple database systems. Also, although reference is made to the index selection tool  132  and optimizer  134  in the singular, note that the tasks performed can actually be performed by multiple threads (up to hundreds, thousands or more) of the index selection tool  132  and the optimizer  134 . 
     The index selection tool  132  automates the index selection process by recommending a set of indexes for a particular workload  142 , which corresponds to sets of query information that are captured from the multiple database systems  102 A,  102 B and merged and sorted into one workload. Note that considering multiple sets of query information from different database systems as a workload is different from index selection processes conventionally performed, which typically consider just the workload from a single database system. Also, the index selection can be performed in parallel on multiple processors or database nodes, and/or in emulation mode (where a database system is emulated without real data). 
     In accordance with some embodiments, each workload captured from a database system can be a workload defined for other purposes. During normal operation, the database system can define a “workload” as a set of requests that have common characteristics, such as an application that issued the requests, a source of the requests, type of query, priority, response time goals, throughput, and so forth. A workload is defined by a workload definition, which defines characteristics of the workload as well as various rules associated with the workload. Each workload  142  used by the index selection tool  132  according to some embodiments can be based on a combining corresponding workloads normally defined by the database systems  102 A,  102 B. These workloads can be logged in corresponding logs of the database systems, such as database query logs (DBQLs)  150 A,  150 B in corresponding database systems  102 A,  102 B. A given workload  142  to be used by the index selection tool  132  can share the same workload identifier as the corresponding workloads logged in the database systems  102 A,  102 B. 
     Based on the workload  142 , the index selection tool  132 , in cooperation with the optimizer  134 , recommends a set of indexes that are appropriate for the given workload. The indexes recommended can be primary indexes or secondary indexes. The term “index” or “indexes” is intended to cover any index that can used to enhance table access in a database system, including, as examples, a unique secondary index (USI), a non-unique secondary index (NUSI), a primary index (PI), covered index, and so forth. 
     A primary index determines distribution of data across multiple database nodes of a database system. For example, hashing can be applied on the primary index of any given table row to produce a hash value to indicate which database node the given table row is to be stored. Primary indexes include PPI (partitioned primary index), multi-level PPI, and H (join index). 
     Other types of indexes, including USIs, NUSIs, and hashed indexes (which are different types of secondary indexes), are data structures in which column values (from a table) are sorted (e.g., in ascending or descending order) and associated with row pointers. To access data in the table, the corresponding index can be consulted to quickly find the rows containing the data. 
     As depicted in  FIG. 1 , each database system  102 A or  102 B can log activity (in the form of workloads, for example) in the respective database system. The logged activity includes logged queries that can be stored in a database query log (DBQL)  150 A (in database system  102 A) or DBQL  150 B (in database system  102 B). The logged workload can be stored with a respective workload identifier, which allows the index selection tool  132  to analyze queries in a particular workload from among different types of workloads (such as strategic workloads versus tactical workloads). In addition to storing the query, the DBQL  150 A or  150 B can also store information associated with the queries, such as account identifier, user identifier, client identifier, usage of objects, rows returned, start and finish times, and so forth. The DBQL  150 A or  150 B can include various DBQL tables, including a table to store the SQL statement of a query, a table to store query objects, a table to store query step information, a table to store explain information, data in XML form, and so forth. 
     Alternatively, instead of storing database activity in the DBQL  150 A or  150 B, the database system  102 A or  102 B can store queries in a query capture database (QCD)  152 A or  152 B, respectively. The QCD  152 A or  152 B is also made up of several tables, which can store captured query plans and other information including data in XML format (to allow quick access by special parsers, for example). 
     The index selection tool  132  in the computer  130  is able to retrieve workload information from corresponding database systems  102 A,  102 B, such as by accessing (combining workloads from) the DBQLs  150 A,  150 B, or the QCDs  152 A,  152 B. Workloads in the DBQLs or QCDs can be accessed by workload identifier, for example. The captured query information from the multiple database systems  102 A,  102 B are merged and sorted by the index selection tool  132  into the workload  142 . As further discussed below, emulation data of the multiple database systems are also retrieved such that index selection can be performed in the emulated environments of the database systems  102 A,  102 B. 
     Although just one workload  142  is depicted in  FIG. 1 , it is noted that the index selection tool  132  can retrieve multiple workloads corresponding to different tables, for example. The computer  130  can also maintain a global view (global dictionary) of all data dictionaries in the domain that includes the database systems  102 A,  102 B. The index selection tool  132  can use the global dictionary to generate views of the multi-system schemas. Having the schemas allow the computer  130  to emulate the customer&#39;s environment. 
     In accordance with some embodiments, the index selection tool  132  along with the optimizer  134  can be considered part of an index selection subsystem. Alternatively, the optimizer  134  can be part of the index selection tool  132 . The optimizer  134  is executed in an emulated environment that is produced by the target emulation tool  136 . The index selection tool  132  provides candidate indexes and statistics to the optimizer  134 , which can generate an index recommendation based on cost analysis. 
     To perform target emulation, the target emulation tool  136  is able to export target emulation data from each of the database systems  102 A,  102 B. The target emulation data includes environment information, such as cost-related information, statistics, random samples, DDL (data definition language) statements, DML (data manipulation language) statements, actual database data, and so forth, from the database systems  102 A,  102 B. The environment information that is exported from the database systems and imported into the computer  130  allows the computer  130  to emulate the environments of the database systems  102 A,  102 B of the multi-system database management system  100 . 
       FIG. 2  is a flow diagram of a process performed by an index selection subsystem (e.g., including index selection tool  132  and optimizer  134  in  FIG. 1 ) according to an embodiment. The index selection subsystem creates (at  202 ) a workload, which is based on combining sets of query information from corresponding database systems  102 A,  102 B. For example, the index selection subsystem can access the DBQLs  150 A,  150 B from the database systems  102 A,  102 B to retrieve the desired information. Alternatively, the index selection subsystem can retrieve the information from the QCDs  152 A,  152 B. The multiple sets of query information from the database systems  102 A,  102 B are combined into the workload  142  ( FIG. 1 ). 
     The reason to combine query information from multiple database systems  102 A,  102 B into one workload  142  is to enable the index selection subsystem to determine whether any given database query touches more than one database system. This may affect which indexes are selected. 
     Query information can be captured in each of the database systems  102 A,  102 B using one of various possible techniques. For example, to capture query information into the QCDs  152 A,  152 B in the database systems  102 A,  102 B, an SQL (Structured Query Language) INSERT EXPLAIN statement can be used. Such a statement would cause query plans, along with various associated information (e.g., CPU utilization, disk utilization, row count, average row size, column statistics, etc.) to be stored into the QCDs or DBQLs. 
     The index selection subsystem next performs (at  204 ) index analysis on the workload, from which a set of candidate indexes are selected. In the index analysis, the index selection tool  132  creates a list of potential indexes. Then, the index selection tool  132  simulates the performance of the workload  142  in the emulated environment (generated from target emulation data imported by the target emulation tool  136 ) as if various combinations of the potential indexes. Based on the simulated performance, the index selection tool  132  produces the set of candidate indexes. The index selection subsystem will consider alternative different indexes for different copies of a particular table maintained in the distinct database systems  102 A,  102 B. Also, the index selection tool  132  can set the optimizer  134  to run in simulation mode. In fact, there can be a large number of optimizer (or parsing engine) simulations being performed in parallel at a given time. 
     The index analysis performed at  204  can be done with multiple threads of the index selection tool  132  and optimizer  134  spawned to run in parallel to improve speed and performance of the index selection problem. 
     Next, the index selection subsystem performs (at  206 ) index validation, in which another simulation is performed to ensure that the optimizer  134  will in fact pick the correct indexes if they are present. The simulation is performed to cover the entire multi-system database management system. Performance of the index validation results in selection of recommended indexes from the set of candidate indexes. In index validation, the optimizer  134  can produce query plans with and without different candidate indexes. The costs of query plans with and without the candidate indexes are compared, and the best performing candidate indexes (those candidate indexes that results in the most cost savings) are selected as the recommended indexes. Note that an index recommendation can involve recommending the addition of an index or the removal of an index. 
     The index validation performed at  206  can also be performed with multiple threads of the index selection tool  132  and optimizer  134 . 
     The candidate indexes that are not selected can be deleted. Note that different recommended indexes can be selected for any given table for the different database systems. For example, different copies of the base tables can be instantiated with different primary indexes in the different database systems. Also, different secondary indexes can be associated with different copies of the base tables in the different database systems. 
     The recommended indexes are then applied (at  208 ) to the corresponding database systems  102 A,  102 B. When applying a recommended index to a database system  102 A or  102 B, a SQL CREATE INDEX statement can be employed. It is possible that a Quality of Service option can be included in the CREATE INDEX statement that would steer storage of the index in a storage device of appropriate performance (e.g., storage in high-speed memory versus disk). 
     The various tasks discussed above can be performed by software, such as the index selection tool  132 , optimizer  134 , target emulation tool  136 , database software  114 A or  114 B, and so forth. Instructions of such software are loaded for execution on a processor (such as CPUs  110 A and  138  in  FIG. 1 ). The processor includes microprocessors, microcontrollers, processor modules or subsystems (including one or more microprocessors or microcontrollers), or other control or computing devices. A “processor” can refer to a single component or to plural components. 
     Data and instructions (of the software) are stored in respective storage devices, which are implemented as one or more computer-readable or computer-usable storage media. The storage media include different forms of memory including semiconductor memory devices such as dynamic or static random access memories (DRAMs or SRAMs), erasable and programmable read-only memories (EPROMs), electrically erasable and programmable read-only memories (EEPROMs) and flash memories; magnetic disks such as fixed, floppy and removable disks; other magnetic media including tape; and optical media such as compact disks (CDs) or digital video disks (DVDs). 
     While the invention has been disclosed with respect to a limited number of embodiments, those skilled in the art will appreciate numerous modifications and variations therefrom. It is intended that the appended claims cover such modifications and variations as fall within the true spirit and scope of the invention.