Epic: Cost-Based Dictionary Encoding

[Rich-T-kid]

Is your feature request related to a problem or challenge?

Aggregating over low-cardinality string columns (e.g. GROUP BY on category/status-like fields) is slower than it needs to be, because DataFusion has no way to represent these as dictionary-encoded arrays automatically. Today, getting the performance benefit requires manually casting columns yourself, there's no config to opt in, no way to bound it by cardinality, and no mechanism for the engine to decide this on its own based on the data or query shape.

Describe the solution you'd like

• Allow users to enable dictionary column reads from parquet files #24112
• Allow users to define the cardinality threshold for dictionary reads #24113
• Physical planning: cast low-medium cardinality columns to dictionary arrays before aggregation #22891
• Improve NDV statistics for Parquet columns (parquet RLE & Dictionary array focus) #24114
• Derive per-query aggregation-heaviness + NDV metadata #24116
• Add physical plan optimization to decide dictionary encoding #24117

Together these give users manual control first (enable dictionary reads, set a cardinality threshold), then build the statistics and optimizer support needed for DataFusion to make that same decision automatically. The end goal is a physical plan optimization that casts low-cardinality string columns to dictionary arrays before aggregation when the stats justify it, without requiring any manual intervention.

Currently

SELECT
  gender,
  shirt_size,
  marital_status,
  region,
  count(*) AS cnt,
  sum(amount) AS total_amount,
  avg(amount) AS avg_amount,
  min(amount) AS min_amount,
  max(amount) AS max_amount
FROM orders
GROUP BY gender, shirt_size, marital_status, region
ORDER BY gender, shirt_size, marital_status, region;

With 20 million rows, we'd repeatedly process the same string data over and over, even though Parquet metadata could tell us up front that these columns are low cardinality (gender: 2, shirt_size: 4, marital_status: 2, region: 10)

once this epic is complete we'd have something like

SET datafusion.parquet.dict_read_enable = true
SET datafusion.parquet.dict_threshold = .05

SELECT
  gender,
  shirt_size,
  marital_status,
  region,
  count(*) AS cnt,
  sum(amount) AS total_amount,
  avg(amount) AS avg_amount,
  min(amount) AS min_amount,
  max(amount) AS max_amount
FROM orders
GROUP BY gender, shirt_size, marital_status, region
ORDER BY gender, shirt_size, marital_status, region;

with dictionary arrays being supported directly in the aggregation pipeline this would be much more efficient. example

Related issues

• Specialize GroupColumn storage for Dictionary and Run-End Encoded group keys #23993
• Optimize take_n on DictionaryGroupValuesColumn<K> #24089
• GROUP BY on a Dictionary column fails at runtime when distinct group count exceeds the key type's capacity #23127
• cache dictionary arc ptr in groupColumn #23921

Additional context

#23187 (comment)
#23187 (comment)

[Rich-T-kid]

@alamb @kumarUjjawal @zhuqi-lucas @asolimando I would appreciate any thoughts you have on this

[alamb]

Together these give users manual control first (enable dictionary reads, set a cardinality threshold), then build the statistics and optimizer support needed for DataFusion to make that same decision automatically. The end goal is a physical plan optimization that casts low-cardinality string columns to dictionary arrays before aggregation when the stats justify it, without requiring any manual intervention.

I think one challenge with this approach is that casting to dictionary will likely be just as expensive as the grouping itself so I am not sure if this will actually save much work.

we could potentially do something like add some heuristic of when to read from parquet as DictionaryArrays (as reading directly into Dictionary from parquet can be fast when it is physically encoded that way)

I think the first step of any such project woudl be to make sure that DataFusion can take full advantage of dictionary arrays when the user specifies them -- then we can move on to trying to automatically chose to use them more frequently

[alamb]

Specifically, i think this one

• Allow users to enable dictionary column reads from parquet files #24112

Would be good way to let people use dictionary more

[Rich-T-kid]

I think one challenge with this approach is that casting to dictionary will likely be just as expensive as the grouping itself so I am not sure if this will actually save much work.

this is a valid point, I think focusing on parquet for now seems like a safe bet since as you mentioned its much more efficent due to RLE encoding.

Specifically, i think this one

#24112

Would be good way to let people use dictionary more

agreed. will work on plumbing this with arrow-rs