System and methods for facilitating a linear grid database with data organization by dimension

• US 20060224603A1
• Filed: 04/05/2005
• Published: 10/05/2006
• Est. Priority Date: 04/05/2005
• Status: Active Grant

• Current Assignee: Walmart Apollo, LLC (WalMart Inc.)
• Original Assignee: Wal-Mart Stores Texas LLC (WalMart Inc.)
• Inventors: Correll, Harold Landorff Jr.
• Granted Patent: US 7,672,930 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A system and methods for organizing and querying data within a linear grid management system. Data having multiple dimensions is associated with physical locations, where a first dimension is associated with a node and a second dimension is associated with a data storage identifier of a memory storage device. The data may have a third dimension which provides a field for ordering data within the memory storage device. Metadata may be used to map a logical table to data stored in the memory storage device. The data query may be divided into multiple subqueries, wherein each subquery is related directly to one node associated with a data storage identifier related to a memory storage device. A preSQL and postSQL process may be generated to access an external database. A dispatcher may manage data subrequests and a node may generate a unique and efficient parsing process from the received data subrequest.

Claims

1. A method for organizing data, comprising:

receiving data at a data storage interface, wherein the data has at least two dimensions;

associating a node with a first dimension of the data, wherein the node is associated with at least one data storage identifier;

associating the at least one data storage identifier with a second dimension of the data; and

providing the data from the data storage interface to a memory storage device identified by the data storage identifier associated with the node.

2. The method of claim 1 further comprising:

using metadata to map a logical table to the data stored in the memory storage device, wherein the metadata comprises at least one data field attribute that describes a portion of the data stored in the memory device.

3. The method of claim 2, wherein the metadata comprises:

a first data field attribute describing the first dimension of the data, wherein the first data field attribute identifies the first dimension as the node; and

a second data field attribute describing the data storage identifier, wherein the second data field attribute identifies the second dimension as the data storage identifier.

4. A method for querying organized data, comprising:

receiving a data query at a data query interface, wherein the data query references at least two dimensions of data;

determining whether the data query requires accessing an external database;

if the data query requires accessing the external database, executing a first sequence, comprising;

creating an external filter query and an external support column query;

accessing the external database with the external filter query;

requesting data from at least one node, wherein the at least one node is associated with a first dimension of data referenced by the data query;

retrieving data from at least one memory storage device identified by at least one data storage identifier associated with a second dimension of data referenced by the data query;

accessing the external database with the external support column query; and

merging data received from the at least one node and the external database;

if the data query does not require accessing the external database, executing a second sequence, comprising;

requesting data from at least one node, wherein the at least one node is associated with a first dimension of data referenced by the data query;

retrieving data from at least one memory storage device identified by at least one data storage identifier associated with a second dimension of data referenced by the data query; and

merging data received from the at least one node.

5. The method of claim 4, wherein accessing the external database with the external filter query comprises:

submitting the external filter query to the external database;

receiving a result set received from the external database;

formatting the result set;

creating at least one subquery for the at least one node, wherein the at least one subquery corresponds to the result set; and

providing the at least one subquery to the at least one node.

6. The method of claim 4, wherein accessing the external database with the external support column query comprises:

defining an external database table;

preparing the external database table for a data load;

submitting the external support column query to the external database;

receiving a result set from the external database, wherein the result set is loaded into the external database table;

creating at least one subquery for the at least one node, wherein the at least one subquery relates to the result set; and

providing the at least one subquery to the at least one node.

7. The method of claim 4, wherein the external filter query comprises a plurality of external filter subqueries.

8. The method of claim 4, wherein the external support column query comprises a plurality of external support column subqueries.

9. The method of claim 4, wherein the method further comprises:

receiving the request for data by the at least one node; and

creating a parsing process to request data from the at least one memory device, wherein the parsing process is created by the at least one node.

10. The method of claim 9, wherein retrieving data from at least one memory storage device comprises:

accessing the at least one memory device identified by the at least one data storage identifier; and

receiving data from the at least one memory storage device.

11. The method of claim 10, wherein accessing the at least one memory device comprises:

creating a list of memory storage devices to search based on the second dimension;

accessing each memory storage device in the list of memory storage devices, wherein accessing each memory storage device comprises uncompressing, opening, and reading data stored on the memory storage device; and

parsing data stored in each memory storage device.

12. The method of claim 10, wherein the method further comprises:

merging data received from the at least on memory storage device.

13. The method of claim 12, wherein the method further comprises:

aggregating received-data; and

removing duplicative data within the received data.

14. The method of claim 4, wherein requesting data from at least one node comprises:

submitting a data request to a dispatcher, wherein the dispatcher is operable for;

determining whether a data request has been submitted;

retrieving the data request, if the dispatcher determines that a data request has been submitted;

calculating a workload capacity for each of the at least one node related to the data request;

creating at least one data subrequest, wherein the data subrequest relates to only one node; and

providing the at least one data subrequest to the related node, if the work capacity of the related node is below a predetermined amount.

15. The method of claim 14, wherein submitting a data request to a dispatcher comprises:

providing the data request to a shared memory storage unit, wherein the dispatcher accesses the shared memory storage unit to retrieve the data request.

16. The method of claim 14, wherein the at least one data subrequest relates to a result set obtained by accessing the external database with the external filter query.

17. A system for organizing data, comprising:

a data storage interface adapted to receive data having at least a first dimension and a second dimension;

at least one node, wherein the at least one node is related to the first dimension of the data; and

at least one memory storage device adapted to store the data, wherein the at least one memory storage device is related to the second dimension of the data,

wherein the at least one node is adapted to access at least one memory storage device.

18. The system of claim 17, further comprising:

at least one data storage identifier adapted to identify the at least one memory storage device, wherein the at least one data storage identifier is related to the second dimension of the data.

19. The system of claim 17, further comprising:

a metadata unit adapted to map the data stored in the at least one memory storage device to a logical table, wherein the metadata unit has at least one data field attribute that describes a portion of the data.

20. The system of claim 19, wherein the metadata unit has a first data field attribute describing the first dimension of the data and a second data field attribute describing the second dimension of the data.

21. The system of claim 20, wherein the first data field attribute describes the first dimension of the data as a node.

22. The system of claim 20, wherein the second data field attribute describes the second dimension of the data as a data storage identifier.

23. A system for querying organized data comprising:

a data query interface adapted to receive a data query, wherein the data query references at least a first dimension of data and a second dimension of data;

a preSQL processing unit adapted to create an external filter query for accessing an external database;

a postSQL processing unit adapted to create an external support column query for accessing the external database; and

at least one node identified by the first dimension of the data, adapted to receive requests for the data and retrieve the data from at least one memory storage device identified by the second dimension of the data.

24. The system of claim 23, wherein the preSQL processing unit is further adapted to:

submit the external filter query to the external database;

format a result set received from the external database;

validate the result set;

create at least one subquery for the at least one node, wherein the at least one subquery is related to the result set; and

provide the at least one subquery to the at least one node.

25. The system of claim 23, wherein the postSQL processing unit is further adapted to:

define an external database table;

prepare a load of data for the external database table;

submit the external support column query to the external database;

receive a result set from the external database, wherein the result set is loaded into the external database table;

create at least one subquery for the at least one node, wherein the at least one subquery is related to the result set; and

provide the at least one subquery to the at least one node.

26. The system of claim 23, wherein the at least one node is further adapted to create a parsing process to request data from the at least one memory device.

27. The system of claim 26, wherein the at least one node is further adapted to:

execute the parsing process, wherein the parsing process accesses the at least one memory device; and

receive data from the at least one memory storage device.

28. The system of claim 27, wherein the parsing process is adapted to:

create a list of memory-storage devices to search based on the second dimension;

access each memory storage device in the list of memory storage devices, wherein accessing each memory storage device includes uncompressing, opening, and reading the data of the memory storage device; and

parse data stored in the memory storage device.

29. The system of claim 28, wherein the data merging unit is further adapted to:

aggregate received data received from the at least one memory storage device and the external database; and

remove duplicative data within the received data.

30. The system of claim 28, wherein the dispatcher is further adapted to:

determine whether a data request has been submitted;

retrieve the data request;

calculate a workload capacity for each of the at least one node related to the data request;

create at least one data subrequest, wherein each data subrequest relates to one node; and

provide the at least one data subrequest to the at least one node.

31. The system of claim 30, wherein the at least one data subrequest relates to a result set received from the external database with the external filter query.

32. The system of claim 23, wherein the at least one memory storage device is identified by at least one data storage identifier related to the second dimension of data.

33. The system of claim 23, further comprising:

a dispatcher adapted to receive the data query from the data query interface, generate at least one data subrequest for each the at least one node, and provide the at least one data subrequest to the at least one node; and

a data merging unit adapted to merge data received from the at least on memory storage device and the external database.

34. A computer-readable medium for organizing data having computer executable instructions for performing steps comprising:

receiving data at a data storage interface, wherein the data has at least two dimensions;

associating a node with a first dimension of the data, wherein the node is associated with at least one data storage identifier;

associating the at least one data storage identifier with a second dimension of the data; and

providing the data from the data storage interface to a memory storage device identified by the data storage identifier associated with the node.

35. The computer-readable medium of claim 34 further comprising:

using metadata to map a logical table to the data stored in the memory storage device, wherein the metadata comprises at least one data field attribute that describes a portion of the data stored in the memory device.

36. The computer-readable medium of claim 35, wherein the metadata comprises:

a first data field attribute describing the first dimension of the data, wherein the first data field attribute identifies the first dimension as the node; and

a second data field attribute describing the data storage identifier, wherein the second data field attribute identifies the second dimension as the data storage identifier.

37. A computer-readable medium for querying organized data having computer executable instructions for performing steps comprising:

receiving a data query at a data query interface, wherein the data query references at least two dimensions of data;

determining whether the data query requires accessing an external database;

if the data query requires accessing the external database, executing a first sequence, comprising;

creating an external filter query and an external support column query;

accessing the external database with the external filter query;

requesting data from at least one node, wherein the at least one node is associated with a first dimension of data referenced by the data query;

retrieving data from at least one memory storage device identified by at least one data storage identifier associated with a second dimension of data referenced by the data query;

accessing the external database with the external support column query; and

merging data received from the at least one node and the external database;

if the data query does not require accessing the external database, executing a second sequence, comprising;

requesting data from at least one node, wherein the at least one node is associated with a first dimension of data referenced by the data query;

retrieving data from at least one memory storage device identified by at least one data storage identifier associated with a second dimension of data referenced by the data query; and

merging data received from the at least one node.

38. The computer-readable medium of claim 37, wherein accessing the external database with the external filter query comprises:

submitting the external filter query to the external database;

receiving a result set received from the external database;

formatting the result set;

creating at least one subquery for the at least one node, wherein the at least one subquery corresponds to the result set; and

providing the at least one subquery to the at least one node.

39. The computer-readable medium of claim 37, wherein accessing the external database with the external support column query comprises:

defining an external database table;

preparing the external database table for a data load;

submitting the external support column query to the external database;

receiving a result set from the external database, wherein the result set is loaded into the external database table;

creating at least one subquery for the at least one node, wherein the at least one subquery relates to the result set; and

providing the at least one subquery to the at least one node.

40. The computer-readable medium of claim 37, wherein the external filter query comprises a plurality of external filter subqueries.

41. The computer-readable medium of claim 37, wherein the external support column query comprises a plurality of external support column subqueries.

42. The computer-readable medium of claim 37, wherein the computer executable instructions further comprise:

receiving the request for data by the at least one node; and

creating a parsing process to request data from the at least one memory device, wherein the parsing process is created by the at least one node.

43. The computer-readable medium of claim 42, wherein retrieving data from at least one memory storage device comprises:

accessing the at least one memory device identified by the at least one data storage identifier; and

receiving data from the at least one memory storage device.

44. The computer-readable medium of claim 43, wherein accessing the at least one memory device comprises:

creating a list of memory storage devices to search based on the second dimension;

accessing each memory storage device in the list of memory storage devices, wherein accessing each memory storage device comprises uncompressing, opening, and reading data stored on the memory storage device; and

parsing data stored in each memory storage device.

45. The computer-readable medium of claim 43, wherein the computer executable instructions further comprise:

merging data received from the at least on memory storage device.

46. The computer-readable medium of claim 45, wherein the computer executable instructions further comprise:

aggregating received data; and

removing duplicative data within the received data.

47. The computer-readable medium of claim 37, wherein requesting data from at least one node comprises:

submitting a data request to a dispatcher, wherein the dispatcher is operable for;

determining whether a data request has been submitted;

retrieving the data request, if the dispatcher determines that a data request has been submitted;

calculating a workload capacity for each of the at least one node related to the data request;

creating at least one data subrequest, wherein the data subrequest relates to only one node; and

providing the at least one data subrequest to the related node, if the work capacity of the related node is below a predetermined amount.

48. The computer-readable medium of claim 47, wherein submitting a data request to a dispatcher comprises:

providing the data request to a shared memory storage unit, wherein the dispatcher accesses the shared memory storage unit to retrieve the data request.

49. The computer-readable medium of claim 47, wherein the at least one data subrequest relates to a result set obtained by accessing the external database with the external filter query.