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

• US 7,672,930 B2
• Filed: 04/05/2005
• Issued: 03/02/2010
• 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.
• Primary Examiner(s): Breene; John E
• Assistant Examiner(s): COLAN, GIOVANNA B
• Application Number:
  US11/100,073
• Publication Number:
  US 20060224603A1
• Time in Patent Office: 1,792 Days
• Field of Search: 707/100, 707/3, 707/102, 707/1, 707/103.R, 707/10, 707/101
• 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 querying organized data, comprising:

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

providing at least one node associated with a first dimension of data referenced by the data query;

providing a set of memory storage locations associated with a second dimension of data referenced by the data query;

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 the at least one node;

retrieving data from at least one memory storage location identified by the 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 the at least one node, wherein the node executes one or more processes for retrieving the requested data from at least one memory storage location identified by the second dimension of data referenced by the data query; and

merging data received from the at least one node.

2. The method of claim 1, 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.

3. The method of claim 1, 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.

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

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

6. The method of claim 1, 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 storage location, wherein the parsing process is created by the at least one node.

7. The method of claim 6, wherein retrieving data from the at least one memory storage location comprises:

accessing the at least one memory storage location identified by the second dimension of the data referenced by the data query; and

receiving data from the at least one memory storage location.

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

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

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

parsing data stored in each memory storage location.

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

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

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

aggregating received data; and

removing duplicative data within the received data.

11. The method of claim 1, 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.

12. The method of claim 11, 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.

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

14. 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;

providing at least one node associated with a first dimension of data referenced by the data query;

providing a set of memory storage locations associated with a second dimension of data referenced by the data query;

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 the at least one node;

retrieving data from at least one memory storage location identified by the 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 the at least one node, wherein the node executes one or more processes for retrieving the requested data from at least one memory storage location identified by the second dimension of data referenced by the data query; and

merging data received from the at least one node.

15. The computer-readable medium of claim 14, 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.

16. The computer-readable medium of claim 14, 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.

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

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

19. The computer-readable medium of claim 14, 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 storage location, wherein the parsing process is created by the at least one node.

20. The computer-readable medium of claim 19, wherein retrieving data from at least one memory storage location comprises:

accessing the at least one memory storage location identified by the second dimension of data referenced by the data query; and

receiving data from the at least one memory storage location.

21. The computer-readable medium of claim 20, wherein accessing the at least one memory storage location comprises:

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

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

parsing data stored in each memory storage location.

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

merging data received from the at least one memory storage location.

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

aggregating received data; and

removing duplicative data within the received data.

24. The computer-readable medium of claim 14, 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.

25. The computer-readable medium of claim 24, 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.

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