PRUNING DISK BLOCKS OF A CLUSTERED TABLE IN A RELATIONAL DATABASE MANAGEMENT SYSTEM

• US 20140095520A1
• Filed: 09/28/2012
• Published: 04/03/2014
• Est. Priority Date: 09/28/2012
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Ziauddin, Mohamed, Witkowski, Andrew
• Granted Patent: US 8,996,544 B2
• Time in Patent Office: Days
• US Class Current: 707/756
• CPC Class Codes: G06F 16/24557 Efficient disk access during query execution
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: G06F 16/285 Clustering or classification

Abstract

Techniques are provided for generating a “dimensional zonemap” that allows a database server to avoid scanning disk blocks of a fact table based on filter predicates in a query that qualify one or more dimension tables. The zonemap divides the fact table into sets of contiguous disk blocks referred to as “zones”. For each zone, a minimum value and a maximum value for each of one or more “zoned” columns of the dimension tables is determined and maintained in the zonemap. For a query that contains a filter predicate on a zoned column, the predicate value can be compared to the minimum value and maximum value maintained for a zone for that zoned column to determine whether a scan of the disk blocks of the zone can be skipped.

Claims

1. A method for pruning disk blocks of a target table in a relational database management system, the method comprising:

dividing the disk blocks of the target table into a plurality of zones;

maintaining, for each zone of the plurality of zones, a minimum column value and a maximum column value for each of one or more zoned columns of one or more zoned tables;

wherein at least one of the one or more zoned tables is not the target table;

receiving a query on the target table;

wherein the query contains a filter predicate on a particular column of the one or more zoned columns;

wherein the filter predicate has a predicate value;

in response to receiving the query, determining, based on the predicate value and minimum column values and the maximum column values maintained for the particular column, zero or more zones of the plurality of zones that cannot possibly contain rows of the target table satisfying the filter predicate; and

determining, based on the zero or more zones of the plurality of zones that cannot possibly contain rows of the target table satisfying the filter predicate, whether a disk scan of the zero or more zones is necessary;

wherein the method is performed by one or more computing devices.

2. The method of claim 1, wherein the particular column is not a column of the target table.

3. The method of claim 1, wherein none of the one or more zoned columns is a column of the target table.

4. The method of claim 1, wherein the target table is a fact table of a star schema and the particular column is a column of a dimension table of the star schema.

5. The method of claim 1, further comprising:

in response to receiving the query, determining, based on the predicate value and minimum column values and maximum column values maintained for the particular column, one or more zones of the plurality of zones that cannot possibly contain rows of the target table satisfying the filter predicate; and

determining, based on the one or more zones of the plurality of zones that cannot possibly contain rows of the target table satisfying the filter predicate, one or more particular zones, of the one or more zones of the plurality of zones that cannot possibly contain rows of the target table satisfying the filter predicate, for which a disk scan is not necessary; and

returning an answer to the query without performing a disk scan of the one or more particular zones.

6. The method of claim 1, wherein the particular column is not a column of the target table, and wherein dividing the disk blocks of the target table into a plurality of zones includes:

performing a left outer join between the target table and the table having the particular column to produce a set of joined rows, each joined row of the set of joined rows corresponding to one row of the target table; and

for each joined row in the set of joined rows, assigning the corresponding row of the target table to one zone of the plurality of zones.

7. The method of claim 1, wherein each zone of the plurality of zones includes at most a predetermined number of contiguous disk blocks.

8. The method of claim 1, wherein maintaining, for each zone of the plurality of zones, a minimum column value and a maximum column value for each of the one or more zoned columns includes maintaining a materialized view in a database, the materialized view including one row for each zone of the plurality of zones, one column for each of the one or more zoned columns storing the minimum column values for the zoned column, and one column for each of the one or more columns storing the maximum column values for the zoned column.

9. The method of claim 1, wherein the filter predicate contains a LIKE operator and the predicate value has a constant character string value or a constant character string value prefixing a wildcard operator.

10. The method of claim 1, wherein the particular column is not a column of the target table, and wherein the query contains join criteria, the join criteria specifying a join between the target table and the table having the particular column, the join criteria further specifying that the join is to be based on a foreign key column of the target table and a unique key column of the table having the particular column.

11. The method of claim 1, wherein the particular column has a database data type;

and wherein the database data type is selected from the group consisting of numeric, character, date, timestamp, row identifier, float, and double.

22. The one or more non-transitory computer-readable media of claim 1, wherein the particular column has a database data type;

and wherein the database data type is selected from the group consisting of numeric, character, date, timestamp, row identifier, float, and double.

12. One or more non-transitory computer-readable media storing instructions which, when executed by one or more processors, cause performance of a method for pruning disk blocks of a target table in a relational database management system, the method comprising:

dividing the disk blocks of the target table into a plurality of zones;

maintaining, for each zone of the plurality of zones, a minimum column value and a maximum column value for each of one or more zoned columns of one or more zoned tables;

wherein at least one of the one or more zoned tables is not the target table;

receiving a query on the target table;

wherein the query contains a filter predicate on a particular column of the one or more zoned columns;

wherein the filter predicate has a predicate value;

in response to receiving the query, determining, based on the predicate value and minimum column values and the maximum column values maintained for the particular column, zero or more zones of the plurality of zones that cannot possibly contain rows of the target table satisfying the filter predicate; and

determining, based on the zero or more zones of the plurality of zones that cannot possibly contain rows of the target table satisfying the filter predicate, whether a disk scan of the zero or more zones is necessary;

wherein the method is performed by one or more computing devices.

13. The one or more non-transitory computer-readable media of claim 12, wherein the particular column is not a column of the target table.

14. The one or more non-transitory computer-readable media of claim 12, wherein none of the one or more zoned columns is a column of the target table.

15. The one or more non-transitory computer-readable media of claim 12, wherein the target table is a fact table of a star schema and the particular column is a column of a dimension table of the star schema.

16. The one or more non-transitory computer-readable media of claim 12, further comprising:

in response to receiving the query, determining, based on the predicate value and minimum column values and maximum column values maintained for the particular column, one or more zones of the plurality of zones that cannot possibly contain rows of the target table satisfying the filter predicate; and

determining, based on the one or more zones of the plurality of zones that cannot possibly contain rows of the target table satisfying the filter predicate, one or more particular zones, of the one or more zones of the plurality of zones that cannot possibly contain rows of the target table satisfying the filter predicate, for which a disk scan is not necessary; and

returning an answer to the query without performing a disk scan of the one or more particular zones.

17. The one or more non-transitory computer-readable media of claim 12, wherein the particular column is not a column of the target table, and wherein dividing the disk blocks of the target table into a plurality of zones includes:

performing a left outer join between the target table and the table having the particular column to produce a set of joined rows, each joined row of the set of joined rows corresponding to one row of the target table; and

for each joined row in the set of joined rows, assigning the corresponding row of the target table to one zone of the plurality of zones.

18. The one or more non-transitory computer-readable media of claim 12, wherein each zone of the plurality of zones includes at most a predetermined number of contiguous disk blocks.

19. The one or more non-transitory computer-readable media of claim 12, wherein maintaining, for each zone of the plurality of zones, a minimum column value and a maximum column value for each of the one or more zoned columns includes maintaining a materialized view in a database, the materialized view including one row for each zone of the plurality of zones, one column for each of the one or more zoned columns storing the minimum column values for the zoned column, and one column for each of the one or more columns storing the maximum column values for the zoned column.

20. The one or more non-transitory computer-readable media of claim 12, wherein the filter predicate contains a LIKE operator and the predicate value has a constant character string value or a constant character string value prefixing a wildcard operator.

21. The one or more non-transitory computer-readable media of claim 12, wherein the particular column is not a column of the target table, and wherein the query contains join criteria, the join criteria specifying a join between the target table and the table having the particular column, the join criteria further specifying that the join is to be based on a foreign key column of the target table and a unique key column of the table having the particular column.