Menu
default-logo-750

GCP – Fast, approximate analytics at scale: Apache DataSketches available in BigQuery

,

In today’s data-driven world, understanding large datasets often requires numerous, complex non-additive1 aggregation operations. But as the size of the data becomes massive2, these types of operations become computationally expensive and time-consuming using traditional methods. That’s where Apache DataSketches come in. We’re excited to announce the availability of Apache DataSketches functions within BigQuery, providing powerful tools for approximate analytics at scale.

Apache DataSketches is an open-source library of sketches, specialized streaming algorithms that efficiently summarize large datasets. Sketches are small probabilistic data structures that enable accurate estimates of distinct counts, quantiles, histograms, and other statistical measures – all with minimal memory, minimal computational overhead, and with a single pass through the data. All but a few of these sketches provide mathematically proven error bounds, i.e., the maximum possible difference between a true value and its estimated or approximated value. These error bounds can be adjusted by the user as a trade-off between the size of the sketch and the size of the error bounds. The larger the configured sketch, the smaller will be the size of the error bounds. 

With sketches, you can quickly gain insights from massive datasets, especially when exact computations are impractical or impossible. The sketches themselves can be merged, making them additive and highly parallelizable, so you can combine sketches from multiple datasets for further analysis. This combination of small size and mergeability can translate into orders-of-magnitude improvement in speed of computational workload compared to traditional methods.

aside_block
<ListValue: [StructValue([(‘title’, ‘$300 in free credit to try Google Cloud data analytics’), (‘body’, <wagtail.rich_text.RichText object at 0x3e6130342520>), (‘btn_text’, ‘Start building for free’), (‘href’, ‘http://console.cloud.google.com/freetrial?redirectPath=/bigquery/’), (‘image’, None)])]>

Why DataSketches in BigQuery?

BigQuery is known for its ability to process petabytes of data, and DataSketches are a natural fit for this environment. With DataSketches functions, BigQuery lets you:

  • Perform rapid approximate queries: Get near-instantaneous results for distinct counts, quantile analysis, adaptive histograms and other non-additive aggregate calculations on massive datasets.

  • Save on resources: Reduce query costs and storage requirements by working with compact sketches instead of raw data.

  • Move between systems: DataSketches have well-defined stored binary representations that let sketches be transported between systems and interpreted by three major languages: Java, C++, and Python, all without losing any accuracy.

Apache DataSketches come to BigQuery through custom C++ implementations using the Apache DataSketches C++ core library compiled to WebAssembly (WASM) libraries, and then loaded within BigQuery Javascript user-defined aggregate functions (JS UDAFs). 

How BigQuery customers use Apache DataSketches

Yahoo started the Apache DataSketches project in 2011, open-sourced it in 2015, and still uses the Apache DataSketches library. They use approximate results in various analytic query operations such as count distinct, quantiles, and most frequent items (a.k.a. Heavy Hitters). More recently, Yahoo adapted the DataSketches library to leverage the large scale of BigQuery, using the Google-defined JavaScript User Defined Aggregate Functions (UDAF) interface to the Google Cloud and BigQuery platform.

“Yahoo has successfully used the Apache DataSketches library to analyze massive data in our internal production processing systems for more than 10 years. Data sketching has allowed us to respond to a wide range of queries summarizing data in seconds, at a fraction of the time and cost of brute-force computation. As an early innovator in developing this powerful technology, we are excited about this fast, accurate, large-scale, open-source technology becoming available to those already working in a Google Cloud BigQuery environment.” – Matthew Sajban, Director of Software Development Engineering, Yahoo

Featured sketches

So, what can you do with Apache DataSketches? Let’s take a look at the sketches integrated with BigQuery.

Cardinality sketches

  • Hyper Log Log Sketch (HLL): The DataSketches library implements this historically famous sketch algorithm with lots of versatility. It is best suited for straightforward distinct counting (or cardinality) estimation. It can be adapted to a range of sizes from roughly 50 bytes to about 2MB depending on the accuracy requirements. It also comes in three flavors: HLL_4, HLL_6, HLL_8 that enable additional tuning of speed and size.

  • Theta Sketch: This sketch specializes in set expressions and allows not only normal additive unions but also full set expressions between sketches with set-intersection and set-difference. Because of its algebraic capability, this sketch is one of the most popular sketches. It has a range of sizes from a few hundred bytes to many megabytes, depending on the accuracy requirements.

  • CPC Sketch: This cardinality sketch takes advantage of recent algorithmic research and enables smaller stored size, for the same accuracy, than the classic HLL sketch. It is targeted for situations where accuracy per stored size is the most critical metric.

  • Tuple Sketch: This extends Theta Sketch to enable the association of other values with each unique item retained by the sketch. This allows the computation of summaries of attributes like impressions or clicks as well as more complex analysis of customer engagement, etc.

Quantile sketches

  • KLL Sketch: This Sketch is designed for quantile estimation (e.g., median, percentiles), and ideal for understanding distributions, creating density and histogram plots, and partitioning large data sets. The KLL algorithm used in this sketch has been proven to have statistically optimal quantile approximation accuracy for a given size. The KLL Sketch can be used with any kind of data that is comparable, i.e., has a defined sorting order between items. The accuracy of KLL is insensitive to the input data distribution.

  • REQ Sketch: This quantile sketch is designed for situations where accuracy at the ends of the rank domain is more important than at the median. In other words, if you’re most interested in accuracy at the 99.99th percentile and not so interested in the accuracy at the 50th percentile, this is the sketch to choose. Like the KLL Sketch, this sketch has mathematically proven error bounds. The REQ sketch can be used with any kind of data that is comparable, i.e., has a defined sorting order between items. By design, the accuracy of REQ is sensitive to how close an item is to the ends of the normalized rank domain (i.e., close to rank 0.0 or rank 1.0), otherwise it is insensitive to the input distribution.

  • T-Digest Sketch: This is also a quantile sketch, but it’s based on a heuristic algorithm and doesn’t have mathematically proven error properties. It is also limited to strictly numeric data. The accuracy of the T-Digest Sketch can be sensitive to the input data distribution. However, it’s a very good heuristic sketch, fast, has a small footprint, and can provide excellent results in most situations.

Frequency sketches

  • Frequent Items Sketch: This sketch is also known as a Heavy-Hitter sketch. Given a stream of items, this sketch identifies, in a single pass, the items that occur more frequently than a noise threshold, which is user-configured by the size of the sketch. This is especially useful in real-time situations. For example, what are the most popular items from a web site that are being actively queried, over the past hour, day, or minute? Its output is effectively an ordered list of the most frequently visited items. This list changes dynamically, which means you can query the sketch, say, every hour to help you understand the query dynamics over the course of a day. In static situations, for example, it can be used to discover the largest files in your database in a single pass and with only a modest amount of memory.

How to get started

To leverage the power of DataSketches in BigQuery, you can find the new functions within the bqutil.datasketches dataset (for US multi-region location) or bqutil.datasketches_<bq_region> dataset (for any other regions and locations). For detailed information on available functions and their usage, refer to the DataSketches README. You can also find demo notebooks in our GitHub repo for the KLL Sketch, Theta Sketch, and FI Sketch. 

Example: Obtaining estimates of Min, Max, Median, 75th, 95th percentiles and total count using the KLL Quantile Sketch

Suppose you have 1 million comparable3 records in 100 different partitions or groups. You would like to understand how the records are distributed by their percentile or rank, without having to bring them all together in memory or even sort them.   

SQL:

code_block
<ListValue: [StructValue([(‘code’, ‘## Creating sample data with 1 million records split into 100 groups of nearly equal sizernrnCREATE TEMP TABLE sample_data ASrnSELECTrn CONCAT(“group_key_”, CAST(RAND() * 100 AS INT64)) AS group_key,rn RAND() AS xrnFROMrn UNNEST(GENERATE_ARRAY(1, 1000000));rnrn## Creating KLL merge sketches for a group keyrnrnCREATE TEMP TABLE agg_sample_data ASrnSELECTrn group_key,rn count(*) AS total_count,rn bqutil.datasketches.kll_sketch_float_build_k(x, 250) AS kll_sketchrnFROM sample_datarnGROUP BY group_key;rnrn## Merge group based sketches into a single sketch and then get approx quantilesrnrnWITH agg_data AS (rn SELECTrn bqutil.datasketches.kll_sketch_float_merge_k(kll_sketch, 250) rnAS merged_kll_sketch,rn SUM(total_count) AS total_countrn FROM agg_sample_datarn)rnSELECTrn bqutil.datasketches.kll_sketch_float_get_quantile(merged_kll_sketch, 0.0, true) AS mininum,rn bqutil.datasketches.kll_sketch_float_get_quantile(merged_kll_sketch, 0.5, true) AS p50,rn bqutil.datasketches.kll_sketch_float_get_quantile(merged_kll_sketch, 0.75, true) AS p75,rn bqutil.datasketches.kll_sketch_float_get_quantile(merged_kll_sketch, 0.95, true) AS p95,rn bqutil.datasketches.kll_sketch_float_get_quantile(merged_kll_sketch, 1.0, true) AS maximum,rn total_countrnFROM agg_data;’), (‘language’, ”), (‘caption’, <wagtail.rich_text.RichText object at 0x3e6130342640>)])]>

This code produces the result:

code_block
<ListValue: [StructValue([(‘code’, ‘[{rn “mininum”: “0.00018315276247449219”,rn “p50”: “0.49736559391021729”,rn “p75”: “0.74863773584365845”,rn “p95”: “0.94818627834320068”,rn “maximum”: “0.99828708171844482”,rn “total_count”: “1000000”rn}]’), (‘language’, ”), (‘caption’, <wagtail.rich_text.RichText object at 0x3e6130342190>)])]>

Example: Estimating user engagement metrics

The DataSketches Tuple Sketch is a powerful tool to analyze properties that have a natural association with unique identifiers.

For example, imagine you have a large-scale web application that records user identifiers and their clicks on various elements. You would like to analyze this massive dataset efficiently to obtain approximate metrics for clicks per unique user. The Tuple Sketch computes the number of unique users and allows you to track additional properties that are naturally associated with the unique identifiers as well.

SQL:

code_block
<ListValue: [StructValue([(‘code’, ‘## Creating sample data with 100M records (1 through 100M) split in 10 nearly equal sized groups of 10M values eachrnrnrnCREATE TEMP TABLE sample_data_100M ASrnSELECTrn CONCAT(“group_key_”, CAST(RAND() * 10 AS INT64)) AS group_key,rn 1000000 * x2 + x1 AS user_id, rn X2 AS clicksrnFROM UNNEST(GENERATE_ARRAY(1, 1000000)) AS x1,rn UNNEST(GENERATE_ARRAY(0, 99)) AS x2;rnrn## Creating Tuple sketches for a group key ( group key can be any dimension for example date, product, location etc ) rnrnrnCREATE TEMP TABLE agg_sample_data_100M ASrnSELECTrn group_key, count(distinct user_id) AS exact_uniq_users_ct,rn sum(clicks) AS exact_clicks_ct,rn bqutil.datasketches.tuple_sketch_int64_agg_int64(user_id, clicks) rn AS tuple_sketchrnFROM sample_data_100MrnGROUP BY group_key;rnrn## Merge group based sketches into a single sketch and then extract relevant metrics like distinct count estimate as well as the estimate of the sum of clicks and its upper and lower bounds.rnrnrnWITHrnagg_data AS (rn SELECTrn bqutil.datasketches.tuple_sketch_int64_agg_union(tuple_sketch)rn AS merged_tuple_sketch, SUM(exact_uniq_users_ct) rn AS total_uniq_users_ct, rn FROM agg_sample_data_100Mrn)rnSELECTrn total_uniq_users_ct,rn bqutil.datasketches.tuple_sketch_int64_get_estimate(merged_tuple_sketch)rn AS distinct_count_estimate,rn bqutil.datasketches.tuple_sketch_int64_get_sum_estimate_and_boundsrn (merged_tuple_sketch, 2)rn AS sum_estimate_and_boundsrnFROM agg_data;rnrnrn## The average clicks / unique user can be obtained by simple divisionrn## Note: the number of digits of precision in the estimates above are due to the fact that the returned values are floating point.’), (‘language’, ”), (‘caption’, <wagtail.rich_text.RichText object at 0x3e6130342280>)])]>

This produces the following result:

code_block
<ListValue: [StructValue([(‘code’, ‘[{rn “total_uniq_users_ct”: “100000000”,rn “distinct_count_estimate”: “102072185.62413435”,rn “sum_estimate_and_bounds”: {rn “sum_estimate”: “5046343196.596302”,rn “sum_lower_bound”: “4890486414.42718”,rn “sum_upper_bound”: “5207147098.07356”rn }rn}]’), (‘language’, ”), (‘caption’, <wagtail.rich_text.RichText object at 0x3e6130342070>)])]>

Get faster, more accurate estimations

In short, DataSketches in BigQuery unlocks a new dimension of approximate analytics, helping you gain valuable insights from massive datasets quickly and efficiently. Whether you’re tracking website traffic, analyzing user behavior, or performing any other large-scale data analysis, DataSketches are your go-to tools for fast, accurate estimations.

To start using DataSketches in BigQuery, refer to the DataSketches-BigQuery repository README for building, installing and testing the DataSketches-BigQuery library in your own environment. In each sketch folder there is a README that details the specific function specifications available for that sketch.

If you are working in a BigQuery environment, the DataSketches-BigQuery library is already available for you to use in all regional public BigQuery datasets.

1. Examples include distinct counting, quantiles, topN, K-means, density estimation, graph analysis, etc.
The results from one parallel partition cannot be simply “added” to the results of another partition – thus the term non-additive (a.k.a. non-linear operations).
2. Massive ~ typically, much larger than what can be conveniently kept in random-access memory.
3. Any two items can be compared to establish their order, i.e. if A < B, then A precedes B.

Read More for the details.

Related Posts