Probabilistic Data Structures and Algorithms in PipelineDB
By Sangli.
PipelineDB uses five aggregate data types when it comes to physical storage. These data types play an important role in processing continuous data. In this article, we will take a look at what these data types are-along with their structures and algorithms-and then we will go through how PipelineDB uses each one of these data types.
Of course, you can learn more about the PipelineDB’s data types, data structures, and algorithms by checking out the official documentation. The relevant page for it is this one. Here, we’re going to try to keep things a bit more simple.
So first, let’s quickly go over the five data types.
- Bloom Filter: a space-optimized data structure designed to estimate set cardinalities and determine whether these set cardinalities contain a particular kind of element.
- Count-Min (CM) Sketch: a data structure that, similar to Bloom Filter, estimates the frequency of each element that has been added.
- Filtered-Space Saving (FSS) Top-K: a data structure and algorithm set that is useful for accurately estimating the top-k most frequent values appearing in a stream when using a constant, minimal memory footprint.
- HyperLogLog (HLL): a data structure and algorithm set that, similarly to Bloom filters, estimates the cardinality of sets with a very high degree of accuracy.
- T-Digest: a data structure that supports very accurate estimations of rank-based statistics such as percentiles and medians while only using a constant amount of space.
Later in this article, we will go over how PipelineDB uses these data types in the sections that follow this one.
Of course, for all of these, you can learn more from reading the official documentation, specifically these particular places: PipelineDB-specific Types and PipelineDB-specific Functions.
You can also find the corresponding data types and functions on these websites. These data types can be used in common tables if you do not want to use them in Continuous Views (CVs), as we will do in this article.
The specific code is implemented in src/backend/utils/adt/. Okay, now with all of that out of the way, let's look at how PipelineDB uses all of the above data types.
Bloom Filter
So let’s start with Bloom Filter. In PipelineDB, Bloom Filter is implemented in src/backend/pipeline/bloom.c. Consider the following:
The Bloom Filter data type is used very frequently and is a built-in data type of PipelineDB. We can use Bloom to store data in Continuous Views (CVs).
To illustrate this point, consider the following example. When creating a CV, you can use UDFs directly to generate the Bloom Filter-type fields.
After doing that, you’ll want to insert some test data, as shown below:
There are also many UDFs available at this page.
Count-Min Sketch
Now there’s Count-Min Sketch. In PipelineDB, a Count-Min (CM) Sketch is implemented in src/backend/pipeline/cmsketch.c.
As discussed before, a CM Sketch estimates the frequency of an element in a large stream, which is similar to a Bloom filter. However, a Bloom filter records whether the element exists or not. An error exists when you use the cm sketch.
Now consider the following example:
To this, let’s insert some test data, as shown below:
To learn more about this, you can check out its description in the PipelineDB’s official documentation.
Filtered-Space Saving (FSS) Top-K
In PipelineDB, Filtered-Space Saving (FSS) Top-K is implemented in src/backend/pipeline/fss.c.
FSS Top-K is used to find the top-k elements in data streams. Our implementation that we show here is based on this paper.
In an actual environment, for example, where there may be computing top-10 elements in the last 5 minutes, FSS Top-K can efficiently save time and memory space. The following shows, more particularly, how FSS Top-K is used in PipelineDB:
Now, into this, insert some test data, as shown below:
Now, insert six data records, and query v_fss, as done below:
After this, five records are found when fss_topk is used. In each record, the value is 1. The inserted value 6 is missing. However, the output of fss_topk_values contains all the values, and this output is the number of each element.
Now, insert a record again, as shown below:
Two records contain the value 5. Now, insert the value 6.
The value 6 appears and takes the place of 4.
If you’d like to learn more, check out the description provided in PipelineDB’s official documentation.
HyperLogLog
In PipelineDB, HyperLogLog (HLL) is implemented in src/backend/pipeline/hll.c.
In most practical applications, HyperLogLog (HLL) is used to solve the count (distinct) problem, but in PipelineDB, it is also used to store the count (distinct) data.
Consider this example:
The physical storage format of the count (distinct) field corresponding to the created v_hll is HLL. In the query process, the parser parses this field into the following function:
hll_count_distinct_finalThe following shows the execution plan:
Here’s an example:
Regardless of the number of insert operations, the result is count (distinct).
In PipelineDB versions earlier than 0.9.7, this has a rather mediocre efficiency with scan operations sometimes negatively affect performance. In PipelineDB 0.9.7, however, this function has been improved significantly, mitigating these issues. To learn more about the releases and versions of PipelineDB, check out this page. This issue is also discussed at detail in this article, too.
T-Digest
Last, there’s T-Digest. In PipelineDB, T-Digest is implemented in src/backend/pipeline/tdigest.c.
As discussed above, T-Digest is mainly used for estimation and calculation based on percentiles and medians. It is similar to the built-in function percentile_cont in the database. This function is seldom used.
The following briefly introduces how to use T-Digest in PipelineDB.
First, consider the following example:
Now, in it, insert data as follows:
For it, the median of 0.5 is 2, and the median of 0.6 is 2.3.
If you’re interested in learning more about T-Digest, I recommend that you check out its official description in the PipelineDB documentation. In it, you’ll learn how to use probabilistic data structures and algorithms.
