System and method for executing queries

Patent metadata

Field	Value
Publication number	US-9424310-B2
Application number	US-201414215949-A
Country	US
Kind code	B2
Filing date	Mar 17, 2014
Priority date	Oct 22, 2009
Publication date	Aug 23, 2016
Grant date	Aug 23, 2016

Abstract

There is provided a computer-implemented method of executing a query plan against a database. An exemplary method comprises accessing a first subset of rows of a database table using a direct access method for an index. The query plan may comprise the direct access method. The exemplary method also comprises determining a processing cost of accessing the first subset of rows. The exemplary method further comprises modifying the direct access method for the index in response to determining that the processing cost exceeds a specified threshold. Additionally, the exemplary method comprises accessing a second subset of rows of the database table using the modified direct access method.

First claim

What is claimed is:

1. A computer-implemented method of executing a query plan against a database, comprising:
accessing a first subset of rows of a database table using a direct access method for an index of the database table, wherein the query plan comprises the direct access method;
determining a processing cost of accessing the first subset of rows;
scanning sequentially the first subset of rows using a sequential access method, wherein the scan begins at a row accessed by the direct access method;
determining a processing cost of the sequential access method, wherein the processing cost is based on a number of consecutive rows accessed in the sequential access method for which a selection predicate is false;
modifying the direct access method for the index in response to determining that the processing cost of the sequential access method exceeds a specified threshold, wherein the specified threshold comprises a ratio of the processing cost of accessing the first subset of rows to the processing cost of the sequential access method; and
accessing a second subset of rows of the database table using the modified direct access method.

2. The method recited in claim 1 , wherein the direct access method comprises selecting one or more rows of the first subset from a page of data, using an initial number of columns of the index.

3. The method recited in claim 2 , wherein the modified direct access method comprises selecting one row of the page using a lesser number of columns than the initial number.

4. The method recited in claim 3 , comprising performing the sequential access method in association with performing the modified direct access method to access the first subset of rows at a processing cost less than the processing cost of the direct access method.

5. The method recited in claim 4 , wherein the sequential access method comprises scanning the page for the first subset of rows based on the selection predicate for a column of the index.

6. The method recited in claim 1 , wherein the index is represented by a balanced tree, wherein the balanced tree comprises index blocks representing a first number of columns of the index, wherein the direct access method uses the first number of columns.

7. The method recited in claim 1 , wherein a processing cost of accessing the second subset of rows is less than the processing cost of accessing the first subset of rows.

8. The method recited in claim 1 , wherein the second subset of rows comprises the first subset of rows.

9. The method recited in claim 8 , wherein the modified direct access method comprises using a different number of columns of the index than a number of columns of the index used by the direct access method.

10. A computer system for executing a query plan against a database, the computer system comprising:
a processor that executes stored instructions;
a cache memory comprising a balanced tree representing an index of a database table; and
a memory device that stores instructions, the memory device comprising:
computer-implemented code to access a first subset of rows of the database table using a direct access method for a first number of columns of the index represented in the balanced tree by scanning one or more rows of the first subset and determining whether a predicate is true for the scanned one or more rows of the first subset;
computer-implemented code to determine a processing cost accessing the first subset of rows, wherein the processing cost comprises a number of consecutive rows in the scanned one or more rows for which a predicate is false;
computer-implemented code to modify the direct access method in response to determining that the processing cost exceeds a specified threshold;
computer-implemented code to access a second subset of rows of the database table using the modified direct access method, wherein the modified direct access method uses a second number of columns of the index represented in the balanced tree; and
computer-implemented code adapted to maintain storage of the balanced tree in the cache memory.

11. The computer system recited in claim 10 , comprising one or more storage engine processes that improve cache replacement policies for B-tree maintenance based on the modified direct access method.

12. The computer system recited in claim 11 , the storage engine processes keeping lower-level B-tree nodes in a cache, and the second number of columns comprising an additional column.

13. The computer system of claim 11 , the second number of columns comprising one less column than the first number of columns.

14. A tangible, machine-readable medium that stores machine-readable instructions executable by a processor to execute a query plan against a database, the tangible, machine-readable medium comprising:
machine-readable instructions that, when executed by the processor, access a first subset of rows of a database table using a direct access method for an index of the database table, wherein the query plan comprises the direct access method;
machine-readable instructions that, when executed by the processor, determine a processing cost of accessing the first subset of rows;
machine-readable instructions that, when executed by the processor, modify the direct access method for the index in response to determining that the processing cost exceeds a specified threshold; and
machine-readable instructions that, when executed by the processor, access a first subset of rows of the database table by using the modified direct access method and a sequential access method.

15. The tangible, machine-readable medium recited in claim 14 , wherein the direct access method comprises machine-readable instructions that, when executed by the processor, access one or more rows of the first subset using a first number of columns of an index of the database table, and wherein the modified direct access method comprises machine-readable instructions that, when executed by the processor, access one or more rows of the second subset using a second number of columns of the index, wherein the first number is not equal to the second number.

16. The tangible, machine-readable medium recited in claim 14 , wherein the direct access method comprises machine-readable instructions that, when executed by the processor, access one or more rows of the first subset from a page of data, using an initial number of columns of the index.

17. The tangible, machine-readable medium recited in claim 16 , wherein the modified direct access method comprises machine-readable instructions that, when executed by the processor, access one row of the page of data using a lesser number of columns than the initial number.

18. The tangible, machine-readable medium recited in claim 17 , wherein the sequential access method comprises machine-readable instructions that, when executed by the processor, scan the page for the first subset of rows based on a selection predicate for a column of the index.

19. The tangible, machine-readable medium recited in claim 14 , wherein a processing cost of accessing the second subset of rows is less than the processing cost of accessing the first subset of rows.

20. The tangible, machine-readable medium recited in claim 14 , wherein the index is represented by a balanced tree, wherein the balanced tree comprises index blocks representing the first number of columns of the index.

Assignees

• Hewlett Packard Development Co Lp
• Hewlett Packard Entpr Dev Lp

Inventors

• Birdsall David W
• Jow Yung-Li L
• Graefe Goetz

Classifications

• G06F17/30463 Primary

  Physics · mapped topic

• G06F17/30466

  Physics · mapped topic

• G06F16/24544 Primary

  Join order optimisation · CPC title

• G06F16/24542 Primary

  Plan optimisation · CPC title