The characteristic of HLL is that it has excellent space complexity O(mloglogn), time complexity is O(n), and the error of the calculation result can be controlled at about 1%-2%. The error is related to the size of the data set and the ha related to the Hierarchy function.

It is an upgraded version of the LogLog algorithm, and its role is to provide imprecise deduplication counts. Its mathematical basis is the Bernoulli test.

Assuming that the coin has both heads and tails, the probability of the coin being flipped up and down is 50%. Keep flipping the coin until it comes up heads, which we record as a full trial.

Then for multiple Bernoulli trials, assume that the number of times is n. It means that there are n times of heads. Suppose the number of tosses experienced per Bernoulli trial is k. For the first Bernoulli trial, the number of times is set to k1, and so on, the nth time corresponds to kn.

Among them, for these n Bernoulli trials, there must be a maximum number of tosses k. For example, after 12 tosses, a head will appear, then this is called k_max, which represents the maximum number of tosses.

Bernoulli’s experiment can easily draw the following conclusions:

  • No number of throws for n Bernoulli processes is greater than k_max.
  • n Bernoulli processes with at least one throw equal to k_max

Finally, combined with the method of maximum likelihood estimation, it is found that there is an estimated correlation between n and k_max: n = 2^k_max. When we only record k_max, we can estimate how many pieces of data there are in total, that is, the cardinality.

  • 1st trial: 3 tosses before it turns heads, at this time k=3, n=1
  • 2nd trial: Heads appear after 2 tosses, at this time k=2, n=2
  • The 3rd trial: 6 tosses before the heads appear, at this time k=6, n=3
  • The nth trial: it took 12 tosses to get heads, at this point we estimate, n = 2^12

Take the first three groups of experiments in the above example, then k_max = 6, and finally n=3, we put it into the estimation formula, obviously: 3 ≠ 2^6 . That is to say, when the number of trials is small, the error of this estimation method is very large.

These three sets of trials, we call one round of estimation. If only one round is performed, when n is large enough, the estimated error rate will be relatively reduced, but still not small enough.

HLL is an engineering implementation based on the HyperLogLog algorithm. It is used to save the intermediate results of the HyperLogLog calculation process. It can only be used as the value column type of the table to continuously reduce the amount of data through aggregation.

To achieve the purpose of speeding up the query, based on it is an estimated result, the error is about 1%, the hll column is generated by other columns or the data in the imported data, and the hll_hash function is used when importing

To specify which column in the data is used to generate the hll column, it is often used to replace count distinct, and is used to quickly calculate uv in business by combining rollup

HLL_UNION_AGG(hll)

This function is an aggregate function that computes a cardinality estimate for all data that satisfies the condition.

This function is used to calculate the cardinality estimate for a single hll column

HLL_HASH(column_name)

Generate HLL column type for insert or import, see related instructions for import usage

  1. When using HLL to deduplicate, you need to set the target column type to HLL and the aggregate function to HLL_UNION in the table creation statement
  2. Columns of HLL type cannot be used as Key columns
  3. The user does not need to specify the length and default value, the length is controlled within the system according to the degree of data aggregation

  1. Stream load Import

    2.     -H "column_separator:," \

    The sample data is as follows（test_hll.csv）：

    The import result is as follows:

    1. # curl --location-trusted -u root: -H "label:label_test_hll_load"     -H "column_separator:,"     -H "columns:dt,id,name,province,os, pv=hll_hash(id)" -T test_hll.csv http://127.0.0.1:8030/api/demo/test_hll/_stream_load
    3. {
    4.     "TxnId": 693,
    5.     "Label": "label_test_hll_load",
    6.     "TwoPhaseCommit": "false",
    7.     "Status": "Success",
    8.     "Message": "OK",
    9.     "NumberTotalRows": 8,
    11.     "NumberFilteredRows": 0,
    12.     "NumberUnselectedRows": 0,
    13.     "LoadBytes": 320,
    14.     "LoadTimeMs": 23,
    15.     "BeginTxnTimeMs": 0,
    16.     "StreamLoadPutTimeMs": 1,
    17.     "ReadDataTimeMs": 0,
    18.     "WriteDataTimeMs": 9,
    19. }

  2. Broker Load

  1. Find the total PV
  1. mysql> select HLL_UNION_AGG(pv) from test_hll;
  3. | hll_union_agg(`pv`) |
  4. +---------------------+
  5. |                   4 |
  6. +---------------------+
  7. 1 row in set (0.00 sec)

Equivalent to:

  1. Find the PV of each day
  1. mysql> select HLL_UNION_AGG(pv) from test_hll group by dt;
  2. +---------------------+
  3. | hll_union_agg(`pv`) |
  4. +---------------------+
  5. |                   4 |
  6. |                   4 |