Enable merge join on encrypted data

A computer program product for encrypting data, the computer program product comprising:

• a computer readable storage medium having computer readable program code stored on the computer readable storage medium, wherein the computer readable storage medium is not a transitory signal per se, the computer readable program code being executed by a central processing unit (CPU) of a computer system to cause the computer system to perform a method comprising:
• the computer system ordering (i) first data in original records in a first database table by a foreign key included in the first database table and (ii) second data in a second database table by a primary key included in the second database table, the first and second database tables being included in a relational database management system;
• the computer system adding fake records to the first database table, the fake records including fake values of the foreign key;
• using an encryption function, the computer system encrypting values of the foreign key in the original records included in the first database table;
• using the encryption function, the computer system encrypting the fake values of the foreign key in the fake records;
• the computer system determining that the encryption function is homomorphic to sorting operators;
• the computer system determining that a decryption function that decrypts the encrypted values of the foreign key in the original records included in the first database table and the encrypted fake values of the foreign key in the fake records is homomorphic to sorting operators;
• in response to the encryption and decryption functions being determined to be homomorphic, the computer system selecting a merge join operation that operates on the first and second database tables and that includes the decryption function in a joining condition;
• using the selected merge join operation, the computer system optimizing an execution of a query that accesses one or more data items in the first database table, wherein the optimizing the execution of the query includes determining that the fake values of the foreign key in the fake records are fake, and in response to the determining that the fake values of the foreign key in the fake records are fake, skipping over the fake records in an access of the one or more data items in the first database table;
• and
• the computer system modifying data items in the first database table by noising the data items, wherein the encrypting the values of the foreign key in the original records and the encrypting the fake values of the foreign key include applying a homomorphic function to the noised data items, and wherein the noising includes the adding the fake records to the first database table.

A computer system comprising:

• a central processing unit (CPU);
• a memory coupled to the CPU;
• and
• a computer readable storage medium coupled to the CPU, the computer readable storage medium containing instructions that are executed by the CPU via the memory to implement a method of encrypting data, the method comprising:
• the computer system ordering (i) first data in original records in a first database table by a foreign key included in the first database table and (ii) second data in a second database table by a primary key included in the second database table, the first and second database tables being included in a relational database management system;
• the computer system adding fake records to the first database table, the fake records including fake values of the foreign key;
• using an encryption function, the computer system encrypting values of the foreign key in the original records included in the first database table;
• using the encryption function, the computer system encrypting the fake values of the foreign key in the fake records;
• the computer system determining that the encryption function is homomorphic to sorting operators;
• the computer system determining that a decryption function that decrypts the encrypted values of the foreign key in the original records included in the first database table and the encrypted fake values of the foreign key in the fake records is homomorphic to sorting operators;
• in response to the encryption and decryption functions being determined to be homomorphic, the computer system selecting a merge join operation that operates on the first and second database tables and that includes the decryption function in a joining condition;
• using the selected merge join operation, the computer system optimizing an execution of a query that accesses one or more data items in the first database table, wherein the optimizing the execution of the query includes determining that the fake values of the foreign key in the fake records are fake, and in response to the determining that the fake values of the foreign key in the fake records are fake, skipping over the fake records in an access of the one or more data items in the first database table;
• and
• the computer system modifying data items in the first database table by noising the data items, wherein the encrypting the values of the foreign key in the original records and the encrypting the fake values of the foreign key include applying a homomorphic function to the noised data items, and wherein the noising includes the adding the fake records to the first database table.