# US 2014/0156635 A1 · Optimizing an order of execution of multiple join operations > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0156635 A1 - Document ID: US20140156635A1 - Status: Published application - Kind: A1 - Application number: 14/076,598 - Filed: 2013-11-11 - Published: 2014-06-05 - Earliest claimed: 2012-12-04 - Assignees: International Business Machines Corporation - Applicants: International Business Machines Corporation - Inventors: MAREK GROCHOWSKI; ARTUR M. GRUSZECKI; TOMASZ KAZALSKI; GRZEGORZ S. MILKA; KONRAD K. SKIBSKI; TOMASZ STRADOMSKI - Web page: https://patentgrep.com/patent/US20140156635A1 ## CPC - G06F 16/24544: {Join order optimisation} - G06F 16/2453: Query optimisation - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A computer-implemented method, system, and/or computer program product optimizes an order of execution of column join operations. A first partitioning of the first data column splits the first data column into first subsets of rows. A second partitioning of the second data column splits the second data column into a second subsets of rows. A first value frequency information indicates a frequency of attribute values within a subset of rows of the first data column processed. A second value frequency information indicates a frequency of attribute values within a subset of rows of the second data column. Cardinalities of sub-tables derived by a respective joining of the subsets of rows of the first and second data columns are estimated, based on the first and second value frequency information. An order of execution of multiple join operations is then optimized based on the estimated cardinalities of the sub-tables. ## Claims ### Claim 1 A method for optimizing an order of execution of multiple join operations based on at least a first data column and a second data column in a database system having multiple processing units, the method comprising: providing, by one or more processors, at least a first partitioning of the first data column, wherein said at least the first partitioning splits the first data column into a plurality of first subsets of rows, each of the first subsets of rows being correlated with a processing unit from the multiple processing units; providing, by one or more processors, at least a second partitioning of the second data column, wherein said at least the second partitioning splits the second data column into a plurality of second subsets of rows, each of the second subsets of rows being correlated with a processing unit from the multiple processing units; providing, by one or more processors, at least a first value frequency information for each processing unit from the multiple processing units, the first value frequency information indicating a frequency of attribute values within a subset of rows of the first data column processed by a respective processing unit from the multiple processing units; providing, by one or more processors, at least a second value frequency information for each processing unit from the multiple processing units, the second value frequency information indicating a frequency of attribute values within a subset of rows of the second data column processed by the respective processing unit from the multiple processing units; estimating, by one or more processors, cardinalities of sub-tables derived by a respective joining of the subset of rows of the first data column and the subset of rows of the second data column which are processed by a same processing unit from the multiple processing units, wherein estimated cardinalities of the sub-tables are based on the first and second value frequency information of the respective processing unit from the multiple processing units; and optimizing, by one or more processors, an order of execution of multiple join operations based on the estimated cardinalities of the sub-tables. ### Claim 2 (depends on 1) The method according to claim 1, wherein a spread of estimated cardinalities of the sub-tables is evaluated for optimizing the order of execution of multiple join operations. ### Claim 3 (depends on 1) The method according to claim 1, wherein the first value frequency information is provided as a set of first value frequency information, said set of first value frequency information comprising different first value frequency information, each first value frequency information being correlated with a certain partitioning of the first data column. ### Claim 4 (depends on 3) The method according to claim 3, wherein the second value frequency information is provided as a set of second value frequency information, the set of second value frequency information comprising different second value frequency information, each second value frequency information being correlated with a certain partitioning of the second data column. ### Claim 5 (depends on 4) The method according to claim 4, wherein different first and second value frequency information is provided for multiple, frequently used partitionings. ### Claim 6 (depends on 1) The method according to claim 1, wherein further statistical information regarding a quantity of unique values of data is provided in a column-separated, partitioning-separated and processing unit-separated manner. ### Claim 7 (depends on 1) The method according to claim 1, wherein the first value frequency information and the second value frequency information are provided as a density distribution function describing a frequency of the attribute values within the subset of rows of the first or second data column processed by the respective processing units from the multiple processing units. ### Claim 8 (depends on 7) The method according to claim 7, wherein the density distribution function is provided as an integrable function. ### Claim 9 (depends on 1) The method according to claim 1, wherein the first value frequency information and the second value frequency information are derived based on feedback of previously performed queries to the first and second data columns. ### Claim 10 (depends on 1) The method according to claim 1, wherein data for generating the first value frequency information and the second value frequency information are collected by the respective processing units from the multiple processing units. ### Claim 11 (depends on 1) The method according to claim 1, further comprising: transmitting data for generating the first value frequency information and the second value frequency information to a central processing unit; and generating, by the central processing unit, the first value frequency information and the second value frequency information. ### Claim 12 (depends on 1) The method according to claim 1, further comprising: storing the first value frequency information and the second value frequency information for later reuse. ### Claim 13 (depends on 1) The method according to claim 1, wherein the cardinalities of sub-tables are estimated before starting the multiple join operations. ### Claim 14 A database system having multiple processing units for parallel processing of join-operations based on at least a first and a second data column, the database system comprising: hardware means for providing at least a first partitioning of the first data column splitting the first data column in a plurality of subsets of rows, each subset of rows being correlated with a processing unit; hardware means for providing at least a second partitioning of the second data column splitting the second data column in a plurality of subsets of rows, each subset of rows being correlated with a processing unit; a statistics hardware unit for providing at least a first value frequency information for each processing unit, the first value frequency information indicating the frequency of attribute values within the subset of rows of the first data column processed by the respective processing unit; a statistics hardware unit for providing at least a second value frequency information for each processing unit, the second value frequency information indicating the frequency of attribute values within the subset of rows of the second data column processed by the respective processing unit; hardware means for estimating the cardinalities of sub-tables derived by the respective joining of the subset of rows of the first data column and the subset of rows of the second data column which are processed by the same processing unit, wherein the estimation of cardinalities is based on the first and second value frequency information of the respective processing unit; and a hardware query optimizer adapted to optimize the order of execution of multiple join operations based on the estimated cardinalities of the sub-tables. ### Claim 15 A computer program product for optimizing an order of execution of multiple join operations based on at least a first data column and a second data column in a database system having multiple processing units, the computer program product comprising a computer readable storage medium having program code embodied therewith, the program code readable and executable by a processor to perform a method comprising: providing at least a first partitioning of the first data column, wherein said at least the first partitioning splits the first data column into a plurality of first subsets of rows, each of the first subsets of rows being correlated with a processing unit from the multiple processing units; providing at least a second partitioning of the second data column, wherein said at least the second partitioning splits the second data column into a plurality of second subsets of rows, each of the second subsets of rows being correlated with a processing unit from the multiple processing units; providing at least a first value frequency information for each processing unit from the multiple processing units, the first value frequency information indicating a frequency of attribute values within a subset of rows of the first data column processed by a respective processing unit from the multiple processing units; providing at least a second value frequency information for each processing unit from the multiple processing units, the second value frequency information indicating a frequency of attribute values within a subset of rows of the second data column processed by the respective processing unit from the multiple processing units; estimating cardinalities of sub-tables derived by a respective joining of the subset of rows of the first data column and the subset of rows of the second data column which are processed by a same processing unit from the multiple processing units, wherein estimated cardinalities of the sub-tables are based on the first and second value frequency information of the respective processing unit from the multiple processing units; and optimizing an order of execution of multiple join operations based on the estimated cardinalities of the sub-tables. ### Claim 16 (depends on 15) The computer program product according to claim 15, wherein a spread of estimated cardinalities of the sub-tables is evaluated for optimizing the order of execution of multiple join operations. ### Claim 17 (depends on 15) The computer program product according to claim 15, wherein the first value frequency information is provided as a set of first value frequency information, said set of first value frequency information comprising different first value frequency information, each first value frequency information being correlated with a certain partitioning of the first data column. ### Claim 18 (depends on 17) The computer program product according to claim 17, wherein the second value frequency information is provided as a set of second value frequency information, the set of second value frequency information comprising different second value frequency information, each second value frequency information being correlated with a certain partitioning of the second data column. ### Claim 19 (depends on 18) The computer program product according to claim 18, wherein different first and second value frequency information is provided for multiple, frequently used partitionings. ### Claim 20 (depends on 15) The computer program product according to claim 15, wherein further statistical information regarding a quantity of unique values of data is provided in a column-separated, partitioning-separated and processing unit-separated manner.