Patent Document ID: 8972378
Application ID: 13656760
Patent Status: 1

Claim One:
1. A method for formulating global statistics for a column of a database table by a computer system, the computer system including one or more processors and system memory, the computer system connected to a plurality of compute nodes configured in a shared-nothing architecture, a database table distributed across the plurality of compute nodes, a data partitioning algorithm defining how portions of the database table are to be partitioned across the plurality of compute nodes, each compute node in the plurality of compute nodes maintaining one or more portions of the database table in a local database instance in accordance with the data partitioning algorithm, the method comprising: accessing a histogram from each of the plurality of compute nodes, each histogram containing statistics for a portion of the column maintained at the compute node in accordance with the data partitioning algorithm, for each accessed histogram: each step in the histogram defined by step boundaries including a non-inclusive lower boundary value and an inclusive upper boundary value, data for each step in the histogram estimating: a number of occurrences of the upper boundary value and an average number of rows per distinct value within the step boundaries; merging the histograms accessed from each of the plurality of compute nodes into a global histogram for the column, the global histogram including global steps defined by step boundaries including a non-inclusive lower boundary value and an inclusive upper boundary value, data for each global step estimating: a number of occurrences of the upper boundary value and a global average number of rows per distinct value within the step boundaries, including for each global step: calculating number of occurrences of the upper boundary value by adding the number of occurrences of upper boundary values across the histograms; and using knowledge of the data partitioning algorithm when calculating the global average number of rows per distinct value for the global step including: determining a mean compute node observed frequency of distinct values within the step boundaries; calculating the probability that a particular distinct value appears at a particular node based on the data partitioning algorithm; and determining a global average row frequency for the global step based on the calculated mean compute node observed frequency and the calculated probability; and storing the global histogram for use in query optimization.