Dynamic Rebuilding of Query Execution Trees and Reselection of Query Execution Operators

A database engine, comprising:

• one or more computing devices, each having one or more processors, memory, and one or more programs stored in the memory, wherein the one or more programs are configured for execution by the one or more processors and comprise instructions for:
• receiving a query;
• parsing the query to form a query execution tree;
• compiling the query execution tree to form a first executable plan that includes a plurality of in-memory operators that execute within the volatile memory without swapping to the non-volatile memory;
• initiating execution of the first executable plan, including initiating execution of a first plurality of in-memory operators in the first executable plan to run in parallel;
• while executing a first in-memory operator of the first plurality, detecting insufficient memory to complete execution of the first in-memory operator;
• and
• in response to detecting insufficient memory to complete execution of the first in-memory operator:
• aborting execution of the first executable plan;
• recompiling the query execution tree to form a second executable plan that replaces the first in-memory operator with a first spooling operator, wherein the first spooling operator executes within a fixed volatile memory budget and is configured to swap to non-volatile memory according to the fixed volatile memory budget;
• recompiling the query execution tree to form a third executable plan that retains the first in-memory operator, but schedules the first in-memory operator to execute not in parallel with the other in-memory operators of the first plurality;
• selecting a final executable plan to be the second executable plan or the third executable plan, according to estimated available volatile memory;
• executing the final executable plan to identify a set of results from the database that is responsive to the query;
• and
• returning the set of results.

A non-transitory computer readable storage medium storing one or more programs configured for execution by a computing device having one or more processors, volatile memory, and non-volatile memory, the one or more programs comprising instructions for:

• receiving a query;
• parsing the query to form a query execution tree;
• compiling the query execution tree to form a first executable plan that includes a plurality of in-memory operators that execute within the volatile memory without swapping to the non-volatile memory;
• initiating execution of the first executable plan, including initiating execution of a first plurality of in-memory operators in the first executable plan to run in parallel;
• while executing a first in-memory operator of the first plurality, detecting insufficient memory to complete execution of the first in-memory operator;
• and
• in response to detecting insufficient memory to complete execution of the first in-memory operator:
• aborting execution of the first executable plan;
• recompiling the query execution tree to form a second executable plan that replaces the first in-memory operator with a first spooling operator, wherein the first spooling operator executes within a fixed volatile memory budget and is configured to swap to non-volatile memory according to the fixed volatile memory budget;
• recompiling the query execution tree to form a third executable plan that retains the first in-memory operator, but schedules the first in-memory operator to execute not in parallel with the other in-memory operators of the first plurality;
• selecting a final executable plan to be the second executable plan or the third executable plan, according to estimated available volatile memory;
• executing the final executable plan to identify a set of results from the database that is responsive to the query;
• and
• returning the set of results.