Dynamically adjust duplicate skipping method for increased performance

CROSS-REFERENCE TO RELATED APPLICATION

0001This application is a continuation of co-pending U.S. patent application Ser. No. 14/170,316, filed Jan. 31, 2014. The aforementioned related patent application is herein incorporated by reference in its entirety.

BACKGROUND

Technical Field

0002Embodiments disclosed herein relate to query optimization in a relational database. More specifically, techniques are disclosed for adjusting duplicate-skipping methods when executing a database query.

Description of the Related Art

0003Relational database management systems (DBMS) use relational techniques for storing and retrieving data in a database. Users request access to data in the database by issuing a database access request, such as a query statement. A query statement is a set of commands for retrieving, inserting, or modifying data from the database.

0004Many database query statements for data retrieval require removal of duplicate results by syntax (e.g., SET FUNCTION DISTINCT and GROUP BY in SQL). Other database query statements do not require duplicate values to be included in the result set (e.g., sub-query statements). When executing a query, a DBMS may remove duplicates through various methods involving scanning an index of the database for distinct values. A database index is a data structure used to quickly locate data without having to search every row in a database table. In a relational database, the index is a copy of select columns of data from the table that can be searched efficiently.

0005One current approach for removing duplicate values from a result set is to skip index keys with duplicate values in leading index columns. Using this approach, DBMS scans an index for distinct values. When the DBMS identifies a distinct value, the DBMS skips over duplicates of that value until identifying the next distinct value. However, this approach incurs significant overhead when scanning a range of index keys scanned which contains few duplicate values. Further, the method used to skip duplicate values remains the same regardless of the proximity of two distinct keys within the index. This results in unnecessarily incurred overhead, and thus, inefficient performance.

SUMMARY

0006Embodiments presently disclosed herein provide a method for skipping duplicate index keys in a database index to identify records in a database that satisfy a database query. The method generally includes estimating a distance in the database index between a current index key and a next index key that is distinct from the current index key. The method generally includes selecting a duplicate-skipping method based on the estimated distance. The method also generally includes performing the selected index-skipping method to identify the next distinct index key.

0007Another embodiment of the invention includes a computer program product, the computer program product comprising a computer-readable storage medium having computer-readable program code embodied therewith. The code, when executed on a processor, may generally perform an operation for skipping duplicate index keys in a database index to identify records in a database that satisfy a database query. The operation may generally include estimating a distance in the database index between a current index key and a next index key that is distinct from the current index key. The operation may also include selecting a duplicate-skipping method based on the estimated distance. The operation may also include performing the selected index-skipping method to identify the next distinct index key.

0008Still another embodiment of the invention includes a system having a processor and a memory containing an operation. The operation may generally include estimating a distance in the database index between a current index key and a next index key that is distinct from the current index key. The operation may generally include selecting a duplicate-skipping method based on the estimated distance. The operation may generally include performing the selected index-skipping method to identify the next distinct index key.

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS

0009So that the manner in which the above recited features, advantages and objects of the present invention are attained and can be understood in detail, a more particular description of the invention, briefly summarized above, may be had by reference to the embodiments thereof which are illustrated in the appended drawings.

0010Note, however, that the appended drawings illustrate only typical embodiments of this invention and are therefore not to be considered limiting of its scope, for the invention may admit to other equally effective embodiments.

0011<figref idref="DRAWINGS">FIG. 1</figref> illustrates an example computing environment, according to one embodiment.

0012<figref idref="DRAWINGS">FIG. 2</figref> illustrates an example computing system configured to set duplicate skipping methods while executing a database query, according to one embodiment.

0013<figref idref="DRAWINGS">FIG. 3</figref> illustrates a method for setting duplicate-skipping methods when executing a query statement, according to one embodiment.

0014<figref idref="DRAWINGS">FIG. 4</figref> illustrates a method for selecting a skipping method based on a distance between a current index key and a next distinct index key, according to one embodiment.

DETAILED DESCRIPTION

0015Embodiments presented herein provide techniques for selecting a method to skip duplicate values when executing a query statement. For example, the embodiments provide techniques for selecting a skipping method when executing a Structured Query Language (SQL) statement against a relational database. In one embodiment, an estimated distance between two distinct and sequential keys in an index of the database is used to determine an appropriate skipping method to perform in response to a query statement.

0016In one embodiment, when executing a query statement requesting distinct values, a database management application probes an index tree of the database table identified in the query. The database management application scans a given index and estimates a distance between a current index key and a next distinct (i.e., non-duplicate) index key.

0017Based on the estimated distance between keys, the database management application may select a corresponding method, such as a “big skip” method or a “little skip” method. The “big skip” method may include performing a binary search algorithm from the root of the index tree. The “little skip” method may include performing a binary search algorithm within the current index page. If the estimated distance between the keys is relatively far (e.g., at least an index leaf page apart), then the database management application sets the method to perform the “big skip” method. Otherwise, if the current index key and the next distinct index key reside within the same index page, the database management application sets the duplicate-skipping method depending on the estimated distance between the current index key and the next distinct index key, relative to their positions within the index page. The database management application estimates the relative distance based on properties of leaf pages of the index, such as the high and low bounds and the number of index keys in a page. If the two keys are separated by relatively many index keys, the database management application sets the method to perform the “little skip” method. However, if the two keys are separated by relatively few duplicate values, the database management application sets the method to perform a “get next” operation to iterate through consecutive index keys to retrieve the next distinct index key.

0018Note, for the approach described below to work effectively, an index should include at least some duplicate values. That is, if the index already stores a collection of distinct values, the approach may increase the overhead of query execution. In one embodiment, the database management application may ascertain whether an index has duplicate values through evaluating statistics of the index, e.g., by evaluating the number of distinct values relative to the number of rows in the database table, etc. Further, the database management application may be configured to determine whether to evaluate the index for adjusting the skipping method. For example, if the database management application determines (e.g., based on statistic information collected) that an index includes relatively few duplicate values, the database management application does not evaluate which method to perform, and instead may perform a default iterative method. Whether the index includes few duplicate values may be determined by a threshold. Doing so avoids computational overhead incurred in selecting skipping methods in contexts where the index includes few duplicate values.

0019Embodiments presented herein provide techniques for setting duplicate-skipping methods when executing a query statement. Setting the skipping methods based on estimated distances between distinct index keys provides an efficient way to determine whether distinct index keys are sparse, thus ensuring that a next distinct index key may be identified in a relatively efficient manner. Further, setting the skipping methods reduces overhead incurred by arbitrarily skipping duplicates to reach a next distinct value, even in the case where no index keys can be skipped throughout the scan of the index. Additionally, the overhead caused by scanning index pages is reduced.

0020<figref idref="DRAWINGS">FIG. 1</figref> illustrates an example computing environment <b>100</b>, according to one embodiment. As shown, the computing environment <b>100</b> includes a client computer <b>105</b> and a server computing system <b>110</b>, each connected to a communications network <b>115</b>.

0021Illustratively, the client computer <b>105</b> includes an application <b>110</b> that communicates with the server computing system <b>110</b> to submit database requests (e.g., query statements) to the server computing system <b>110</b>. Although shown as a single client computer, the client computer <b>105</b> is included to be representative of a single client or multiple clients. The server computing system <b>110</b> may include an index <b>112</b>, a database management application <b>114</b>, and a relational database management system (DBMS) <b>116</b>.

0022The database management application <b>114</b> processes requests sent by the client computer <b>105</b> to the server computing system <b>110</b>. As part of doing so, the database management application <b>114</b> sends query statements to the DMBS <b>116</b>. The DBMS <b>116</b> includes one or more software applications configured to manage relational databases <b>118</b>. The index <b>112</b> may store values corresponding to the database table columns managed by the database management application <b>114</b>. Specifically, the index <b>112</b> may store key values corresponding to a key table column. The index <b>112</b> may be structured as a binary search tree, where index keys are organized in leaf nodes (index pages). Doing so allows index pages to be ordered in a sequential manner, which enables certain index pages to be skipped during a search.

0023<figref idref="DRAWINGS">FIG. 2</figref> further illustrates an example server computing system <b>110</b> configured with a database management system that is configured to adjust a variety of duplicate-skipping methods, according to one embodiment. As shown, the server computing system <b>200</b> includes, without limitation, a central processing unit (CPU) <b>205</b>, a network interface <b>215</b>, an interconnect (i.e., bus) <b>217</b>, a memory <b>220</b>, and storage <b>230</b>. The server computing system <b>200</b> also may include an I/O device interface <b>210</b> connecting I/O devices <b>212</b> (e.g., keyboard, display, and mouse devices) to the server computing system <b>110</b>.

0024The CPU <b>205</b> may retrieve and execute programming instructions stored in the memory <b>220</b>. Similarly, the CPU <b>205</b> may retrieve and store application data residing in the memory <b>220</b>. The interconnect <b>217</b> may facilitate transmission, such as of programming instructions and application data, among the CPU <b>205</b>, I/O device interface <b>210</b>, storage <b>230</b>, network interface <b>215</b>, and memory <b>220</b>. CPU <b>205</b> is included to be representative of a single CPU, multiple CPUs, a single CPU having multiple processing cores, and the like. Additionally, the memory <b>220</b> is included to be representative of a random access memory. Furthermore, the storage <b>230</b> may be a disk drive storage device. As shown, the memory <b>220</b> includes the database management application <b>114</b> and the DBMS <b>116</b>.

0025Although shown as a single unit, the storage <b>230</b> may be a combination of fixed and/or removable storage devices, such as fixed disc drives, floppy disc drives, tape drives, removable memory cards or optical storage, network attached storage (NAS), or a storage area-network (SAN). As shown, the storage <b>230</b> includes the index <b>112</b> and the relational databases <b>118</b>.

0026In one embodiment, the database management application <b>114</b> receives a database query statement from a client computer. The database query statement may specify that that only distinct values should be retrieved from the relational databases <b>118</b> for values from at least one of the columns referenced by the query. In such a case, the database management application <b>114</b> may determine a duplicate-skipping method to perform when retrieving distinct values from the index <b>112</b>. To do so, the database management application <b>114</b> may scan the tree of the index <b>112</b> within a given start and stop key range. For example, the range may include every leaf page of the index <b>112</b>. As another example, the range may be constrained by specified predicates.

0027The database management application <b>114</b> may set a skipping method based on a proximity between distinct keys. When initially probing the index <b>112</b>, the database management application <b>114</b> sets an initial index key in an initial leaf page as a current index key. Further, the database management application <b>114</b> generates a search index key having an arbitrary value. The search index key is used to locate a next distinct index key. The arbitrary value generated for the search index key should be greater than the value of the current index key if the direction of the scan is forward, or less than the value of the current index key if the direction of the scan is in reverse.

0028If the current index key and the next distinct index key reside in index leaf pages at least an index page apart, then the database management application may determine that the keys are within a “far” proximity. A “far” proximity may result from the current index key having many duplicate values. If the current index key and the next distinct index key reside in the same index leaf page, the database management application may determine the keys are within “near” proximity. A “near” proximity may result from the current index key having relatively few duplicate values. Of course, the “far” and “near” proximities may be configured based on the needs of the DBMS <b>116</b>.

0029After estimating the distance between the distinct keys, the database management application <b>114</b> sets the duplicate-skipping method depending on whether the proximity is “far” or “near.” As further described below, if the proximity between the distinct keys is “far,” the database management application <b>114</b> performs a “big skip” method that searches through multiple index pages. Otherwise, if the proximity is “near,” the database management application <b>114</b> performs a “little skip” method that has a comparatively smaller scope of search than the “big skip” method.

0030<figref idref="DRAWINGS">FIG. 3</figref> illustrates a method <b>300</b> for setting duplicate-skipping methods when executing a query statement, according to one embodiment. Method <b>300</b> is performed in response to a DBMS receiving a query to execute against a database. In particular, the DBMS receives a query that requests distinct values from certain columns of records in the database. For example, the database query may correspond to a request for records having distinct last names in an employee database.

0031In one embodiment, the database management application may determine whether the index a reasonable candidate for adjusting duplicate-skipping methods. More specifically, the database management application determines whether the index includes a threshold amount of duplicate values such that the amount of computation involved in performing method <b>300</b> is less than the amount of computation involved by not doing so. To do so, the database management application may evaluate statistical data about the database tables to be accessed, such as how many unique records are present in the table relative to the number of total rows. For example, if the index contains a considerable amount of duplicate values, then the database management application proceeds to select an appropriate duplicate-skipping method.

0032Once the database management application determines the database index is a reasonable candidate for adjusting duplicate-skipping methods, the database management application scans the index for distinct values within a given start and stop key range. As stated, the range may be every leaf page in the index, or alternatively, the range may be constrained by specified predicates. When scanning the index, the database management application records the low and high bounds and the number of keys of the current leaf page being scanned. The database management application may retrieve such information from the header of the leaf page. Further, during the initial scan of the index, the database management application designates the current index key.

0033At step <b>305</b>, the database management application generates a search index key having an arbitrary value that is used to locate the next distinct index key. The search key may be generated by masking index columns after the current key value with an appropriate highest value in the index (or an appropriate lowest value, if the scan is in a reverse direction). For example, assume that the current index key has a value corresponding to the last name “Smith.” The database management application may generate an arbitrary search index key having a last name value of “SmithZZZZ.”

0034At step <b>310</b>, the database management application determines the distance between a current index key and a next distinct index key. Because the location of the next distinct index key in the index is not immediately ascertainable, the database management application uses the generated search key to estimate the distance. More specifically, the database management application compares the generated search index key with the page bound of the current index leaf page. If the search index key value is greater than the current page bound, then the next distinct index key does not reside within the current index leaf page. However, if the search index key value is smaller (i.e., the search index key value is within the current leaf index page), then the next distinct key value resides within the current index leaf page.

0035At step <b>315</b>, the database management application selects a skipping method based on the estimated distance. In one embodiment, if the estimated distance is at least an index page apart, the database management application sets the duplicate-skipping method to perform a “big skip,” that is, the method skips through a larger range of key values than if the estimated distance spanned the same leaf index page. Otherwise, if the next distinct index key resides within the current leaf index page, the database management application sets the duplicate-skipping method to perform a smaller scale operation than the “big skip.” <figref idref="DRAWINGS">FIG. 4</figref> shows how the database management application selects the skipping method in further detail.

0036At step <b>320</b>, the database management application performs the selected skipping method to retrieve the next distinct index key. The database management application generates a table row result corresponding to the next distinct index key. At step <b>325</b>, database management application sets the next distinct index key as the current index key. At step <b>330</b>, the database management application determines whether the current index key is the last index key in the key range. If not, then the database management application sets the next distinct key as a new current key and repeats the method <b>300</b> until the database management application iterates completely through the key range.

0037<figref idref="DRAWINGS">FIG. 4</figref> illustrates a method <b>400</b> for selecting a duplicate-skipping method based on a distance between a current index key and a next distinct index key, according to one embodiment. Assume that the distance between the current index key and the next distinct index key is already estimated, using, e.g., the techniques described above. The database management application selects a duplicate-skipping method based on the estimated distance.

0038At step <b>405</b>, the database management application determines whether the estimated distance between current index key and the next distinct index key are at least a leaf index page apart. The distance may be estimated by comparing the generated search index key with the boundary of the current leaf page. If the distinct keys are separated by at least two leaf index pages, then the current index key has duplicate values that occupy a sizeable portion of the index. At step <b>410</b>, if the current and next index keys are at least two leaf pages apart, the database management application sets the skipping method as a “big skip” method. In one embodiment, under the “big skip” method, the database management application performs a binary search from the root of the index tree. Doing so allows the database management application to skip over a large amount of duplicate values without actually having to parse through each duplicate value of the current index key. Of course, the “big skip” method is not strictly limited to a binary search algorithm from the root of the index tree. Other search algorithms may be performed on the index to retrieve the next distinct index key.

0039If the current and next distinct index keys are within the same leaf index page, it is more efficient to use a method that does not require as much processing as a binary search from the root of the index tree. In some cases, the database management application may locate the next distinct index key by simply performing a “get-next” operation and iterating through an insignificant amount of duplicate values.

0040To determine whether to iterate through consecutive keys, the database management application determines whether the current index key and the next distinct index key are separated by a relatively low amount of duplicate keys. To do so, at step <b>415</b>, the database management application estimates the distance between the current index key and the generated search key. The estimated distance is compared with properties of the current leaf page. Such properties may be retrieved from the leaf index header and may include the number of index keys in the leaf page, the low bound of the leaf page, and the high bound of the leaf page.

0041The database management application may use the comparison to determine whether the current index key is “close” to the next distinct index key. For example, the index keys may be “close” if the leaf index page has relatively few index keys and the position of the current index key is located near the high bound of the index page. As another example, the index keys are not “close” if the leaf index page is relatively large, and the position of the current index key is located near the low bound of the index page, and the position of the next distinct index key is located near the high bound of the index page.

0042At step <b>425</b>, if the current index key and the next distinct index key is are separated by relatively few duplicate index keys, the database management application sets the method to perform a “get next” operation to iterate through consecutive index keys until reaching the next distinct index key.

0043At step <b>430</b>, if the current index key and the next distinct index key are separated by relatively many duplicate index keys, the database management application sets the skipping method as a “little skip” method. In one embodiment, under the “little skip” method, the database management application performs a binary search algorithm from the current index key within the index page to retrieve the next distinct index key. Of course, the “little skip” method is not limited to a binary search algorithm. Other search algorithms may also be applied to the index tree to retrieve the next distinct index key.

0044In one embodiment, the database management application may disable the “little skip” approach if, when executing the query, the database management application determines that the keys are mostly consecutive and each of the keys are retrieved through a “get next” operation. The database management application may re-enable the “big skip” and “little skip” methods if, at execution time, the database management application detects that duplicate values are repeated across index keys or across index leaf pages.

0045In the preceding, reference is made to embodiments of the invention. However, it should be understood that the invention is not limited to specific described embodiments. Instead, any combination of the following features and elements, whether related to different embodiments or not, is contemplated to implement and practice the invention. Furthermore, although embodiments of the invention may achieve advantages over other possible solutions and/or over the prior art, whether or not a particular advantage is achieved by a given embodiment is not limiting of the invention. Thus, the following aspects, features, embodiments and advantages are merely illustrative and are not considered elements or limitations of the appended claims except where explicitly recited in a claim(s). Likewise, reference to “the invention” shall not be construed as a generalization of any inventive subject matter disclosed herein and shall not be considered to be an element or limitation of the appended claims except where explicitly recited in a claim(s).

0046The present invention may be a system, a method, and/or a computer program product. The computer program product may include a computer readable storage medium (or media) having computer readable program instructions thereon for causing a processor to carry out aspects of the present invention.

0047The computer readable storage medium can be a tangible device that can retain and store instructions for use by an instruction execution device. The computer readable storage medium may be, for example, but is not limited to, an electronic storage device, a magnetic storage device, an optical storage device, an electromagnetic storage device, a semiconductor storage device, or any suitable combination of the foregoing. A non-exhaustive list of more specific examples of the computer readable storage medium includes the following: a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), a static random access memory (SRAM), a portable compact disc read-only memory (CD-ROM), a digital versatile disk (DVD), a memory stick, a floppy disk, a mechanically encoded device such as punch-cards or raised structures in a groove having instructions recorded thereon, and any suitable combination of the foregoing. A computer readable storage medium, as used herein, is not to be construed as being transitory signals per se, such as radio waves or other freely propagating electromagnetic waves, electromagnetic waves propagating through a waveguide or other transmission media (e.g., light pulses passing through a fiber-optic cable), or electrical signals transmitted through a wire.

0048Computer readable program instructions described herein can be downloaded to respective computing/processing devices from a computer readable storage medium or to an external computer or external storage device via a network, for example, the Internet, a local area network, a wide area network and/or a wireless network. The network may comprise copper transmission cables, optical transmission fibers, wireless transmission, routers, firewalls, switches, gateway computers and/or edge servers. A network adapter card or network interface in each computing/processing device receives computer readable program instructions from the network and forwards the computer readable program instructions for storage in a computer readable storage medium within the respective computing/processing device.

0049Computer readable program instructions for carrying out operations of the present invention may be assembler instructions, instruction-set-architecture (ISA) instructions, machine instructions, machine dependent instructions, microcode, firmware instructions, state-setting data, or either source code or object code written in any combination of one or more programming languages, including an object oriented programming language such as Java, Smalltalk, C++ or the like, and conventional procedural programming languages, such as the “C” programming language or similar programming languages. The computer readable program instructions may execute entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user's computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider). In some embodiments, electronic circuitry including, for example, programmable logic circuitry, field-programmable gate arrays (FPGA), or programmable logic arrays (PLA) may execute the computer readable program instructions by utilizing state information of the computer readable program instructions to personalize the electronic circuitry, in order to perform aspects of the present invention.

0050Aspects of the present invention are described herein with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer readable program instructions.

0051These computer readable program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks. These computer readable program instructions may also be stored in a computer readable storage medium that can direct a computer, a programmable data processing apparatus, and/or other devices to function in a particular manner, such that the computer readable storage medium having instructions stored therein comprises an article of manufacture including instructions which implement aspects of the function/act specified in the flowchart and/or block diagram block or blocks.

0052The computer readable program instructions may also be loaded onto a computer, other programmable data processing apparatus, or other device to cause a series of operational steps to be performed on the computer, other programmable apparatus or other device to produce a computer implemented process, such that the instructions which execute on the computer, other programmable apparatus, or other device implement the functions/acts specified in the flowchart and/or block diagram block or blocks.

0053The flowchart and block diagrams in the Figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods, and computer program products according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of instructions, which comprises one or more executable instructions for implementing the specified logical function(s). In some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or acts or carry out combinations of special purpose hardware and computer instructions.

0054As described, embodiments presented herein provide techniques for setting a duplicate-skipping method when executing a query statement. A database management application estimates a distance between two distinct index keys relative to leaf pages of the index. The database management application uses the estimated distance to determine an appropriate skipping method to perform when retrieving a next distinct index key. Advantageously, by varying the skipping methods based on distances between distinct keys, any possible overhead incurred from merely using the same duplicate-skipping method throughout the index scan is avoided.

0055While the foregoing is directed to embodiments of the present invention, other and further embodiments of the invention may be devised without departing from the basic scope thereof, and the scope thereof is determined by the claims that follow.