System and method for use of lock-less techniques with a multidimensional database
AssigneeOracle International Corporation
InventorsYoung Joon Kim, Vilas Ketkar, Shubhagam Gupta, Haritha Gongalore
Life of this patent
Estimating the term…
Abstract
In accordance with an embodiment, described herein is a system and method for use of lock-less data structures and processes with a multidimensional database computing environment. Lock-less algorithms or processes can be implemented with specific hardware-level instructions so as to provide atomicity. A memory stores an index cache retaining a plurality of index pages of the multidimensional database. A hash table indexes index pages in the index cache, wherein the hash table is accessible by a plurality of threads in parallel through application of the lock-less process.
Claims20
A method for supporting data access in a database server within a multidimensional database environment, the database server comprising a processor and a memory and having access to a storage containing a plurality of data blocks wherein each of the plurality of data blocks is associated with a corresponding index page and a key, the method comprising:
- providing, in said memory, a hash table comprising a plurality of linked lists and a plurality of buckets, wherein one of said plurality of linked lists is associated with each of the plurality of buckets;
- providing an index cache in said memory;
- accessing the index cache concurrently by a plurality of threads;
- for each thread, of the plurality of threads:
- commencing an operation against a particular data block of the plurality of data blocks, wherein the particular data block is associated with a particular key and a particular index page;
- identifying in the hash table a particular bucket associated with the particular index page by performing a hash function on the particular key associated with the particular data block;
- traversing the linked list associated with the identified particular bucket using a compare-and-swap function that executes atomically to search for the particular index page corresponding to the data block;
- responsive to the search finding the particular index page corresponding to the data block, returning a pointer to the data block in said index cache from the index page corresponding to the data block in said index cache;
- responsive to the search not finding the particular index page corresponding to the data block, loading the index page corresponding to the data block from said storage into said index cache.
A system for supporting data access within a multidimensional database environment, the method comprising:
- a database server comprising a processor and a memory and having access to a storage containing a plurality of data blocks wherein each of the plurality of data blocks is associated with a corresponding index page and a key;
- a hash table in said memory of the database server comprising a plurality of linked lists and a plurality of buckets, wherein one of said plurality of linked lists is associated with each of the plurality of buckets;
- an index cache in said memory of the database server;
- a plurality of threads operating on said database server to access the index cache concurrently;
- wherein each of the plurality of threads is configured to:
- commence an operation against a particular data block of the plurality of data blocks, wherein the particular data block is associated with a particular key and a particular index page;
- identify in the hash table a particular bucket associated with the particular index page by performing a hash function on the particular key associated with the particular data block;
- traverse the linked list associated with the identified particular bucket using a compare-and-swap function that executes atomically to search for the particular index page corresponding to the data block;
- responsive to the search finding the particular index page corresponding to the data block, return a pointer to the data block in said index cache from the index page corresponding to the data block in said index cache;
- responsive to the search not finding the particular index page corresponding to the data block, load the index page corresponding to the data block from said storage into said index cache.
A non-transitory computer-readable medium having instructions stored thereon for supporting data access in a database server within a multidimensional database environment server comprising a processor and a memory and having access to a storage containing a plurality of data blocks each associated with a corresponding index page and a key, which instructions, when executed on the database server, cause the database server to perform steps comprising:
- providing, in said memory, a hash table comprising a plurality of linked lists and a plurality of buckets, wherein one of said plurality of linked lists is associated with each of the plurality of buckets;
- providing an index cache in said memory;
- accessing the index cache concurrently by a plurality of threads;
- for each thread, of the plurality of threads:
- commencing an operation against a particular data block of the plurality of data blocks, wherein the particular data block is associated with a particular key and a particular index page;
- identifying in the hash table a particular bucket associated with the particular index page by performing a hash function on the particular key associated with the particular data block;
- traversing the linked list associated with the identified particular bucket using a compare-and-swap function that executes atomically to search for the particular index page corresponding to the data block;
- responsive to the search finding the particular index page corresponding to the data block, returning a pointer to the data block in said index cache from the index page corresponding to the data block in said index cache;
- responsive to the search not finding the particular index page corresponding to the data block, loading the index page corresponding to the data block from said storage into said index cache.
Dependencies are inferred from the claim text.