Extraction method, extraction device, and extraction program
AssigneeNippon Telegraph and Telephone Corporation
InventorYuya Watari
Life of this patent
Estimating the term…
Abstract
An extraction apparatus (10) is the extraction apparatus that extracts a common plan subtree that is a common part among a plurality of plan trees from the plurality of plan trees, and includes a first assignment unit (11) that calculates, based on information of nodes of a plan tree, a hash value for each node to assign the calculated hash value to the corresponding each node, a second assignment unit (12) that assigns a unique number associated with a set of pointers to each node based on the hash value of each node, and a common plan subtree extraction unit (13) that lists subtrees below a node having the same unique number to extract the common plan subtree from the plurality of plan trees.
Claims12
An extraction method executed by an extraction apparatus to optimize multiple queries and reduce a time to extract a common plan subtree that is a common part among a plurality of plan trees corresponding to the multiple queries by avoiding use of acyclic graphs, the extraction method comprising:
- calculating, based on pieces of information of nodes of a plan tree of the plurality of plan trees, a hash value for each of the nodes to assign the calculated hash value to the corresponding each of the nodes;
- assigning a unique number different from the hash value and associated with a set of pointers to each of the nodes based on the hash value of each of the nodes;
- and
- listing subtrees below a node of the nodes having a same unique number in an associative array indexed by hash value, to extract the common plan subtree from the plurality of plan trees.
An extraction apparatus configured to optimize multiple queries and reduce a time to extract a common plan subtree that is a common part among a plurality of plan trees corresponding to the multiple queries by avoiding use of acyclic graphs, the extraction apparatus comprising:
- first assignment circuitry configured to calculate, based on pieces of information of nodes of a plan tree of the plurality of plan trees, a hash value for each of the nodes to assign the calculated hash value to the corresponding each of the nodes;
- second assignment circuitry configured to assign a unique number different from the hash value and associated with a set of pointers to each of the nodes based on the hash value of each of the nodes;
- and
- extraction circuitry configured to list subtrees below a node of the nodes having a same unique number in an associative array indexed by hash value, to extract the common plan subtree from the plurality of plan trees.
A non-transitory computer readable medium storing a program configured to cause a computer to perform a method to optimize multiple queries and reduce a time to extract a common plan subtree that is a common part among a plurality of plan trees corresponding to the multiple queries by avoiding use of acyclic graphs, comprising:
- calculating, for a plurality of plan trees, based on pieces of information of nodes of a plan tree of the plurality of plan trees, a hash value for each of the nodes to assign the calculated hash value to the corresponding each of the nodes;
- assigning a unique number different from the hash value and associated with a set of pointers to each of the nodes based on the hash value of each of the nodes;
- and
- listing subtrees below a node of the nodes having a same unique number in an associative array indexed by hash value, to extract a common plan subtree from the plurality of plan trees, the common plan subtree being a common part among the plurality of plan trees.
Dependencies are inferred from the claim text.