Database segment searching

• US 20100332457A1
• Filed: 06/27/2009
• Published: 12/30/2010
• Est. Priority Date: 06/27/2009
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Graefe, Goetz
• Granted Patent: US 8,108,400 B2
• Time in Patent Office: Days
• US Class Current: 707/673
• 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:

for a segment of a database stored on a computer-readable medium, 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, where one or more of the segment records have values for a field of the database, performing by a processor of a computing device one or more of;

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 just the segment records and not to the records of the database other than the segment records,

wherein the lowest values and the highest values, and the bitmap, are each adapted to permit determination of whether the segment has to be loaded into memory from the computer-readable medium to locate one or more selected records of the database that satisfy a query, and

wherein the index is adapted to permit searching of the segment records after the segment has been loaded into the memory, to at least partially locate the selected records that satisfy the query, without having to examine all the segment records.

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 computer-readable medium apart from where the segment of the database is stored on the 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 computer-readable medium 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 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 computer-readable medium apart from where the segment of the database is stored on the 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 computer-readable medium 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 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 computer-readable medium 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 computer-readable medium is;

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 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 one or more of;

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;

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

,

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.

11. The computer-readable medium of claim 10, wherein the method further comprises, in response to determining that the segment records are to be searched against the query, and after loading the segment into the memory:

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

wherein the index relates to just the segment records and not to the records of the database other than the segment records.

12. The 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.

13. A system comprising:

a processor;

a non-volatile storage to store 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 computer-readable medium to store 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,

wherein the segment records are loaded from the non-volatile storage into the memory responsive to one or more of a first condition and a second condition being satisfied,

the 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,

the 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.

14. The system of claim 13, wherein the computer program is further executed by the processor to, after having loaded the segment records into the memory, search the segment records against the query by using an index for the segment, to at least partially locate the selected records that satisfy the query,

wherein the index relates to just the segment records and not to the records of the database other than the segment records.

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