Function EncodeNdv

be/src/exec/incr-stats-util.cc:62–99

To save space when sending NDV estimates around the cluster, we compress them using RLE, since they are often sparse. The resulting string has the form CVCVCVCV where C is the count, i.e. the number of times the subsequent V (value) should be repeated in the output string. C is between 0 and 255 inclusive, the count it represents is one more than the absolute value of C (since we never have a 0 co

// shorter than the input. Otherwise it is set to false, and the input is returned
// unencoded.
string EncodeNdv(const string& ndv, bool* is_encoded) {
  DCHECK_EQ(ndv.size(), AggregateFunctions::DEFAULT_HLL_LEN);
  string encoded_ndv(AggregateFunctions::DEFAULT_HLL_LEN, 0);
  int idx = 0;
  char last = ndv[0];

  // Keep a count of how many times a value appears in succession. We encode this count as
  // a byte 0-255, but the actual count is always one more than the encoded value
  // (i.e. in the range 1-256 inclusive).
  uint8_t count = 0;
  for (int i = 1; i < AggregateFunctions::DEFAULT_HLL_LEN; ++i) {
    if (ndv[i] != last || count == numeric_limits<uint8_t>::max()) {
      if (idx + 2 > AggregateFunctions::DEFAULT_HLL_LEN) break;
      // Write a (count, value) pair to two successive bytes
      encoded_ndv[idx++] = count;
      count = 0;
      encoded_ndv[idx++] = last;
      last = ndv[i];
    } else {
      ++count;
    }
  }

  // +2 for the remaining two bytes written below
  if (idx + 2 > AggregateFunctions::DEFAULT_HLL_LEN) {
    *is_encoded = false;
    return ndv;
  }

  encoded_ndv[idx++] = count;
  encoded_ndv[idx++] = last;

  *is_encoded = true;
  encoded_ndv.resize(idx);
  DCHECK_GT(encoded_ndv.size(), 0);
  DCHECK_LE(encoded_ndv.size(), AggregateFunctions::DEFAULT_HLL_LEN);
  return encoded_ndv;
}

string DecodeNdv(const string& ndv, bool is_encoded) {
  if (!is_encoded) return ndv;