Efficient distributed query execution

• US 10,248,701 B2
• Filed: 09/18/2015
• Issued: 04/02/2019
• Est. Priority Date: 09/18/2015
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kotoulas, Spyros, Sbodio, Marco L., Stephenson, Martin J., Tommasi, Pierpaolo
• Primary Examiner(s): Mackes, Kris E
• Assistant Examiner(s): Bui, Tiffany Thuy T
• Application Number:
  US14/858,657
• Publication Number:
  US 20170083632A1
• Time in Patent Office: 1,292 Days
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06F 16/256 in federated or virtual databases

Abstract

An embodiment of the invention provides a method wherein a database query including a first constraint and additional constraint(s) are received in a first node. Data in the first node that satisfies the first constraint is identified, encoded, and sent to a second node. Encoded data is identified in a mapping table in the second node; and, one or more missing identifiers are identified that include encoded data that is not in the mapping table. The missing identifier is sent to the first node, decoded to retrieve the value of the missing identifier, and mapped to the retrieved value. The mapping of the missing identifier and the retrieved value are sent to the second node. A dictionary in the second node is queried with the retrieved value to identify an identification number for the retrieved value. The missing identifier is mapped to the identification number for the retrieved value.

Claims

1. A method for query execution in multiple nodes of a distributed database system, said method comprising:

receiving a database query in a first node of the distributed database system, the database query including a first constraint and at least one additional constraint;

identifying data in the first node that satisfies the first constraint with a first processor;

encoding the data with an encoder to generate encoded data;

sending the encoded data to a second node of the distributed database system with a first communications device, wherein each node of the nodes includes a data field, a predicate field, and an object field;

encoding a predicate in the second node to generate an encoded predicate; and

encoding an object in the second node to generate an encoded object;

identifying at least one encoded data of the encoded data that is in a mapping table in the second node with a second processor;

identifying at least one missing identifier with the second processor, the at least one missing identifier including at least one encoded data of the encoded data that is not in the mapping table in the second node;

sending the missing identifier to the first node with a second communications device;

decoding the missing identifier to retrieve the value of the missing identifier;

mapping the missing identifier to the retrieved value;

sending the mapping of the missing identifier and the retrieved value to the second node with the first communications device;

querying a dictionary in the second node with the retrieved value to identify an identification number for the retrieved value;

rewriting the database query to include;

the identification number for the retrieved value; and

at least one identification number for the at least one encoded data of the

encoded data that is in the mapping table in the second node; and

mapping the missing identifier to the identification number for the retrieved value.

2. The method according to claim 1, wherein said rewriting of the database query includes rewriting the database query to include:

an encoded predicate; and

an encoded object.

3. The method according to claim 1, wherein unencoded data is not sent to the second node of the distributed database system.

4. The method according to claim 1, wherein values of the encoded subjects are not sent to the second node of the distributed database system.

5. A method for improving the efficiency of distributed query execution in multiple nodes of a federated database system, said method comprising:

receiving a database query in a first node of the federated database system, the database query including a set of constraints;

identifying a set of bindings with a first processor in the first node that satisfies a subset of the set of constraints, wherein each binding in the set of bindings includes a variable and a value;

encoding the values in the set of bindings with an encoder to generate encoded bindings;

sending bindings to a second node of the federated database system with a first communications device, said sending of the bindings to the second node including only sending the encoded bindings;

identifying a second set of bindings in the second node that satisfies a second subset of the set of constraints;

identifying at least one missing encoded binding of the encoded bindings that is not in the dictionary in the second node with a second processor;

sending a request for the missing encoded binding with a second communications device, the request being sent to the first node;

repeating previous process for every other node in the federated database system until all of the set of constraints are satisfied;

retrieving a value corresponding to the missing encoded binding from a mapping table in the first node;

retrieving encoded values from the mapping table in the first node,

sending the remaining constraints to satisfy the second subset of the set of constraints to the second node, wherein the second subset of the set of constraints is the difference between the set of constraints and the subset of the set of constraints;

sending the retrieved value to the second node with the first communications device; and

updating the dictionary in the second node with the retrieved value and mapping the retrieved value to the missing encoded binding with the second processor.

6. The method according to claim 5, wherein the set of constraints include variables.

7. The method according to claim 5, wherein the variable is an unknown element in a constraint in the subset of the set of constraints, and wherein the value satisfies the constraint.

8. The method according to claim 5, further comprising identifying at least one encoded binding of the encoded bindings that is in a dictionary in the second node.

9. The method according to claim 5, wherein unencoded bindings are not sent to the second node of the federated database system.

10. A computer program product for improving the efficiency of distributed query execution in multiple nodes of a federated database system, said computer program product comprising:

a non-transitory computer readable storage medium having stored thereon;

first program instructions executable by a device to cause the device to receive a database query in a first node of the federated database system, the database query including a set of constraints;

second program instructions executable by the device to cause the device to identify a set of bindings in the first node that satisfies a subset of the set of constraints, wherein each binding in the set of bindings includes a variable and a value;

third program instructions executable by the device to cause the device to encode the values in the set of bindings to generate encoded bindings;

fourth program instructions executable by the device to cause the device to send bindings to a second node of the federated database system, wherein said fourth program instructions only sends the encoded bindings;

fifth program instructions executable by the device to cause the device to identify at least one missing encoded binding of the encoded bindings that is not in the dictionary in the second node;

sixth program instructions executable by the device to cause the device to send a request for the missing encoded binding to the first node;

seventh program instructions executable by the device to cause the device to retrieve a value corresponding to the missing encoded binding from a mapping table in the first node;

eighth program instructions executable by the device to cause the device to send the retrieved value to the second node;

ninth program instructions executable by the device to cause the device to update the dictionary in the second node with the retrieved value and mapping the retrieved value to the missing encoded binding;

tenth program instructions executable by the device to cause the device to identify a second set of bindings in the second node that satisfies a second subset of the set of constraints;

eleventh program instructions executable by the device to cause the device to repeat previous process for every other node in the federated database system until all of the set of constraints are satisfied;

twelfth program instructions executable by the device to cause the device to retrieve encoded values from the mapping table in the first node; and

thirteenth program instructions executable by the device to cause the device to send the remaining constraints to satisfy the second subset of the set of constraints to the second node, wherein the second subset of the set of constraints is the difference between the set of constraints and the subset of the set of constraints.