Method and system for dynamically partitioning very large database indices on write-once tables
AssigneeSap SE
InventorIvan Schreter
Life of this patent
Estimating the term…
Abstract
Methods and systems for partitioning and dynamically merging a database index are described. A database index includes a single first-level index partition stored in a data cache. As the first-level index partition in the data cache reaches a predetermined size, it is copied to secondary storage and a new index partition is generated in the data cache. When the number of index partitions in secondary storage reaches some predetermined number, the index partitions are merged to create a single index partition of a higher level in a hierarchy of index partitions having an exponentially increasing size with each increase in level within the hierarchy.
Claims19
A processor-implemented method for partitioning a database index, the method comprising:
- after determining that a first-level index partition stored in a data cache exceeds a threshold size, performing a first-level partitioning operation to i) write the first-level index partition stored in the data cache to a secondary storage, and ii) generate a new first-level index partition in the data cache;
- and
- after determining that a number of first-level index partitions in the secondary storage has reached a predetermined number, performing a first-level merge operation to i) merge the predetermined number of first-level index partitions into a single second-level index partition, and ii) delete the predetermined number of first-level index partitions from the secondary storage.
A processor-implemented relational database management system comprising:
- an index partitioning module to perform a first-level partitioning operation upon determining that a first-level index partition stored in a data cache exceeds a threshold size, the first-level partitioning operation including i) writing the first-level index partition stored in the data cache to a secondary storage, and ii) generating a new first-level index partition in the data cache;
- and
- an index merging module to perform a first-level merge operation upon determining that a number of first-level index partitions in the secondary storage has reached a predetermined number, the first-level merge operation including i) merging the predetermined number of first-level index partitions into a single second-level index partition, and ii) deleting the predetermined number of first-level index partitions from the secondary storage.
A processor-implemented method comprising:
- receiving, at a query processing module, a query specifying data selection criterion;
- and
- utilizing a database index to process the query and to provide, from a database table, records satisfying the data selection criterion, the database index structured as a hierarchy of index partitions having a plurality of levels with one index partition at a first-level residing in a data cache and all other index partitions residing in secondary storage, each index partition structured as a B-tree and increasing exponentially in size with each increase in level within the hierarchy.
Dependencies are inferred from the claim text.