Query optimization methods, apparatuses, and systems for secure multi-party database

Patent metadata

Field	Value
Publication number	US-12259885-B2
Application number	US-202318492456-A
Country	US
Kind code	B2
Filing date	Oct 23, 2023
Priority date	Apr 23, 2021
Publication date	Mar 25, 2025
Grant date	Mar 25, 2025

Abstract

Implementations of this specification provide query optimization methods, apparatuses, and systems for secure multi-party databases. In an implementation, a method includes: receiving a current query associated with a plurality of target database of a multi-party database system, generating a plurality of execution plans for the current query, determining, for each execution plan, a respective cost computation formula of a plurality of cost computation values for computing an execution cost of jointly executing the execution plan by the plurality of target databases, receiving a secure computation result from each of a plurality of query engines corresponding to the plurality of target databases, and determining an optimal execution plan having a lowest cost value in the plurality of cost computation formulas based on the secure computation result.

First claim

What is claimed is:

1. A computer-implemented method, comprising:
receiving, by a central device of a multi-party database system, a current query associated with a plurality of target databases of the multi-party database system;
generating, by the central device, a plurality of execution plans for the current query;
determining, by the central device for each execution plan, a respective cost computation formula of a plurality of cost computation formulas for computing an execution cost of jointly executing the execution plan by the plurality of target databases;
receiving, by the central device, a secure computation result from each of a plurality of query engines corresponding to the plurality of target databases, wherein the secure computation result is obtained by performing secure multi-party computation (MPC) based on a target secure computation method corresponding to the respective cost computation formula; and
determining, by the central device, an optimal execution plan having a lowest cost value in the plurality of cost computation formulas based on a cryptographic result of a cost value of each of the plurality of cost computation formulas.

2. The computer-implemented method according to claim 1 , wherein the execution cost comprises computing resource costs of the plurality of target databases and costs of communications between the plurality of target databases.

3. The computer-implemented method according to claim 1 , further comprising:
determining, by the central device, the target secure computation method based on the plurality of cost computation formulas; and
sending, by the central device, the target secure computation method to the plurality of query engines.

4. The computer-implemented method according to claim 1 , wherein the secure computation result is an index number of a cost computation formula with the lowest cost value in the plurality of cost computation formulas; and wherein
determining the optimal execution plan having the lowest cost value comprises:
determining an execution plan corresponding to the index number as the optimal execution plan.

5. The computer-implemented method according to claim 1 , wherein the secure computation result is
the cryptographic result of each of the plurality of cost computation formulas.

6. The computer-implemented method according to claim 5 , wherein the cryptographic result is a cost value shard computed based on secret sharing; and wherein
determining the optimal execution plan comprises:
aggregating a plurality of cost value shards sent by the plurality of query engines for a same execution plan of the plurality of execution plans to obtain a cost value of the same execution plan; and
determining the optimal execution plan by comparing cost values of the plurality of execution plans.

7. The computer-implemented method according to claim 5 , wherein the cryptographic result is a ciphertext cost value encrypted based on a public key of the central device; and wherein
determining the optimal execution plan comprises:
decrypting the ciphertext cost value based on a private key corresponding to the public key, to obtain a plaintext cost value; and
determining the optimal execution plan by comparing plaintext cost values of the plurality of execution plans.

8. A non-transitory, computer-readable medium storing one or more instructions executable by a computer system to perform operations comprising:
receiving, by a central device of a multi-party database system, a current query associated with a plurality of target databases of the multi-party database system;
generating, by the central device, a plurality of execution plans for the current query;
determining, by the central device for each execution plan, a respective cost computation formula of a plurality of cost computation formulas for computing an execution cost of jointly executing the execution plan by the plurality of target databases;
receiving, by the central device, a secure computation result from each of a plurality of query engines corresponding to the plurality of target databases, wherein the secure computation result is obtained by performing secure multi-party computation (MPC) based on a target secure computation method corresponding to the respective cost computation formula; and
determining, by the central device, an optimal execution plan having a lowest cost value in the plurality of cost computation formulas based on a cryptographic result of a cost value of each of the plurality of cost computation formulas.

9. The non-transitory, computer-readable medium according to claim 8 , wherein the execution cost comprises computing resource costs of the plurality of target databases and costs of communications between the plurality of target databases.

10. The non-transitory, computer-readable medium according to claim 8 , the operations further comprising:
determining, by the central device, the target secure computation method based on the plurality of cost computation formulas; and
sending, by the central device, the target secure computation method to the plurality of query engines.

11. The non-transitory, computer-readable medium according to claim 8 , wherein the secure computation result is an index number of a cost computation formula with the lowest cost value in the plurality of cost computation formulas; and wherein
determining the optimal execution plan having the lowest cost value comprises:
determining an execution plan corresponding to the index number as the optimal execution plan.

12. The non-transitory, computer-readable medium according to claim 8 , wherein the secure computation result is
the cryptographic result of each of the plurality of cost computation formulas.

13. The non-transitory, computer-readable medium according to claim 12 , wherein the cryptographic result is a cost value shard computed based on secret sharing; and wherein
determining the optimal execution plan comprises:
aggregating a plurality of cost value shards sent by the plurality of query engines for a same execution plan of the plurality of execution plans to obtain a cost value of the same execution plan; and
determining the optimal execution plan by comparing cost values of the plurality of execution plans.

14. The non-transitory, computer-readable medium according to claim 12 , wherein the cryptographic result is a ciphertext cost value encrypted based on a public key of the central device; and wherein
determining the optimal execution plan comprises:
decrypting the ciphertext cost value based on a private key corresponding to the public key, to obtain a plaintext cost value; and
determining the optimal execution plan by comparing plaintext cost values of the plurality of execution plans.

15. A central device of a multi-party database system, comprising:
one or more processors; and
one or more computer memory devices interoperably coupled with the one or more processors and storing programming instructions for execution by the one or more processors to perform operations comprising:
receiving a current query associated with a plurality of target databases of the multi-party database system;
generating a plurality of execution plans for the current query;
determining, for each execution plan, a respective cost computation formula of a plurality of cost computation formulas for computing an execution cost of jointly executing the execution plan by the plurality of target databases;
receiving a secure computation result from each of a plurality of query engines corresponding to the plurality of target databases, wherein the secu

Assignees

• Alipay Hangzhou Inf Tech Co Ltd

Inventors

• Yang Yang
• Huang Qunshan
• Qi Jun
• Cao Shunde
• Duan Pu
• Du Jian
• Mao Qingkai
• Zhao Yang
• Yu Kefeng
• Wang Lei
• Zhang Benyu

Classifications

• H04L9/06

  the encryption apparatus using shift registers or memories for block-wise {or stream} coding, e.g. DES systems {or RC4; Hash functions; Pseudorandom sequence generators} · CPC title

• H04L2209/46

  Secure multiparty computation, e.g. millionaire problem · CPC title

• H04L9/085

  Secret sharing or secret splitting, e.g. threshold schemes · CPC title

• G06F16/2456

  Join operations · CPC title

• G06F21/6218

  to a system of files or objects, e.g. local or distributed file system or database · CPC title