Associating summaries with pointers in persistent data structures

• US 9,002,860 B1
• Filed: 02/06/2012
• Issued: 04/07/2015
• Est. Priority Date: 02/06/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ghemawat, Sanjay
• Primary Examiner(s): Mofiz, Apu
• Assistant Examiner(s): BIBBEE, JARED M
• Application Number:
  US13/366,934
• Time in Patent Office: 1,156 Days
• Field of Search: 707/755
• US Class Current: 707/755
• CPC Class Codes: G06F 12/0284 Multiple user address space allocation, e.g. using different base addresses interprocessor communication G06F15/163
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Methods for organizing and retrieving data values in a persistent data structure are provided. Data values are grouped into data blocks and pointers are obtained for each data block. In addition, one or more summaries, related to a properties of the data block, are created and associated with the data block'"'"'s pointer. The summaries allow for a more efficient retrieval of data values from the data structure by preventing unnecessary retrieval calls to persistent storage when the summaries do not match query criteria.

Claims

1. A computer-implemented method for managing a database comprising:

receiving a data set to be stored in a database;

organizing and storing the data set into data blocks within a data structure;

obtaining a pointer to each data block;

for at least one data block, obtaining a set of values that summarizes a property of the data values stored in the data block;

associating the set of values with the data block'"'"'s pointer; and

storing the set of values in a pointer block with the data block'"'"'s pointer in the same pointer block as the set of values.

2. The method of claim 1, wherein obtaining the set of values that summarizes the property of the data values, comprises:

predicting based on historical query data the property that defines the set of values and

summarizing the range of data values in the data block corresponding to the predicted property.

3. The method of claim 1, wherein multiple sets of values, each representing a property of the data values stored in the data block, are associated with a data block.

4. The method of claim 1, wherein the data structure is a B-tree.

5. The method of claim 1, wherein the data structure is an stable.

6. The method of claim 1, wherein the set of values is in a Bloom Filter.

7. The method of claim 1, wherein the set of values is in a bit-vector.

8. The method of claim 1, wherein the set of values includes range information.

9. The method of claim 1, wherein the property is selected based on an application which is predicted to query the database.

10. A computer-implemented method for managing a database comprising:

receiving a data structure query;

loading a pointer block, which includes a data block pointer and an associated set of values, which summarizes a property of the data values stored in the data block, into memory;

comparing a criteria of the received query to information from the loaded set of values;

responsive to a match between the query criteria and information from the set of values, dereferencing the data block pointer to find the referenced data block, retrieving the referenced data block from persistent storage, and parsing the retrieved data block to obtain values that are responsive to the query criteria before returning the query results; and

responsive to no match between the query criteria and the information from the set of values, skipping the data block pointer traversal, the retrieval of the referenced data block from persistent storage, and the parsing of the retrieved data block; and

returning the query results.

11. The method of claim 10, wherein the data structure is a B-tree or an stable.

12. The method of claim 10, wherein the set of values is in a Bloom Filter or a bit-vector.

13. The method of claim 10, wherein the set of values includes range information.

14. The method of claim 10, wherein multiple sets of values, each representing a property of the data values stored in the data block, are associated with a data block.

15. A non-transitory computer-readable medium having stored therein computer executable code that causes one or more processors to execute the steps of:

receiving a data set to be stored in a database;

organizing and storing the data set into data blocks within a data structure;

obtaining a pointer to each data block;

for at least one data block, obtaining a set of values that summarizes a property of the data values stored in the data block;

associating the set of values with the data block'"'"'s pointer; and

storing the set of values in a pointer block with the data block'"'"'s pointer in the same pointer block as the set of values.

16. The non-transitory computer-readable medium of claim 15, wherein obtaining the set of values that summarizes the property of the data values, comprises:

predicting based on historical query data the property that defines the set of values and

summarizing the range of data values in the data block corresponding to the predicted property.

17. The non-transitory computer-readable medium of claim 15, wherein the data structure is a B-tree or an stable.

18. The non-transitory computer-readable medium of claim 15, wherein the set of values is a in Bloom Filter or a bit-vector.

19. The non-transitory computer-readable medium of claim 15, wherein the set of values includes range information.