COMPRESSION AWARE PHYSICAL DATABASE DESIGN

• US 20120323929A1
• Filed: 06/17/2011
• Published: 12/20/2012
• Est. Priority Date: 06/17/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Syamala, Manoj, Kimura, Hideaki, Narasayya, Vivek
• Granted Patent: US 9,009,124 B2
• Time in Patent Office: Days
• US Class Current: 707/748
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

A plurality of indicators representing a plurality of respective candidate database configurations may be obtained, each of the candidate database configurations including a plurality of database queries and a plurality of candidate database indexes associated with a database table. A portion of the candidate database indexes included in the plurality of database indexes may be selected based on skyline selection. An enumeration of the portion of the plurality of the candidate database indexes may be determined based on a greedy algorithm.

Claims

1. A system comprising:

a design manager embodied via executable instructions stored on a computer-readable storage medium, the design manager including;

a request receiving engine configured to receive a request for an estimate size of a first compressed index associated with a first database index that is based on a database table;

a base index engine configured to obtain a plurality of values indicating sizes of a plurality of second compressed indexes associated with a plurality of respective second database indexes other than the first database index, the second database indexes based on the database table; and

a size estimate engine configured to determine the estimate size of the first compressed database index based on one or more of the plurality of values.

2. The system of claim 1, wherein:

the database table is included in a relational database system.

3. The system of claim 1, further comprising:

a column set determination engine configured to determine a first set of table columns associated with the database table, wherein the first database index is based on the first set of table columns;

a compression type engine configured to determine that a compression associated with the requested estimate size associated with the first compressed index generates compressed indexes that share a common compressed size independent of an ordering of tuples associated with database table columns; and

an index selection engine configured to select one of the second database indexes that is, in common with the first database index, based on the first set of table columns, wherein

the size estimate engine is configured to determine the estimate size of the first compressed database index based on deducing the estimate size of the first compressed database index based on the value indicating the size of the compressed index associated with the selected one of the second database indexes.

4. The system of claim 3, wherein:

the compression associated with the requested estimate size includes one or more of;

null suppression or global dictionary compression.

5. The system of claim 1, further comprising:

a column set determination engine configured to determine a first set of table columns associated with the database table, wherein the first database index is based on the first set of table columns;

a compression type engine configured to determine that a compression associated with the requested estimate size associated with the first compressed index generates compressed indexes that share a common compressed size independent of an ordering of tuples associated with database table columns; and

an index selection engine configured to select one or more of the second database indexes that are based on one or more of the table columns included in one or more subsets of the first set of table columns, wherein

the size estimate engine is configured to determine the estimate size of the first compressed database index based on extrapolating the estimate size of the first compressed database index based on determining one or more size reduction values for each selected second database index, based on determining differences between the value indicating the size of the compressed index associated with the selected one of the second database indexes and a value indicating the size of the selected one of the second database indexes.

6. The system of claim 1, further comprising:

a column set determination engine configured to determine a first set of table columns associated with the database table, wherein the first database index is based on the first set of table columns;

an index selection engine configured to select one or more of the second database indexes that are based on one or more of the table columns included in one or more subsets of the first set of table columns, wherein

the size estimate engine is configured to determine the estimate size of the first compressed database index based on extrapolating the estimate size of the first compressed database index based on an order-dependent column extrapolation, based on

determining one or more run lengths of values stored in one or more columns of the selected one or more of the second database indexes, and

determining at least one penalty value associated with a size reduction that is associated with one or more columns of the selected one or more of the second database indexes.

7. The system of claim 6, wherein:

a compression associated with the requested estimate size includes one or more of;

page-local dictionary encoding or run length encoding.

8. The system of claim 1, further comprising:

a table sample locator configured to determine whether a database table sample associated with the database table is stored in a table sample storage device;

a table sample retrieval engine configured to obtain the database table sample, based on a first result of the determination of whether a database table sample associated with the database table is stored in a table sample storage device;

a table sample determination engine configured to obtain a random sample from the database table, based on a second result of the determination of whether a database table sample associated with the database table is stored in a table sample storage device, the random sample including a subset of rows included in the database table; and

a sample storage engine configured to initiate storage of the random sample obtained by the table sample determination engine, as the database table sample in the table sample storage device, wherein

the base index engine is configured to obtain the plurality of values based on one or more compression fraction values associated with the obtained database table sample.

9. The system of claim 8, further comprising:

a partial index sample locator configured to determine whether a partial index table sample associated with a database partial index associated with the database table is stored in a table sample storage device;

a partial index sample engine configured to obtain the partial index table sample, based on a first result of the determination of whether the partial index table sample is stored in the table sample storage device;

a filtered sample determination engine configured to obtain a filtered sample from the database table sample, based on a second result of the determination of whether the partial index table sample is stored in the table sample storage device; and

a filtered sample storage engine configured to initiate storage of the filtered sample obtained by the filtered sample determination engine, as the partial index table sample in the table sample storage device.

10. The system of claim 8, further comprising:

a materialized view sample locator configured to determine whether a materialized view sample associated with a materialized view associated with the database table is stored in a table sample storage device;

a materialized view sample determination engine configured to obtain the materialized view sample, based on a first result of the determination of whether the materialized view table sample is stored in the table sample storage device;

a join synopsis determination engine configured to obtain a plurality of join synopses of a database associated with the database table, based on a second result of the determination of whether the partial index table sample is stored in the table sample storage device; and

a join synopsis storage engine configured to initiate storage of the plurality of join synopses obtained by the join synopsis determination engine, as the partial index table sample in the table sample storage device.

11. A method comprising:

obtaining a plurality of indicators representing a plurality of respective database indexes associated with a database table; and

determining, via a device processor, an estimate size for a target group of the plurality of database indexes, based on a directed graph that includes;

a plurality of index nodes that represent size estimations associated with a portion of the respective database indexes, and

a plurality of deduction nodes that include candidate deductions that are associated with one or more of the index nodes that are arranged as parent nodes relative to the deduction nodes in the directed graph, the plurality of deduction nodes associated with one or more of the index nodes arranged as children nodes relative to the deduction nodes, each of the children nodes indicating a candidate deduction compression associated with the each of the children nodes.

12. The method of claim 11, further comprising:

obtaining a predetermined error value representing a predetermined error ratio, a predetermined confidence value representing a predetermined confidence parameter, and a predetermined sampling ratio value representing a predetermined sampling ratio, wherein

determining the estimate size includes determining the estimate size for the target group of the plurality of database indexes, based on the predetermined error value, the predetermined confidence value, and the predetermined sampling ratio value.

13. The method of claim 11, wherein:

determining the estimate size includes;

initializing a plurality of the index nodes representing the target group of the plurality of database indexes with a state value indicating an initial state,

updating a first one of the index nodes with a state value indicating a deduced state, when a first candidate design strategy includes a task associated with estimating a size of the index associated with the first one of the index nodes based on size deduction, and

updating a second one of the index nodes with a state value indicating a sampled state, when a second candidate design strategy includes a task associated with estimating a size of the index associated with the first one of the index nodes based on database table sampling.

14. The method of claim 13, wherein:

determining the estimate size includes;

updating a first one of the deduction nodes with a state value indicating an enabled state, when the one or more children nodes associated with the first one of the deduction node are associated with one or more of a sampled state or a deduced state.

15. A computer program product tangibly embodied on a computer-readable storage medium and including executable code that, when executed, causes at least one data processing apparatus to:

obtain a plurality of indicators representing a plurality of respective candidate database configurations, each of the candidate database configurations including a plurality of database queries and a plurality of candidate database indexes associated with a database table;

select a portion of the candidate database indexes included in the plurality of database indexes based on skyline selection; and

determine an enumeration of the portion of the plurality of the candidate database indexes based on a greedy algorithm.

16. The computer program product of claim 15, wherein the executable code is configured to cause the at least one data processing apparatus to:

select the portion of the candidate database indexes included in the plurality of database indexes based on skyline selection, based on;

determining a cost estimate associated with each of the respective candidate database configurations, based on index size estimates and query runtime estimates associated with each database query associated with of the respective candidate database configurations.

17. The computer program product of claim 16, wherein the executable code is configured to cause the at least one data processing apparatus to:

select the portion of the candidate database indexes included in the plurality of database indexes based on skyline selection, based on;

ranking the respective candidate database configurations, based on a combination of speed of estimated query runtime and small size determinations associated with each respective candidate database configuration.

18. The computer program product of claim 15, wherein the executable code is configured to cause the at least one data processing apparatus to:

determine the enumeration of the portion of the plurality of the candidate database indexes based on the greedy algorithm and backtracking.

19. The computer program product of claim 18, wherein:

the greedy algorithm includes one or more of;

a pure greedy algorithm or a density-based greedy algorithm.

20. The computer program product of claim 18, wherein:

the backtracking is based on;

determining that one of the candidate database configurations included in a greedy algorithm selection exceeds a size limit, and

replacing a candidate database index that is included in the one of the candidate database configurations included in the greedy algorithm selection that exceeds the size limit, with a compressed candidate database index that is based on the replaced candidate database index.