Compiling just the best bits: finding the maximum benefit shared subexpressions in a query workload

Patent metadata

Field	Value
Publication number	US-2025086176-A1
Application number	US-202418638931-A
Country	US
Kind code	A1
Filing date	Apr 18, 2024
Priority date	Sep 8, 2023
Publication date	Mar 13, 2025
Grant date	—

Abstract

In a computer, each of many statement plan trees respectively represents a distinct database statement in a database workload. Each statement plan tree contains a distinct set of tree nodes. A first statement plan tree contains a first subtree and represents a first statement. A second statement plan tree contains a second subtree, and a third statement plan tree contains a third subtree. By agglomeration, a first cluster subplan is generated that represents the first subtree of the first statement plan tree and the second subtree of the second statement plan tree. By subsequent agglomeration, a second cluster subplan is generated that represents the third subtree of the third statement plan tree and the first cluster subplan. Execution of the first database statement uses the second cluster subplan for acceleration. Agglomeration may be decided based on novel net benefit estimation, novel inter-cluster distance, and a novel and tunable compilation cost.

First claim

What is claimed is:

1 . A method comprising:
generating, for an instruction set architecture (ISA) of a processor, an instruction sequence that can execute a first subplan in a statement plan for a database statement; and executing the database statement by:
invoking the instruction sequence to execute the first subplan in the statement plan, and
interpreting, without generating logic, a second subplan in the statement plan.

2 . The method of claim 1 further comprising the instruction sequence accepting a runtime argument that identifies at least one selected from a group consisting of:
a database table,
a table column,
a representation of the second subplan in the statement plan,
a second instruction sequence for the ISA that can execute the second subplan in the statement plan, and
logic for a second ISA that lacks registers.

3 . The method of claim 1 wherein:
said executing the database statement comprises the instruction sequence accepting, as a runtime argument, a first database operator that does not access a database table;
the method further comprises after said executing the database statement, the instruction sequence accepting, as said runtime argument, a second database operator that accesses a database table.

4 . The method of claim 1 wherein said invoking the instruction sequence causes said interpreting.

5 . The method of claim 1 wherein:
the instruction sequence can execute a third subplan in a second statement plan for a second database statement;
said generating is based on the first subplan and the third subplan.

6 . The method of claim 1 wherein said invoking the instruction sequence occurs before said interpreting the second subplan.

7 . A method comprising:
receiving a plurality of statement plan trees, wherein:
a) each statement plan tree of the plurality of statement plan trees represents a distinct database statement,
b) each statement plan tree of the plurality of statement plan trees contains a distinct plurality of tree nodes,
c) the plurality of statement plan trees contains: a first statement plan tree that contains a first subtree, a second statement plan tree that contains a second subtree, and a third statement plan tree that contains a third subtree, and
d) the first statement plan tree represents a first database statement;
generating a first cluster subplan that represents the first subtree of the first statement plan tree and the second subtree of the second statement plan tree; generating a second cluster subplan that represents the third subtree of the third statement plan tree and the first cluster subplan; and executing the first database statement based on the second cluster subplan.

8 . The method of claim 7 wherein:
the plurality of statement plan trees contains a fourth statement plan tree that contains a fourth subtree;
the method further comprises:
calculating:
a first estimated acceleration provided by the second cluster subplan and
a second estimated acceleration provided by a third cluster subplan that represents the fourth subtree of the fourth statement plan tree and the first cluster subplan;

compiling the second cluster subplan in response to the first estimated acceleration exceeding the second estimated acceleration.

9 . The method of claim 8 further comprising:
calculating a third estimated acceleration provided by a fourth cluster subplan that represents the fourth subtree in the fourth statement plan tree and the second cluster subplan;
detecting that a compilation cost exceeds the third estimated acceleration.

10 . The method of claim 7 wherein:
the first subtree contains a fourth subtree;
said executing the first database statement comprises the second cluster subplan accepting a runtime argument that identifies the fourth subtree.

11 . A method comprising:
predefining a plurality of distinct database operators, wherein each database operator of the plurality of distinct database operators respectively has an acceleration constant and a time complexity; receiving a statement plan tree that represents a database statement, wherein:
the statement plan tree contains a subtree that contains a plurality of tree nodes, and
each tree node of the subtree respectively specifies a database operator of the plurality of distinct database operators and a content cardinality;
calculating respectively for each tree node of the subtree:
a) an estimated latency based on the content cardinality of the tree node and the time complexity of the database operator of the tree node and
b) an estimated acceleration based on the estimated latency of the tree node and the acceleration constant of the database operator of the tree node;
deciding, based on the estimated acceleration of each tree node of the subtree, to compile the subtree; compiling the subtree into an instruction sequence; and executing the database statement based on the instruction sequence.

12 . The method of claim 11 wherein said deciding to compile the subtree is based on an estimated cost selected from a group consisting of:
a) a cost that does not depend on a count of the plurality of tree nodes and
b) a fixed cost that does not depend on at least one selected from a group consisting of the statement plan tree and the subtree.

13 . The method of claim 11 wherein:
the plurality of distinct database operators comprises a database operator that represents an unspecified parameter;
said predefining the acceleration constant of the unspecified parameter comprises zeroing the acceleration constant.

14 . The method of claim 11 wherein the content cardinality of a particular tree node in the subtree is provided by one selected from a group consisting of:
a) a query optimizer that generated the statement plan tree and
b) a previous execution of one selected from a group consisting of the database statement and the subtree.

15 . One or more non-transitory computer-readable media storing instructions that, when executed by one or more processors, cause:
generating, for an instruction set architecture (ISA) of a processor, an instruction sequence that can execute a first subplan in a statement plan for a database statement; and executing the database statement by:
invoking the instruction sequence to execute the first subplan in the statement plan, and
interpreting, without generating logic, a second subplan in the statement plan.

16 . The one or more non-transitory computer-readable media of claim 15 wherein said instructions further cause said instruction sequence accepting a runtime argument that identifies at least one selected from a group consisting of:
a database table,
a table column,
a representation of the second subplan in the statement plan,
a second instruction sequence for the ISA that can execute the second subplan in the statement plan, and
logic for a second ISA that lacks registers.

17 . The one or more non-transitory computer-readable media of claim 15 wherein:
said executing the database statement comprises the instruction sequence accepting, as a runtime argument, a first database operator that does not access a database table;
said instructions further cause after said executing the database statement, the instruction sequence accepting, as said runtime argument, a second database operator that accesses a database table.

18 . One or more non-transitory computer-readable media storing instructions that, when executed by one or more processors, cause:
receiving a plurality of statement plan

Assignees

• Oracle Int Corp

Inventors

• Lim Lawrence
• Aghababaie Beni Laleh
• Swart Garret F

Classifications

• G06F16/24524

  Access plan code generation and invalidation; Reuse of access plans · CPC title

• G06F16/24542 Primary

  Plan optimisation · CPC title

• G06F11/3419

  by assessing time · CPC title