DATABASE DESIGNER

• US 20110213766A1
• Filed: 06/16/2010
• Published: 09/01/2011
• Est. Priority Date: 02/22/2010
• Status: Active Grant

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Vertica Systems Incorporated (Open Text Corporation)
• Inventors: Hong, Mingsheng, Sun, Chang-Jian, Arun, Priya, Lawande, Shilpa
• Granted Patent: US 8,290,931 B2
• Time in Patent Office: Days
• US Class Current: 707/718
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/284 Relational databases

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for a database designer and a database storage designer. In one aspect, a method includes creating a set of candidate projections and progressively narrowing the set of candidate projections and a set of queries by eliminating candidate projections that do not satisfy a performance improvement criterion for remaining queries based on the properties associated with the candidate projections.

Claims

1. A method performed by data processing apparatus, the method comprising:

creating a set of candidate projections each being based on a column sort order in a set of column sort orders and being associated with properties of one or more tables in a set of tables to which the column sort order applies, wherein a column sort order is a sequence of one or more columns, each column'"'"'s data being stored in an order; and

until a stopping condition is reached, progressively narrowing the set of candidate projections and a set of queries by eliminating candidate projections that do not satisfy a performance improvement criterion for remaining queries based on the properties associated with the candidate projections.

2. The method of claim 1 wherein narrowing the set of queries further comprises eliminating queries from the set of queries that are sufficiently optimized by the remaining candidate projections.

3. The method of claim 1 wherein one or more of the candidate projections in the set of candidate projections is each associated with segmentation information that describes how data of the candidate projection would be stored across a plurality of nodes.

4. The method of claim 3 wherein the segmentation information specifies a set of one or more high number of distinct value columns in the candidate projection to be used for distributing the data across the nodes.

5. The method of claim 1 wherein progressively narrowing further comprises removing tables, from the set of tables, that have candidate projections in the set of candidate projections, that are no longer referenced by remaining queries in the set of queries.

6. The method of claim 5 wherein stopping condition is reached when the set of tables is empty, when the set of queries is empty, or when a number of queries in the set of queries is beyond a threshold.

7. The method of claim 1 wherein progressively narrowing further comprises removing tables from the set of tables that have a number of candidate projections, in the set of candidate projections, that has reached a target number of projections.

8. The method of claim 7 wherein the target number of projections is determined by a design policy.

9. The method of claim 8 wherein the design policy favors query performance, load performance, or a balance between query and load performance.

10. The method of claim 9 wherein the balance is achieved by increasing a number of projections in the candidate set of projections until query optimization is no longer benefited.

11. The method of claim 10 wherein query optimization is no longer benefited when a percentage of queries in the set of queries that have been optimized is beyond a threshold.

12. The method of claim 7 wherein the target number of projections allows for up to K node failures.

13. The method of claim 1 wherein eliminating candidate projections comprises generating an execution plan for each of one or more remaining queries in the set of queries wherein each execution plan is based on one or more of the remaining candidate projections.

14. The method of claim 13 further comprising:

for each execution plan, associating a benefit value with each candidate projection used by the execution plan wherein the benefit value is based on a contribution the candidate projection makes towards optimizing the execution plan; and

eliminating candidate projections from the set of candidate projections that do not satisfy the performance improvement criterion based on respective benefit values associated with the candidate projections.

15. The method of claim 13 wherein the benefit value associated with each candidate projection is determined based on whether the candidate projection'"'"'s columns are used in any of the execution plan'"'"'s highlights.

16. The method of claim 15 wherein a plan highlight is a run-length encoding on a predicate evaluation, on a grouping and aggregate keys, or on join keys on a foreign key side of a foreign key/primary key join.

17. The method of claim 15 wherein a plan highlight is a sort-based optimization on a value index on a predicate evaluation, on a group-by pipeline, on a merge join, on a order-by sort elimination, or on an analytics sort elimination.

18. The method of claim 15 wherein a plan highlight is a fully distributed group-by or an identically segmented projection join.

19. The method of claim 1 wherein the properties of a table in the set of tables are statistical properties and include a number of rows in a column of the table, a number of unique values in a column of the table, or both.

20. The method of claim 1 wherein eliminating queries comprises:

generating an execution plan for each of one or more remaining queries in the set of queries wherein each execution plan is based on one or more of the remaining candidate projections;

determining a difference in a level of optimization of each execution plan between the execution plan as optimized by the set of candidate projections before a most recent narrowing of the set of candidate projections and the execution plan as optimized after the most recent narrowing of the set of candidate projections;

determining for each query whether the query is sufficiently optimized based on the determined difference in the level of optimization; and

eliminating queries from the set of queries that are sufficiently optimized.

21. The method of claim 1 wherein creating the set of candidate projections further comprises:

generating seeds and extenders based on structural properties of queries in the set of queries;

creating a set of column sort orders from the seeds and extenders;

adding segmentation column sort orders to the set of column sort orders; and

creating the set of candidate projections from the set of column sort orders.

22. The method of claim 21 wherein the structural properties include one or more columns relied on by the set of queries and wherein a column in the one or more columns is a predicate column, a group-by column, an order-by column, a join column, or an analytics column.

23. The method of claim 21 wherein one or more candidate projections in the set of candidate projections satisfy an override.

24. The method of claim 23 wherein the override specifies a sort order, an encoding, or segmentation properties of a candidate projection.

25. The method of claim 23 wherein the override requires that column sort orders for a table in the set of tables begin with a specific column, the method further comprising eliminating column sort orders for the table that do not begin with the specific column.

26. The method of claim 23 wherein the override requires that column sort orders for a table in the set of tables have one or more columns with respective encodings, the method further comprising eliminating column sort orders for the table that do not have the one or more columns with the respective encodings.

27. The method of claim 23 wherein the override requires that column sort orders for a table in the set of tables be segmented by a column of the table, the method further comprising eliminating extended column sort orders for the table that are not segmented on the column.

28. The method of claim 21 wherein generating seeds and extenders further comprises:

if the column is a predicate column and a number of run-length encoding buckets defined by sorting and run-length encoding the column does not exceed a threshold, generating a seed equal to the column and an extender equal to the column.

29. The method of claim 21 wherein generating seeds and extenders further comprises:

if the column is in a set of group-by columns for a query in the set of queries, generating a seed equal to the set of group-by columns.

30. The method of claim 21 wherein generating seeds and extenders further comprises:

if the column is in a set of group-by columns and a number of run-length encoding buckets defined by sorting and run-length encoding the column does not exceed a threshold, generating an extender equal to the set of group-by columns.

31. The method of claim 21 wherein creating column sort orders from the seeds and extenders further comprises applying the extenders to the seeds and to results of applying the extenders to the seeds until no additional column sort orders can be generated.

32. The method of claim 1, further comprising for each of one or more of the remaining candidate projections that are not segmented, segmenting the candidate projection on one or more primary key columns of a table corresponding to the candidate projection or segmenting the candidate projection on a column that has a highest number of distinct values.

33. The method of claim 1, further comprising for each of one or more of the remaining candidate projections that are not segmented, if there is a functional dependency between a first column and a second column in the candidate projection, specifying that the candidate projection is sorted and run-length encoded on the first and second columns.

34. The method of claim 1, further comprising for each of one or more of the remaining candidate projections that are not segmented, performing one or more encoding experiments to determine an encoding scheme that yields optimal storage compression.

35. The method of claim 1 wherein creating the set of candidate projections and narrowing the set of candidate projections is performed by a relational database management system (RDBMS).

36. The method of claim 35 wherein the RDBMS is a row-oriented database, a column-oriented database, or a hybrid row and column-oriented database.

37. A computer program product, encoded on a computer-readable storage device, operable to cause data processing apparatus to perform operations comprising:

creating a set of candidate projections each being based on a column sort order in a set of column sort orders and being associated with properties of one or more tables in a set of tables to which the column sort order applies, wherein a column sort order is a sequence of one or more columns, each column'"'"'s data being stored in an order; and

until a stopping condition is reached, progressively narrowing the set of candidate projections and a set of queries by eliminating candidate projections that do not satisfy a performance improvement criterion for remaining queries based on the properties associated with the candidate projections.

38. A system comprising:

a sort order generator configured to create a set of column sort orders derived from a set of queries, wherein a column sort order is a sequence of one or more columns, each column'"'"'s data being stored in an order;

a projection generator configured create a set of candidate projections, each being based on a column sort order in the set of column sort orders and being associated with properties of one or more tables in a set of tables to which the column sort order applies; and

a candidate projection filter configured to filter one or more candidate projections from the set of candidate projections that do not satisfy a performance improvement criterion for the set of queries.

39. The system of claim 38 further comprising:

a query filter configured to filter one or more queries from the set of queries that are sufficiently optimized by candidate projections in the set of candidate projections.

40. The system of claim 39 further comprising:

a table filter configured to filter one or more tables from the set of tables that have a number of candidate projections in the set of candidate projections that has reached a target number of projections.

41. A computer-implemented method comprising:

segmenting a projection that includes a subset of a table'"'"'s columns in a sort order;

adding to the sort order, one or more first columns of the table that are functionally depended on by one or more of the projection'"'"'s columns;

appending to the sort order, one or more second columns of the table that functionally depend on one or more of the column'"'"'s projections; and

determining encoding schemes that improve storage compression for one or more columns of the projection.

42. The method of claim 41 in which segmenting comprises segmenting the projection on one or more primary key columns of the table.

43. The method of claim 41 in which segmenting comprises segmenting the projection on a column of the table having a highest number of distinct values.

44. The method of claim 41 in which segmenting results in the projection'"'"'s data being substantially evenly distributed across nodes.

45. The method of claim 41 in which adding the first columns to the projection comprises run-length encoding the first columns.

46. The method of claim 41 in which appending the second columns to the sort order comprises run-length encoding the second columns.

47. The method of claim 41 in which appending to the sort order to the one or more second columns comprises determining that a relationship of a number of run-length encoding buckets associated with the projection to a number of rows in the table is within a threshold.

48. The method of claim 41 in which if the first table columns are sort optional, the first table columns are prepended to the sort order.

49. The method of claim 41 comprising appending to the sort order one or more high number of distinct value columns from the table that are not run-length encoded.

50. The method of claim 41 in which a first column A functionally depends on a second column B, if it holds true that given any two tuples r1 and r2, if r1.A=r2.A, then r1.B=r2.B.

51. The method of claim 41 in which determining the encoding scheme for the one or more columns comprises creating a new projection that includes all of the projection'"'"'s encoded columns and one or more versions of each non-encoded column of the projection encoded according to a respective encoding scheme.

52. The method of claim 51 further comprising populating the new projection with data from the table.

53. The method of claim 52 in which the data is a random sampling of rows in the table that respects the table'"'"'s row ordering.

54. The method of claim 52 in which the data is not stored in an intermediate table before populating the new projection.

55. The method of claim 41 comprising determining which column versions require the least amount of storage for the data.

56. A computer program product, encoded on a computer-readable storage device, operable to cause data processing apparatus to perform operations comprising:

segmenting a projection that includes a subset of a table'"'"'s columns in a sort order;

adding to the sort order, one or more first columns of the table that are functionally depended on by one or more of the projection'"'"'s columns;

appending to the sort order, one or more second columns of the table that functionally depend on one or more of the column'"'"'s projections; and

determining encoding schemes that improve storage compression for one or more columns of the projection.

57. A system comprising:

a segmentor configured to segment a projection that includes a subset of a table'"'"'s columns in a sort order;

a first functional dependency modifier configured to add to the sort order, one or more first columns of the table that are functionally depended on by one or more of the projection'"'"'s columns;

a second functional dependency modifier configured to append to the sort order, one or more second columns of the table that functionally depend on one or more of the column'"'"'s projections; and

an encoding experimentation component configured to determine encoding schemes that improve storage compression for one or more columns of the projection.

58. The system of claim 57 wherein the segmentor is further configured to perform operations comprising segmenting the projection on one or more primary key columns of the table.

59. The system of claim 57 in which the segmentor is further configured to perform operations comprising segmenting the projection on a column of the table having a highest number of distinct values.

60. The system of claim 57 in which segmenting results in the projection'"'"'s data being substantially evenly distributed across nodes.

61. The system of claim 57 in which adding the first columns to the projection comprises run-length encoding the first columns.

62. The system of claim 57 in which appending the second columns to the sort order comprises run-length encoding the second columns.

63. The system of claim 57 in which appending the sort order to the one or more second columns comprises determining that a relationship of a number of run-length encoding buckets associated with the projection to a number of rows in the table is within a threshold.

64. The system of claim 57 in which if the first table columns are sort optional, the first table columns are prepended to the sort order.

65. The system of claim 57 further comprising a component configured to append to the sort order one or more high number of distinct value columns from the table that are not run-length encoded.

66. The system of claim 57 in which a first column A functionally depends on a second column B, if it holds true that given any two tuples r1 and r2, if r1.A=r2.A, then r1.B=r2.B.

67. The system of claim 57 wherein the encoding experimentation component is further configured to determine which column versions require the least amount of storage for the data.