Techniques for using zone map information for post index access pruning

• US 9,514,187 B2
• Filed: 04/04/2014
• Issued: 12/06/2016
• 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
• Primary Examiner(s): Perveen, Rehana
• Assistant Examiner(s): Khong, Alexander
• Application Number:
  US14/245,934
• Publication Number:
  US 20150286682A1
• Time in Patent Office: 977 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations

Abstract

Techniques for using zone map information for post index access pruning. In one embodiment, for example, a method for using zone map information for post index access pruning comprises: receiving a query statement comprising a first filter predicate on an indexed column of a database table and a second filter predicate on a zoned column of a database table; identifying zero or more pruneable zones of a zone map based on a value for the zoned column in the second filter predicate; obtaining a set of data record addresses from an index on the indexed column based on a value for the indexed column in the first filter predicate; and pruning, from access paths for processing the query statement, any data records, corresponding to data record addresses in the set of data record addresses, that are physically located in one of the pruneable zones.

Claims

1. A method for using zone map information for post index access pruning comprising:

receiving a query statement comprising a first filter predicate on an indexed column of a first database table and a second filter predicate on a zoned column of a second database table;

identifying one or more pruneable zones of a zone map based on a value for the zoned column in the second filter predicate;

wherein the zone map comprises a plurality of zones corresponding to a plurality of contiguous regions of disk blocks;

wherein, for each zone of the plurality of zones, the zone map stores a minimum column value for the zoned column for the zone and a maximum column value for the zoned column for the zone;

obtaining a set of data record addresses from an index on the indexed column based on a value for the indexed column in the first filter predicate; and

pruning, from access paths for processing the query statement, any data records, corresponding to data record addresses in the set of data record addresses, that are physically located in one of the one or more pruneable zones.

2. The method of claim 1, wherein each of the data record addresses in the set of data record address is a row identifier.

3. The method of claim 1, wherein each of the data record addresses in the set of data record addresses comprises information identifying a physical location of the corresponding data record.

4. The method of claim 1, wherein the indexed column and the zoned column are columns of the same database table.

5. The method of claim 1, wherein the indexed column is a column of a fact table in a star schema and the zoned column is a column of a dimension table in the star schema.

6. The method of claim 1, wherein the set of data record addresses are obtained from the index as a stream of data record addresses;

and wherein the method further comprises;

processing the stream of data record addresses including, for each data record address in the set of data record addresses, determining whether the data record corresponding to the data record address is physically located within one of the one or more pruneable zones, and pruning the corresponding data record from access paths for processing the query statement depending on whether the corresponding data record is physically located within one of the one or more pruneable zones.

7. The method of claim 1, wherein the index on the indexed column is a B-tree index or a bitmap index.

8. The method of claim 1, wherein the second filter predicate is an equality predicate, an inequality predicate, a range predicate, a like predicate with a constant prefix, or an in-list predicate.

9. The method of claim 1, further comprising:

fetching, from a cache or from disk, any data records, corresponding to data record addresses in the set of data record addresses, that are not physically located in any of the one or more pruneable zones.

10. The method of claim 1, wherein:

the zoned column is a first zoned column;

the query statement comprises a plurality of filter predicates on a zoned column, each on a different zoned column, the plurality of filter predicates comprising the second filter predicate on the first zoned column; and

identifying the one or more pruneable zones of the zone map is based on the values for the different zoned columns in the plurality of filter predicates on a zoned column.

11. One or more non-transitory computer-readable media storing instructions which, when executed by one or more computing devices, causes the one or more computing devices to perform steps for using zone map information for post index access pruning comprising:

receiving a query statement comprising a first filter predicate on an indexed column of a first database table and a second filter predicate on a zoned column of a second database table;

identifying one or more pruneable zones of a zone map based on a value for the zoned column in the second filter predicate;

wherein the zone map comprises a plurality of zones corresponding to a plurality of contiguous regions of disk blocks;

wherein, for each zone of the plurality of zones, the zone map stores a minimum column value for the zoned column for the zone and a maximum column value for the zoned column for the zone;

obtaining a set of data record addresses from an index on the indexed column based on a value for the indexed column in the first filter predicate; and

pruning, from access paths for processing the query statement, any data records, corresponding to data record addresses in the set of data record addresses, that are physically located in one of the one or more pruneable zones.

12. The one or more non-transitory computer-readable media of claim 11, wherein each of the data record addresses in the set of data record address is a row identifier.

13. The one or more non-transitory computer-readable media of claim 11, wherein each of the data record addresses in the set of data record addresses comprises information identifying a physical location of the corresponding data record.

14. The one or more non-transitory computer-readable media of claim 11, wherein the indexed column and the zoned column are columns of the same database table.

15. The one or more non-transitory computer-readable media of claim 11, wherein the indexed column is a column of a fact table in a star schema and the zoned column is a column of a dimension table in the star schema.

16. The one or more non-transitory computer-readable media of claim 11, wherein the set of data record addresses are obtained from the index as a stream of data record addresses;

and wherein the steps further comprise;

processing the stream of data record addresses including, for each data record address in the set of data record addresses, determining whether the data record corresponding to the data record address is physically located within one of the one or more pruneable zones, and pruning the corresponding data record from access paths for processing the query statement depending on whether the corresponding data record is physically located within one of the one or more pruneable zones.

17. The one or more non-transitory computer-readable media of claim 11, wherein the index on the indexed column is a B-tree index or a bitmap index.

18. The one or more non-transitory computer-readable media of claim 11, wherein the second filter predicate is an equality predicate, an inequality predicate, a range predicate, a like predicate with a constant prefix, or an in-list predicate.

19. The one or more non-transitory computer-readable media of claim 11, the steps further comprising:

fetching, from a cache or from disk, any data records, corresponding to data record addresses in the set of data record addresses, that are not physically located in any of the pruneable zones.

20. The one or more non-transitory computer-readable media of claim 11, wherein:

the zoned column is a first zoned column;

the query statement comprises a plurality of filter predicates on a zoned column, each on a different zoned column, the plurality of filter predicates comprising the second filter predicate on the first zoned column; and

the step of identifying the one or more pruneable zones of the zone map is based on the values for the different zoned columns in the plurality of filter predicates on a zoned column.

21. A method for using zone map information for post index access pruning comprising:

receiving a query statement comprising a first filter predicate on a first column of a database table and a second filter predicate on a second column of the table;

querying a zone map for any zones of the zone map that cannot possibly contain rows of the table that satisfy the second filter predicate, wherein querying the zone map returns identifiers of one or more zones of the zone map that cannot possibly contain rows of the table that satisfy the second filter predicate;

wherein the zone map comprises a plurality of zones corresponding to a plurality of contiguous regions of disk blocks;

wherein, for each zone of the plurality of zones, the zone map stores a minimum column value for the second column for the zone and a maximum column value for the second column for the zone;

storing the one or more returned zone identifiers in a memory;

responsive to initiating an index scan of an index on the first column for rows of the table that satisfy the first filter predicate, receiving row identifiers of one or more rows of the table that satisfy the first filter predicate; and

for each row identifier of the one or more rows of the table that satisfy the first filter predicate;

determining, based at least in part on at least a portion of the row identifier and the zone identifiers stored in memory, whether the row identified by the row identifier is physically located in one of the one or more identified zones of the zone map that cannot possibly contain rows of the table that satisfy the second filter predicate,

if the row identified by the row identifier is physically located in one of the one or more identified zones of the zone map that cannot possibly contain rows of the table that satisfy the second filter predicate, then discarding the row identifier, and

if the row identified by the row identifier is not physically located in one of the one or more identified zones of the zone map that cannot possibly contain rows of the table that satisfy the second filter predicate, then fetching the row from a cache or a physical location on disk.

22. The method of claim 21, wherein the portion of the row identifier identifies a physical location on disk where the corresponding row is stored.

23. The method of claim 21, wherein the zone map comprises, for each zone of the plurality of zones of the zone map, information identifying a contiguous portion of physical disk covered by the zone.