# US 2009/0265305 A1 · Partial Indexes for Multi-Node Database

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2009/0265305 A1
- Document ID: US20090265305A1
- Status: Published application
- Kind: A1
- Application number: 12/107,329
- Filed: 2008-04-22
- Published: 2009-10-22
- Earliest claimed: 2008-04-22
- Assignees: International Business Machines Corporation
- Inventors: Eric L. BARSNESS; David L. DARRINGTON; Amanda PETERS; John M. SANTOSUOSSO
- Web page: https://patentgrep.com/patent/US20090265305A1

## CPC

- G06F 16/278: {Data partitioning, e.g. horizontal or vertical partitioning}
- G06F 16/22: Indexing; Data structures therefor; Storage structures
- G06F 16/2471: {Distributed queries}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 1

A method of distributing a database across a plurality of compute nodes provided by a parallel computing system, comprising:
subdividing data records stored in the database to create a plurality of database portions, wherein the database includes an index of the data records;
distributing each of the plurality of database portions to one of the plurality of compute nodes;
subdividing the index to create a plurality of sub-indexes, wherein each sub-index provides an index of the data records stored in one of the plurality of database portions, to the exclusion of at least some records in the database; and
distributing at least one of the sub-indexes to the compute node storing the data records indexed by the at least one sub-index.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
receiving a database query of the records stored the compute node storing the data records indexed by the at least one sub-index;
executing the query operation against the data records using the at least one sub-index.

### Claim 3 (depends on 1)

The method of claim 1, further comprising, maintaining index usage statistics reflecting the use of the sub-index in processing database queries directed to the compute node storing the data records indexed by the at least one sub-index.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
generating an index for the database portion 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.

### Claim 5 (depends on 4)

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

### Claim 6 (depends on 1)

The method of claim 1, wherein the index for the database records are constrained by a distinct constraint, and wherein the distinct constraint is enforced each time a database query operation is performed on the database portions stored on one of the plurality of compute nodes.

### Claim 7 (depends on 1)

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.

### Claim 8 (depends on 1)

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.

### Claim 9

A computer readable storage medium containing a program which, when executed, performs an operation for distributing a database across a plurality of compute nodes provided by a parallel computing system, comprising:
subdividing data records stored in the database to create a plurality of database portions, wherein the database includes an index of the data records;
distributing each of the plurality of database portions to one of the plurality of compute nodes;
subdividing the index to create a plurality of sub-indexes, wherein each sub-index provides an index of the data records stored in one of the plurality of database portions, to the exclusion of at least some records in the database; and
distributing at least one of the sub-indexes to the compute node storing the data records indexed by the at least one sub-index.

### Claim 10 (depends on 9)

The computer readable storage medium of claim 9, wherein the operation further comprises:
receiving a database query of the records stored the compute node storing the data records indexed by the at least one sub-index;
executing the query operation against the data records using the at least one sub-index.

### Claim 11 (depends on 9)

The computer readable storage medium of claim 9, wherein the operation further comprises:
maintaining index usage statistics reflecting the use of the sub-index in processing database queries directed to the compute node storing the data records indexed by the at least one sub-index.

### Claim 12 (depends on 9)

The computer readable storage medium of claim 9, wherein the operation further comprises:
generating an index for the database portion 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.

### Claim 13 (depends on 12)

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

### Claim 14 (depends on 9)

The computer readable storage medium of claim 9, wherein the index for the database records are constrained by a distinct constraint, and wherein the distinct constraint is enforced each time a database query operation is performed on the database portions stored on one of the plurality of compute nodes.

### Claim 15 (depends on 9)

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

### Claim 16 (depends on 9)

The computer readable storage medium of claim 9, 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.

### Claim 17

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 distribute a database across the plurality of compute nodes by performing the steps of:
subdividing data records stored in the database to create a plurality of database portions, wherein the database includes an index of the data records,
distributing each of the plurality of database portions to one of the plurality of compute nodes,
subdividing the index to create a plurality of sub-indexes, wherein each sub-index provides an index of the data records stored in one of the plurality of database portions, to the exclusion of at least some records in the database, and
distributing at least one of the sub-indexes to the compute node storing the data records indexed by the at least one sub-index.

### Claim 18 (depends on 17)

The parallel computing system of claim 17, wherein the steps further comprise:
receiving a database query of the records stored the compute node storing the data records indexed by the at least one sub-index;
executing the query operation against the data records using the at least one sub-index.

### Claim 19 (depends on 17)

The parallel computing system of claim 17, wherein the steps further comprise, maintaining index usage statistics reflecting the use of the sub-index in processing database queries directed to the compute node storing the data records indexed by the at least one sub-index.

### Claim 20 (depends on 17)

The parallel computing system of claim 17, wherein the steps further comprise:
generating an index for the database portion 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.

### Claim 21 (depends on 20)

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

### Claim 22 (depends on 17)

The parallel computing system of claim 17, wherein the index for the database records are constrained by a distinct constraint, and wherein the distinct constraint is enforced each time a database query operation is performed on the database portions stored on one of the plurality of compute nodes.

### Claim 23 (depends on 17)

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

### Claim 24 (depends on 17)

The parallel computing system of claim 17, 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.

### Claim 25 (depends on 17)

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