# Using KLL Datasketch Algorithms in Impala

You can use the stochastic streaming algorithm (KLL) that uses the percentile/quantile functions to statistically analyze the approximate distribution of comparable data from a very large stream.

Use the `ds_kll_quantiles()`

or its inverse functions the Probability Mass Function `ds_kll_PMF()`

and the Cumulative Distribution Function `ds_kll_CDF()`

to obtain the analysis. Query results
produced by this KLL algorithm are approximate but within well defined error bounds.

## Data Types and File Formats

KLL function currently supports only floats. If you sketch an int data the KLL function converts it into float.

You can sketch data from any file formats. However it is recommended to save the sketches into parquet tables. It is not recommended to save the sketches to text format.

## Using KLL Sketches

This datasketch algorithm works in two phases.

- First it creates a sketch from the dataset provided for the algorithm.
- As the second step in the process you can read the estimate from the sketch.

Using this approach you can create granular sketches for a specific dataset (e.g. one sketch per partition) and later use them to provide answers for different quantile queries without reading the actual data as they can also be merged together. Using KLL you can create sketches by Hive and read it with Impala for getting the estimate and vice versa.

**Creating a sketch**

The following example shows how to create a sketch using the `ds_kll_sketch`

function from a
column (float_col) containing the supported data type. This created sketch is a data structure
containing an approximate calculation of some facet of the data and which are compatible
regardless of which system reads or writes them.

`select ds_kll_sketch(float_col) from tableName;`

where `ds_kll_sketch()`

is an aggregate function that receives a float
parameter (e.g. a float column of a table) and returns a serialized Apache DataSketches KLL
sketch of the input data set wrapped into STRING type. Since the serialized data might contain
unsupported characters this query may error out. So another approach to this method is to insert
the derived sketch into a table or a view and later use for quantile approximations.

**Inserting the derived sketch into a table**

If you save the sketches to a table or view with the same granularity (e.g. one sketch for each partition in a table) then later you can simply read the sketch for quantile approximation.

`insert into table_name select ds_kll_sketch(float_col) from tableName;`

**Debugging the created sketch**

To troubleshoot the sketch created by the `ds_kll_sketch`

function, use `ds_kll_stringify`

on the
sketch. `ds_kll_stringify()`

receives a string that is a serialized Apache DataSketches sketch and
returns its stringified format by invoking the related function on the sketch's interface.

`select ds_kll_stringify(ds_kll_sketch(float_col)) from tableName;`

```
+-------------------------------------------+
| ds_kll_stringify(ds_kll_sketch(float_col))|
+-------------------------------------------+
| ### KLL sketch summary: |
| K : 200 |
| min K : 200 |
| M : 8 |
| N : 100 |
| Epsilon : 1.33% |
| Epsilon PMF : 1.65% |
| Empty : false |
| Estimation mode : false |
| Levels : 1 |
| Sorted : false |
| Capacity items : 200 |
| Retained items : 100 |
| Storage bytes : 432 |
| Min value : 0 |
| Max value : 9 |
| ### End sketch summary |
+-------------------------------------------+
```

**Determining the number of datasets sketched**

To determine the number of records sketched into this sketch, use `ds_kll_n`

function.

`select ds_kll_n(ds_kll_sketch(float_col)) from tableName;`

```
+------------------------------------+
| ds_kll_n(ds_kll_sketch(float_col)) |
+------------------------------------+
| 100 |
+------------------------------------+
```

## Calculate Quantile

This function `ds_kll_quantile()`

function receives two parameters, a STRING parameter that
contains a serialized KLL sketch and a DOUBLE (0.5) that represents the rank of the quantile in
the range of [0,1]. E.g. rank=0.5 means the approximate median of all the sketched data.

```
+------------------------------------------------+
| ds_kll_quantile(ds_kll_sketch(float_col), 0.5) |
+------------------------------------------------+
| 4.0 |
+------------------------------------------------+
```

This query returns a data (4.0) that is bigger than the 50% of the data.

**Calculating quantiles**

To calculate the quantiles for multiple rank parameters, use the function
`ds_kll_quantiles_as_string ()`

that is very similar to `ds_kll_quantile()`

but this function receives
any number of rank parameters and returns a comma separated string that holds the results for
all of the given ranks.

```
select ds_kll_quantiles_as_string(ds_kll_sketch(float_col), 0.5, 0.6, 1) from tableName;
```

```
+-------------------------------------------------------------------+
| ds_kll_quantiles_as_string(ds_kll_sketch(float_col), 0.5, 0.6, 1) |
+-------------------------------------------------------------------+
| 4, 5, 9 |
+-------------------------------------------------------------------+
```

## Calculate Rank

This rank function `ds_kll_rank()`

receives two parameters, a STRING that represents a serialized
DataSketches KLL sketch and a float to provide a probing value in the sketch.

```
select ds_kll_rank(ds_kll_sketch(float_col), 4) from tableName;
```

```
+------------------------------------------------+
| ds_kll_rank(ds_kll_sketch(float_col), 4) |
+------------------------------------------------+
| 0.48 |
+------------------------------------------------+
```

This query returns a DOUBLE that is the rank of the given probing value in the range of [0,1]. E.g. a return value of 0.48 means that the probing value given as parameter is greater than 48% of all the values in the sketch.

## Calculate Probability Mass Function (PMF)

This Probabilistic Mass Function (PMF) `ds_kll_pmf_as_string()`

receives a
serialized KLL sketch and one or more float values to represent ranges in the sketched values.
In the following example, the float values [1, 3, 4, 8] represent the following ranges: (-inf, 1),
[1, 3), [3, 4), [4, 8) [8, +inf)

`select ds_kll_pmf_as_string(ds_kll_sketch(float_col), 1, 3, 4, 8) from tableName`

```
+------------------------------------------------------------+
| ds_kll_pmf_as_string(ds_kll_sketch(float_col), 1, 3, 4, 8) |
+------------------------------------------------------------+
| 0.12, 0.24, 0.12, 0.36, 0.16 |
+------------------------------------------------------------+
```

This query returns a comma separated string where each value in the string is a number in the range of [0,1] and shows what percentage of the data is in the particular ranges.

## Calculate Cumulative Distribution Function (CDF)

This Cumulative Distribution Function (CDF) `ds_kll_cmf_as_string()`

receives a
serialized KLL sketch and one or more float values to represent ranges in the sketched values.
In the following example, the float values [1, 3, 4, 8] represents the following ranges: (-inf,
1), (-inf, 3), (-inf, 4), (-inf, 8), (-inf, +inf)

`select ds_kll_cdf_as_string(ds_kll_sketch(float_col), 1, 3, 4, 8) from tableName;`

```
+------------------------------------------------------------+
| ds_kll_cdf_as_string(ds_kll_sketch(float_col), 1, 3, 4, 8) |
+------------------------------------------------------------+
| 0.12, 0.36, 0.48, 0.84, 1 |
+------------------------------------------------------------+
```

This query returns a comma separated string where each value in the string is a number in the range of [0,1] and shows what percentage of the data is in the particular ranges.

## Calculate the Union

To take advantage of the UNION function, create granular sketches for a specific dataset (one sketch per partition), write these sketches to a separate table and based on the partition you are interested in, you can UNION the relevant sketches together to get an estimate.

`insert into sketch_tbl select ds_kll_sketch(float_col) from tableName;`

```
select ds_kll_quantile(ds_kll_union(sketch_col), 0.5) from sketch_tbl
where partition_col=1 OR partition_col=5;
```

This function ds_kll_union() receives a set of serialized Apache DataSketches KLL sketches
produced by `ds_kll_sketch()`

and merges them into a single sketch.