Database system with improved methodology for page allocation

• US 6,470,360 B1
• Filed: 12/20/1999
• Issued: 10/22/2002
• Est. Priority Date: 12/20/1999
• Status: Expired due to Term

• Current Assignee: Sybase Incorporated (SAP SE)
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: Vaitheeswaran, Girish
• Primary Examiner(s): RONES, CHARLES
• Application Number:
  US09/467,738
• Time in Patent Office: 1,037 Days
• Field of Search: 707/205, 707/206, 707/2, 711/129
• US Class Current: 1/1
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

A database system providing a methodology for optimized page allocation is described. During page allocation in the system, once an allocation page with free space has been located in the system'"'"'s global allocation map or GAM (i.e., using routine page allocation steps), the page identifier for that allocation page is stored in a hint array, as part of that object'"'"'s (i.e., table'"'"'s) object descriptor or des. For a table undergoing a lot of splits (i.e., insert-intensive object), the system may store an array of allocation page “hints” (allocation page identifiers) in the des for that object (e.g., table). The array itself comprises a cache of slots (e.g., eight slots), each of which stores an allocation page identifier (“hint”) obtained from the GAM (from a GAM traversal occurring during the page allocation process) or is empty (i.e., has not been filled from the GAM and is therefore set to the initial value of null). For example, the first slot may store the page identifier for one allocation page. A second slot may store the page identifier for another, completely different allocation page, and so forth and so on. On subsequent passes through the page allocation process, the system can, rather than going to the GAM, randomly select (e.g., randomly hash on) a particular slot of the cache. In this manner, the incoming clients will, instead of competing for the same first-available allocation page, randomly select among multiple available allocation pages. Since each allocation page itself is protected by a separate latch, the system is able to decrease contention during the page allocation process by randomly accessing different elements of the “hint” array. In this manner, the system can avoid the computationally-expensive process of page allocation that is usually required as well as avoid contention for the first-available allocation page.

Claims

1. In a database system having a database comprising database objects, each object itself comprising a plurality of pages, the database including allocation pages for tracking allocation of pages for objects, an improved method for allocating data pages, the method comprising:

maintaining an allocation data structure indicating allocation pages that references pages with free space;

maintaining on a per object basis a cache memory comprising a plurality of slots, each for storing a page identifier indicating an allocation page that reference pages with suitable free space;

in response to a database operation requiring allocation of a page for a particular object, randomly selecting one of the slots of said cache memory for that particular object;

obtaining an allocation page identifier from the selected slot, if an identifier is available from that slot, otherwise, obtaining an allocation page identifier from said allocation data structure; and

accessing the corresponding allocation page referenced by the obtained allocation page identifier for allocating a new data page for the particular object.

2. The method of claim 1, further comprising:

storing said obtained allocation page identifier in the selected slot for subsequent retrieval from the cache memory.

3. The method of claim 1, wherein said particular object comprises a database table.

4. The method of claim 1, further comprising:

repeating the steps for a plurality of database operations, wherein most of the allocation page identifiers obtained are retrieved from the cache memory.

5. The method of claim 1, wherein a plurality of cache memories are created, each one specific to an object requiring page allocation.

13. The method of claim 1, wherein said cache memory comprises at least 8 slots.

6. In a database system having a database comprising database tables, each table itself comprising a plurality of data pages, the database including allocation pages for tracking allocation of data pages, an improved method for allocating data pages, the method comprising:

maintaining an allocation map storing allocation page identifiers for allocation pages, including storing information about allocation pages that reference data pages with free space available;

maintaining a cache memory comprising a plurality of slots for storing allocation page identifiers obtained from the map;

in response to a request from a client for page allocation, randomly selecting one of the slots of said cache memory;

if the selected slot is empty,

obtaining an allocation page identifier from said allocation map, and

storing said obtained allocation page identifier in the selected slot for subsequent retrieval from the cache memory;

if the slot is not empty, obtaining an allocation page identifier that is stored by the slot;

accessing the particular allocation page referenced by the allocation page identifier that is obtained; and

based on the access to the particular allocation page, allocating a new data page.

7. The method of claim 6, wherein said cache memory is associated with a particular table.

8. The method of claim 6, further comprising:

repeating the steps for a plurality of client requests, wherein most of the requests can be satisfied by page identifiers present in the cache memory.

9. The method of claim 6, wherein a plurality of cache memories are created, each one specific to an object requiring page allocation.

10. The method of claim 6, wherein each allocation page references 256 data pages.

11. The method of claim 6, wherein said allocation map stores information indicating whether a particular allocation page referenced by the allocation map references data pages with available free space.

12. The method of claim 6, wherein each data page stores 2K.

14. The method of claim 6, wherein each slot initially stores a null value for indicating that the slot is empty.

15. The method of claim 6, wherein said step of randomly selecting includes invoking a random number function.

16. The method of claim 6, wherein said step of obtaining an allocation page identifier from said allocation map includes:

scanning said allocation map for locating an allocation page that references data pages having free space.

17. The method of claim 6, wherein said allocation map comprises a bit map.

18. The method of claim 17, wherein, in said allocation map, a bit is set for those allocation pages corresponding to data pages not having available free space.

19. The method of claim 6, wherein said data pages exist in a single shared memory available to a plurality of processes.

20. The method of claim 6, wherein access to each allocation page is protected by a latch.

21. A database system with improved allocation of data pages, the system comprising:

a computer providing a database comprising database tables, each table itself comprising a plurality of data pages, the database including allocation pages for tracking allocation of data pages;

an allocation map for storing allocation page identifiers for allocation pages, including storing information about allocation pages that reference data pages with free space available;

a cache memory comprising a plurality of slots for storing allocation page identifiers obtained from the map;

program logic for randomly selecting one of the slots of said cache memory in response to a request from a client for page allocation and, if the selected slot is empty, obtaining an allocation page identifier from said allocation map and storing said obtained allocation page identifier in the selected slot for subsequent retrieval from the cache memory;

program logic for obtaining an allocation page identifier that is stored by the slot if the slot is not empty; and

program logic for accessing the particular allocation page referenced by the obtained allocation page identifier and, based on the access to the particular allocation page, allocating a new data page.

22. The system of claim 21, wherein said cache memory is associated with a particular table.

23. The system of claim 21, wherein said computer includes multiple processors.

24. The system of claim 21, further comprising a plurality of cache memories, each one specific to an object requiring page allocation.

25. The system of claim 21, wherein each allocation page references 256 data pages.

26. The system of claim 21, wherein said allocation map stores information indicating whether a particular allocation page referenced by the allocation map references data pages with available free space.

27. The system of claim 21, wherein each data page stores 2K.

28. The system of claim 21, wherein said cache memory comprises at least 8 slots.

29. The system of claim 21, wherein each slot initially stores a null value for indicating that the slot is empty.

30. The system of claim 21, wherein said program logic for randomly selecting includes invoking a random number function.

31. The system of claim 21, wherein said program logic for obtaining an allocation page identifier from said allocation map includes:

program logic for scanning said allocation map for locating an allocation page that references data pages having free space.

32. The system of claim 21, wherein said allocation map comprises a bit map.

33. The system of claim 32, wherein, in said allocation map, a bit is set for those allocation pages corresponding to data pages not having available free space.

34. The system of claim 21, wherein said data pages exist in a single shared memory available to a plurality of processes.

35. The system of claim 21, wherein access to each allocation page is protected by a latch.