Index Maintenance in a Multi-Node Database

• US 20090265306A1
• Filed: 04/22/2008
• Published: 10/22/2009
• Est. Priority Date: 04/22/2008
• Status: Active Grant

• Current Assignee: Domo, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Darrington, David L., Barsness, Eric L., Santosuosso, John M., Peters, Amanda
• Granted Patent: US 8,090,710 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2471 Distributed queries

Abstract

Embodiments of the invention enable a database spread over multiple nodes to allow each node to have different indexes over the data in tables, depending on how each node would benefit (or not benefit) from having the index(es). When a database table is spread across the nodes of a multi-node or distributed system, each node may maintain only the portion of the index relevant to that node, if doing so would improve the performance of query processing operations on that node. Further, the database may periodically redistributed across the compute nodes based on index performance. Doing so allows the database system to intelligently trade off between consuming space for the index on a node and the usefulness of having an index on that node.

Claims

1. A method for improving the efficiency of database query processing on a distributed database, comprising:

receiving a query of the database, wherein the database includes a collection of data records subdivided into a plurality of database portions, wherein each of the plurality of database portions is stored on one of a plurality of compute nodes and wherein each compute node includes a respective partial index of the data records stored on the respective compute node, wherein the partial indexes are generated from an index of all the data records in the database, so that each partial index is limited to those data records on the respective compute node;

distributing the query to one or more compute nodes of the plurality of compute nodes for execution;

executing, by the one or more compute nodes, the query operation against the data records of the respective compute node using the respective partial index; and

during query execution, monitoring the use of the partial index stored on the first compute node in executing the database query.

2. The method of claim 1, further comprising:

refactoring the plurality of database portions of the collection of database records, based at least in part on the monitored use of the partial index;

distributing each of the plurality of re-factored database portions to one of the plurality of compute nodes;

generating an index for at least one of the re-factored database portions distributed to one of the plurality of compute nodes; and

storing the generated index on the compute node storing the database records reflected in the generated index.

3. The method of claim 2, wherein the index is generated by the compute node storing the records reflected in the generated index.

4. The method of claim 1, further comprising, upon determining the index did not improve query execution performance on the first compute node, discarding the partial index.

5. The method of claim 1, further comprising:

evaluating the database records stored on a second compute node;

evaluating the performance of query execution on the second compute node; and

based on the evaluations, generating an index for the database records stored on the second compute node.

6. The method of claim 1, wherein the index of the data records is represented as one of a b-tree, a balanced tree, and an encoded vector index.

7. The method of claim 1, wherein the plurality of compute nodes are configured to communicate over a toroidal mesh network connecting each respective compute node to a nearest 2N neighboring compute nodes in N dimensions.

8. A computer-readable storage medium containing a program which, when executed, performs an operation for improving the efficiency of database query processing on a distributed database, comprising:

receiving a query of the database, wherein the database includes a collection of data records subdivided into a plurality of database portions, wherein each of the plurality of database portions is stored on one of a plurality of compute nodes and wherein each compute node includes a respective partial index of the data records stored on the respective compute node, wherein the partial indexes are generated from an index of all the data records in the database, so that each partial index is limited to those data records on the respective compute node;

distributing the query to one or more compute nodes of the plurality of compute nodes for execution;

executing, by the one or more compute nodes, the query operation against the data records of the respective compute node using the respective partial index; and

during query execution, monitoring the use of the partial index stored on the first compute node in executing the database query.

9. The computer-readable storage medium of claim 8, wherein the operation further comprises:

refactoring the plurality of database portions of the collection of database records, based at least in part on the monitored use of the partial index;

distributing each of the plurality of re-factored database portions to one of the plurality of compute nodes;

generating an index for at least one of the re-factored database portions distributed to one of the plurality of compute nodes; and

storing the generated index on the compute node storing the database records reflected in the generated index.

10. The computer-readable storage medium of claim 9, wherein the index is generated by the compute node storing the records reflected in the generated index.

11. The computer-readable storage medium of claim 8, wherein the operation further comprises, upon determining the index did not improve query execution performance on the first compute node, discarding the partial index.

12. The computer-readable storage medium of claim 8, wherein the operation further comprises:

evaluating the database records stored on a second compute node;

evaluating the performance of query execution on the second compute node; and

based on the evaluations, generating an index for the database records stored on the second compute node.

13. The computer-readable storage medium of claim 8, wherein the index of the data records is represented as one of a b-tree, a balanced tree, and an encoded vector index.

14. The computer-readable storage medium of claim 8, wherein the plurality of compute nodes are configured to communicate over a toroidal mesh network connecting each respective compute node to a nearest 2N neighboring compute nodes in N dimensions.

15. A parallel computing system, comprising:

a plurality of compute nodes, each having at least a processor and a memory, wherein the memory on each node is configured to store a portion of an in-memory database; and

a service node configured to improve the efficiency of database query processing on a distributed database by performing the steps of;

receiving a query of the database, wherein the database includes a collection of data records subdivided into a plurality of database portions, wherein each of the plurality of database portions is stored on one of a plurality of compute nodes and wherein each compute node includes a respective partial index of the data records stored on the respective compute node, wherein the partial indexes are generated from an index of all the data records in the database, so that each partial index is limited to those data records on the respective compute node,

distributing the query to one or more compute nodes of the plurality of compute nodes for execution,

executing, by the one or more compute nodes, the query operation against the data records of the respective compute node using the respective partial index, and

during query execution, monitoring the use of the partial index stored on the first compute node in executing the database query.

16. The parallel computing system of claim 15, wherein the steps further comprise:

refactoring the plurality of database portions of the collection of database records, based at least in part on the monitored use of the partial index;

distributing each of the plurality of re-factored database portions to one of the plurality of compute nodes;

generating an index for at least one of the re-factored database portions distributed to one of the plurality of compute nodes; and

storing the generated index on the compute node storing the database records reflected in the generated index.

17. The parallel computing system of claim 16, wherein the index is generated by the compute node storing the records reflected in the generated index.

18. The parallel computing system of claim 15, wherein the steps further comprise, upon determining the index did not improve query execution performance on the first compute node, discarding the partial index.

19. The parallel computing system of claim 15, wherein the steps further comprise:

evaluating the database records stored on a second compute node;

evaluating the performance of query execution on the second compute node; and

based on the evaluations, generating an index for the database records stored on the second compute node.

20. The parallel computing system of claim 15, wherein the index of the data records is represented as one of a b-tree, a balanced tree, and an encoded vector index.

21. The parallel computing system of claim 15, wherein the plurality of compute nodes are configured to communicate over a toroidal mesh network connecting each respective compute node to a nearest 2N neighboring compute nodes in N dimensions.

22. The parallel computing system of claim 15, wherein the service node is one of the plurality of compute nodes.