# US 10,482,085 B2 · Methods and systems for estimating the number of points in two-dimensional data > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,482,085 B2 - Document ID: US10482085B2 - Status: Granted - Kind: B2 - Application number: 14/975,086 - Filed: 2015-12-18 - Published: 2017-06-22 - Granted: 2019-11-19 - Earliest claimed: 2015-12-18 - Assignees: Sap SE - Applicants: Sap SE - Inventors: Guido Moerkotte; Norman May; Alexander Boehm - Web page: https://patentgrep.com/patent/US10482085B2 ## CPC - G06F 16/24534: {Query rewriting; Transformation} - G06F 16/1744: {using compression, e.g. sparse files} - G06F 16/2246: {Trees, e.g. B+trees} - G06F 16/2453: Query optimisation - G06F 16/283: {Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method, medium, and system to generate cardinality estimates for at least one query execution plan for a query by representing a given set of multidimensional data including a plurality of data points having a value by a hierarchical tree data structure including nodes, each node representing a distribution of a subset of the points in the data set and being partitioned into tiles; calculating a bounding rectangle of the data points in each node; entering all non-empty tiles into a queue; processing of the queue can continue until a computational memory space limit is reached or until a desired estimation resolution is met; and encoding the resulting tree structure. ## Claims ### Claim 1 A computer-implemented method of optimizing execution of a query that accesses data by a computer, the method comprising: representing a given set of multidimensional data including a plurality of data points having a value by a hierarchical tree data structure including nodes, each node representing a distribution of a subset of the points in the data set and being partitioned into tiles; calculating a bounding rectangle of the data points in each node; entering all non-empty tiles into a queue; processing of the queue can continue until a computational memory space limit is reached or until a desired estimation resolution is met; encoding the resulting tree structure; determining compression scales for the hierarchical tree data structure, the compression scale including a compression factor and a decompression factor; persisting a record of the compression scales; and during the processing of the queue, compressing and decompressing the nodes using the compression scales. ### Claim 2 (depends on 1) The method of claim 1, further comprising determining a classification for each of the nodes, the determined classification being selected from a plurality of possible classifications. ### Claim 3 (depends on 2) The method of claim 2, wherein the classification is based on a size of the tiles comprising each node. ### Claim 4 (depends on 2) The method of claim 2, further comprising configuring the queue based on the classification of the tiles. ### Claim 5 (depends on 4) The method of claim 4, wherein tiles are processed based on an order thereof in the queue. ### Claim 6 (depends on 3) The method of claim 3, further comprising: storing nodes of a same classification in a same array; indexing a child node by a child base index containing an index of a first child node within the array, wherein the children of each node are stored consecutively; and indexing the children nodes other than the first child node within a sub-array of the array of the children nodes. ### Claim 7 (depends on 1) The method of claim 1, wherein the compression scales vary depending on a number of bits used to represent the range of values of the node. ### Claim 8 (depends on 1) The method of claim 1, further comprising: determining whether a query rectangle is fully contained within a bounding rectangle for all the data points; in response to the determination that the query rectangle is fully contained within the bounding rectangle, store the number of data points as an estimate for the query; and in response to the determination that the query rectangle is not fully contained within the bounding rectangle, a total frequency of all tiles that are fully contained by the query tile can be summed and a fraction of the frequency of a tile according to the area covered by the query tile is added. ### Claim 9 A non-transitory, computer-readable medium storing program instructions thereon, the medium comprising: instructions to represent a given set of multidimensional data including a plurality of data points having a value by a hierarchical tree data structure including nodes, each node representing a distribution of a subset of the points in the data set and being partitioned into tiles; instructions to calculate a bounding rectangle of the data points in each node; instructions to enter all non-empty tiles into a queue; instructions to process of the queue can continue until a computational memory space limit is reached or until a desired estimation resolution is met; and instructions to encode the resulting tree structure; instructions to determine compression scales for the hierarchical tree data structure, the compression scale including a compression factor and a decompression factor; instructions to persist a record of the compression scales; and instructions to, during the processing of the queue, compress and decompress the nodes using the compression scales. ### Claim 10 (depends on 9) The medium of claim 9, further comprising instructions to determine a classification for each of the nodes, the determined classification being selected from a plurality of possible classifications. ### Claim 11 (depends on 10) The medium of claim 10, wherein the classification is based on a size of the tiles comprising each node. ### Claim 12 (depends on 10) The medium of claim 10, further comprising instructions to configure the queue based on the classification of the tiles. ### Claim 13 (depends on 12) The medium of claim 12, wherein tiles are processed based on an order thereof in the queue. ### Claim 14 (depends on 11) The medium of claim 11, further comprising: instructions to store nodes of a same classification in a same array; instructions to index a child node by a child base index containing an index of a first child node within the array, wherein the children of each node are stored consecutively; and instructions to index the children nodes other than the first child node within a sub-array of the array of the children nodes. ### Claim 15 (depends on 9) The medium of claim 9, wherein the compression scales vary depending on a number of bits used to represent the range of values of the node. ### Claim 16 (depends on 9) The medium of claim 9, further comprising: instructions to determine whether a query rectangle is fully contained within a bounding rectangle for all the data points; instructions to, in response to the determination that the query rectangle is fully contained within the bounding rectangle, store the number of data points as an estimate for the query; and instructions to, in response to the determination that the query rectangle is not fully contained within the bounding rectangle, a total frequency of all tiles that are fully contained by the query tile can be summed and a fraction of the frequency of a tile according to the area covered by the query tile is added. ### Claim 17 A system, comprising: a memory storing processor-executable program instructions, and a processor to execute the processor-executable program instructions in order to: represent a given set of multidimensional data including a plurality of data points having a value by a hierarchical tree data structure including nodes, each node representing a distribution of a subset of the points in the data set and being partitioned into tiles; calculate a bounding rectangle of the data points in each node; enter all non-empty tiles into a queue; process of the queue can continue until a computational memory space limit is reached or until a desired estimation resolution is met; encode the resulting tree structure; determine compression scales for the hierarchical tree data structure, the compression scale including a compression factor and a decompression factor; persist a record of the compression scales; and during the processing of the queue, compress and decompress the nodes using the compression scales. ### Claim 18 (depends on 17) The system of claim 17, including execution of the processor-executable program instructions causing the processor to: determine a classification for each of the nodes, the determined classification being selected from a plurality of possible classifications, the classification is based on a size of the tiles comprising each node; store nodes of a same classification in a same array; index a child node by a child base index containing an index of a first child node within the array, the children of each node are stored consecutively; and index the children nodes other than the first child node within a sub-array of the array of the children nodes. ### Claim 19 (depends on 17) The system of claim 17, including execution of the processor-executable program instructions causing the processor to vary the compression scales depending on a number of bits used to represent the range of values of the node. ### Claim 20 (depends on 17) The system of claim 17, including execution of the processor-executable program instructions causing the processor to: determine whether a query rectangle is fully contained within a bounding rectangle for all the data points; in response to the determination that the query rectangle is fully contained within the bounding rectangle, store the number of data points as an estimate for the query; and in response to the determination that the query rectangle is not fully contained within the bounding rectangle, sum a total frequency of all tiles that are fully contained by the query tile, and add a fraction of the frequency of a tile according to the area covered by the query tile.