Database segment searching

• US 8,108,400 B2
• Filed: 06/27/2009
• Issued: 01/31/2012
• Est. Priority Date: 06/27/2009
• Status: Expired due to Fees

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Graefe, Goetz
• Primary Examiner(s): Ng, Amy
• Application Number:
  US12/493,189
• Publication Number:
  US 20100332457A1
• Time in Patent Office: 948 Days
• Field of Search: 707/705, 707/706, 707/712, 707/732, 707/745, 707/754, 707/741, 707/755, 711/112, 711/213
• US Class Current: 707/741
• CPC Class Codes: G06F 16/2228 Indexing structures

Abstract

A segment encompasses a number of segment records less than the total number of records of a database. The segment records have values for a field of the database. Lowest and highest values of the segment records for the field, and a bitmap for the segment, can be determined and stored. Selected bits of the bitmap each correspond to a value for the field. Each selected bit is set to one where at least one segment record has the value to which the bit corresponds. An index relating to just the segment records can be determined and stored. The lowest and highest values, and the bitmap, are adapted to permit determination of whether the segment has to be loaded into memory to locate records that satisfy a query. The index is adapted to permit searching of the segment records after the segment has been loaded into the memory.

Claims

1. A method comprising:

receiving a segment of a database stored on a non-transitory computer-readable medium, the segment encompassing a plurality of records of the database less than a total number of records of the database the plurality of records are referred to as segment records, where one or more of the segment records have values for a field of the database;

determining and storing a plurality of lowest values of the segment records for the field and a plurality of highest values of the segment records for the field;

determining and storing a bitmap for the segment, one or more selected bits of the bitmap each corresponding to a different value for the field, each selected bit set to one where one or more of the segment records have the value to which the selected bit corresponds and set to zero where none of the segment records have the value to which the selected bit corresponds;

determining and storing an index for the segment, the index relating to only the segment records and not to the records of the database other than the segment records;

loading the segment into memory from the non-transitory computer-readable medium to locate one or more selected records of the database that satisfy a query, wherein the lowest values and the highest values, and the bitmap, each separately permits determination of whether the segment is loaded, without having to use the index to make a determination, wherein where the one or more selected bits of the bitmap that each correspond to a different value for the field are set, one or more of the segment records definitively include the different value for the field; and

searching, using the index, the segment records after the segment is loaded into the memory, to at least partially locate the selected records that satisfy the query.

2. The method of claim 1, wherein determining and storing the lowest values of the segment records for the field and the highest values of the segment records for the field comprises storing the lowest values and the highest values on the non-transitory computer-readable medium apart from where the segment of the database is stored on the non-transitory computer-readable medium.

3. The method of claim 1, further comprising, after determining and storing the lowest values of the segment records for the field and the highest values of the segment records for the field:

receiving the query requesting one or more selected records of the database be located;

determining whether to search the segment records against the query by comparing the query against the lowest values of the segment records for the field and against the highest values of the segment records for the field;

in response to determining that the segment records are to be searched against the query,

loading the segment, including all the segment records, from the non-transitory computer-readable medium into the memory, such that all the segment records of the segment are simultaneously located within the memory, the memory being faster to access than the non-transitory computer-readable medium is, to search the segment records against the query to at least partially locate the selected records that satisfy the query; and

,

in response to determining that the segment records are not to be searched against the query,

skipping the segment, such that none of the segment records are loaded into the memory and such that the segment records are not searched to locate the selected records that satisfy the query.

4. The method of claim 1, wherein determining and storing the bitmap for the segment comprises storing the bitmap on the non-transitory computer-readable medium apart from where the segment of the database is stored on the non-transitory computer-readable medium.

5. The method of claim 1, further comprising, after determining and storing the bitmap for the segment:

receiving the query requesting one or more selected records of the database that satisfy one or more given values for the field of the database;

determining whether to search the segment records against the query by determining whether any of the given values has a corresponding selected bit within the bitmap equal to one;

in response to determining that any of the given values has a corresponding selected bit within the bitmap equal to one,

loading the segment, including all the segment records, from the non-transitory computer-readable medium into the memory, such that the segment records of the segment are simultaneously located within the memory, the memory being faster to access than the non-transitory computer-readable medium is, to search the segment records against the query to at least partially locate the selected records that satisfy the query; and

,

in response to determining that none of the given values has a corresponding selected bit within the bitmap equal to one,

skipping the segment, such that none of the segment records are loaded into the memory and such that the segment records are not searched to locate the selected records that satisfy the query.

6. The method of claim 1, wherein the selected bits of the bitmap are first selected bits, and a second selected bit of the bitmap corresponds to a range of values for the field, the second selected bit set to one where one or more of the segment records have a value falling within the range of values and set to zero where none of the segment records have a value falling within the range of values.

7. The method of claim 1, wherein determining and storing the index for the segment comprises storing the index as part of the segment, such that the index is stored on the computer-readable medium with the segment of the database.

8. The method of claim 1, further comprising, after determining and storing the index for the segment,

receiving a query requesting one or more selected records of the database be located;

determining whether to search the segment records against the query;

in response to determining that the segment records are to be searched against the query,

loading the segment, including all the segment records, from the non-transitory computer-readable medium into memory, such that the segment records of the segment are simultaneously located within the memory, the memory being faster to access than the computer-readable medium is; and

searching the segment records, as loaded within the memory, against the query by using the index for the segment, to at least partially locate the selected records that satisfy the query.

9. The method of claim 8, wherein determining whether to search the segment records against the query comprises one or more of:

comparing the query against the lowest values of the segment records for the field and the highest values of the segment records for the field to determine whether to search the segment records against the query;

using the bitmap in relation to the query to determine whether to search the segment records against the query.

10. A non-transitory computer-readable medium having a computer program stored thereon, where execution of the computer programs by a processor of a computing device causes a method to be performed, the method comprising:

receiving a query requesting one or more selected records of a total number of records of a database stored on non-volatile storage, the database including a segment encompassing a plurality of records of the database less than the total number of records of the database and that are referred to as segment records, where one or more of the segment records have values for a field of the database;

determining whether to search the segment records against the query by;

determining whether the query encompasses any of a plurality of lowest values of the segment records for the field or any of a plurality of highest values of the segment records for the field,

determining whether any of one or more given values encompassed by the query has a corresponding selected bit within a bitmap, the bitmap including one or more selected bits that each correspond to a different value for the field, each selected bit set to one where one or more of the segment records have the value to which the selected bit corresponds and set to zero where none of the segment records have the value to which the selected bit corresponds, wherein where the one or more selected bits of the bitmap that each correspond to a different value for the field are set, one or more of the segment records definitively include the different value for the field;

wherein, the lowest values and the highest values and the bitmap separately permits determination whether to search the segment records against the query;

in response to determining that the segment records are to be searched against the query,

loading the segment, including all the segment records, from the non-volatile storage into memory, such that all the segment records of the segment are simultaneously located within the memory, the memory being faster to access than the non-volatile storage is; and

,

after loading the segment into the memory, searching the segment records, as loaded into the memory, against the query by using the index for the segment, to at least partially locate the selected records that satisfy the query, where the index relates to just the segment records and not to the records of the database other than the segment records;

in response to determining that the segment records are not to be searched against the query,

skipping the segment, such that none of the segment records are loaded into the memory and such that segment records are not searched to locate the selected records that satisfy the query,

wherein where the one or more selected bits of the bitmap that each correspond to a different value for the field are set, one or more of the segment records definitively include the different value for the field.

11. The non-transitory computer-readable medium of claim 10, wherein the lowest values, the highest values, and the bitmap are stored within the segment records as part of the segment.

12. A system comprising:

a processor;

a non-volatile storage storing a database, the database including a segment, the segment encompassing a plurality of records of the database less than a total number of records of the database and that are referred to as segment records;

memory that is accessible faster than the non-volatile storage is;

a non-transitory computer-readable medium storing a computer program, the computer program executed by the processor to load the segment records from the non-volatile storage into the memory, such that all the segment records of the segment are simultaneously located within the memory, to search the segment records against the query;

a first condition being that the query encompasses any of a plurality of lowest values of the segment records for the field or any of a plurality of highest values of the segment records for the field;

a second condition being that any of one or more given values encompassed by the query has a corresponding selected bit within a bitmap that is equal to one, the bitmap including one or more selected bits that each correspond to a different value for the field, each selected bit set to one where one or more of the segment records have the value to which the selected bit corresponds and set to zero where none of the segment records have the value to which the selected bit corresponds;

wherein the computer program executed by the processor loads the segment records from the non-volatile storage into the memory responsive to both of the first condition and the second condition being satisfied, without using an index for the segment of the segment records, wherein the second condition where the one or more selected bits of the bitmap that each corresponding to a different value for the field are set, one or more of the segment records definitively include the different value for the field;

wherein the computer program is further executed by the processor to, after loading the segment records into the memory, search the segment records against the query by using the index for the segment, to at least partially locate the selected records that satisfy the query, the index relating to just the segment records and not to the records of the database other than the segment records.

13. The system of claim 12, wherein the lowest values, the highest values, and the bitmap are stored within the segment records as part of the segment.