NVIDIA / NVIDIA/cudf

[FEA] Implement batch processing versions for column/table operations to address wide schema performance bottleneck

Open
#21,253 1 comment 0 reactions 1 assignee Claimed by @ttnghia View on GitHub
feature request libcudf Performance Spark
Dominant language
C++
Stars
9.8k
Forks
1.1k
Avg merge
3d 6m
Merged PRs (30d)
278

Description

## Summary

We want to implement batch processing versions of several cudf APIs that currently process columns sequentially. Even the input are tables, these APIs only process individual columns of the input tables one after another. When operating on tables with many columns (100-1000+), per-column processing style becomes a significant bottleneck. Batch versions would process multiple columns in a single kernel launch with a single time data copy between host and device, dramatically reducing overhead for wide schema workloads. If a single kernel call and data copy is not possible, a few times of such operations are also acceptable instead of hundreds to thousands as in the current APIs.

## Motivation

### The Wide Schema Problem

Wide schemas (tables with hundreds to thousands of columns) are increasingly common in the industry. For example:
- **Feature stores for ML**: 100-1000+ features per entity (user profiles, product attributes, embeddings)
- **IoT/sensor data**: Thousands of sensor readings per device per timestamp
- **Financial analytics**: Many metrics per transaction or account (risk scores, derived features)
- **Log analytics**: Parsed fields from semi-structured data (JSON flattening, event properties)

### Current Per-Column Processing Performance Issue

Most cudf operations process columns independently through separate kernel launches and data movement process. While the overhead per kernel launch is small (~5-10 microseconds), it accumulates significantly:

- **1000 columns x 5us = 5ms overhead** per table operation, just from kernel launches
- Operations like `gather()`, `scatter()`, `copy_if_else()`, and binary operations all exhibit `O(N_columns)` kernel launches

In order to launch a kernel, most APIs also need to transfer some amount of data from host to device memory before the kernel launch, then transfer back some results from device to host after kernel finished and synchronize CUDA stream to make the transferred data available before the functions can continue any other operation. This memcpy-kernel-memcpy-sync pattern repeats hundreds of time in wide schema situations, causing severe throttle issue in the computation pipeline.

### Proven Success with Batch Processing

We have already demonstrated significant improvements with batch processing in cudf:

| Optimization | Improvement |
|-------------|-------------|
| Batch strings construction ([PR #17035](https://github.com/rapidsai/cudf/pull/17035)) | 30% runtime reduction |
| Batch null counts ([PR #20872](https://github.com/rapidsai/cudf/pull/20872)) | 27-49% for groupby with many aggregations |
| [WIP] Batch table concatenation | 50% (fixed width and structs), 30% (lists) |

These results validate that batch processing is an effective approach for wide schema optimization.

---

## APIs Requested for Batch Processing

Some of the most expensive APIs called in Spark-Rapids that need to have batch processing support are listed as below.

### `batch_concatenate`

**Example Use cases in Spark-Rapids**:
- Shuffle coalescing
- Batch merging after parallel operations
- Combining partitioned results
- Stream concatenation in data ingestion pipelines

### `batch_gather`

**Example Use cases in Spark-Rapids**:
- Join result materialization
- Sort result gathering
- Row filtering and sampling
- Conditional expression evaluation

### `batch_scatter`

**Example of Use cases in Spark-Rapids**:
- Shuffle partitioning
- Distributed join preparation
- Data redistribution for parallel processing

### `batch_copy_if_else`

**Example of Use cases in Spark-Rapids**:
- SQL IF expressions
- CASE WHEN expressions
- Null value replacement
- Conditional data transformation

### `batch_binary_operation`

**Example of Use cases in Spark-Rapids**:
- Arithmetic expressions in projections
- Filter predicate evaluation (comparisons)
- Aggregation computations
- Hash partition assignment

---

## Implementation Considerations

1. **Type homogeneity**: Batch APIs work best when columns share the same data type. The API could either:
- Require all columns to have the same type (simpler, more efficient), or
- Group columns by types internally to reduce thread divergence.

2. **Fixed-width vs. variable-width**: Initial implementation could focus on fixed-width types (int, float, etc.) where batching is straightforward. Variable-width types (strings, lists) may require more complex handling.

3. **Memory layout**: Consider whether to use structure-of-arrays (current cudf layout) or array-of-structures for the batch kernel, depending on access patterns.

4. **Fallback behavior**: When batch processing isn't beneficial (few columns), the batch processing APIs could fall back to sequential processing using the existing APIs.

5. Generalization: The fused kernels typically address some specific workflows but we should also look into a way to implement them such that they can be easily extended to use for other related situations as well.

## Additional Context

This request is part of a broader effort to optimize cudf for wide schema workloads in the Spark-Rapids ecosystem. Wide schemas are becoming increasingly common in modern data analytics, and these optimizations would benefit any cudf user working with tables that have many columns.

---

## Related Work

- [PR #17035](https://github.com/rapidsai/cudf/pull/17035): Batch strings column construction
- [PR #20872](https://github.com/rapidsai/cudf/pull/20872): Batch null count

---

## Related Issues

Some of previous issues can be fixed by the batch processing approach proposed in this work:
- https://github.com/rapidsai/cudf/issues/21115
- https://github.com/rapidsai/cudf/issues/21155
- https://github.com/rapidsai/cudf/issues/13509
- https://github.com/rapidsai/cudf/issues/19625
- https://github.com/rapidsai/cudf/issues/11923

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.