System and method for retrieving information from a database

• US 20040062106A1
• Filed: 09/27/2002
• Published: 04/01/2004
• Est. Priority Date: 09/27/2002
• Status: Active Grant

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: Teradata US, Inc. (Teradata Corporation)
• Inventors: Ramesh, Bhashyam, Cohen, Steven B., Catozzi, John R.
• Granted Patent: US 7,203,691 B2
• Time in Patent Office: Days
• US Class Current: 365/202
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method for retrieving information from a database includes identifying a cylinder. The cylinder includes a plurality of data segments. The method also includes retrieving the plurality of data segments from the cylinder during a single retrieval operation. In addition, the method includes storing the plurality of data segments in a cache.

Claims

1. A method for retrieving information from a database, comprising:

identifying a cylinder comprising a plurality of data segments;

retrieving the plurality of data segments from the cylinder during a single retrieval operation; and

storing the plurality of data segments in a cache.

2. The method of claim 1, further comprising retrieving an index associated with the cylinder during a second retrieval operation, wherein retrieving the plurality of data segments comprises retrieving the plurality of data segments using the index.

3. The method of claim 1, wherein storing the plurality of data segments comprises storing the plurality of data segments in one of a plurality of slots in the cache.

4. The method of claim 3, further comprising:

generating at least one segment descriptor block associated with at least one of the data segments; and

generating a cylinder descriptor block associated with the slot in which the data segments are stored.

5. The method of claim 4, wherein one of the segment descriptor blocks comprises:

a first pointer identifying a location of the associated data segment in the cache;

a slot number of the slot in which the data segment is stored; and

at least one second pointer identifying at least one other of the segment descriptor blocks.

6. The method of claim 4, further comprising:

selecting at least one of a plurality of hash buckets, each hash bucket associated with a first chain and a second chain; and

inserting each of the segment descriptor blocks into the first chain of the at least one hash bucket.

7. The method of claim 6, further comprising:

moving one of the segment descriptor blocks from one of the first chains to one of the second chains when the data segment associated with the segment descriptor block is accessed; and

moving the segment descriptor block back to one of the first chains when the data segment associated with the segment descriptor block is no longer being accessed.

8. The method of claim 4, wherein generating one of the segment descriptor blocks comprises:

determining if one of the data segments is already in the cache; and

generating the segment descriptor block if the data segment is not already in the cache.

9. The method of claim 4, wherein the cylinder descriptor block comprises:

a slot number of the slot in which the data segments are stored;

a position of the slot in the cache;

a number of segment descriptor blocks; and

at least one pointer identifying at least one of the segment descriptor blocks, the segment descriptor blocks forming a chain.

10. The method of claim 3, wherein:

the cylinder comprises a first cylinder associated with a scan of one or more database tables; and

further comprising;

determining if any slot is storing a second cylinder associated with the scan of the one or more tables and if so using the slot to store the first cylinder;

determining if any of the slots are releasable when none of the slots are storing a second cylinder associated with the scan of the one or more tables;

using a releasable slot as the slot for the first cylinder; and

loading the plurality of data segments individually if no slot for the first cylinder is found.

11. The method of claim 3, further comprising releasing the slot in response to an explicit or implicit request.

12. The method of claim 11, wherein:

the explicit request comprises at least one of a request to release the slot and termination of a process that requested the cylinder; and

the implicit request comprises a lack of a process accessing any of the retrieved data segments for a specified amount of time.

13. The method of claim 1, wherein identifying the cylinder comprises:

receiving a request for at least a portion of information stored in the cylinder; and

identifying the cylinder using the request.

14. The method of claim 13, wherein retrieving the plurality of data segments from the cylinder comprises:

identifying the plurality of data segments in the cylinder, the plurality of data segments associated with the requested information;

identifying a beginning address associated with one of the data segments;

identifying an ending address associated with another of the data segments; and

retrieving all contents of the cylinder between the beginning and ending addresses.

15. A system for retrieving information from a database, comprising:

logic encoded on at least one computer readable medium; and

the logic operable when executed to;

identify a cylinder comprising a plurality of data segments;

retrieve the plurality of data segments from the cylinder during a single retrieval operation; and

store the plurality of data segments in a cache.

16. The system of claim 15, wherein:

the logic is further operable to retrieve an index associated with the cylinder during a second retrieval operation; and

the logic is operable to retrieve the plurality of data segments using the index.

17. The system of claim 15, wherein the logic is operable to store the plurality of data segments in one of a plurality of slots in the cache.

18. The system of claim 17, wherein the logic is further operable to:

generate at least one segment descriptor block associated with at least one of the retrieved data segments; and

generate a cylinder descriptor block associated with the slot in which the data segments are stored.

19. The system of claim 18, wherein one of the segment descriptor blocks comprises:

a first pointer identifying a location of the associated data segment in the cache;

a slot number of the slot in which the data segment is stored; and

at least one second pointer identifying at least one other of the segment descriptor blocks.

20. The system of claim 18, wherein the logic is further operable to:

select at least one of a plurality of hash buckets, each hash bucket associated with a first chain and a second chain;

insert each of the segment descriptor blocks into the first chain of the at least one hash bucket;

move one of the segment descriptor blocks from one of the first chains to one of the second chains when the data segment associated with the segment descriptor block is accessed; and

move the segment descriptor block back to one of the first chains when the data segment associated with the segment descriptor block is no longer being accessed.

21. The system of claim 18, wherein the cylinder descriptor block comprises:

a slot number of the slot in which the data segments are stored;

a position of the slot in the cache;

a number of segment descriptor blocks; and

at least one pointer identifying at least one of the segment descriptor blocks, the segment descriptor blocks forming a chain.

22. The system of claim 17, wherein:

the cylinder comprises a first cylinder associated with a scan of one or more database tables; and

the logic is further operable to;

determine if any slot is storing a second cylinder associated with the scan of the one or more tables and if so using the slot to store the first cylinder;

determine if any of the slots are releasable when none of the slots are storing a second cylinder associated with the scan of the one or more tables;

use a releasable slot as the slot for the first cylinder; and

load the plurality of data segments individually if no slot for the first cylinder is found.

23. The system of claim 17, wherein:

the logic is further operable to release the slot in response to an explicit or implicit request;

the explicit request comprises at least one of a request to release the slot and termination of a process that requested the cylinder; and

the implicit request comprises a lack of a process accessing any of the retrieved data segments for a specified amount of time.

24. The system of claim 15, wherein the logic is operable to identify the cylinder and retrieve the plurality of data segments by:

receiving a request for at least a portion of information stored in the cylinder;

identifying the cylinder using the request.

identifying the plurality of data segments in the cylinder, the plurality of data segments associated with the requested information;

identifying a beginning address associated with one of the data segments;

identifying an ending address associated with another of the data segments; and

retrieving all contents of the cylinder between the beginning and ending addresses.

25. A system for retrieving information from a database, comprising:

a memory comprising a plurality of slots, each slot operable to store at least a portion of one of a plurality of cylinders; and

one or more processors collectively operable to;

identify one of the cylinders, the identified cylinder comprising a plurality of data segments;

retrieve the plurality of data segments from the cylinder during a single retrieval operation; and

store the plurality of data segments in one of the slots.

26. The system of claim 25, wherein:

the one or more processors are further collectively operable to retrieve an index associated with the cylinder during a second retrieval operation; and

the one or more processors are collectively operable to retrieve the plurality of data segments using the index.

27. The system of claim 25, wherein the one or more processors are further collectively operable to:

generate at least one segment descriptor block associated with at least one of the retrieved data segments; and

generate a cylinder descriptor block associated with the slot in which the data segments are stored.

28. The system of claim 27, wherein one of the segment descriptor blocks comprises:

a first pointer identifying a location of the associated data segment in the cache;

a slot number of the slot in which the data segment is stored; and

at least one second pointer identifying at least one other of the segment descriptor blocks.

29. The system of claim 27, wherein the one or more processors are further collectively operable to:

select at least one of a plurality of hash buckets, each hash bucket associated with a first chain and a second chain;

insert each of the segment descriptor blocks into the first chain of the at least one hash bucket;

move one of the segment descriptor blocks from one of the first chains to one of the second chains when the data segment associated with the segment descriptor block is accessed; and

move the segment descriptor block back to one of the first chains when the data segment associated with the segment descriptor block is no longer being accessed.

30. The system of claim 27, wherein the cylinder descriptor block comprises:

a slot number of the slot in which the data segments are stored;

a position of the slot in the cache;

a number of segment descriptor blocks; and

at least one pointer identifying at least one of the segment descriptor blocks, the segment descriptor blocks forming a chain.

31. The system of claim 25, wherein:

the cylinder comprises a first cylinder associated with a scan of one or more database tables; and

the one or more processors are further collectively operable to;

determine if any slot is storing a second cylinder associated with the scan of the one or more tables and if so using the slot to store the first cylinder;

determine if any of the slots are releasable when none of the slots are storing a second cylinder associated with the scan of the one or more tables;

use a releasable slot as the slot for the first cylinder; and

load the plurality of data segments individually if no slot for the first cylinder is found.

32. The system of claim 25, wherein:

the one or more processors are further collectively operable to release the slot in response to an explicit or implicit request;

the explicit request comprises at least one of a request to release the slot and termination of a process that requested the cylinder; and

the implicit request comprises a lack of a process accessing any of the retrieved data segments for a specified amount of time.

33. The system of claim 25, wherein the one or more processors are collectively operable to identify the cylinder and retrieve the plurality of data segments by:

receiving a request for at least a portion of information stored in the cylinder;

identifying the cylinder using the request.

identifying the plurality of data segments in the cylinder, the plurality of data segments associated with the requested information;

identifying a beginning address associated with one of the data segments;

identifying an ending address associated with another of the data segments; and

retrieving all contents of the cylinder between the beginning and ending addresses.

34. A computer-readable medium containing computer-executable code for instructing a computer to:

identify a cylinder comprising a plurality of data segments;

retrieve the plurality of data segments from the cylinder during a single retrieval operation; and

store the plurality of data segments in a cache.

35. A database management system, comprising:

a massively parallel processing system comprising;

one or more nodes;

a plurality of processors, each of the one or more nodes providing access to one or more processors; and

a plurality of virtual processes, each of the one or more processors providing access to one or more virtual processes;

a set of one or more database tables residing on the one or more nodes, the one or more database tables containing information organized by geographic location; and

one or more of the plurality of virtual processes operable to;

identify a cylinder comprising a plurality of data segments, the plurality of data segments forming at least a portion of at least one of the database tables;

retrieve the plurality of data segments from the cylinder during a single retrieval operation; and

store the plurality of data segments in a cache.

36. A method for retrieving information from a database, comprising:

retrieving a plurality of data segments from a cylinder in a single operation;

generating a segment descriptor block for each of at least some of the retrieved data segments, each segment descriptor block identifying a location of a corresponding data segment in a cache;

inserting each of the segment descriptor blocks into at least one of a plurality of first chains; and

moving one of the segment descriptor blocks from one of the first chains to one of a plurality of second chains when the data segment associated with the segment descriptor block is accessed, wherein the segment descriptor blocks form a third chain within at least one of the first chains and the second chains.

37. The method of claim 36, further comprising moving the segment descriptor block from the second chain back to one of the first chains when the data segment associated with the segment descriptor block is no longer being accessed.

38. The method of claim 36, further comprising aging one of the segment descriptor blocks by removing the segment descriptor block from one of the first chains, the segment descriptor block still forming part of the third chain.

39. The method of claim 38, further comprising releasing a slot in which the data segments are stored when all of the segment descriptor blocks have been removed from the first chains.

40. The method of claim 38, wherein the segment descriptor block is aged when space is needed in the cache.

41. The method of claim 36, further comprising generating a cylinder descriptor block, the cylinder descriptor block comprising:

a number of segment descriptor blocks residing in the first and second chains; and

a pointer identifying one of the segment descriptor blocks.

42. The method of claim 41, wherein the number of segment descriptor blocks is decremented when one of the segment descriptor blocks is aged.

43. A system for retrieving information from a database, comprising:

logic encoded on at least one computer readable medium; and

the logic operable when executed to;

retrieve a plurality of data segments from a cylinder in a single operation;

generate a segment descriptor block for each of at least some of the retrieved data segments, each segment descriptor block identifying a location of a corresponding data segment in a cache;

insert each of the segment descriptor blocks into at least one of a plurality of first chains; and

move one of the segment descriptor blocks from one of the first chains to one of a plurality of second chains when the data segment associated with the segment descriptor block is accessed, wherein the segment descriptor blocks form a third chain within at least one of the first chains and the second chains.

44. The system of claim 43, wherein the logic is further operable to:

move the segment descriptor block from the second chain back to one of the first chains when the data segment associated with the segment descriptor block is no longer being accessed;

age one of the segment descriptor blocks by removing the segment descriptor block from one of the first chains, the segment descriptor block still forming part of the third chain; and

release a slot in which the data segments are stored when all of the segment descriptor blocks have been removed from the first chains.

45. The system of claim 43, wherein the logic is further operable to generate a cylinder descriptor block, the cylinder descriptor block comprising:

a number of segment descriptor blocks residing in the first and second chains; and

a pointer identifying one of the segment descriptor blocks.

46. A system for retrieving information from a database, comprising:

a memory operable to store at least a portion of a cylinder; and

one or more processors collectively operable to;

retrieve a plurality of data segments from the cylinder in a single operation;

generate a segment descriptor block for each of at least some of the retrieved data segments, each segment descriptor block identifying a location of a corresponding data segment in the memory;

insert each of the segment descriptor blocks into at least one of a plurality of first chains; and

move one of the segment descriptor blocks from one of the first chains to one of a plurality of second chains when the data segment associated with the segment descriptor block is accessed, wherein the segment descriptor blocks form a third chain within at least one of the first chains and the second chains.

47. The system of claim 46, wherein the one or more processors are further collectively operable to:

move the segment descriptor block from the second chain back to one of the first chains when the data segment associated with the segment descriptor block is no longer being accessed;

age one of the segment descriptor blocks by removing the segment descriptor block from one of the first chains, the segment descriptor block still forming part of the third chain; and

release a slot in which the data segments are stored when all of the segment descriptor blocks have been removed from the first chains.

48. The system of claim 46, wherein the one or more processors are further collectively operable to generate a cylinder descriptor block, the cylinder descriptor block comprising:

a number of segment descriptor blocks residing in the first and second chains; and

a pointer identifying one of the segment descriptor blocks.

49. A computer-readable medium containing computer-executable code for instructing a computer to:

retrieve a plurality of data segments from a cylinder in a single operation;

generate a segment descriptor block for each of at least some of the retrieved data segments, each segment descriptor block identifying a location of a corresponding data segment in a cache;

insert each of the segment descriptor blocks into at least one of a plurality of first chains; and

move one of the segment descriptor blocks from one of the first chains to one of a plurality of second chains when the data segment associated with the segment descriptor block is accessed, wherein the segment descriptor blocks form a third chain within at least one of the first chains and the second chains.

50. A database management system, comprising:

a massively parallel processing system comprising;

one or more nodes;

a plurality of processors, each of the one or more nodes providing access to one or more processors; and

a plurality of virtual processes, each of the one or more processors providing access to one or more virtual processes;

a set of one or more database tables residing on the one or more nodes, the one or more database tables containing information organized by geographic location; and

one or more of the plurality of virtual processes operable to;

retrieve a plurality of data segments from a cylinder, the plurality of data segments forming at least a portion of at least one of the database tables;

generate a segment descriptor block for each of at least some of the retrieved data segments, each segment descriptor block identifying a location of a corresponding data segment in a cache;

insert each of the segment descriptor blocks into at least one of a plurality of first chains; and

move one of the segment descriptor blocks from one of the first chains to one of a plurality of second chains when the data segment associated with the segment descriptor block is accessed, wherein the segment descriptor blocks form a third chain within at least one of the first chains and the second chains.