Optimization of split queries

• US 10,437,821 B2
• Filed: 10/26/2016
• Issued: 10/08/2019
• Est. Priority Date: 10/26/2016
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Goerzig, Benny, Kohler, Mathias, Kerschbaum, Florian
• Primary Examiner(s): Raab, Christopher J
• Application Number:
  US15/335,330
• Publication Number:
  US 20180113905A1
• Time in Patent Office: 1,077 Days
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

Methods and apparatus, including computer program products, are provided for split query optimization. In some example embodiments, a method may include: determining, for a query comprising a plurality of operations, a first workload distribution between a first data store and a second data store, the first workload distribution indicating that a first portion of the query is to be performed at the first data store and a second portion of the query is to be performed at the second data store; and determining, based at least on the first workload distribution, a second workload distribution, the determining of the second workload distribution includes pushing down, to the first portion of the query, a first operation from the second portion of the query such that the first operation is performed at the first data store instead of at the second data store.

Claims

1. A computer-implemented method comprising:

determining, for a query comprising a plurality of operations, a first workload distribution between a first data store storing encrypted data and a second data store storing unencrypted data, the query including a first portion that can be performed on the encrypted data and a second portion that cannot be performed on the encrypted data, the first workload distribution being determined based at least on the second portion of the query being unable to be performed on the encrypted data in the first data store, and the first workload distribution indicating that the first portion of the query is to be performed at the first data store and the second portion of the query is to be performed at the second data store;

determining, based at least on the first workload distribution, a second workload distribution, the determining of the second workload distribution comprising a reordering of at least a first operation and a second operation in the second portion of the query, the first operation and the second operation being reordered based at least on the first operation and the second operation being non-conflicting operations that can be at least one of commuted, distributed, and combined without affecting a respective result of the first operation and the second operation, and the reordering including pushing down, to the first portion of the query, the first operation such that the first operation is performed at the first data store instead of at the second data store; and

executing the query, the executing comprising distributing, to the first data store and the second data store, respective portions of an execution plan corresponding to the first portion of the query and the second portion of the query, the execution plan being generated based at least on the second workload distribution.

2. The computer-implemented method of claim 1, wherein the encrypted data in the first data store is generated at least by applying one or more encryption schemes.

3. The computer-implemented method of claim 2, wherein the determining of the first workload distribution comprises:

identifying a split cause operation present in the query, the split cause operation being an operation that is incompatible with the one or more encryption schemes applied at the first data store and unable to be performed on the encrypted data in the first data store; and

including, in the second portion of the query, the split cause operation.

4. The computer-implemented method of claim 1, wherein the determining of the second workload distribution comprises:

decomposing, into a plurality of atomic operations, one or more operations included in the query.

5. The computer-implemented method of claim 1, wherein the determining of the second workload distribution further comprises:

identifying, based at least on an operator tree corresponding to the query, the first operation to push down to the first portion of the query, the first operation being identified based at least on the first operation being an operation that can be performed on the encrypted data in the first data store.

6. The computer-implemented method of claim 5, further comprising:

selecting, from the operator tree, a first node corresponding to the first operation; and

switching a relative position of the first node and a child node of the first node corresponding to the second operation, the relative position of the first node and the child node being switched based at least on the first operation and the second operation being non-conflicting operations.

7. The computer-implemented method of claim 6, further comprising:

traversing the operator tree to select a second node corresponding to third operation; and

switching a relative position of the second node and a child node of the second node, when the third operation and a fourth operation corresponding to the child node of the second node are determined to be non-conflicting operations.

8. The computer-implemented method of claim 7, wherein the operator tree is traversed starting from a leaf node of the operator tree, and wherein the traversing of the operator tree includes skipping over one or more nodes corresponding to split cause operations.

9. The computer-implemented method of claim 1, further comprising:

obtaining, from the first data store, a first estimate and a second estimate of a size of an output data, the first estimate corresponding to an amount of the encrypted data transferred from the first data store when the first operation is performed at the first data store, and the second estimate corresponding to an amount of the encrypted data transferred from the first data store when the first operation is not performed at the first data store; and

determining to push down the first operation based at least on the first estimate not exceeding the second estimate.

10. The computer-implemented method of claim 9, wherein the first estimate and the second estimate are obtained from the first data store in response to an output size of the first operation being greater than an input size of the first operation.

11. The computer-implemented method of claim 1, wherein performing the first operation at the first data store instead of the second data store decreases an amount of data that is at least one of transferred from the first data store to the second data store and decrypted at the second data store.

12. A system, comprising:

at least one processor; and

at least one memory including program code which when executed by the at least one memory provides operations comprising;

determining, for a query comprising a plurality of operations, a first workload distribution between a first data store storing encrypted data and a second data store storing unencrypted data, the query including a first portion that can be performed on the encrypted data and a second portion that cannot be performed on the encrypted data, the first workload distribution being determined based at least on the second portion of the query being unable to be performed on the encrypted data in the first data store, and the first workload distribution indicating that the first portion of the query is to be performed at the first data store and the second portion of the query is to be performed at the second data store;

determining, based at least on the first workload distribution, a second workload distribution, the determining of the second workload distribution comprising a reordering of at least a first operation and a second operation in the second portion of the query, the first operation and the second operation being reordered based at least on the first operation and the second operation being non-conflicting operations that can be at least one of commuted, distributed, and combined without affecting a respective result of the first operation and the second operation, and the reordering including pushing down, to the first portion of the query, the first operation such that the first operation is performed at the first data store instead of at the second data store; and

executing the query, the executing comprising distributing, to the first data store and the second data store, respective portions of an execution plan corresponding to the first portion of the query and the second portion of the query, the execution plan being generated based at least on the second workload distribution.

13. The system of claim 12, wherein the encrypted data in the first data store is generated at least by applying one or more encryption schemes.

14. The system of claim 13, further comprising:

identifying a split cause operation present in the query, the split cause operation being an operation that is incompatible with the one or more encryption schemes applied at the first data store and unable to be performed on the encrypted data in the first data store; and

including, in the second portion of the query, the split cause operation.

15. The system of claim 12, wherein the determining of the second workload distribution further comprises:

identifying, based at least on an operator tree corresponding to the query, the first operation to push down to the first portion of the query, the first operation being identified based at least on the first operation being an operation that can be performed on the encrypted data in the first data store.

16. The system of claim 15, further comprising:

selecting, from the operator tree, a first node corresponding to the first operation; and

switching a relative position of the first node and a child node of the first node corresponding to the second operation, the relative position of the first node and the child node being switched based at least on the first operation and the second operation being non-conflicting operations.

17. The system of claim 15, further comprising:

obtaining, from the first data store, a first estimate and a second estimate of a size of an output data, the first estimate corresponding to an amount of the encrypted data transferred from the first data store when the first operation is performed at the first data store, and the second estimate corresponding to an amount of the encrypted data transferred from the first data store when the first operation is not performed at the first data store; and

determining to push down the first operation based at least on the first estimate not exceeding the second estimate.

18. A non-transitory computer-readable storage medium including program code which when executed by at least one processor causes operations comprising:

determining, for a query comprising a plurality of operations, a first workload distribution between a first data store storing encrypted data and a second data store storing unencrypted data, the query including a first portion that can be performed on the encrypted data and a second portion that cannot be performed on the encrypted data, the first workload distribution being determined based at least on the second portion of the query being unable to be performed on the encrypted data in the first data store, and the first workload distribution indicating that the first portion of the query is to be performed at the first data store and the second portion of the query is to be performed at the second data store;

determining, based at least on the first workload distribution, a second workload distribution, the determining of the second workload distribution comprising a reordering of at least a first operation and a second operation in the second portion of the query, the first operation and the second operation being reordered based at least on the first operation and the second operation being non-conflicting operations that can be at least one of commuted, distributed, and combined without affecting a respective result of the first operation and the second operation, and the reordering including pushing down, to the first portion of the query, the first operation such that the first operation is performed at the first data store instead of at the second data store; and

executing the query, the executing comprising distributing, to the first data store and the second data store, respective portions of an execution plan corresponding to the first portion of the query and the second portion of the query, the execution plan being generated based at least on the second workload distribution.