Workload reduction mechanism for index tuning

[0002] In a relational database system, individual records of data are stored in tables. Each table includes fields, or columns, of information and individual records are stored as rows, with a data entry in each column. Data may also be null within a column, which indicates no data was stored for that column. For example, in an employment database, there may be a table EMPLOYEES which includes columns such as employee ID, lastname, firstname, address, city, state and so forth. One record, including data in the several columns, would typically be entered in the EMPLOYEE table for each employee. Similarly, other tables may be established in accordance with the logical schema of the database. For example, a table SALARY HISTORY may include columns of salary history information, with each record being identified by an employee ID. Another table, MANAGERS, may include columns identifying information specific to managers and may also include the employee ID field. Relations between the tables would be established by reference to the columns which appear in multiple tables such as employee ID in the above example.

[0003] Operations on the data in a database are performed using a database access language. Structured Query Language (SQL) is a standard language for relational database management systems. SQL statements enable a user to perform database management operations, such as table or index creation, as well as to manipulate and extract the data contained in the database. For a given database system, the multiple SQL statements which are successfully executed by the database (garbage statements i.e. those including typographical errors, can be submitted but should not be considered part of the workload) comprise a workload of the system.

[0004] A major task in database management systems is in locating specific records within individual tables in response to the queries submitted to the database. Typically, the query statements identify one or more columns which are used as keys in the search process. The key is used to restrict the rows.in the table which the database system must evaluate to determine if they satisfy the query. For example, the EMPLOYEES table described in the above example may be searched for all employees who live in Boston, Mass. To that end, the system may scan through every entry in the EMPLOYEES table, specifically searching the city and state columns, to locate the desired records. In many instances, however, the table may span multiple pages and scanning the entire table may require multiple time consuming input/output (I/O) operations.

[0005] To reduce the time required to locate particular records, indexes may be established to map particular column values to records. Indexes provide more direct access to individual records, thus reducing search time, including costly I/O operations, to locate the records. Indexes, however, come with a cost of added storage space and an increase in time required to insert, delete or update records. Whenever a record is inserted or deleted, the system not only processes the record in the table, but also any indexes which include columns of the table. Further, updating a record can require relocation of the corresponding entry in one or more indexes.

[0006] An index tuning system looks at the logical schema and workload of a database, including specifics of tables and queries, to establish indexes which provide for efficient operation of the database system. One such index tuning system is presented in U.S. Pat. No. 5,404,510 in which the indexes are identified based on a detailed analysis of the workload with weight given to the importance of specific requests.

[0007] Typically, when an index tuning mechanism is implemented on a database, the database is tuned with respect to one or more “target” tables included within the database. One drawback of such a tuning system is that a workload associated with a given database often includes many statements which are not relevant to index tuning efforts. That is, many statements may reference non-target tables or may not affect data retrieval efforts within the database. As a result, the tuning mechanism wastes resources analyzing statements which are not relevant to the index tuning efforts.

[0008] In accordance with a workload reduction mechanism for index tuning, a method and apparatus is provided that selects relevant database query statements from a database workload, standardizes a format of the relevant database query statements and reduces the formatted, relevant database query statements into a representative set of database query statements. These statements can then be provided to an index tuning mechanism. With such an arrangement, the index tuning mechanism is able to tune the system in a shorter period of time and use less storage space while analyzing fewer statements.

[0009] In accordance with a further aspect of a workload reduction mechanism for index tunning, a system is provided that includes a database workload source which provides input to a workload filter. The workload filter selects relevant database query statements from the workload source and provides input to a formatting system. The formatting system standardizes a format of the relevant database query statements. The system also includes a hash table that includes a hash of each representative database query statement selected from the relevant database query statements.

[0010] Also provided is a computer program product to provide a workload reduction mechanism for index tuning.

[0011] The foregoing and other objects, features and advantages of the invention will be apparent from the following more particular description of A Workload Reduction Mechanism for Index Tuning, as illustrated in the accompanying drawings in which like reference characters refer to the same parts throughout the different views. For clarity and ease of description, the drawings are not necessarily to scale, emphasis instead being placed upon illustrating the principles of the invention.

[0012] FIG. 1 is a schematic illustration of a database management system embodying a workload reduction mechanism for index tuning.

[0013] FIG. 2 is a block diagram illustrating the internal organization of the workload preprocessor of FIG. 1.

[0014] FIG. 3 is a flow diagram of the filtering process implemented by the filter component of FIG. 2.

[0015] FIG. 4 is a flow diagram of the workload collapse process implemented by the collapse component of FIG. 2.

[0016] FIG. 5 is flow diagram of the database query statement formatting process implemented by the format component of FIG. 2.

[0017] FIG. 6 is a block diagram illustrating the internal organization of the format component of FIG. 2.

[0018] FIG. 1 is a schematic illustration of a database management system 10 embodying a work load reduction mechanism for index tuning. The database management system 10 is shown to include a processor 12, an IO device 14 and a system memory 16 connected by a system bus 18. Here the database is shown stored locally on storage disk 20A and storage disk 20B. It should be understood however, that the database can also be stored remotely on one or more 10 devices (not shown).

[0019] System memory 16 is shown to include a database workload 22. The database workload can reside in memory as shown, within the database, or in any other secondary storage. Typically, a database workload includes all database statements submitted to a database over a specified period of time. Several workload collection mechanisms can exist, three of which will be discussed below.

[0020] A first mechanism filters application code, searching the source code for all database statements. A second mechanism introduces either a software or hardware collection process to the database environment between an application and the database. The process reads database statements as they are submitted to the database for processing and writes the statements to memory. A third collection mechanism uses a database cache. Some database systems maintain an internal cache of frequently accessed database statements which have run against the database. This cache is typically used to share database statements between different users to save processing time, since the shared database statements do not have to be reparsed, however, the cache may also be used to collect workload information. For ease of explanation and clarity of description, the remainder of the description will assume that the database workload is provided by a database cache capturing SQL statements.

[0021] System memory 16 is further shown to include a tuning system 24, which operates on a database workload 22. The tuning system 24 includes a workload preprocessor 26 and an index tuner 28. The workload preprocessor 26 takes the database workload 22 as input and provides a reduced workload 30 to the index tuner 28.

[0022] As is well know, an index is created in a database to increase the performance of data retrieval. The index tuner 28 analyzes the indexes already created in the database system, as well as the database workload 22 run on the system, and modifies the existing indexes or, creates new indexes, to maximize the performance of the database system. When processing a request, a database system can use some or all of the available indexes to locate the requested rows efficiently. The index tuner 28 operates as described in U.S. Pat. No. 5,404,510 which is hereby incorporated by reference.

[0023] The database workload 22 includes all SQL statements submitted to the database over a period of time. Typically, not all SQL statements included in the database workload are of interest to the index tuner 28. That is, many of the statements may define or modify the structure of the database or address the security for the database. These types of SQL statements generally do not address data retrieval efforts and are therefore not relevant to the index tuner 28. Therefore, to provide the complete database workload 22 to the index tuner 28 may be inefficient and wasteful of processing resources. Accordingly, the workload preprocessor 26 reduces a workload of a database system, such that the index tuner 28 can operate more efficiently.

[0024] FIG. 2 is a block diagram illustrating the internal organization of the workload preprocessor 26 of FIG. 1. The workload preprocessor 26 is shown to include a filter component 22, a format component 36 and a collapse component 40, all connected in series. That is, the filter component 32 provides at its output, input to the format component 36 which in turn provides at its output, input to the collapse component 40.

[0025] By way of background, SQL statements may be divided into multiple categories. The more common of these categories are Data Definition Language (DDL) statements and Data Manipulation Language (DML) statements. DDL statements define a database, modify its structure and destroy it after it is no longer needed. DML statements enter data into the database, change the data or read data from the database.

[0026] The database workload 22 is provided to the filter component 32, which analyzes the database workload 22 and selects those database query statements that are relevant to the tuning system 24. When tuning a database, the tuning mechanism typically tunes the database for optimal performance with respect to one or more particular tables included in the database. Specifically, the filter component 32 screens the database workload 22 to select DML statements which are directed at a target table. DDL statements, which define and destroy a database, provide little, if any, information regarding the data retrieval efforts for a particular database and as such may be ignored for index tuning purposes. After filtering the database workload 22, the filter component 32 provides the relevant statements 34 to the format component 36.

[0027] SQL, like many database access languages, is a simple but powerful computer programming language. Rather than defining many complex instructions, SQL provides a few basic instructions which can be grouped and ordered to perform the requisite tasks. In addition, there are few constraints on the syntax of an SQL statement. As a result of all this “programming freedom”, two separate users, endeavoring to formulate the same query, commonly generate physically different statements. These physical differences may be as basic as the spacing or occurrence of carriage returns within the statement or may be as complex as the use of complex conditionals in a statement. Moreover, from the standpoint of the index tuner 28, two apparently different statements are, in reality, similar for the purpose of index evaluation. In an effort to better analyze the workload 22 of the database management system 10, therefore, the format component 36 takes the relevant statements 34 and reformats those statements into a single, common, syntactical format. A more detailed description of the format component 36 is provided below with reference to FIG. 4 and FIG. 5.

[0028] These formatted, relevant statements are provided to the collapse component 40. The collapse component 40 analyzes the formatted relevant statements 38 and provides at its output, a reduced workload 30. The reduced workload 30 includes a set of database statements, representative of the database statements included in the database workload 22, provided in a single, common format.

[0029] FIG. 3 is a flow diagram of the filtering process implemented by the filter component of FIG. 2. The filtering process begins at step 42 where the workload is provided from a source. As previously described, multiple mechanisms are available for collecting a database workload. For ease of explanation, it is assumed that the database workload has been provided by a database cache. It should be apparent to one of ordinary skill in the art however, that the technique which will be described below may be applied to any of the workload collection mechanisms previously described.

[0030] At step 44, a database statement is identified from the database workload and, at step 46, a query is made as to whether the identified database statement references a target database table. To determine whether the database statement references a target table, an actual name of the table to which a table synonym or table alias referenced in the statement refers is ascertained. Generally, a dependency table exists which cross references synonyms and aliases to actual table names.

[0031] If the database statement does not reference a target database table, the database statement is not classified as a relevant statement. No further filtering of this statement is necessary. Therefore, flow returns to step 44 where a next database statement is identified.

[0032] If, however, it is determined at step 46 that the database statement does reference a target database table, step 46 is followed by step 48. At step 48, a query is made as to whether the database statement includes a data manipulation language key word. In the SQL database query language, four database manipulation language keywords are provided. These keywords are INSERT, UPDATE, DELETE and SELECT. If no DML keyword is included in the database statement at step 48, control returns to step 44 where a next database statement is identified from the workload. If however, a DML keyword is included in the database statement, the database statement is classified as a relevant database statement at step 50. If this is the last database statement included in the database workload 22 as determined at step 52, the process ends at step 54. If, however, it is not the final statement, a next database statement is identified at step 44.

[0033] Once the relevant database statements 34 have been selected from the database workload 22 by the filter component 32, they are provided to the format component 36. The format component standardizes the format and content of the relevant database statements 34 to provide a set of database statements which may be analyzed by the collapse component 40.

[0034] FIG. 4 is a flow diagram of the database statement formatting process implemented by the format component 36 of FIG. 2. The format component 36 reformats each of the relevant database statements 34 to make them appear as similar as possible. As described above, a database workload 22 is a collection of all database statements run on a database for a period of time. Each of these statements may have been written and submitted by different people thus representing an individual writing style of each of those people. As a result, a logically identical query, submitted by a number of different people, may each be physically different from one another even though they provide the same data at output and further are identical from an index tuning standpoint. Accordingly, the format component 36 analyzes each database statement and rewrites the statement according to consistent, syntactical rules.

[0035] For each relevant database statement 34 identified by the filtering process of FIG. 3, a synonym, included in the relevant database statement, is substituted with a root value for the synonym at step 60. A synonym is another name for a table, view, sequence or program unit, providing a direct reference to the object. Synonyms can be public or private and are typically used for security or convenience reasons. For example, synonyms can mask the name and owner of an object, provide public access to an object, and simplify an SQL statement for a database user. For example, in a table called SALES_DATA in a schema owned by a user KFERGUSON, a query to the table would be made with the statement:

[0036] SELECT*FROM kferguson.sales_data;

[0037] To simplify this SQL statement, and any other statement which references this table, a synonym for the table name is created, SALES. The synonym is created in a separate SQL statement. Referencing the table using the synonym for the table, the statement becomes:

[0038] SELECT*FROM sales;

[0039] As described above, the format component 36 replaces each synonym with the root value for the synonym. A root value of a synonym is a most basic form of the value. That is, in the example above, the root value of the synonym SALES is KFERGUSON.SALES_DATA. As a result, for each occurrence of the synonym SALES in the relevant database statements 34, the identifier KFERGUSON.SALES_DATA is substituted.

[0040] Once all synonyms have been removed from the relevant database statement 34, simple operator phrases are substituted for complex operator phrases at step 62. In SQL, as in other database query languages, a number of operators are used to create conditionals in a WHERE clause within a statement. Examples of such operators are:

[0041] =,<,>, AND, OR, NOT and IN.

[0042] In many cases, these operators are combined to form complex conditionals such as testing for one or more identifiers to be equal to all values (AND) or, to be equal to one or more values (OR) or, to be one in a list of values (IN). From an index tuning perspective however, after an identifier is tested once, each additional test of the same identifier need not be represented in the query statement. This is because each additional query of the identifier adds no additional information regarding data retrieval efforts other than a frequency value which can be stored with the reformatted statement rather than represented in the statement. In addition to simplifying the conditional statements, the wildcard operator * is replaced in a statement with the actual names of each of the columns in the table at step 62.

[0043] At step 64, a common parameter naming convention is implemented and the sequence of the parameters are reordered. That is, SQL statements often query a database to provide each record where an entry in a column of the record is equal to a literal such as a last name, an ID number, etc. Here, the format component 36 substitutes a parameter for the literal. In addition, SQL allows a user to include parameters in a SQL statement. These user defined parameters, which are typically referred to as bound variables, are also replaced using the same common parameter naming convention. After substitution, the parameters may be reordered to a standard order such as an alphabetical order.

[0044] At step 66, the use of delimiters in a database statement is standardized. That is, all white space and carriage returns occurring within a single database statement are substituted with a single space. One or more spaces between expressions in a statement as well as one or more carriage returns within a statement are allowed in SQL. Often times, these additional spaces or carriage returns are included to enhance the human readability of an SQL query statement. Therefore, to make analysis and comparison of the database statements simpler, these additional spaces and carriage returns are removed at step 66. In addition to additional white space and carriage returns, parenthesis are often added to a statement to improve readability. These superfluous parenthesis are also removed at step 66.

[0045] At step 68, expressions within the database statement are converted from case non-specific to case consistent throughout the query statement. That is, the database statement is rewritten as all capital letters or, in the alternative, as all lowercase letters. A common practice of some users is to capitalize all SQL keywords within a SQL statement while writing all remaining expressions in lowercase characters. By rewriting the statement in a consistent case, comparison of the statements during the collapse process implemented by the collapse component 40 is simplified.

[0046] At step 70, the use of aliases within a database statement is standardized. That is, all superfluous aliases are removed and a common aliases naming convention is followed, substituting each alias with a preselected, common alias. An alias is an alternate method of referencing a table in the database. In database statements which reference multiple tables, aliases may be used to assist in keeping track of which column name belongs to which table. An example is provided below:

[0047] SELECT A.last_name, B.last_name

[0048] FROM EMP A MGR B

[0049] WHERE A.dept=B.dept;

[0050] Here, the aliases A and B are used to reference the two tables EMP and MGR. In an instance such as this, use of the aliases is advantageous because they are used to distinguish between the last_name and dept columns which occur in both tables. There are occasions however, where an alias is superfluous. Take, for instance, the following SQL statement:

[0051] SELECT A.last_name FROM EMP A WHERE id=195;

[0052] Here, the alias A is unnecessary and is eliminated by the format component 36 at step 70. Once all superfluous aliases are removed, any remaining aliases are renamed in a predetermined manner and are reordered to a preselected order, such as an alphabetical order.

[0053] At step 72, identifiers occurring within the database statement are reordered to a predetermined, identifier sequence. An identifier is an expression in the database statement that identifies tables or column names. In the above example, A.last_name, EMP and id are identifiers. Here, the identifiers are reordered, typically alphabetically.

[0054] FIG. 5 is a block diagram illustrating the internal organization of the format component 36 of FIG. 2. The format component 36 is shown to include a collection of seven filters, connected in series. The filters include a synonym filter 80, an operator filter 82, a parameter filter 84, a delimiter filter 86, a case filter 88, an alias filter 90 and an identifier filter 92. The ordering of these filters are for illustrative purposes only. One of ordinary skill in the art would appreciate that various ordering arrangements are possible, each yielding a similar result to the arrangement shown.

[0055] The operation of these filters will be described in conjunction with an example including two sample tables and a sample workload. The two tables provided are Employee, (Table 1), and Customer, (Table 2). Only the column headings are shown in the tables. The sample workload is provided in Table 3 and includes only relevant database statements.

[0056] The employee table is shown to include the following nine columns: id, first_name, last_name, address, city, state, department, job_code and salary. The customer table is shown to include the following seven columns: id, company_name, address, city, state, contact_name and salesperson_id. The SQL statements in the workload table are labeled with a single character reference, letters A-H.

[0057] Provided below, in Table 4, is a progression of the format of the statements as they are processed by each of the filters. Table 4 is shown to include the statement identifier, a reference character for the filter which is processing the statement, and the resulting statement format after processing by the identified filter.

[0058] As may be seen in Table 4, statement A is first reformatted by the parameter filter 84 which replaces the literal “1” with the character string “:PARAM”. The parameter filter 84 also reorders the parameters to a predefined order, however, as only one parameter is included in statement A, reordering is not required. Because statement A does not include a synonym, it is passed, unaltered, through the synonym filter 80. The only operator included in statement A, the equal sign (=), cannot be further simplified by the operator filter 82 and as such, the statement passes through the operator filter 82 unaltered as well.

[0059] The delimiter filter 86 processes statement A, standardizing the spacing of the statement by adding a single space between the comma after the identifier last_name and the identifier address. The case filter 88 converts all expressions in statement A to uppercase letters. Alternatively, the case filter 88 can convert the statement to all lowercase letters as well, as long as all statements from the workload are handled the same way. Statement A does not include any aliases so it is passed, unaltered, through the alias filter 90. The final reformatting of statement A is performed by the identifier filter 92 which reorders the identifiers “last_name” and “address” to be listed in the statement alphabetically.

[0060] Statement B, as may be seen in table 4, is processed by three of the filters, the parameter filter 84, the delimiter filter 86 and the case filter 88. The parameter filter 84 replaces the bound variable “:5” with the character string “:PARAM”. The delimiter filter 86 adds a space on either side of the equal sign (=). Finally, the case filter 88 converts all expressions in statement B to uppercase characters.

[0061] Again, as with statements A and B, statement C passes through the synonym 80 and operator 82 filters unaltered. The literal “Monique” in statement C is replaced with the string “:PARAM” by the parameter filter 84. Statement C includes carriage returns within the statement. The delimiter filter 86 removes these carriage returns and replaces each of them with a single space and then, the entire statement is capitalized by the case filter 88.

[0062] Statement D includes a synonym, emp, for the employee table. The synonym filter 80 determines the root value for the synonym and replaces the synonym with the root value, employee, in the statement. As described above, synonym information is typically stored in a lookup table which cross references a synonym with its root value. The parameter filter 84 replaces the bound variable “:1” with the string “:PARAM” and then the statement is capitalized by the case filter 88.

[0063] Statement E is first parsed by the parameter filter 84 which replaces the literal “5” with the character string “:PARAM”. Statement E is already capitalized so it passes through the case filter 88 to the alias filter 90. The alias filter 90 identifies the alias “e” in the statement and determines whether this alias is superfluous. Here, the alias is superfluous as only a single table is referenced in the statement and therefore there is no need to differentiate between similarly named columns in two different tables. Accordingly, the alias filter 90 removes the alias and all references to it in the statement. The identifier filter 92 then reorders the “address” and “last_name” identifiers.

[0064] Statement F includes a wildcard operator which is expanded out to the names of each of the columns by the operator filter 82. The remaining operators in the statement, “>”, “and” and “=” cannot be further simplified by the operator filter 82 and therefore remain unaltered. The literal “25000” and the bound variable “:5” are each replaced with the string “:PARAM” by the parameter filter 84. Finally, the case filter 88 converts the statement to uppercase characters.

[0065] Statement G is reformatted by five of the filters, the parameter filter 84, the delimiter filter 86, the case filter 88, the alias filter and the identifier filter 92. The parameter filter 84 replaces the user provided parameter “ID” with the character string “:PARAM” in both locations. The delimiter filter 86 replaces the carriage returns with a single space and the case filter 88 capitalizes the statement. The alias filter 90 parses the statement and identifies two aliases, “emp” and “cust”. In statement G, two tables re referenced which have similarly named columns. Accordingly, neither of the aliases re superfluous. The alias filter 90 replaces the aliases with simple, preselected aliases, ere using the characters A and B. Any character strings may be used as long as each alias in a single workload is replaced in a consistent manner. It is also important to assign the aliases consistently, always assigning the same alias to a particular table.

[0066] Statement H is also reformatted by five of the filters, the operator filter 82, the parameter filter 84, the delimiter filter 86, the case filter 88 and the alias filter 90. Statement H includes two OR expressions connected by a single AND operator. Because each OR is logically comparing the same identifiers and simply testing these operators against two literals, each OR expression may be reduced into one or the other test for equality against a literal. Here, they are both reduced to include only the first equality expression by the operator filter 82. The parameter filter 84 replaces the literals with the character string “:PARAM” and the delimiter filter 86 standardizes the spacing around the equal (=) signs in the statement and removes the unnecessary parenthesis. The case filter 88 capitalizes the statement.

[0067] Statement H includes aliases which are analyzed by the alias filter 90. Here, as in statement G, the aliases are found not to be superfluous and therefore the aliases are replaced with aliases conforming to a consistent naming scheming such as here where they are replaced with single characters of the alphabet beginning with the letter A.

[0068] The resulting reformatted, relevant database query statements are provided below in Table 5.

[0069] FIG. 6 is a flow diagram of the workload collapse process implemented by the collapse component 40 of FIG. 2. The collapse process begins at step 100 where the next database query statement is identified from the reformatted, relevant database statements 38 provided from the format component 36. A hash key is calculated for the database query statement at step 102. The hash key uses an algorithm which generates a value that is unique to a given SQL statement, such as the MD5 message digesting algorithm. The hash key of the statement is compared to entries in a hash table at step 104 to determine whether the hash key is already represented as an entry in the hash table. The hash table includes hashes of prior statements. If, at step 104, it is determined that the hash key of the statement is not already in the hash table, a new entry for the statement is added to the table at step 106. If the hash key matches an entry in the table, however, statistics associated with the entry are modified at step 108. These statistics may represent a count of matching hashes, indicating a match of the statement, or other information such as a number of input/output operations executed by the statements or an amount of memory used by the statement.

[0070] At step 110, the process determines whether this is the final statement. If it is not the final statement, the process returns to step 100 where a next database statement is identified. If it is the final statement, the process ends at step 112. The output of the process is a table representing each unique statement and associated statistics derived from additional subsequent occurrences of the same statements. It is this final selection of statements which is provided to the index tuner 28 of FIG. 1.

[0071] Provided below in Table 6 is a representative output of the collapse process using the information from Table 5 as input. As may be seen, the workload has been reduced to include only four statements. In the far left column, a label is included which represents which statements have been reduced into the final form of the statement provided in the second column.

[0072] It will be apparent to those of ordinary skill in the art that methods involved in A Workload Reduction Mechanism for Index Tuning may be embodied in a computer program product that includes a computer usable medium. For example, such a computer usable medium can include a readable memory device, such as a hard drive device, a CD-ROM, a DVD-ROM, or a computer diskette, having computer readable program code segments stored thereon. The computer readable medium can also include a communications or transmission medium, such as a bus or a communications link, either optical, wired, or wireless, having program code segments carried thereon as digital or analog data signals.

[0073] It should be noted that, although the description references SQL, the techniques described herein for providing a workload reduction mechanism for index tuning can be applied to any database query language and should not be construed as applying solely to SQL. Moreover, the formatting operation should not be limited to the discussed operations. The type of ordering of the individual formatting operations are for illustrative purposes only. It will be apparent to ordinary skill in the art that fewer or additional formatting operations can be appropriate given the specific nature of a particular database system and associated workload.

[0074] While this invention has been particularly shown and described with references to preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention as defined by the appended claims.