Method of storing elements in a database

• US 6,308,169 B1
• Filed: 07/15/1998
• Issued: 10/23/2001
• Est. Priority Date: 07/21/1997
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Dabaghi, Ataullah, Ronström, Ulf Mikael
• Primary Examiner(s): Shah, Sanjiv
• Application Number:
  US09/115,948
• Time in Patent Office: 1,196 Days
• Field of Search: 707/2, 707/4, 707/101, 707/103, 707/202, 707/206, 707/3, 707/5, 382/253
• US Class Current: 707/610
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

The present invention relates to a method of storing elements in a database and of finding such stored elements. A reference to a storage space intended for the storage of a data element in the database is calculated by means of a mathematical function, wherein the function input data is an external key belonging to the element, and wherein the result obtained with the mathematical function points to an internal position of the element in the database. The result is divided into at least three parts (A, B, C). A first part (A) constitutes a reference to a fragment (A4) belonging to the database, a second part (B) constitutes a reference to a page (B4) within the fragment (A4), and a third part (C) constitutes a reference to a so-called bucket (C4) belonging to the page (B4). A bucket (C4) is comprised of at least one container in which the element can be stored, or is stored. The containers are given a size that corresponds to the size of a container header and the elements belonging to the container, said size varying with the amount of elements concerned. The size of a maximum container is limited so as to be at the most equal to the amount of data-information that can be read at one time into a cache memory belonging to a processor that operates within the database or that uses the database.

Claims

1. A method of storing elements in a database and of finding such stored elements, wherein a reference to the storage space intended for the storage of a data element in the database is calculated by means of a mathematical function, wherein the function input data is comprised of an external key belonging to said element, wherein the result obtained with said mathematical function points to an internal position in the database for said element, and wherein the result is divided into different parts, wherein said result is divided into at least three parts, in that a first part constitutes a direct or indirect reference to a fragment belonging to said database;

in that a second part constitutes a direct or indirect reference to a page in said fragment;

in that a third part constitutes a direct or indirect reference to a so-called bucket belonging to said page;

in that said bucket includes at least one container in which said element can be stored, or is already stored, or wherein a direct or indirect reference to said element is stored;

in that the size of a maximum-size container is limited so as to be at the most equal to the amount of data information that can be read at one time into a cache memory belonging to a processor operating within the database or utilising said database; and

in that, where the time taken to process the amount of information that can be read at one time into a cache memory exceeds the time for a cache-miss, the maximum-growth size of a container is limited so that the time taken to process a maximum-size container will be less than the time lapse for a cache-miss, regardless of how much data-information can be read into the cache memory at a time.

2. A method according to claim 1, wherein a direct reference is comprised of an internal address that points directly to an intended position or via a mathematical function;

and in that an indirect reference constitutes a pointer which points to a table in which a relevant internal address that points directly to the intended position is available.

3. A method according to claim 1, wherein said first part constitutes an indirect reference to all replicas that belong to said fragment.

4. A method according to claim 1, wherein said second part points to a register;

and in that said register is comprised of a vector of pointers that point to different pages.

5. A method according to claim 1, wherein said third parts points to a relevant bucket belonging to said page;

and in that pointing is effected via a mathematical function.

6. A method according to claim 1, wherein respective buckets include a container and possibly also an overfill container belonging to a respective bucket.

7. A method according to claim 6, wherein the whole of the container indicated by said mathematical function is read into a cache memory belonging to a processor that searches for an element.

8. A method according to claim 7, wherein the whole of the overfill container is read into said cache memory, when said element is not found in the container that has been read into said cache memory.

9. A method according to claim 1, wherein respective containers are allocated a size which corresponds to the size of the header and to the size of elements that belong to said container;

and in that said size varies with the number of elements belonging to said container.

10. A method according to claim 9, wherein said page is divided into a number of buffers;

in that respective buffers are divided into a first part and a second part of a so-called availability-list-limit;

in that respective buffers are adapted to include a maximum-size container that accommodates the whole of said first and said second parts, or a first non-maximum container with a start in said first part that extends into said second part, or a first non-maximum container with a start in said first part that does not extend into said second part, and a possible second non-maximum container with a start in said second part.

11. A method according to claim 1, wherein said page is divided into a number of buffers;

in that respective buffers are divided into a first part and a second part of a so-called availability-list-limit;

in that respective buffers are adapted to include a maximum-size container that accommodates the whole of said first and said second parts, or a first non-maximum container with a start in said first part that extends into said second part, or a first non-maximum container with a start in said first part that does not extend into said second part, and a possible second non-maximum container with a start in said second part.

12. A method according to claim 11, wherein the check as to whether a memory space within a buffer shall be divided between two containers that share a common buffer is assigned to said two containers, regardless of whether or not the availability-list-limit is exceeded by one or the other of said containers.

13. A method according to claim 11, wherein a first number of buffers is comprised of static buffers;

in that a second number of buffers is comprised of free buffers;

in that the first part belonging to said static buffers is adapted to include a container; and

in that said second part belonging to said static buffers and both parts belonging to said free buffers are adapted to include an overfill container.

14. A method according to claim 13, wherein a container placed within a first part starts at the beginning of said first part and when a further element is added to said container grows towards the centre of the associated buffer;

and in that a container that is placed within a second part starts at the end of said second part and grows towards the centre of the associated buffer when a further element is added to the container.

15. A method according to claim 13, wherein a relevant bucket is adapted to include an overfill container when a further element is allocated to a maximum sized container belonging to said bucket;

and in that said further element is allocated a position within said overfill container.

16. A method according to claim 15 wherein said overfill container is allocated a position within a part that is available on said availability list;

and in that said available part is removed from said list at the time of said allocation.

17. A method according to claim 16, wherein said header includes four information carrying fields, of which a first information carrying field includes information concerning the size of said container, and in that when the bucket includes only one container:

said second information carrying field indicates that a possible overfill container exists on the same page;

the third information carrying field indicates that no overfill container exists;

the fourth information field is not used;

in that when the bucket includes a container and an overfill container on the same page;

the second information carrying field indicates that a possible overfill container exists on the same page;

the third information carrying field indicates that an overfill container exists;

the fourth information carrying field points to said overfill container;

in that when said bucket includes an overfill container on said overfill page;

the second information carrying field indicates an overfill container exists on said overfill page;

the third information carrying field includes a pointer which points to said overfill page;

said fourth information carrying field includes a pointer that points to said overfill container; and

in that the size of respective fields is adapted to respective situations; and

in that elements belonging to said container are allocated positions immediately behind said header and after one another in said container.

18. A method according to claim 17, wherein the whole of the overfill container is read into said cache memory, when said element is not found in the container that has been read into said cache memory.

19. A method according to claim 15 wherein one of the pages belonging to said fragment is an overfill page;

in that said overfill page includes solely free buffers; and

in that said overfill container is allocated a position within a part belonging to a buffer on said overfill page when no parts are available in the availability list.

20. A method according to claim 19, wherein said header includes four information carrying fields, of which a first information carrying field includes information concerning the size of said container, and in that when the bucket includes only one container:

said second information carrying field indicates that a possible overfill container exists on the same page;

the third information carrying field indicates that no overfill container exists;

the fourth information field is not used;

in that when the bucket includes a container and an overfill container on the same page;

the second information carrying field indicates that a possible overfill container exists on the same page;

the third information carrying field indicates that an overfill container exists;

the fourth information carrying field points to said overfill container;

in that when said bucket includes an overfill container on said overfill page;

the second information carrying field indicates that an overfill container exists on said overfill page;

the third information carrying field includes a pointer which points to said overfill page;

said fourth information carrying field includes a pointer that points to said overfill container; and

in that the size of the respective fields is adapted to respective situations; and

in that elements belonging to said container are allocated positions immediately behind said header and after one another in said container.

21. A method according to claim 13, wherein an availability list is adapted to include all available second parts belonging to said static buffers and all available first and second parts belonging to said free buffers on said page.

22. A method according to claim 21, wherein an available second part belonging to a buffer is removed from said availability list when a non-maximum container within a corresponding first part exceeds the availability-list-limit with respect to size.

23. A method according to claim 22 wherein the introduction of an hysteresis which, when an available second part shall be removed from or added to said availability list in conjunction with an increase or decrease in the size of a container within said first part, causes a second part to be removed from said availability list after a container within said first part has exceeded the availability-list-limit by a predetermined value;

and in that a second part is added to the availability list after a container within said first part has decreased and lies beneath said availability-list-limit by a predetermined value.

24. A method according to claim 22, wherein said overfill container is allocated a position within a part that is available on said availability list;

and in that said available part is removed from said list at the time of said allocation.

25. A method according to claim 22, wherein one of the pages belonging to said fragment is an overfill page;

in that said overfill page includes solely free buffers; and

in that said overfill container is allocated a position within a part belonging to a buffer on said overfill page when no parts are available in the availability list.

26. A method according to claim 21, wherein an available second part belonging to a buffer is added to the availability list when a container within a corresponding first part that has earlier exceeded said availability-list-limit with respect to size decreases and no longer exceeds said limit.

27. A method according to claim 26, wherein the introduction of an hysteresis which, when an available second part shall be removed from or added to said availability list in conjunction with an increase or decrease in the size of a container within said first part, causes a second part to be removed from said availability list after a container within said first part has exceeded the availability-list-limit by a predetermined value;

and in that a second part is added to the availability list after a container within said first part has decreased and lies beneath said availability-list-limit by a predetermined value.

28. A method according to claim 1, wherein said element includes a header with five groups of information;

in that when said element is available for transactions a first group will include a part of the result obtained with said mathematical function, a second group will comprise element status bits, a third group will comprise information to the effect that the element is not locked, a fourth group will include information relating to the length of a local key belonging to said element, a fifth group will include information relating to the length of an element key belonging to said element; and

in that said element also includes said local key and said element key.

29. A method according to claim 28, wherein when the element is locked against transactions due to an ongoing transaction that affects said element, the first and second groups together will include a pointer that points to a transaction register belonging to said transaction;

in that said transaction register includes said part of the result obtained with said mathematical function, said status bits, and the type of lock that has been applied to said element;

in that said third group includes information to the effect that said element is locked;

in that said fourth group includes information relating to the length of said local key; and

in that said fifth group includes information relating to the length of said element key.

30. A method according to claim 29, wherein said header is comprised of four bytes;

in that said first group comprises 19 bits, said second group comprises four bits, said third group comprises 1 bit, said fourth group comprises four bits, and said fifth group comprises four bits.

31. A method according to claim 28, wherein said status bits are used in element replicating processes, such as in replicating said fragment;

in that respective bits indicate whether or not said element has been replicated; and

in that a plurality of simultaneous replicating processes each use their respective status bit.

32. A method according to claim 28, wherein said part of the result obtained with said mathematical function is used in fragment dividing processes and fragment combining processes.

33. A method according to claim 1, wherein said page is divided into a number of buffers;

in that respective buffers are divided into a first part and a second part of a so-called availability-list-limit;

in that respective buffers are adapted to include a maximum-size container that accommodates the whole of said first and said second parts, or a first non-maximum container with a start in said first part that extends into said second part, or a first non-maximum container with a start in said first part that does not extend into said second part, and a possible second non-maximum container with a start in said second part.