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

• US 8,311,998 B2
• Filed: 12/21/2009
• Issued: 11/13/2012
• Est. Priority Date: 04/05/2005
• Status: Active Grant

• Current Assignee: Walmart Apollo, LLC (WalMart Inc.)
• Original Assignee: WalMart Inc.
• Inventors: Correll, Harold Landorff Jr.
• Primary Examiner(s): COLAN, GIOVANNA B
• Application Number:
  US12/643,545
• Publication Number:
  US 20100100556A1
• Time in Patent Office: 1,058 Days
• Field of Search: 707/706, 707/713, 707/758
• US Class Current: 707/706
• 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

Systems and methods for retrieving data within a linear grid management system are disclosed. Data having multiple dimensions is associated with physical locations, where a first dimension of the data is associated with a set of nodes and a second dimension of the data is associated with a set of memory storage locations. A received data query can be divided into multiple subqueries or data requests, such that each subquery is directed to a particular node identified by the first dimension of data referenced by the data query. When receiving a subquery, a node generates a unique and efficient parsing process to retrieve data from the memory storage locations identified by the second dimension of data referenced by the data query.

Claims

1. A system for querying organized data comprising:

one or more nodes configured to execute one or more processes, wherein the one or more nodes includes a first node uniquely identified by a first value and a second node uniquely identified by a second value;

a plurality of memory storage locations, each in communication with both the first node and the second node, wherein the first node and the second node are configured to retrieve data from the plurality of memory storage locations;

a data query interface adapted to receive a first data query and to divide the first data query into a first subquery and a second subquery, wherein the first subquery references the first value in a first dimension of data, and wherein the second subquery references the second value in the first dimension of data;

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

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

a dispatcher adapted to direct the first subquery to the first node based on the first value being in the first dimension of data of the first subquery, and further adapted to direct the second subquery to the second node based on the second value being in the first dimension of data of the second subquery.

2. The system of claim 1, wherein the pre-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 first node, wherein the at least one subquery is related to the result set; and

provide the at least one subquery to the first node.

3. The system of claim 1, wherein the post-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 first node, wherein the at least one subquery is related to the result set; and

provide the at least one subquery to the first node.

4. The system of claim 1, the first node and the second node each being further configured to create dynamically a parsing process to request data from the plurality of memory storage locations.

5. The system of claim 4, the first node being further configured to execute the parsing process to access the one or more memory storage locations, and receive data from the plurality of memory storage locations.

6. The system of claim 4, the first node being further configured to:

create a list of memory storage locations to search based on the second dimension of the second subquery; and

access each memory storage location in the list of memory storage locations, wherein accessing each memory storage location includes uncompressing, opening, and reading the data of the memory storage location.

7. The system of claim 1, wherein each of the plurality of memory storage locations is uniquely identified by at least one data storage identifier related to the second dimension of the first subquery.

8. The system of claim 1, further comprising a data merging unit configured to aggregate received data received from the one or more memory storage locations and the external database, and remove duplicative data within the received data.

9. The system of claim 1, the first node configured to parse the first subquery and, based on the first subquery, to retrieve data from the plurality of memory storage locations.

10. The system of claim 1, further comprising a merging unit configured to construct at least a portion of a response to the first data query by merging data received from the first node and the second node in response to the first and second subqueries.

11. The system of claim 5, the first node comprising hardware to execute the parsing process.