Pushdown Of Sorting And Set Operations (Union, Intersection, Minus) To A Large Number Of Low-Power Cores In A Heterogeneous System

A computer system for performing a query operation on a pair of relations, the system comprising:

• a database system;
• and
• a heterogeneous system (HS) that is coupled to the database system and includes a plurality of compute nodes arranged in one or more hierarchies,
• wherein each hierarchy of the one more hierarchies has a plurality of leaf nodes, a plurality of intermediate nodes and a root node,
• wherein each of the plurality of leaf nodes is coupled to an intermediate node and each of the intermediate nodes is coupled to either another intermediate node or to the root node;
• wherein the database system is configured to:
• receive a request to perform the query operation on the pair of relations;
• determine a type of query operation from the request;
• compute a cost of performing the query operation on the database system alone;
• compute one or more costs of performing the query operation on the database system with assistance of the HS,
• wherein each of the one or more costs corresponds to a particular algorithm for performing the query operation,
• wherein portions of the query operation on the pair of relations can be performed on one or more of the plurality of leaf nodes, the plurality of intermediate nodes, or the root node in each hierarchy;
• and
• compare the costs to determine whether to use the assistance of the HS for the requested query operation;
• select for the query operation an algorithm with the lowest cost based on the comparison;
• perform portions of the query operation in accordance with the selected algorithm on the pair of relations;
• and
• wherein the heterogeneous system is configured to:
• perform portions of the query operation in accordance with the selected algorithm on the pair of relations on one or more of the plurality of leaf nodes, the plurality of intermediate or switch nodes, the root node;
• and
• transmit results of the query operation to the database system.

A non-transitory computer readable medium carrying one or more sequences of instructions for performing a query operation on a pair of relations in a database system coupled to a heterogeneous system (HS), wherein execution of the one or more sequences by one or more processors causes the processors to perform the steps of:

• receiving a request to perform a query operation on the pair of relations;
• determining the type of query operation from the request;
• based on the type of query operation,
• computing a cost of performing the query operation on the database system alone;
• computing one or more costs of performing the query operation on the database system with assistance of the HS,
• wherein each of the one or more costs corresponds to a particular algorithm for performing the query operation,
• wherein the HS includes a plurality of compute nodes arranged in one or more hierarchies, wherein each hierarchy of the one more hierarchies has a plurality of leaf nodes, a plurality of intermediate nodes and a root node, wherein each of the plurality of leaf nodes is coupled to an intermediate node and each of the intermediate nodes or switch nodes is coupled to either another intermediate node or switch node or to the root node,
• wherein portions of the query operation on the pair of relations are performed on one or more of the plurality of leaf nodes, the plurality of intermediate nodes, or the root node in each hierarchy;
• and
• comparing the costs to determine whether to use the assistance of the HS for the requested query operation;
• selecting for the query operation an algorithm with the lowest cost based on the comparison;
• if the query operation is performed with the assistance of the HS, then performing portions of the query operation in accordance with the selected algorithm on the pair of relations on one or more of the plurality of leaf nodes, the plurality of intermediate or switch nodes, the root node in each hierarchy, or the database system;
• and
• providing results of the requested query.