Adaptive acceleration of retrieval queries

• US 20030158842A1
• Filed: 01/17/2003
• Published: 08/21/2003
• Est. Priority Date: 02/21/2002
• Status: Abandoned Application

• Current Assignee: Infocyclone Limited
• Original Assignee: Infocyclone Limited
• Inventors: Berlovitch, Albert, Kfir, Ziv, Weinraub, Yehuda, Kaplan, Yiftach, Ben-Eliahu, Rachel, Shurman, Michael, Levy, Eliezer, Moskovich, Reuven, Giladi, Ran, Menachi, Eliav, Turkel, Itzhak, Gang, Shahar
• Application Number:
  US10/347,033
• Publication Number:
  US 20030158842A1
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/24532 of parallel queries

Abstract

A database server accelerator, comprising a plurality of query execution machines, adapted to resolve database queries, a plurality of respective memory units, adapted to cache data from the database, each memory unit being accessible only by its respective execution machine, and a data-manager adapted to determine the data to be cached in each of the plurality of memory units.

Claims

1. A database server accelerator, comprising:

a plurality of query execution machines, adapted to resolve database queries;

a plurality of respective memory units, adapted to cache data from the database, each memory unit being accessible only by its respective execution machine; and

a data-manager adapted to determine the data to be cached in each of the plurality of memory units.

2. An accelerator according to claim 1, wherein the plurality of execution machines are included in a single casing.

3. An accelerator according to claim 1, comprising a query dispatcher adapted to provide queries to the plurality of query execution machines.

4. An accelerator according to claim 3, wherein the query dispatcher is adapted to provide at least some of the queries to a plurality of execution machines which jointly resolve the at least some queries.

5. An accelerator according to claim 3, wherein the query dispatcher is adapted to select one or more query machines to perform a query, at least partially according to the data referred to by the query and the data stored in the memory units.

6. An accelerator according to claim 1, wherein at least one of the execution machines comprises a plurality of processors.

7. An accelerator according to claim 6, wherein each of the plurality of processors of a specific execution machine can access all the address space of the respective memory unit of the execution machine.

8. An accelerator according to claim 6, wherein at least one of the processors of a specific execution machine can access only a portion of the address space of the respective memory unit of the execution machine.

9. An accelerator according to claim 1, wherein at least two of the execution machines have different processing powers.

10. An accelerator according to claim 1, wherein all the execution machines have the same processing power.

11. An accelerator according to claim 1, wherein at least two of the memory units have different storage space.

12. An accelerator according to claim 1, wherein all the memory units have the same storage space.

13. An accelerator according to claim 1, wherein at least two of the execution machines are adapted to resolve different types of queries.

14. An accelerator according to claim 1, wherein the data-manager is adapted to have each memory unit cache only data not stored in any of the other memory units.

15. An accelerator according to claim 1, wherein the data-manager is adapted to have at least two memory units store at least one common data portion.

16. An accelerator according to claim 15, wherein the data-manager is adapted to have at least two memory units cache the same data.

17. An accelerator according to claim 1, comprising a compiler adapted to convert queries provided to a plurality of the execution machines into operator statements executable by the machines.

18. An accelerator according to claim 1, wherein the data-manager is adapted to determine the data to be cached according to a roster of queries recently received by a system including the accelerator.

19. An accelerator according to claim 18, wherein the data-manager is adapted to determine the data to be cached based on the response times of the accelerator and at least one database server to at least one of the queries of the roster.

20. An accelerator according to claim 1, wherein the data-manager is adapted to repeatedly determine periodically the data to be cached in each of the plurality of memory units.

21. A method of preparing a database command for execution by a multi-executor database server, comprising:

receiving a high level database command;

retrieving, from an execution plan cache, an execution plan including one or more executable operator statements, corresponding to the received database command, the execution plan not defining which executor is to execute each of the operator statements; and

converting the execution plan into an operational plan that, for each of the operator statements, states a group of one or more executors from which an executor which is to execute the statement is to be selected.

22. A method according to claim 21, wherein converting the execution plan into a operational plan comprises converting into a operational plan that states for each of the operator statements a single executor which is to execute the statement.

23. A method according to claim 21, wherein converting the execution plan into a operational plan comprises converting using a method adapted to minimize the number of executors used in handling the command.

24. A method according to claim 21, wherein for each statement, the group of one or more executors includes all the executors stated for other statements of the plan that generate data required by the statement.

25. A database server, comprising:

a plurality of database execution machines;

a plurality of memory units, associated respectively with the execution machines, adapted to store data of a database; and

a resource governor adapted to periodically determine which portions of the database are to be stored in each of the memory units.

26. A database server according to claim 25, wherein the resource governor is adapted to determine a transfer of a database portion from a first memory unit to a second memory unit.

27. A database server according to claim 25, wherein the resource governor is adapted to determine which portions of the database are to be stored in each of the memory units responsive to a roster of queries recently received by a system including the database server.

28. A database server according to claim 27, wherein the resource governor is adapted to group the queries of the roster into clusters and to determine the portions of the database to be stored in each of the memory units in a manner which preferentially places data referenced by queries of a single cluster in the same memory unit.

29. A database server, comprising:

at least one memory unit adapted to store data of a database;

a resource governor adapted to periodically determine which indices should be created for which portions of the database stored in the memory unit; and

an index creating unit adapted to automatically create the indices determined by the resource governor, responsive to the periodic determination.

30. A database server according to claim 29, wherein the resource governor is adapted to determine the indices that should be created at least partially according to a roster of queries recently directed to a system including the database server.

31. A database server according to claim 30, wherein the resource governor is adapted to organize the queries of the roster into clusters, to assign importance scores to the clusters and to determine the indices to be created for one or more of the clusters at least partially according to an order of the scores of the clusters.

32. A database server according to claim 31, wherein for one or more of the clusters, the resource governor is adapted to determine for one or more columns referenced by queries of the cluster, access types most commonly used in accessing the columns and to select one or more indices for the column at least partially according to the determined access types.

33. A method of resolving a database command, comprising:

receiving a high level database command;

retrieving an execution plan corresponding to the received database command, the execution plan including at least one non-executable replaceable directive representing a group of a plurality of different sequences of one or more directives, which perform the same task; and

replacing the non-executable replaceable directive by one of the sequences of the group.

34. A method according to claim 33, wherein receiving the high level database command comprises receiving an SQL command.

35. A method according to claim 33, wherein replacing the non-executable directive comprises selecting one of the sequences of the group to replace the non-executable directive, at least partially according to at least one parameter of data generated by the at least one of the directives of the plan executed before the replacement.

36. A method according to claim 35, wherein the at least one parameter comprises a number of rows of in the generated data.

37. A method according to claim 33, wherein replacing the non-executable directive comprises selecting one of the sequences of the group to replace the non-executable directive, depending on one or both of a time utilized so far to execute the plan or an expected time remaining until completion of the plan.

38. A method according to claim 33, wherein replacing the non-executable directive comprises selecting one of the sequences of the group to replace the non-executable directive, depending on at least one state parameter of an execution machine executing the plan.

39. A method according to claim 38, wherein the at least one state parameter comprises a work load of the execution machine.

40. A method according to claim 38, wherein the at least one state parameter comprises a number of queries waiting to be executed by the machine.

41. A method according to claim 38, wherein the at least one state parameter comprises an amount of available memory in the machine.

42. A method according to claim 33, wherein replacing the non-executable directive comprises replacing after executing at least one of the directives of the plan.

43. A method according to claim 33, wherein replacing the non-executable directive comprises replacing by a processor which is to execute the segment replacing the non-executable directive.

44. A method according to claim 33, wherein replacing the non-executable directive comprises replacing by an executor which did not generate the execution plan.

45. A method according to claim 33, wherein each of the sequences of one or more directives comprises a single directive.

46. A method according to claim 33, wherein at least one of the sequences of one or more directives comprises a plurality of directives.

47. A method according to claim 33, comprising estimating an execution time of each of a plurality of the sequences of the group and replacing the non-executable directive comprises replacing by a sequence having a shortest execution time.

48. A method of caching data by a database server accelerator, comprising:

selecting queries to be handled by the accelerator; and

caching the data required to resolve the selected queries, responsive to the selection.

49. A method according to claim 48, wherein selecting the queries to be handled by the accelerator comprises estimating, for a plurality of queries, the benefit to the queries from handling the queries by the accelerator and selecting the queries to be handled by the accelerator responsive to the estimation.

50. A method according to claim 49, wherein estimating the benefit to the queries comprises estimating, for each of the plurality of queries, the difference between the handling time of the query by the accelerator and the handling time of the query by at least one database server.

51. A method according to claim 49, wherein determining which queries are to be handled by the accelerator comprises assigning each of the queries an acceleration score and determining the handled queries at least partially according to the scores, preferring queries with higher scores to be handled by the accelerator.

52. A method according to claim 51, wherein determining the handled queries comprises grouping the queries into clusters and determining one or more clusters of queries to be handled.

53. A method according to claim 52, wherein grouping the queries into clusters comprises grouping queries relating to the same data columns in same clusters.

54. A method according to claim 51, wherein better acceleration scores are given to queries with higher QoS ratings.

55. A method according to claim 51, wherein the acceleration score increases with the popularity of the query.

56. A method of determining a data organization of data of a database, comprising:

accumulating a roster of queries recently directed to the database;

grouping the queries of the roster into a plurality of clusters;

arranging the clusters in an order in which their data is to be handled; and

determining an organization for the data of queries of one or more clusters at least partially according to the order from the arranging.

57. A method according to claim 56, wherein accumulating the roster of queries comprises accumulating queries directed to the database in a recent predetermined time period.

58. A method according to claim 56, wherein accumulating the roster of queries comprises accumulating queries which were recently directed to the database at least a predetermined number of times.

59. A method according to claim 56, wherein grouping the queries into clusters comprises grouping the queries at least partially according to the data portions they reference.

60. A method according to claim 56, comprising defining a query distance function which provides a distance measure for pairs of queries and wherein grouping the queries into clusters comprises grouping queries into clusters which each has a respective hub query, such that the distance between each query and the hub of the cluster to which the query is assigned is shorter than the distance to any other hub.

61. A method according to claim 60, wherein the value of the query distance function depends on the number of data portions referenced by both the queries to which the function is applied.

62. A method according to claim 60, wherein the value of the query distance function depends on the sizes of data portions referenced by both the queries to which the function is applied.

63. A method according to claim 60, wherein the value of the query distance function depends on the similarity of the access types used by the queries to which the function is applied in accessing data portions referenced by both the queries.

64. A method according to claim 60, wherein grouping the queries into clusters comprises grouping such that each query is included in only a single cluster.

65. A method according to claim 56, wherein grouping the queries into clusters comprises grouping such that all the data portions referenced by queries of a single cluster can be hosted by a single execution machine of a server of the database.

66. A method according to claim 56, wherein arranging the clusters comprises assigning each cluster a score and organizing the clusters at least partially according to the score values.

67. A method according to claim 66, wherein the cluster score depends on resources required in order to handle the queries of the cluster.

68. A method according to claim 66, wherein the cluster score depends on resources required in order to organize the data required by the cluster.

69. A method according to claim 66, wherein the organization is performed for a database accelerator and wherein the cluster score depends on an expected advantage from handling the queries of the cluster by the accelerator as compared to handling by a database server associated with the accelerator.

70. A method according to claim 56, wherein determining an organization for the data comprises determining which indices are to be created.

71. A method according to claim 56, wherein determining an organization for the data comprises determining which data portions are to be cached by an accelerator.

72. A method according to claim 56, wherein determining an organization for the data comprises determining a partitioning of one or more data tables.

73. A method according to claim 56, wherein determining an organization for the data comprises determining which data portions are to be hosted by each of a plurality of separate execution machines.

74. A method of determining whether a query is to be handled by an accelerator, comprising:

determining whether the query can be resolved by the accelerator with its currently cached data;

determining at least one additional attribute of the accelerator or the query; and

determining whether to handle the query by the accelerator, responsive to the at least one additional attribute.

75. A method according to claim 74, wherein the at least one additional attribute comprises a current load of the accelerator.

76. A method according to claim 74, wherein the at least one additional attribute comprises an expected response time of the accelerator for the query.

77. A method according to claim 74, wherein the at least one additional attribute comprises an expected response time of a database server accelerated by the accelerator, for the query.

78. A method according to claim 74, wherein the at least one additional attribute comprises whether the accelerator has a compiled version of the query.

79. A database server, comprising:

at least one memory unit adapted to store data of a database including tables, in verticals including one or more columns of the table, at least one of the tables being stored in a plurality of separate verticals; and

an execution machine adapted to resolve queries using the data in the at least one memory unit, the execution machine adapted to always load into a processor of the machine entire rows of verticals on which it operates.

80. A server according to claim 79, wherein the execution machine is not adapted to execute directives that relate to a plurality of verticals of a single table.

81. A server according to claim 79, comprising a resource governor adapted to determine which columns of a table are to be stored in the at least one memory unit in a single vertical, at least partially according to directives expected to be performed by the execution machine.

82. A server according to claim 79, wherein the at least one memory unit is adapted to store only a portion of at least one table.

83. A database server, comprising:

at least one memory unit adapted to store data of a database including tables, at least one of the tables being stored in a plurality of separate sub-portions;

an execution machine adapted to resolve queries using the data in the at least one memory unit; and

a resource governor adapted to determine the sub-groups in which the data to be stored in the at least one memory unit are to be organized, at least partially according to the queries expected to be received by the database server.

84. A server according to claim 83, wherein the execution machine is not adapted to execute directives that relate to data in a plurality of sub-portions of a single table.