Methods for stratified sampling-based query execution
A method for stratified-sampling-based query execution includes: receiving a query; collecting a first data sample from the first dataset using a non-stratified sampling technique; performing statistical analysis on the first data sample; identifying a stratum classifier from the statistical analysis; generating a stratum classification by calculating strata boundaries for the stratum classifier; and calculating a result to the query based on analysis of the second data sample.
1. A method for stratified-sampling-based query execution comprising:
receiving and interpreting a query; wherein interpreting the query comprises identifying a first set of data shards containing data relevant to the query;
collecting a first data sample from the first set of data shards using a non-stratified sampling technique;
performing statistical analysis on the first data sample; wherein performing statistical analysis comprises calculating a first variance of the first data sample;
identifying a stratum classifier of the first data sample from the statistical analysis;
generating a stratum classification by calculating strata boundaries for the stratum classifier; wherein calculating strata boundaries comprises calculating a set of strata boundaries such that a stratified sampling variance of the first data sample using those strata boundaries is less than the first variance;
collecting a second data sample using a stratified sampling technique; wherein the stratified sampling technique is performed according to the stratum classification; and
calculating a result to the query based on analysis of the second data sample;
wherein collecting a second data sample comprises identifying a second set of data shards containing data relevant to the query and collecting the second data sample from the second set of data shards; wherein the second set of data shards contains data not contained in the first set of data shards; wherein the second set of shards are sharded by the stratum classifier; wherein identifying the second set of data shards comprises identifying the second set of data shards according to the stratified sampling technique.
2. The method of claim 1 , wherein collecting a second data sample comprises collecting data until a stratified sampling variance of a combination of the first and second data samples is lower than a threshold variance.
3. The method of claim 1 , wherein collecting a second data sample comprises collecting data until a confidence interval of the query result is below a threshold value; wherein the confidence interval depends upon a stratified sampling variance of a combination of the first and second data samples.