Function OptimalNumOfBits

cpp/src/parquet/bloom_filter.h:245–273

Calculate optimal size according to the number of distinct values and false positive probability. @param ndv The number of distinct values. @param fpp The false positive probability. @return it always return a value between kMinimumBloomFilterBytes * 8 and kMaximumBloomFilterBytes * 8, and the return value is always a power of 16

  /// @return it always return a value between kMinimumBloomFilterBytes * 8 and
  /// kMaximumBloomFilterBytes * 8, and the return value is always a power of 16
  static uint32_t OptimalNumOfBits(uint32_t ndv, double fpp) {
    ARROW_DCHECK(fpp > 0.0 && fpp < 1.0);
    const double m = -8.0 * ndv / log(1 - pow(fpp, 1.0 / 8));
    uint32_t num_bits;

    // Handle overflow.
    if (m < 0 || m > kMaximumBloomFilterBytes << 3) {
      num_bits = static_cast<uint32_t>(kMaximumBloomFilterBytes << 3);
    } else {
      num_bits = static_cast<uint32_t>(m);
    }

    // Round up to lower bound
    if (num_bits < kMinimumBloomFilterBytes << 3) {
      num_bits = kMinimumBloomFilterBytes << 3;
    }

    // Get next power of 2 if bits is not power of 2.
    if ((num_bits & (num_bits - 1)) != 0) {
      num_bits = static_cast<uint32_t>(::arrow::bit_util::NextPower2(num_bits));
    }

    // Round down to upper bound
    if (num_bits > kMaximumBloomFilterBytes << 3) {
      num_bits = kMaximumBloomFilterBytes << 3;
    }

    return num_bits;
  }

  bool FindHash(uint64_t hash) const override;
  void InsertHash(uint64_t hash) override;