Exact Count Bitmap

Exact Count Bitmap (정확 카운트 비트맵)

druid-exact-count-bitmap 확장은 Roaring Bitmap을 사용해 LONG 타입 열의 정확한 카디널리티(count)를 계산하는 기능을 제공해요. HyperLogLog 같은 근사 카디널리티 집계기와 달리, 이 집계기는 정확한 고유값 개수를 돌려줘요.

출처: 문서

본문

이 확장은 Roaring Bitmap을 사용해 LONG 타입 열에 대한 정확한 카디널리티 계산 기능을 제공해요. HyperLogLog와 같은 근사 카디널리티 집계기와 달리, 이 집계기는 정확한 distinct count를 제공해요.

Installation

이 Apache Druid 확장을 사용하려면 extensions load list에 druid-exact-count-bitmap을 포함해 주세요.

druid-exact-count-bitmap

Comparison with Similar Aggregations

Distinct Count 집계기는 Exact Count 집계기와 비슷하게 동작해요. 그래서 이 두 집계기의 동작 차이를 이해하는 것이 중요해요.

Exact Count	Distinct Count
전제 조건이 필요 없어요 (예: hash partition, segment granularity 설정).	집계를 수행하려면 전제 조건이 필요해요.
64비트 숫자 열(BIGINT)에서만 동작해요.	dimension 열에서 동작해요 (String, Complex Type 등 포함).

How it Works

이 확장은 내부 데이터 구조로 Roaring64NavigableMap을 사용해서 64비트 정수의 정확한 카디널리티를 효율적으로 저장하고 계산해요. 서로 다른 목적을 가진 두 타입의 집계기를 제공해요.

Build Aggregator (Bitmap64ExactCountBuild)

BUILD 집계기는 원시 LONG 값에서 직접 카디널리티를 계산하고 싶을 때 사용해요.

• 수집(ingestion) 시점이나 원시 데이터를 질의할 때 사용해요.
• LONG 타입 열에만 사용해야 해요.

예시:

{
  "type": "Bitmap64ExactCountBuild",
  "name": "unique_values",
  "fieldName": "id"
}

Merge Aggregator (Bitmap64ExactCountMerge)

MERGE 집계기는 미리 계산된(pre-computed) 비트맵을 다룰 때 사용해요.

• 미리 집계된 데이터(BUILD로 이전에 집계된 열)를 질의할 때 사용돼요.
• 비트 연산(bitwise operations)으로 여러 비트맵을 결합해요.
• BUILD로 집계된 열이나 이전 MERGE로 집계된 열에 사용해야 해요.

Bitmap64ExactCountMerge 집계기는 timeseries 타입 질의에 사용하길 권장해요. topN과 groupBy 질의에서도 동작하긴 해요.

예시:

{
  "type": "Bitmap64ExactCountMerge",
  "name": "total_unique_values",
  "fieldName": "unique_values" // Must be a pre-computed bitmap
}

Typical Workflow

수집 시점에 BUILD로 초기 비트맵을 만들어요.

{
  "type": "index",
  "spec": {
    "dataSchema": {
      "metricsSpec": [
        {
          "type": "Bitmap64ExactCountBuild",
          "name": "unique_users",
          "fieldName": "user_id"
        }
      ]
    }
  }
}

집계된 데이터를 질의할 때는 MERGE로 비트맵을 결합해요.

{
  "queryType": "timeseries",
  "aggregations": [
    {
      "type": "Bitmap64ExactCountMerge",
      "name": "total_unique_users",
      "fieldName": "unique_users"
    }
  ]
}

Usage

SQL Query

SQL 질의에서 BITMAP64_EXACT_COUNT 함수를 사용할 수 있어요.

SELECT BITMAP64_EXACT_COUNT(column_name)
FROM datasource
WHERE ...
GROUP BY ...

Post-Aggregator

추가 처리를 위해 post-aggregator도 사용할 수 있어요.

{
  "type": "bitmap64ExactCount",
  "name": "<output_name>",
  "fieldName": "<aggregator_name>"
}

Considerations

• 메모리 사용량: Roaring Bitmap은 효율적이지만, 정확한 고유값을 저장하는 것은 일반적으로 HyperLogLog 같은 근사 알고리즘보다 더 많은 메모리를 소비해요.
• 입력 타입: 이 집계기는 LONG(64비트 정수) 열에서만 동작해요. String이나 다른 데이터 타입은 사용 전에 long으로 변환해야 해요.
• Build vs Merge: 원시 숫자 데이터에는 항상 BUILD, 미리 집계된 데이터에는 MERGE를 사용해요. 미리 집계된 데이터에 BUILD를, 원시 데이터에 MERGE를 사용하면 올바르게 동작하지 않아요.

Example Use Cases

User Analytics: 시간 경과에 따른 고유 사용자 수

-- First ingest with BUILD aggregator
-- Then query with:
SELECT
  TIME_FLOOR(__time, 'PT1H') AS hour,
  BITMAP64_EXACT_COUNT(unique_users) as distinct_users
FROM user_metrics
GROUP BY 1

High-Precision Metrics: 정확한 count가 필요할 때

{
  "type": "groupBy",
  "dimensions": [
    "country"
  ],
  "aggregations": [
    {
      "type": "Bitmap64ExactCountMerge",
      "name": "exact_user_count",
      "fieldName": "unique_users"
    }
  ]
}

Walkthrough Using Wikipedia datasource

Batch Ingestion Task Spec

{
  "type": "index",
  "spec": {
    "dataSchema": {
      "dataSource": "wikipedia_metrics",
      "timestampSpec": {
        "column": "__time",
        "format": "auto"
      },
      "dimensionsSpec": {
        "dimensions": [
          "channel",
          "namespace",
          "page",
          "user",
          "cityName",
          "countryName",
          "regionName",
          "isRobot",
          "isUnpatrolled",
          "isNew",
          "isAnonymous"
        ]
      },
      "metricsSpec": [
        {
          "type": "Bitmap64ExactCountBuild",
          "name": "unique_added_values",
          "fieldName": "added"
        },
        {
          "type": "Bitmap64ExactCountBuild",
          "name": "unique_delta_values",
          "fieldName": "delta"
        },
        {
          "type": "Bitmap64ExactCountBuild",
          "name": "unique_comment_lengths",
          "fieldName": "commentLength"
        },
        {
          "name": "count",
          "type": "count"
        },
        {
          "name": "sum_added",
          "type": "longSum",
          "fieldName": "added"
        },
        {
          "name": "sum_delta",
          "type": "longSum",
          "fieldName": "delta"
        }
      ],
      "granularitySpec": {
        "type": "uniform",
        "segmentGranularity": "DAY",
        "queryGranularity": "HOUR",
        "rollup": true,
        "intervals": [
          "2016-06-27/2016-06-28"
        ]
      }
    },
    "ioConfig": {
      "type": "index",
      "inputSource": {
        "type": "druid",
        "dataSource": "wikipedia",
        "interval": "2016-06-27/2016-06-28"
      },
      "inputFormat": {
        "type": "tsv",
        "findColumnsFromHeader": true
      }
    },
    "tuningConfig": {
      "type": "index",
      "maxRowsPerSegment": 5000000,
      "maxRowsInMemory": 25000
    }
  }
}

원시 bytes가 있는 datasource 질의

{
  "queryType": "timeseries",
  "dataSource": {
    "type": "table",
    "name": "wikipedia_metrics"
  },
  "intervals": {
    "type": "intervals",
    "intervals": [
      "-146136543-09-08T08:23:32.096Z/146140482-04-24T15:36:27.903Z"
    ]
  },
  "granularity": {
    "type": "all"
  },
  "aggregations": [
    {
      "type": "Bitmap64ExactCountBuild",
      "name": "a0",
      "fieldName": "unique_added_values"
    }
  ]
}

미리 집계된 비트맵이 있는 datasource 질의

{
  "queryType": "timeseries",
  "dataSource": {
    "type": "table",
    "name": "wikipedia_metrics"
  },
  "intervals": {
    "type": "intervals",
    "intervals": [
      "-146136543-09-08T08:23:32.096Z/146140482-04-24T15:36:27.903Z"
    ]
  },
  "granularity": {
    "type": "all"
  },
  "aggregations": [
    {
      "type": "Bitmap64ExactCountMerge",
      "name": "a0",
      "fieldName": "unique_added_values"
    }
  ]
}

Other Examples

Kafka ingestion task spec

{
  "type": "kafka",
  "spec": {
    "dataSchema": {
      "dataSource": "ticker_event_bitmap64_exact_count_rollup",
      "timestampSpec": {
        "column": "timestamp",
        "format": "millis",
        "missingValue": null
      },
      "dimensionsSpec": {
        "dimensions": [
          {
            "type": "string",
            "name": "key"
          }
        ],
        "dimensionExclusions": []
      },
      "metricsSpec": [
        {
          "type": "Bitmap64ExactCountBuild",
          "name": "count",
          "fieldName": "value"
        }
      ],
      "granularitySpec": {
        "type": "uniform",
        "segmentGranularity": "HOUR",
        "queryGranularity": "HOUR",
        "rollup": true,
        "intervals": null
      },
      "transformSpec": {
        "filter": null,
        "transforms": []
      }
    },
    "ioConfig": {
      "topic": "ticker_event",
      "inputFormat": {
        "type": "json",
        "flattenSpec": {
          "useFieldDiscovery": true,
          "fields": []
        },
        "featureSpec": {}
      },
      "replicas": 1,
      "taskCount": 1,
      "taskDuration": "PT3600S",
      "consumerProperties": {
        "bootstrap.servers": "localhost:9092"
      },
      "pollTimeout": 100,
      "startDelay": "PT5S",
      "period": "PT30S",
      "useEarliestOffset": false,
      "completionTimeout": "PT1800S",
      "lateMessageRejectionPeriod": null,
      "earlyMessageRejectionPeriod": null,
      "lateMessageRejectionStartDateTime": null,
      "stream": "ticker_event",
      "useEarliestSequenceNumber": false,
      "type": "kafka"
    }
  }
}

Post-aggregator 질의

{
  "queryType": "timeseries",
  "dataSource": {
    "type": "table",
    "name": "ticker_event_bitmap64_exact_count_rollup"
  },
  "intervals": {
    "type": "intervals",
    "intervals": [
      "2020-09-13T06:35:35.000Z/146140482-04-24T15:36:27.903Z"
    ]
  },
  "descending": false,
  "virtualColumns": [],
  "filter": null,
  "granularity": {
    "type": "all"
  },
  "aggregations": [
    {
      "type": "count",
      "name": "cnt"
    },
    {
      "type": "Bitmap64ExactCountMerge",
      "name": "a0",
      "fieldName": "count"
    }
  ],
  "postAggregations": [
    {
      "type": "arithmetic",
      "fn": "/",
      "fields": [
        {
          "type": "bitmap64ExactCount",
          "name": "a0",
          "fieldName": "a0"
        },
        {
          "type": "fieldAccess",
          "name": "cnt",
          "fieldName": "cnt"
        }
      ],
      "name": "rollup_rate"
    }
  ],
  "limit": 2147483647
}

더 알아보기 (Learn more)

• 동작이 비슷하지만 전제 조건이 다른 DistinctCount 집계기와 비교해 보세요.
• Aggregations와 Post Aggregations 문서를 참고해 보세요.