Automatic Vertical-Database Design

• US 20080040348A1
• Filed: 08/02/2006
• Published: 02/14/2008
• Est. Priority Date: 08/02/2006
• Status: Active Grant

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: entIT Software LLC (Open Text Corporation)
• Inventors: Zdonik, Stanley B., Rasin, Alexander, Trajman, Omer, Lawande, Shilpa
• Granted Patent: US 10,007,686 B2
• Time in Patent Office: Days
• US Class Current: 707/7
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof

Abstract

An automatic physical-layout designer for a database-management system determines the database'"'"'s physical layout from a set of training queries, the database'"'"'s logical design, and a parameter k that indicates how many storage nodes can be lost without losing access to any of the data. The designer lays the database out as a column store such that the stored columns constitute redundant projections on the system'"'"'s different storage nodes. It repeatedly identifies a projection, whose addition to the design will result in the greatest performance improvement for the training queries. In doing so, it takes into account the different compression formats to which the different projections lend themselves. When a projection has been identified as one to be added, it is added on one node, and k projections having the same columns are added to other nodes. The designer continues thus adding projections until a space budget has been reached.

Claims

1. A computer system configured as a database designer for specifying a layout, among a plurality of storage nodes, of a database whose logical design includes at least one table of which each is organized in rows and columns, the computer system being so configured as to:

A) determine a physical design for the database by;

i) choosing a set of candidate sort orders; and

ii) in each of a plurality of projection-selection operations;

a) selecting a candidate sort order, from among the candidate sort orders not previously selected, in accordance with the cost of executing training queries on physical projections that have those candidate sort orders;

b) identifying the training queries for which addition of a projection having the selected sort order results in a cost-of-execution change that meets some cost-improvement criterion;

c) adding to at least one of the storage nodes of the physical design a first physical projection, thereby associated with that projection-selection operation and not similarly associated with a previous projection-selection operation, having the selected sort order and including vertically arranged versions of the logical columns that the training queries thus identified require; and

d) adding at least to one different one of the storage nodes of the physical design at least a further physical projection, whose sort order differs from that of the first physical projection, whose physical column versions are versions of the logical columns of which the first physical projection'"'"'s physical column versions are versions, such that all data in the first physical projection is replicated on more than one of the storage node; and

B) generating an output indicative of the resultant physical design.

2. A computer system as defined in claim 1 configured to remove from the set of training queries those identified as being the training queries for which the cost-of-execution change resulting from addition of a projection having the selected sort order meets the cost-improvement criterion.

3. A computer system as defined in claim 1 wherein the cost-improvement criterion depends on a ratio of cost reduction to storage space.

4. A computer system as defined in claim 1 wherein the data in some of the physical column versions are sorted in accordance with the values of another column'"'"'s attribute.

5. A computer system as defined in claim 1 wherein:

A) the database designer additionally initializes the physical design by so assigning to the storage nodes of the physical design a plurality of super-projections of each of the logical design'"'"'s tables as to result in a physical design in which all of the database'"'"'s data remain available whenever no more than k of the nodes become unavailable, where k is some positive integer; and

B) at least one said projection-selection operation further includes deleting from a said storage node of the physical design a super-projection'"'"'s physical column made redundant on that storage node by the addition of that projection-selection operation'"'"'s first physical projection or further physical projection.

6. For employing a computer system to lay out among a plurality of storage nodes a database whose logical design includes at least one table of which each is organized in rows and columns, a method that comprises employing the computer system to:

A) determine a physical design for the database by;

i) choosing a set of candidate sort orders; and

ii) in each of a plurality of projection-selection operations;

a) selecting a candidate sort order, from among the candidate sort orders not previously selected, in accordance with the cost of executing training queries on physical projections that have those candidate sort orders;

b) identifying the training queries for which addition of a projection having the selected sort order results in a cost-of-execution change that meets some cost-improvement criterion;

c) adding to at least one of the storage nodes of the physical design a first physical projection, thereby associated with that projection-selection operation and not similarly associated with a previous projection-selection operation, having the selected sort order and including vertically arranged versions of the logical columns that the training queries thus identified require; and

d) adding at least to one different one of the storage nodes of the physical design at least a further physical projection, whose sort order differs from that of the first physical projection, whose physical column versions are versions of the logical columns of which the first physical projection'"'"'s physical column versions are versions, such that all data in the first physical projection is replicated on more than one of the storage node; and

B) physically arrange the database'"'"'s data in at least one storage device in accordance with the design thus determined.

7. A method as defined in claim 6 comprising removing from the set of training queries those identified as being the training queries for which the cost-of-execution change resulting from addition of a projection having the selected sort order meets the cost-improvement criterion.

8. A method as defined in claim 6 wherein the cost-improvement criterion depends on a ratio of cost reduction to storage space.

9. A method as defined in claim 6 wherein the data in some of the physical column versions are sorted in accordance with the values of another column'"'"'s attribute.

10. A method as defined in claim 6 wherein:

A) the method further comprises initializing the physical design by so assigning to the storage nodes of the physical design a plurality of super-projections of each of the logical design'"'"'s tables as to result in a physical design in which all of the database'"'"'s data remain available whenever no more than k of the nodes become unavailable, where k is some positive integer; and

B) at least one said projection-selection operation further includes deleting from a said storage node of the physical design a super-projection'"'"'s physical column made redundant on that storage node by the addition of that projection-selection operation'"'"'s first physical projection or further physical projection.

11. A storage medium containing machine instructions readable by a computer system to configure the computer system as a database designer that specifies a layout, among a plurality of storage nodes, of a database whose logical design includes at least one table of which each is organized in rows and columns, by:

A) determining a physical design for the database by;

i) choosing a set of candidate sort orders; and

ii) in each of a plurality of projection-selection operations;

a) selecting a candidate sort order, from among the candidate sort orders not previously selected, in accordance with the cost of executing training queries on physical projections that have those candidate sort orders;

b) identifying the training queries for which addition of a projection having the selected sort order results in a cost-of-execution change that meets some cost-improvement criterion;

c) adding to at least one of the storage nodes of the physical design a first physical projection, thereby associated with that projection-selection operation and not similarly associated with a previous projection-selection operation, having the selected sort order and including vertically arranged versions of the logical columns that the training queries thus identified require; and

d) adding at least to one different one of the storage nodes of the physical design at least a further physical projection, whose sort order differs from that of the first physical projection, whose physical column versions are versions of the logical columns of which the first physical projection'"'"'s physical column versions are versions, such that all data in the first physical projection is replicated on more than one of the storage node; and

B) generating an output indicative of the resultant physical design.

12. A storage medium as defined in claim 11 whose instructions configure the computer system to remove from the set of training queries those identified as being the training queries for which the cost-of-execution change resulting from addition of a projection having the selected sort order meets the cost-improvement criterion.

13. A storage medium as defined as defined in claim 11 wherein the cost-improvement criterion depends on a ratio of cost reduction to storage space.

14. A storage medium as defined in claim 11 wherein the data in some of the physical column versions are sorted in accordance with the values of another column'"'"'s attribute.

15. A storage medium as defined in claim 11 wherein:

A) the database designer additionally initializes the physical design by so assigning to the storage nodes of the physical design a plurality of super-projections of each of the logical design'"'"'s tables as to result in a physical design in which all of the database'"'"'s data remain available whenever no more than k of the nodes become unavailable, where k is some positive integer; and

B) at least one said projection-selection operation further includes deleting from a said storage node of the physical design a super-projection'"'"'s physical column made redundant on that storage node by the addition of that projection-selection operation'"'"'s first physical projection or further physical projection.

18. A computer system as defined in claim 11 wherein the cost estimates are additionally based on the candidate physical versions'"'"' sort orders.

16. A computer system configured as an automatic database designer that, for a database whose logical design includes at least one table of which each is organized in rows and columns, determines a physical design by:

A) making a list that includes, for each of a plurality of the database'"'"'s logical columns, a plurality of vertically arranged candidate physical versions of which at least a plurality differ at least by compression format from one another;

B) for different ones of the candidate physical versions of the same logical columns, making respective cost estimates of the different costs of executing training queries on the database by using those different candidate physical versions, wherein the cost estimate depends on the candidate physical versions'"'"' compression formats;

C) selecting from among the candidate physical versions in accordance with those estimates;

D) including the candidate versions thus selected in a physical design; and

E) generating an output indicative of the resultant physical design.

17. A computer system as defined in claim 16 wherein the physical design so assigns the physical versions of the columns to a plurality of storage nodes that that the set of storage nodes remaining after removal of any k of the nodes contains all of the database'"'"'s data, where k is a positive integer.

19. For managing a database whose logical design includes at least one table of which each is organized in rows and columns, a method comprising:

A) determining a physical design for the database by;

i) making a list that includes, for each of a plurality of the database'"'"'s logical columns, a plurality of vertically arranged candidate physical versions of which at least a plurality differ at least by compression format from one another;

ii) for different ones of the candidate physical versions of the same logical columns, making respective cost estimates of the different costs of executing training queries on the database by using those different candidate physical versions, wherein the cost estimates depend on those candidate physical versions'"'"' compression formats;

iii) selecting from among the candidate physical versions in accordance with those cost estimates; and

iv) including the candidate column versions thus selected in a physical design; and

;

B) physically arranging the database'"'"'s data in at least one storage device in accordance with the design thus determined.

20. A method as defined in claim 19 wherein the physical design so assigns the physical versions of the columns to a plurality of storage nodes that that the set of storage nodes remaining after removal of any k of the nodes contains all of the database'"'"'s data, where k is a positive integer.

21. A method as defined in claim 19 wherein the cost estimates are additionally based on the candidate physical versions'"'"' sort orders.

22. A storage medium containing instructions readable by a computer system to configure the computer system as an automatic database designer that, for a database whose logical design includes at least one table of which each is organized in rows and columns, determines a physical design by:

A) making a list that includes, for each of a plurality of the database'"'"'s logical columns, a plurality of vertically arranged candidate physical versions of which at least a plurality differ at least by compression format from one another;

B) for different ones of the candidate physical versions of the same logical columns, making respective cost estimates of the different costs of executing training queries on the database by using those different candidate physical versions, wherein the cost estimate depends on the candidate physical versions'"'"' compression formats;

C) selecting from among the candidate physical versions in accordance with those estimates;

D) including the candidate versions thus selected in a physical design; and

E) generating an output indicative of the resultant physical design.

23. A storage medium as defined in claim 22 wherein the physical design so assigns the physical versions of the columns to a plurality of storage nodes that that the set of storage nodes remaining after removal of any k of the nodes contains all of the database'"'"'s data, where k is a positive integer.

24. A storage medium as defined in claim 22 wherein the cost estimates are additionally based on the candidate physical versions'"'"' sort orders.

25. A computer system configured as an automatic database designer that, for a database whose logical design includes at least one table of which each is organized in rows and columns, specifies a physical design by:

A) making a list that includes, for each of a plurality of the database'"'"'s logical columns, a plurality of candidate physical versions of which at least a plurality differ at least by sort order from one another;

B) for different ones of the candidate physical versions of the same logical columns, making respective cost estimates of the different costs of executing training queries on the database by using those different candidate physical versions, wherein the cost estimate depends on those different candidate physical versions'"'"' sort orders;

C) selecting from among the candidate physical versions in accordance with those cost estimates;

D) including the candidate physical versions thus selected in a physical design; and

E) generating an output indicative of the resultant physical design.

26. A computer system as defined in claim 25 wherein the physical design so assigns the physical versions of the columns to a plurality of storage nodes that that the set of storage nodes remaining after removal of any k of the nodes contains all of the database'"'"'s data, where k is a positive integer.

27. For employing a computer system to lay out a database whose logical design includes at least one table of which each is organized in rows and columns, a method that comprises employing the computer system to:

A) make a list that includes, for each of a plurality of the database'"'"'s logical columns, a plurality of candidate physical versions of which at least a plurality differ at least by sort order from one another;

B) for different ones of the candidate physical versions of the same logical columns, make respective cost estimates of the different costs of executing training queries on the database by using those different candidate physical versions, wherein the cost estimate depends on those different candidate physical versions'"'"' sort orders;

C) select from among the candidate physical versions in accordance with those cost estimates;

D) include the candidate physical versions thus selected in a physical design; and

E) physically arranging the database'"'"'s data in at least one storage device in accordance with the design thus determined.

28. A method as defined in claim 27 wherein the physical design so assigns the physical versions of the columns to a plurality of storage nodes that that the set of storage nodes remaining after removal of any k of the nodes contains all of the database'"'"'s data, where k is a positive integer.

29. A storage medium containing machine instructions readable by a computer system to configure the computer system as an automatic database designer that, for a database whose logical design includes at least one table of which each is organized in rows and columns, determines a physical design by:

A) making a list that includes, for each of a plurality of the database'"'"'s logical columns, a plurality of candidate physical versions of which at least a plurality differ at least by sort order from one another;

B) for different ones of the candidate physical versions of the same logical columns, making respective cost estimates of the different costs of executing training queries on the database by using those different candidate physical versions, wherein the cost estimate depends on those different candidate physical versions'"'"' sort orders;

C) selecting from among the candidate physical versions in accordance with those cost estimates;

D) including the candidate physical versions thus selected in a physical design; and

E) generating an output indicative of the resultant physical design.

30. A storage medium as defined in claim 29 wherein the physical design so assigns the physical versions of the columns to a plurality of storage nodes that that the set of storage nodes remaining after removal of any k of the nodes contains all of the database'"'"'s data, where k is a positive integer.

31. A computer system configured as an automatic database designer that, for a database whose logical design includes at least one table of which each is organized in rows and columns, specifies a layout thereof among a plurality of storage nodes by:

A) estimating the cost of executing a set of training queries and thereby, choosing a plurality of different vertically arranged physical projections of the logical columns that together contain at least k+1 copies of all the database'"'"'s data, where k is a positive integer;

B) assigning the physical projections thus chosen to the storage nodes in such a manner that the set of storage nodes remaining after removal of any k of the nodes contains all of the database'"'"'s data; and

C) generating an output representative of a physical design in which the chosen physical projections are thus assigned.

32. For employing a computer system to specify a physical design in accordance with which to lay out among a plurality of storage nodes a database whose logical design includes at least one table of which each is organized in rows and columns, a method that comprises employing the computer system to:

A) by estimating the cost of executing a set of training queries, choose a plurality of different vertically arranged physical projections of the logical columns that together contain at least k+1 copies of all the database'"'"'s data, where k is a positive integer;

B) assign the physical projections thus chosen to the storage nodes in such a manner that the set of storage nodes remaining after any k of the nodes is removed contains all of the database'"'"'s data; and

C) generate an output representative of a physical design in which the chosen physical projections are thus assigned.

33. A storage medium containing machine instructions readable by a computer system to configure the computer system as an automatic database designer that, for a database whose logical design includes at least one table of which each is organized in rows and columns, determines a layout thereof among a plurality of storage nodes by:

A) estimating the cost of executing a set of training queries and thereby choosing a plurality of different vertically arranged physical projections of the logical columns that together contain at least k+1 copies of all the database'"'"'s data, where k is a positive integer;

B) assigning the physical projections thus chosen to the storage nodes in such a manner that the set of storage nodes remaining after any k of the nodes is removed contains all of the database'"'"'s data; and

C) generating an output representative of a physical design in which the chosen physical projections are thus assigned.