SYSTEM AND METHODS FOR FACILITATING A LINEAR GRID DATABASE WITH DATA ORGANIZATION BY DIMENSION

• US 20100100556A1
• Filed: 12/21/2009
• Published: 04/22/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.
• Granted Patent: US 8,311,998 B2
• Time in Patent Office: Days
• US Class Current: 707/754
• 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:

a data query interface adapted to receive a first data query, wherein the first data query references at least a first dimension of data and a second 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

one or more nodes, including a first node identified by a first value in the first dimension of the data, the first node being adapted to receive requests for the data and retrieve the data from at least one memory storage location identified by the second dimension of the data referenced by the first data query.

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 being further configured to create dynamically a parsing process to request data from the at least one memory storage location.

5. The system of claim 4, the first node being further configured to execute the parsing process to access the at least one memory storage location, and receive data from the at least one memory storage location.

6. The system of claim 4, the parsing process being configured to:

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

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; and

parse data stored in the memory storage location.

7. The system of claim 1, wherein the at least one memory storage location is identified by at least one data storage identifier related to the second dimension of data.

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

9. The system of claim 1, further comprising a dispatcher configured to generate a data request based on the first data query, to identify at least one node of the one or more nodes based on a value in the first dimension of data referenced by the data query, and to forward the data request to the at least one node.

10. The system of claim 9, the dispatcher being further configured to:

calculate a workload capacity for each of the one or more nodes related to the first data query;

create at least one data request, wherein each data request relates to one of the one or more nodes; and

provide the at least one data request to the first node.

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

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

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

associating the set of nodes with a first dimension of data referenced by the data query, the set of nodes being configured to access the set of memory storage locations;

identifying a first node from the set of nodes based on the first dimension of data referenced by the data query;

requesting data from the first node; and

receiving data from the identified node, wherein the received data is retrieved by the identified node from at least one of the set of memory storage locations identified by the second dimension of data referenced by the data query.

13. The method of claim 12, each node in the set of nodes being identifiable by a predetermined value of the first dimension of data referenced by the data query.

14. The method of claim 12, further comprising:

formulating a first data request based on the data query, the first data request relating to a first value in the first dimension of data referenced by the data query;

transmitting the first data request to the first node;

identifying a second node from the set of nodes based on the first dimension of data referenced by the data query;

formulating a second data request based on the data query, the second data request relating to a second value in the first dimension of data referenced by the data query; and

transmitting the second data request to the second node.

15. The method of claim 14, further comprising merging data received from the first node and the second node to form a response to the data query.

16. The method of claim 12, further comprising:

if the data query requires accessing a external database, executing a 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 of the set of nodes;

retrieving data from at least one of the set of memory storage locations;

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

merging data received from the set of nodes and the external database.

17. A system for querying organized data comprising:

a data query interface for receiving a data query referencing at least a first dimension of data and a second dimension of data;

a first node identified by the first dimension of data referenced by the data query;

a set of memory storage locations identified by the second dimension of data referenced by the data query; and

a dispatcher for generating a data request based on the data query, and for routing the data request to the first node based on identification of the first node in the first dimension of data referenced by the data query;

the first node being configured to receive the data request from the dispatcher and to execute a parsing process for retrieving data from the set of memory storage locations.

18. The system of claim 17, the first node being further configured to dynamically produce the parsing process for retrieving data from the set of memory locations.

19. The system of claim 17, further comprising a second node identified by the first dimension of data referenced by the data query, wherein a first value in the first dimension of data identifies the first node, and a second value in the first dimension of data identifies the second node.

20. The system of claim 17, further comprising:

a processing unit configured to create an external filter query for accessing an external database, the external filter query being derived from the received data query; and

a data merging unit for merging data received from the first node and the external database.