METHOD AND SYSTEM FOR PERFORMING A SCAN OPERATION ON A TABLE OF A COLUMN-ORIENTED DATABASE

• US 20090019029A1
• Filed: 07/11/2007
• Published: 01/15/2009
• Est. Priority Date: 07/11/2007
• Status: Abandoned Application

• Current Assignee: InfiniDB, Inc.
• Original Assignee: InfiniDB, Inc.
• Inventors: Dempsey, Robert J., Zhou, Weidong, Weber, John D., LeBlane, Patrick M., Lowe, Jason B., Tommaney, James Joseph, Figg, Phillilp R.
• Application Number:
  US11/775,980
• Publication Number:
  US 20090019029A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24547 Optimisations to support specific applications; Extensibility of optimisers
• CPC Class Codes: G06F 16/24557 Efficient disk access during query execution
• CPC Class Codes: G06F 16/284 Relational databases

Abstract

A method and system for performing a scan operation on a table of a column-oriented database is described. One embodiment receives a database query that references a particular column in a table, the particular column being horizontally partitioned into at least one extent, the at least one extent including at least one data block; consults, for each extent in the particular column for which associated metadata is available, the metadata associated with that extent to determine whether that extent is required to process the scan operation; acquires, for each extent in the particular column for which associated metadata is not available, metadata associated with that extent and uses the acquired metadata associated with that extent to determine whether that extent is required to process the scan operation; and performs the scan operation on only those extents in the particular column determined to be required to process the scan operation.

Claims

1. A method for performing a scan operation on a table of a column-oriented database, the table including rows and columns, the method comprising:

receiving a database query that references a particular column in the table, the particular column being horizontally partitioned into at least one extent, the at least one extent including at least one data block;

consulting, for each extent in the particular column for which associated metadata is available, the metadata associated with that extent to determine whether that extent is required to process the scan operation;

acquiring, for each extent in the particular column for which associated metadata is not available, metadata associated with that extent and using the acquired metadata associated with that extent to determine whether that extent is required to process the scan operation; and

performing the scan operation on only those extents in the particular column determined to be required to process the scan operation.

2. The method of claim 1, wherein acquiring, for each extent in the particular column for which associated metadata is not available, metadata associated with that extent includes storing the acquired metadata associated with that extent in an extent map for use in subsequent scan operations.

3. The method of claim 1, wherein the metadata associated with an extent includes minimum and maximum values of data contained in that extent.

4. The method of claim 3, wherein determining whether an extent is required to process the scan operation includes determining whether a value required for the scan operation lies between the minimum and maximum values, inclusive.

5. The method of claim 3, wherein determining whether an extent is required to process the scan operation includes determining whether a value required for the scan operation lies between the minimum and maximum values, exclusive.

6. The method of claim 1, further comprising:

eliminating automatically from the scan operation all columns in the table that are not required to process the scan operation.

7. The method of claim 1, wherein the database query is in the form of a Structured Query Language (SQL) statement.

8. A database query processing system, comprising:

a director module configured to receive a database query that references a particular column in a table of a column-oriented database, the particular column being horizontally partitioned into at least one extent, the at least one extent including at least one data block;

a user module configured to;

consult, for each extent in the particular column for which associated metadata is available, the metadata associated with that extent to determine whether that extent is required to process the scan operation; and

acquire, for each extent in the particular column for which associated metadata is not available, metadata associated with that extent and to use the acquired metadata associated with that extent to determine whether that extent is required to process the scan operation; and

at least one performance module configured to perform the scan operation on only those extents in the particular column determined to be required to process the scan operation.

9. The database query processing system of claim 8, wherein the user module is configured, for each extent in the particular column for which associated metadata is not available, to store the acquired metadata associated with that extent in an extent map for use in subsequent scan operations.

10. The database query processing system of claim 8, wherein the metadata associated with an extent includes minimum and maximum values of data contained in that extent.

11. The database query processing system of claim 10, wherein, to determine whether an extent is required to process the scan operation, the user module is configured to determine whether a value required for the scan operation lies between the minimum and maximum values, inclusive.

12. The database query processing system of claim 10, wherein, to determine whether an extent is required to process the scan operation, the user module is configured to determine whether a value required for the scan operation lies between the minimum and maximum values, exclusive.

13. The database query processing system of claim 8, wherein the user module is configured to eliminate automatically from the scan operation all columns in the table that are not required to process the scan operation.

14. The database query processing system of claim 8, wherein the database query is in the form of a Structured Query Language (SQL) statement.