Automatic vertical-database design

• US 10,007,686 B2
• Filed: 08/02/2006
• Issued: 06/26/2018
• 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: Lawande, Shilpa, Rasin, Alexander, Trajman, Omer, Zdonik, Stanley B.
• Primary Examiner(s): Burke, Jeff A
• Application Number:
  US11/461,926
• Publication Number:
  US 20080040348A1
• Time in Patent Office: 4,346 Days
• Field of Search: 707 5, 707715, 707803, 707974
• 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-implemented method comprising:

for each of multiple candidate sort orders of a table having rows and columns, determining a cost based on candidate training queries that have execution costs that satisfy an improvement criterion;

based on the respective costs of the candidate sort orders, selecting sort orders at least one of which satisfies all of the candidate training queries;

for each of the selected sort orders, adding, to a design of a database, an included projection, wherein a projection is a subset of the columns of the table sorted according to a same order, the columns of the projection to be physically stored in accordance with the selected sort order; and

each of the multiple candidate sort orders from which the sort orders are selected defining an order with respect to a putative projection comprising a view of one or more columns that are not necessarily identical to the columns of the included projection.

2. The method of claim 1 where selecting sort orders from candidate sort orders includes determining storage space which would be required by a projection corresponding to the sort order.

3. The method of claim 2 where selecting sort orders is based on which sort order has a largest ratio of cost to storage space as compared to other sort orders.

4. The method of claim 1, further comprising segmenting the projection into a plurality of segments.

5. The method of claim 4, further comprising replicating each of the segments on a plurality of storage nodes.

6. The method of claim 5 where each replicated segment has a different sort order.

7. The method of claim 5 where a same column in each of the replicated segments is compressed according to a different compression scheme on each of the plurality of storage nodes.

8. The method of claim 1, further comprising:

assigning to each of a plurality of storage nodes a super-projection of all tables for the database; and

deleting from a storage node in the plurality of storage nodes a super-projection'"'"'s physical column made redundant on that storage node by the addition of the projection to that storage node.

9. The method of claim 1 where the determined cost is based on an estimated time to evaluate queries or an estimated number of disk operations required to evaluate queries.

10. The method of claim 9 where the estimated number of disk operations takes into consideration compression of projections and sort orders used to execute the query.

11. A non-transitory computer-readable medium containing instructions operable to cause a computer system to perform operations comprising:

for each of multiple candidate sort of a table having rows and columns, determining a cost based on candidate training queries that have execution costs that satisfy an improvement criterion;

based on the respective costs of the candidate sort orders, selecting sort orders at least one of which satisfies all of the candidate training queries; and

in addition to any indexes for the database, for each of the selected sort orders, adding, to a design of a database, an included projection, wherein a projection is a subset of the columns of the table sorted according to a same order, the columns of the projection to be physically stored in accordance with the selected sort order; and

each of the multiple candidate sort orders from which the sort orders are selected defining an order with respect to a putative projection comprising a view of one or more columns that are not necessarily identical to the columns of the included projection.

12. The computer-readable medium of claim 11 where selecting sort orders from candidate sort orders includes determining storage space which would be required by a projection corresponding to the sort order.

13. The computer-readable medium of claim 12 where selecting sort orders is based on which sort order has a largest ratio of cost to storage space as compared to other sort orders.

14. The computer-readable medium of claim 11, further comprising instructions operable to cause the computer system to perform operations comprising segmenting the projection into a plurality of segments.

15. The computer-readable medium of claim 14, further comprising instructions operable to cause the computer system to perform operations comprising replicating each of the segments on a plurality of storage nodes.

16. The computer-readable medium of claim 15 where each replicated segment has a different sort order.

17. The computer-readable medium of claim 15 where a same column in each of the replicated segments is compressed according to a different compression scheme on each of the plurality of storage nodes.

18. The computer-readable medium of claim 11, further comprising instructions operable to cause the computer system to perform operations comprising:

assigning to each of a plurality of storage nodes a super-projection of all tables for the database; and

deleting from a storage node in the plurality of storage nodes a super-projection'"'"'s physical column made redundant on that storage node by the addition of the projection to that storage node.

19. The computer-readable medium of claim 11 where the determined cost is based on an estimated time to evaluate queries or an estimated number of disk operations required to evaluate queries.

20. The computer-readable medium of claim 19 where the estimated number of disk operations takes into consideration compression of projections and sort orders used to execute the query.

21. A system comprising:

a computer-readable medium containing instructions; and

one or more processors operable to execute the instructions to perform operations comprising;

for each of multiple candidate sort orders of a table having rows and columns, determining a cost based on candidate training queries that have execution costs that satisfy an improvement criterion;

based on the respective costs of the candidate sort orders, selecting sort orders at least one of which satisfies all of the candidate training queries; and

for each of the selected sort orders, adding, to a design of a database, an included projection, wherein a projection is a subset of the columns of the table sorted according to a same order, the columns of the projection to be physically stored in accordance with the selected sort order; and

each of the multiple candidate sort orders from which the sort orders are selected defining an order with respect to a putative projection comprising a view of one or more columns that are not necessarily identical to the columns of the included projection.

22. The system of claim 21 where selecting sort orders from candidate sort orders includes determining storage space which would be required by a projection corresponding to the sort order.

23. The system of claim 22 where selecting sort orders is based on which sort order has a largest ratio of cost to storage space as compared to other sort orders.

24. The system of claim 21, further comprising instructions operable to cause the computer system to perform operations comprising segmenting the projection into a plurality of segments.

25. The system of claim 24, further comprising instructions operable to cause the computer system to perform operations comprising replicating each of the segments on a plurality of storage nodes.

26. The system of claim 25 where each replicated segment has a different sort order.

27. The system of claim 25 where a same column in each of the replicated segments is compressed according to a different compression scheme on each of the plurality of storage nodes.

28. The system of claim 21, further comprising instructions operable to cause the computer system to perform operations comprising:

assigning to each of a plurality of storage nodes a super-projection of all tables for the database; and

deleting from a storage node in the plurality of storage nodes a super-projection'"'"'s physical column made redundant on that storage node by the addition of the projection to that storage node.

29. The system of claim 21 where the determined cost is based on an estimated time to evaluate queries or an estimated number of disk operations required to evaluate queries.

30. The system of claim 29 where the estimated number of disk operations takes into consideration compression of projections and sort orders used to execute the query.