DISTRIBUTED HARDWARE-BASED DATA QUERYING

• US 20110040771A1
• Filed: 06/04/2009
• Published: 02/17/2011
• Est. Priority Date: 06/18/2008
• Status: Abandoned Application

• Current Assignee: Petascan Limited
• Original Assignee: Petascan Limited
• Inventors: Lazovsky, Alexander, Gilyadov, Camuel
• Application Number:
  US12/989,652
• Publication Number:
  US 20110040771A1
• Time in Patent Office: Days
• US Class Current: 707/754
• CPC Class Codes: G06F 13/385 for adaptation of a particular data processing system to different peripheral devices

Abstract

A data storage apparatus (20, 92, 116) includes a data processing unit (24) and multiple storage units (36, 60). Each storage unit includes one or more memory devices (40, 64), which are operative to store a data partition that is drawn from a data structure and assigned to the storage unit, and logic circuitry (44, 68, 72), which is configured to accept one or more sub-queries addressed to the storage unit and to process the respective data partition stored in the storage unit responsively to the sub-queries, so as to produce filtered data. The data processing unit is configured to transform an input query defined over the data structure into the sub-queries, to provide the sub-queries to the storage units, and to process the filtered data produced by the storage units, so as to generate and output a result in response to the input query.

Claims

1. A data storage apparatus, comprising:

multiple storage units, each storage unit comprising;

one or more memory devices, which are operative to store a data partition that is drawn from a data structure and assigned to the storage unit; and

logic circuitry, which is configured to accept one or more sub-queries addressed to the storage unit and to process the respective data partition stored in the storage unit responsively to the sub-queries, so as to produce filtered data; and

a data processing unit, which is configured to transform an input query defined over the data structure into the sub-queries, to provide the sub-queries to the storage units, and to process the filtered data produced by the storage units, so as to generate and output a result in response to the input query.

2. The apparatus according to claim 1, wherein the data structure comprises data elements stored in multiple rows and columns, and wherein the data processing unit is configured to divide the data structure into multiple tiles, each tile comprising the data elements that are stored in an intersection of a respective first sub-range of the rows and a respective second sub-range of the columns, and to store the data structure by distributing the tiles among the storage units.

3. The apparatus according to claim 2, wherein the data processing unit is configured to distribute the tiles among the memory devices in accordance with a random pattern.

4. The apparatus according to claim 2, wherein the data processing unit is configured to distribute a subset of the tiles that are associated with a given sub-range of the rows substantially evenly among the memory devices.

5. The apparatus according to claim 2, wherein the data processing unit is configured to distribute a first subset of the tiles that are associated with a first sub-range of the rows among the memory devices according to a first distribution, and to distribute a second subset of the tiles that are associated with a second sub-range of the rows, which succeeds the first sub-range, according to a second distribution that is different from the first distribution.

6. The apparatus according to claim 2, wherein the logic circuitry in a given storage unit is configured to store a given tile in the memory devices in a first orientation, and, in response to a given sub-query that addresses the given tile, to rotate the given tile to a second orientation and to execute the given sub-query using the rotated tile.

7. The apparatus according to claim 1, wherein the data processing unit is configured to define a given sub-query that addresses a given data partition stored in a given storage unit, and to provide the given sub-query to the given storage unit for processing.

8. The apparatus according to claim 1, wherein the logic circuitry in a given storage unit is configured to filter the data partition stored in the given storage unit responsively to one or more of the sub-queries addressed to the storage unit.

9. The apparatus according to claim 1, wherein the data processing unit is configured to apply additional filtering to the filtered data produced by the storage units.

10. The apparatus according to claim 1, wherein the logic circuitry in a given storage unit is configured to perform a data aggregation operation on the data partition stored in the given storage unit responsively to one or more of the sub-queries addressed to the storage unit.

11. The apparatus according to claim 1, wherein the logic circuitry in a given storage unit is configured to apply at least one of a logic operation and an arithmetic operation to the data partition stored in the given storage unit.

12. The apparatus according to claim 1, wherein the logic circuitry comprises programmable logic, and wherein the data processing unit is configured to reconfigure the programmable logic responsively to a criterion defined over at least one of the data structure and the input query.

13. The apparatus according to claim 1, wherein a given storage unit comprises at least one asymmetric interface for data storage and retrieval in the memory devices of the given storage unit, the asymmetric interface having a first bandwidth for the data storage and a second bandwidth, higher than the first bandwidth, for the data retrieval.

14. The apparatus according to claim 1, wherein the logic circuitry in a given storage unit is configured to compress at least some of the data partition assigned to the given storage unit prior to storing the data partition in the memory devices.

15. The apparatus according to claim 14, wherein the logic circuitry in the given storage unit is configured to apply a given sub-query to the compressed data partition so as to produce the filtered data, and to decompress only the filtered data.

16. The apparatus according to claim 1, wherein the data processing unit is configured to encrypt data exchanged with the storage units and with end users.

17. The apparatus according to claim 1, wherein the logic circuitry in a given storage unit is configured to encrypt data stored in the memory devices.

18. The apparatus according to claim 1, and comprising multiple Network Interface Cards (NICs) coupled to the respective storage units, wherein the storage units are configured to exchange data over a network via the respective NICs.

19. The apparatus according to claim 1, wherein the storage units are configured to communicate with one another so as to exchange data for processing the sub-queries.

20. The apparatus according to claim 1, wherein the data processing unit is configured to identify input queries whose processing accesses common data elements, and to cause the storage units to access the common data elements jointly while processing the identified input queries.

21. The apparatus according to claim 1, wherein the data processing unit is configured to convert the data structure into a raw data format, so as to produce data partitions having the raw data format for storage in the storage units.

22. The apparatus according to claim 1, wherein the data processing unit is configured to represent a given data partition, which is assigned to a given storage unit and has a given data format, using code that is executable by the given storage unit, and wherein the logic circuitry in the given storage unit is configured to access the given data format by executing the code.

23. The apparatus according to claim 1, wherein the logic circuitry in a given storage unit is configured to communicate using a communication protocol that is compatible with another type of storage units, which do not have query processing capabilities.

24. The apparatus according to claim 1, wherein the data processing unit is configured to allocate first and second separate sets of hardware elements in the multiple storage units to respective first and second user groups, and to prevent access of users in the first group to the hardware elements in the second set.

25. The apparatus according to claim 24, wherein the allocated hardware elements comprise at least one element type selected from a group of types consisting of ones of the storage units, ones of the memory devices and parts of the logic circuitry.

26. The apparatus according to claim 1, wherein the data processing unit is configured to measure an amount of a resource of the apparatus that is used in processing the input query.

27. The apparatus according to claim 1, wherein the logic circuitry in a given storage unit is configured to deactivate at least one hardware component of the given storage unit so as to reduce power consumption of the given storage unit.

28. The apparatus according to claim 1, wherein the logic circuitry in a given storage unit is configured to run one of a Structured Query Language (SQL) query processor and a SQL rule engine.

29. A data storage apparatus, comprising:

a storage unit, which comprises;

one or more memory devices, which are operative to store data; and

circuitry, which is configured to apply a first filtering operation to the stored data in response to a query defined over the data, so as to produce pre-filtered data; and

a data processing unit, which is configured to receive the pre-filtered data from the storage unit and to apply a second filtering operation to the pre-filtered data, so as to produce a result of the query.

30. A data storage apparatus, comprising:

a storage unit, which comprises;

one or more memory devices, which are operative to store data; and

circuitry, which is configured to apply a data aggregation operation to the stored data in response to a query defined over the data, so as to produce pre-processed data; and

a data processing unit, which is configured to receive the pre-processed data from the storage unit and to process the pre-processed data, so as to produce a result of the query.

31. The apparatus according to claim 30, wherein the data aggregation operation comprises computation of a statistical property of at least some of the stored data.

32. The apparatus according to claim 30, wherein the data aggregation operation comprises computation of a sum of at least some of the stored data.

33. The apparatus according to claim 30, wherein the data aggregation operation comprises producing a sample of at least some of the stored data.

34. A method for data storage, comprising:

storing a plurality of data partitions drawn from a data structure in a respective plurality of storage units;

transforming an input query defined over the data structure into multiple sub-queries and providing the sub-queries to the storage units;

using logic circuitry in each storage unit, accepting one or more of the sub-queries addressed to the storage unit, and processing a respective data partition stored in the storage unit responsively to the accepted sub-queries, so as to produce filtered data; and

processing the filtered data produced by the multiple storage units, so as to generate and output a result in response to the input query.

35. The method according to claim 34, wherein the data structure comprises data elements stored in multiple rows and columns, and wherein storing the data partitions comprises dividing the data structure into multiple tiles, each tile comprising the data elements that are stored in an intersection of a respective first sub-range of the rows and a respective second sub-range of the columns, and distributing the tiles among the storage units.

36. The method according to claim 35, wherein distributing the tiles comprises distributing the tiles among the memory devices in accordance with a random pattern.

37. The method according to claim 35, wherein distributing the tiles comprises distributing a subset of the tiles that are associated with a given sub-range of the rows substantially evenly among the memory devices.

38. The method according to claim 35, wherein distributing the tiles comprises distributing a first subset of the tiles that are associated with a first sub-range of the rows among the memory devices according to a first distribution, and distributing a second subset of the tiles that are associated with a second sub-range of the rows, which succeeds the first sub-range, according to a second distribution that is different from the first distribution.

39. The method according to claim 35, wherein processing the data partition comprises storing a given tile in a first orientation, and, in response to a given sub-query that addresses the given tile, rotating the given tile to a second orientation executing the given sub-query using the rotated tile.

40. The method according to claim 34, wherein transforming the input query comprises defining a given sub-query that addresses a given data partition stored in a given storage unit, and wherein providing the sub-queries comprises providing the given sub-query to the given storage unit for processing.

41. The method according to claim 34, wherein processing the data partition comprises filtering the data partition responsively to one or more of the sub-queries addressed to the storage unit.

42. The method according to claim 34, wherein processing the filtered data comprises applying additional filtering to the filtered data produced by the storage units.

43. The method according to claim 34, wherein processing the data partition comprises performing a data aggregation operation on the data partition responsively to one or more of the sub-queries addressed to the storage unit.

44. The method according to claim 34, wherein processing the data partition comprises applying at least one of a logic operation and an arithmetic operation to the data partition.

45. The method according to claim 34, wherein the logic circuitry includes programmable logic, and comprising reconfiguring the programmable logic responsively to a criterion defined over at least one of the data structure and the input query.

46. The method according to claim 34, wherein processing the data partition comprises performing data storage and retrieval using at least one asymmetric interface, the asymmetric interface having a first bandwidth for the data storage and a second bandwidth, higher than the first bandwidth, for the data retrieval.

47. The method according to claim 34, wherein storing the data partitions comprises compressing at least some of a data partition assigned to a given storage unit prior to storing the data partition.

48. The method according to claim 47, wherein processing the data partition comprises applying a given sub-query to the compressed data partition so as to produce the filtered data, and decompressing only the filtered data.

49. The method according to claim 34, and comprising encrypting data exchanged with the storage units and with end users.

50. The method according to claim 34, wherein storing the data partitions comprises encrypting the data partitions stored in the storage units.

51. The method according to claim 34, and comprising exchanging data over a network with the storage units via respective Network Interface Cards (NICs) coupled to the storage units.

52. The method according to claim 34, wherein processing a given data partition by a given storage unit comprises communicating with another storage unit so as to exchange data for processing the sub-queries.

53. The method according to claim 34, and comprising identifying input queries whose processing accesses common data elements, and causing the storage units to access the common data elements jointly while processing the identified input queries.

54. The method according to claim 34, wherein storing the data partitions comprises converting the data structure into a raw data format, and storing the data partitions having the raw data format in the storage units.

55. The method according to claim 34, wherein storing the data partitions comprises representing a given data partition, which is assigned to a given storage unit and has a given data format, using code that is executable by the given storage unit, and wherein processing the given data partition comprises executing the code by the given storage unit so as to access the given data format.

56. The method according to claim 34, and comprising communicating with the storage units using a communication protocol that is compatible with another type of storage units, which do not have query processing capabilities.

57. The method according to claim 34, and comprising allocating first and second separate sets of hardware elements in the plurality of the storage units to respective first and second user groups, and preventing access of users in the first group to the hardware elements in the second set.

58. The apparatus according to claim 57, wherein the allocated hardware elements comprise at least one element type selected from a group of types consisting of ones of the storage units, ones of the memory devices and parts of the logic circuitry.

59. The method according to claim 34, and comprising measuring an amount of a resource that is used in processing the input query.

60. The method according to claim 34, and comprising deactivating at least one hardware component of a given storage unit so as to reduce power consumption of the given storage unit.

61. The method according to claim 34, wherein processing the data partition comprises running one of a Structured Query Language (SQL) query processor and a SQL rule engine.

62. A method for data storage, comprising:

storing data in a storage unit that includes processing circuitry;

using the processing circuitry in the storage unit, applying a first filtering operation to the stored data in response to a query defined over the data, so as to produce pre-filtered data; and

applying a second filtering operation to the pre-filtered data by a processor separate from the storage unit, so as to produce a result of the query.

63. A method for data storage, comprising:

storing data in a storage unit that includes processing circuitry;

using the processing circuitry in the storage unit, applying a data aggregation operation to the stored data in response to a query defined over the data, so as to produce pre-processed data; and

processing the pre-processed data by a processor separate from the storage unit, so as to produce a result of the query.

64. The method according to claim 63, wherein the data aggregation operation comprises computation of a statistical property of at least some of the stored data.

65. The method according to claim 63, wherein the data aggregation operation comprises computation of a sum of at least some of the stored data.

66. The method according to claim 63, wherein the data aggregation operation comprises producing a sample of at least some of the stored data.