Global-results processing matrix for processing queries

• US 7,945,581 B2
• Filed: 11/14/2002
• Issued: 05/17/2011
• Est. Priority Date: 11/14/2002
• Status: Active Grant

• Current Assignee: LexisNexis Risk Data Management, Inc. (RELX PLC)
• Original Assignee: LexisNexis Risk Data Management, Inc. (RELX PLC)
• Inventors: Smith, Jake, Hicks, Nigel, Halliday, Gavin, Poulsen, Ole, Chapman, Richard, Bayliss, David
• Primary Examiner(s): Padmanabhan; Kavita
• Application Number:
  US10/293,482
• Publication Number:
  US 20040098372A1
• Time in Patent Office: 3,106 Days
• Field of Search: None
• US Class Current: 707/770
• CPC Class Codes: G06F 16/24532 of parallel queries

Abstract

A system and methods for parallel processing of queries to one or more databases are described herein. One or more databases may be distributed among a subset of slave nodes of a global-results processing matrix. A query to the database may be generated using a query-based high-level programming language. The query-based source code then may be converted to intermediary source code in a common programming language and then compiled into a dynamic link library (DLL) or other type of executable. The DLL is then distributed among the slave nodes of the processing matrix, whereupon the slave nodes execute related portions of the DLL substantially in parallel to generate initial query results. The initial query results may then be provided to a master node of the global-results processing matrix for additional processing, whereby the master node is adapted to execute one or more associated portions of the DLL on the initial query results.

Claims

1. A system for processing at least one query to at least one electronic database, the system comprising:

a query server for receiving a query and compiling at least one executable from query language based source code, the at least one executable having at least a first portion and a second portion, the first portion configured to generate a portion of initial query results and the second portion configured to execute one or more operations on a set of initial query results;

a first type of processing matrix adapted to perform a database operation on hierarchical data;

a second type of processing matrix adapted to perform an indexing database operation;

a third type of processing matrix adapted to perform a database operation on large amounts of data;

a query agent being adapted to select a type of processing matrix, from at least the first type of processing matrix, the second type of processing matrix, and the third type of processing matrix, to process the query based on at least one database operation to be performed to process the query, wherein each type of processing matrix comprises a master node and a plurality of slave nodes;

the master node of the selected type of processing matrix being adapted to receive the at least one executable and comprising;

at least one storage device; and

a processor; and

the plurality of slave nodes of the selected type of processing matrix operably connected to the master node, each of the plurality of slave nodes receiving at least the same first portion of the at least one executable from the master node, each slave node comprising;

disk storage for receiving and storing a distinct portion of the database wherein the entire database is distributed among the plurality of slave nodes in distinct portions; and

a processor for executing the first portion of the at least one executable on the distinct portion of the database to generate a portion of initial query results;

wherein the plurality of slave nodes executes the first portion of the at least one executable substantially in parallel to generate the set of initial query results;

wherein the second portion of the at least one executable is executed on the initial query results to generate resultant query results, which are stored at the master node; and

wherein the plurality of slave nodes are used to process the query.

2. The system of claim 1, wherein the query server generates intermediary source code from query source code, the query source code representing at least one database operation using the database and wherein the query source code is formatted based in part on a query-based programming language and compiles the intermediary source code to generate the at least one executable.

3. The system of claim 2, wherein the intermediary source code is one of a group consisting of:

C source code, C++ source code, Fortran source code; and

Pascal source code.

4. The system of claim 2, further comprising a query agent operably connected to the query server and the master node and being adapted to:

submit the at least one executable to the master node for execution; and

monitor an execution of the at least one executable.

5. The system of claim 4, further comprising a scheduling services module operably connected to the query agent and the query server and being adapted to:

schedule a time of execution of the at least one executable by the master node and slave nodes based on at least one characteristic of the at least one executable; and

direct the query agent to submit the executable to the master node at the scheduled time.

6. The system of claim 5, wherein the at least one characteristic of the at least one executable includes one of a group consisting of:

an expected execution time of the at least one executable;

a priority of the at least one executable;

a type of the at least one database operation represented by the at least one executable; and

a number of slave nodes expected to execute the at least one executable.

7. The system of claim 2, further comprising a work-unit reporting module operably connected to the query server and being adapted to store at least a portion of the final query results.

8. The system of claim 2, further comprising a query builder module operably connected to the query server and being adapted to facilitate a client in generating the query source code using the query-based language.

9. The system of claim 8, wherein the query builder module includes a graphical user interface.

10. The system of claim 8, wherein the query builder module is further adapted to display at least a portion of the final query results to the client.

11. The system of claim 8, wherein the query builder module is further adapted to submit a representation of the query source code to the query server over a network.

12. The system of claim 1, further comprising a staging zone adapted to distribute the database among the slave nodes, each slave node receiving a different database portion.

13. The system of claim 12, wherein data of the database is distributed randomly among the slave nodes.

14. The system of claim 13, wherein the staging zone is further adapted to distribute the database using a hash function on a record field of each record of the database.

15. The system of claim 1, wherein the at least one executable includes at least one dynamic link library (DLL).

16. The system of claim 15, wherein each processing node further includes a software agent being adapted to execute a portion of the at least one DLL, wherein a software agent at the master node is configured to execute a second portion of the DLL.

17. The system of claim 1, wherein at least the slave nodes are substantially homogeneous.

18. The system of claim 17, wherein the processors of the master and slave nodes are of the type found in general purpose, single-user microcomputers.

19. The system of claim 1, wherein the at least one database operation represented by the first portion of the at least one executable includes one of a group consisting of:

linking, matching, filtering, scoring, sorting, counting, and joining.

20. The system of claim 1, wherein the at least one database operation represented by the second portion of the at least one executable includes one of a group consisting of:

sorting, linking, collating, filtering, counting, deduping, joining, appending, merging, purging, non-hierarchical linking, neural-net scoring, and formatting.

21. The system of claim 1, wherein the plurality of slave nodes includes between ten slave nodes and one thousand slave nodes.

22. The system of claim 1, wherein the plurality of slave nodes includes between fifty slave nodes and five hundred slave nodes.

23. The system of claim 1, wherein the plurality of slave nodes includes between 100 slave nodes and three hundred slave nodes.

24. The system of claim 1, wherein the plurality of slave nodes includes at least one thousand slave nodes.

25. The system of claim 1, wherein the first and second portions of the at least one executable are at least essentially the same.

26. The system of claim 1, wherein the database operation on large amounts of data includes one of a group consisting of:

sorting, linking, collating, filtering, counting, deduping, joining, appending, merging, purging, non-hierarchical linking, neural-net scoring, and formatting.

27. A system for processing at least one query to at least one electronic database, the system comprising:

a first type of processing node adapted to perform a database operation on hierarchical data;

a second type of processing node adapted to perform an indexing database operation;

a third type of processing node adapted to perform a database operation on large amounts of data;

a query agent being adapted to select a type of processing node, from at least the first type of processing node, the second type of processing node, and the third type of processing node, to process the query based on at least one database operation to be performed to process the query, wherein the selected type of processing node comprises a plurality of processing nodes;

the plurality of processing nodes being interconnected via a network and being adapted to execute at least one executable compiled from the query to generate results, the at least one executable having at least a first portion and a second portion, the first portion configured to generate a portion of initial query results and the second portion configured to execute one or more operations on a set of initial query results, each processing node comprising a processor, memory operably connected to the processor, disk storage operably connected to the processor and a network interface operably connected to the processor and adapted to facilitate communication with other processing nodes over the network;

the plurality of processing nodes comprising;

a plurality of slave nodes, each slave node comprising;

disk storage for storing a distinct portion of the database, wherein the entire database is distributed among the plurality of slave nodes in distinct portions; and

a processor for executing the same first portion of the at least one executable on the distinct portion of the database to generate the portion of initial query results;

wherein the plurality of slave nodes executes the first portion of the at least one executable substantially in parallel to generate the set of initial query results;

wherein the plurality of slave nodes are used to process the query;

and

a master node being adapted to receive the at least one executable and operably connected to the plurality of slave nodes, the master node comprising;

at least one storage device storing the set of initial query results generated by the plurality of slave nodes; and

a processor adapted to execute the second portion of the at least one executable on the stored set of initial query results to generate resultant query results.

28. The system of claim 27, further comprising a query server operably connected to the master node and being adapted to:

generate intermediary source code from query source code, the query source code representing at least one database operation using the database and wherein the query source code is formatted based in part on a query-based programming language; and

compile the intermediary source code to generate the at least one executable.

29. The system of claim 28, wherein the intermediary source code is one of a group consisting of:

C source code, C++ source code, Fortran source code; and

Pascal source code.

30. The system of claim 28, further comprising a query agent operably connected to the query server and the master node and being adapted to:

submit the at least one executable to the master node for execution; and

monitor an execution of the at least one executable.

31. The system of claim 30, further comprising a scheduling services module operably connected to the query agent and the query server and being adapted to:

schedule a time of execution of the at least one executable by the master node and slave nodes based on at least one characteristic of the at least one executable; and

direct the query agent to submit the executable to the master node at the scheduled time.

32. The system of claim 28, further comprising a work-unit reporting module operably connected to the query server and being adapted to store at least a portion of the final query results.

33. The system of claim 28, further comprising a query builder module operably connected to the query server and being adapted to facilitate a client in generating the query source code using the query-based language.

34. The system of claim 33, wherein the query builder module includes a graphical user interface.

35. The system of claim 33, wherein the query builder module is further adapted to display at least a portion of the final query results to the client.

36. The system of claim 33, wherein the query builder module is further adapted to submit a representation of the query source code to the query server over a network.

37. The system of claim 27, further comprising a staging zone adapted to distribute the database among the slave nodes, each slave node receiving a different database portion.

38. The system of claim 37, wherein data of the database is distributed randomly among the slave nodes.

39. The system of claim 38, wherein the staging zone is further adapted to distribute the database using a hash function on a record field of each record of the database.

40. The system of claim 27, wherein the at least one executable includes at least one dynamic link library (DLL).

41. The system of claim 40, wherein each processing node further includes a software agent being adapted to execute a portion of the at least one DLL, wherein a software agent at the master node is configured to execute a second portion of the DLL.

42. The system of claim 27, wherein at least the slave nodes are substantially homogeneous.

43. The system of claim 42, wherein the processors of the master and slave nodes are of the type found in general purpose, single-user microcomputers.

44. The system of claim 27, wherein the first and second portions of the at least one executable are at least essentially the same.

45. The system of claim 27, wherein the database operation on large amounts of data includes one of a group consisting of:

sorting, linking, collating, filtering, counting, deduping, joining, appending, merging, purging, non-hierarchical linking, neural-net scoring, and formatting.

47. The system of claim 44, wherein the intermediary source code is one of a group consisting of:

C source code, C++ source code, Fortran source code; and

Pascal source code.

46. A system for processing at least one query to an electronic database, the system comprising:

a query server being adapted to;

generate intermediary source code from query source code, the query source code representing at least one database operation performed on the database and wherein the query source code is formatted based in part on a query-based programming language; and

compile the intermediary source code to generate at least one executable, the at least one executable having at least a first portion and a second portion, the first portion configured to generate a portion of initial query results and the second portion configured to execute one or more operations on a set of initial query results; and

a first type of processing matrix adapted to perform a database operation on hierarchical data;

a second type of processing matrix adapted to perform an indexing database operation;

a third type of processing matrix adapted to perform a database operation on large amounts of data; and

a query agent being adapted to;

select a global-results type of processing matrix, from at least the first type of processing matrix, the second type of processing matrix, and the third type of processing matrix, to process the at least one query associated with the query source code based on at least one database operation to be performed to process the query; and

the global-results type of processing matrix including;

a plurality of slave nodes, each slave node storing on disk storage a different portion of the database and being adapted to execute the same first portion of the at least one executable using the different portion of the database to generate the portion of initial query results, the first portion of the at least one executable representing at least one database operation on the different portion of the database, the plurality of slave nodes executing the first portion of the at least one executable substantially in parallel to generate a set of initial query results, wherein the entire database is distributed among the plurality of slave nodes in distinct portions, and wherein the plurality of slave nodes are used to process the query; and

a master node operably connected to the plurality of slave nodes and being adapted to;

store the set of initial query results on disk storage of the master node; and

execute the second portion of the at least one executable on the stored set of initial query results to generate resultant query results, the second portion of the at least one executable representing at least one database operation on the set of initial query results.

48. The system of claim 46, further comprising a query agent operably connected to the query server and the master node and being adapted to:

submit the at least one executable to the master node for execution; and

monitor an execution of the at least one executable by the master node and the plurality of slave nodes.

49. The system of claim 48, further comprising a scheduling service module operably connected to the query agent and the query server and being adapted to:

schedule a time of execution of the at least one executable by the master node and slave nodes based on at least one characteristic of the at least one executable; and

direct the query agent to submit the executable to the master node at the scheduled time.

50. The system of claim 49, wherein the at least one characteristic of the at least one executable includes one of a group consisting of:

an expected execution time of the at least one executable;

a priority of the at least one executable;

a type of the at least one database operation represented by the at least one executable; and

a number of slave nodes expected to execute the at least one executable.

51. The system of claim 46, further comprising a work-unit reporting module operably connected to the query server and being adapted to store at least a portion of the final query results.

52. The system of claim 46, further comprising a query builder module operably connected to the query server and being adapted to facilitate a client in generating the query source code using the query-based language.

53. The system of claim 52, wherein the query builder module includes a graphical user interface.

54. The system of claim 52, wherein the query builder module is further adapted to display at least a portion of the final query results to the client.

55. The system of claim 52, wherein the query builder module is further adapted to submit a representation of the query source code to the query server over a network.

56. The system of claim 46, further comprising a staging zone adapted to distribute the database among the slave nodes, each slave node receiving a different database portion.

57. The system of claim 56, wherein the staging zone is further adapted to distribute the database using a hash function on a record field of each record of the database.

58. The system of claim 46, wherein the at least one executable includes at least one dynamic link library (DLL).

59. The system of claim 58, wherein each processing node further includes a software agent being adapted to execute a portion of the at least one DLL, wherein a software agent at the master node is configured to execute a second portion of the DLL.

60. The system of claim 46, wherein the processing nodes are substantially homogeneous.

61. The system of claim 46, wherein the at least one database operation represented by the first portion of the at least one executable includes one of a group consisting of:

linking, matching, filtering, scoring, sorting, counting, and joining.

62. The system of claim 46, wherein the at least one database operation represented by the second portion of the at least one executable includes one of a group consisting of:

sorting, linking, collating, filtering, counting, deduping, joining, appending, merging, purging, non-hierarchical linking, neural-net scoring, and formatting.

63. The system of claim 46, wherein the first and second portions of the at least one executable are at least essentially the same.

64. The system of claim 46, wherein the database operation on large amounts of data includes one of a group consisting of:

sorting, linking, collating, filtering, counting, deduping, joining, appending, merging, purging, non-hierarchical linking, neural-net scoring, and formatting.

65. A method for processing at least one query to an electronic database distributed among a plurality of slave nodes of a global-results type of processing matrix, each slave node storing a separate database portion of the database on disk storage, wherein the entire database is distributed among the plurality of slave nodes in distinct portions, the method comprising:

receiving a query in a query-based language source code and compiling at least one executable from the query-based language source code, the at least one executable having at least a first portion and a second portion, the first portion configured to generate a portion of initial query results and the second portion configured to execute one or more operations on the set of initial query results;

providing a first type of processing matrix adapted to perform a database operating on hierarchical data;

providing a second type of processing matrix adapted to perform an indexing database operation;

providing a third type of processing matrix adapted to perform a database operation on large amounts of data;

selecting the global-results type of processing matrix, from at least the first type or processing matrix, the second type of processing matrix, and the third type of processing matrix, to process the query based on at least one database operation to be performed to process the query;

executing, at each slave node, the same first portion of the at least one executable using the stored separate database portion to generate the portion of initial query results, the first portion of the at least one executable representing at least one database operation on the stored separate database portion, the first portion of the at least one executable being executed by the slave node substantially in parallel with an execution of the first portion of the at least one executable by other slave nodes, wherein the plurality of slave nodes are used to process the query;

storing the portions of initial query results received from each slave node to disk storage of a master node of the global-results type of processing matrix as the set of initial query results; and

executing, at the master node, the second portion of the at least one executable using the stored set of initial query results to generate final query results, the second portion of the at least one executable representing at least one database operation on the set of initial query results.

66. The method of claim 65, further comprising:

generating intermediary source code from query source code, the query source code representing least one database operation using the database and wherein the query source code is formatted based in part on a query-based programming language; and

compiling the intermediary source code to generate the at least one executable.

67. The method of claim 66, wherein the at least one executable includes at least one dynamic link library (DLL).

68. The method of claim 65, wherein the processing nodes are substantially homogeneous.

69. The method of claim 65, wherein the at least one database operation represented by the first portion of the at least one executable includes one of a group consisting of:

linking, matching, filtering, scoring, sorting, counting, and joining.

70. The method of claim 65, wherein the at least one database operation represented by the second portion of the at least one executable includes one of a group consisting of:

sorting, linking, collating, filtering, counting, deduping, joining, appending, merging, purging, non-hierarchical linking, neural-net scoring, and formatting.

71. The method of claim 65, wherein the plurality of slave nodes includes between ten slave nodes and one thousand slave nodes.

72. The method of claim 65, wherein the plurality of slave nodes includes between fifty slave nodes and five hundred slave nodes.

73. The method of claim 65, wherein the plurality of slave nodes includes between 100 slave nodes and three hundred slave nodes.

74. The method of claim 65, wherein the plurality of slave nodes includes at least one thousand slave nodes.

75. The method of claim 65, wherein the database operation on large amounts of data includes one of a group consisting of:

sorting, linking, collating, filtering, counting, deduping, joining, appending, merging, purging, non-hierarchical linking, neural-net scoring, and formatting.

76. A system comprising:

a first type of processing matrix adapted to perform a database operation on hierarchical data;

a second type of processing matrix adapted to perform an indexing database operation;

a third type of processing matrix adapted to perform a database operation on large amounts of data;

a global-results type of processing matrix, selected from at least the first type of processing matrix, the second type of processing matrix, and the third type of processing matrix, to process a query based on at least one database operation to be performed to process the query, the global-results type of processing matrix including a master node and a plurality of slave nodes, each of the master node and slave nodes including a processor and disk storage, and

a computer readable medium, the computer readable medium comprising;

a first set of executable instructions being adapted to manipulate the processor of each slave node to execute a same first portion of an at least one executable, the at least one executable having at least a first portion and a second portion, the first portion configured to generate a portion of initial query results and the second portion configured to execute one or more operations on the set of initial query results using a portion of a database stored at the disk storage of the slave node to generate final query results, the first portion of the at least one executable representing at least one database operation on the stored database portion, the first portion being executed by the slave node substantially in parallel with an execution of the first portion by other slave nodes, wherein the entire database is distributed among the plurality of slave nodes in distinct portions and wherein the plurality of slave nodes are used to process the query, the first portion of the at least one executable representing at least one database operation; and

a second set of executable instructions being adapted to manipulate the processor of the master node to execute the second portion of the at least one executable using the initial query results to generate final query results, the second portion of the at least one executable representing at least one database operation using the initial query results.

77. The computer readable medium of claim 76, further comprising a third set of executable instructions being adapted to manipulate a processor to:

generate intermediary source code from query source code, the query source code representing at least one database operation using the database and wherein the query source code is formatted based in part on a query-based programming language;

compile the intermediary source code to generate the at least one executable; and

provide the at least one executable to the master node.

78. The computer readable medium of claim 76, wherein the at least one executable includes at least one dynamic link library (DLL).

79. The computer readable medium of claim 76, wherein the at least one database operation represented by the first portion of the at least one executable includes one of a group consisting of:

linking, matching, filtering, scoring, sorting, counting, and joining.

80. The computer readable medium of claim 76, wherein the at least one database operation represented by the second portion of the at least one executable includes one of a group consisting of:

sorting, linking, collating, filtering, counting, deduping, joining, appending, merging, purging, non-hierarchical linking, neural-net scoring, and formatting.

81. The system of claim 76, wherein the database operation on large amounts of data includes one of a group consisting of:

sorting, linking, collating, filtering, counting, deduping, joining, appending, merging, purging, non-hierarchical linking, neural-net scoring, and formatting.