iT邦幫忙

2025 iThome 鐵人賽

DAY 27
0
Rust

DataFusion 闖關攻略:30 天學習 Rust 查詢引擎之旅系列 第 28

Day 28: StringView 深入解析 - Apache Arrow 字串處理的革命性改進

  • 分享至 

  • xImage
  •  

前言

回顧 Day 2 的內容可以知道 DataFusion 建構在 Apache Arrow 之上。而 Arrow 後續推出新的數據類型 StringView (Utf8View) 在字串處理上更優化了記憶體利用效率,當然也直接影響了 DataFusion 的效能。

在數據分析場景中,子字串提取時,需要大量的記憶體複製。因此 Arrow 社群推出了 StringView 類型,透過內聯短字串零拷貝視圖引用的設計,改變了字串處理的效率。在 ClickBench 等基準測試中,性能提升可達 2-3 倍。而 DataFusion 也從 49.0.0 版本開始將 StringView 設為預設的字串類型。

今天我們將深入理解 StringView 的設計哲學、實現細節,以及 DataFusion 如何整合並善用這個強大的 Arrow 特性。

傳統字串類型的瓶頸

Utf8 和 LargeUtf8 的限制

在 Apache Arrow 中,傳統的字串類型是 Utf8LargeUtf8。它們使用經典的「偏移量數組 + 連續數據緩衝區」設計:

Utf8Array 結構:
┌──────────────────────────────────────┐
│  Offsets Buffer (i32)                │
│  [0, 5, 11, 17, ...]                 │
└──────────────────────────────────────┘
          ↓
┌──────────────────────────────────────┐
│  Data Buffer (連續的 UTF-8 字節)      │
│  "Hello""World""Apache"...           │
└──────────────────────────────────────┘

原理介紹:

  • 每個字串由一對偏移量定義: [offset_i, offset_i+1)
  • 字串資料存儲在連續的緩衝區中
  • 要訪問第 i 個字串,需要讀取 data[offsets[i]..offsets[i+1]]

效能問題

這種設計在以下場景中會產生嚴重的效能開銷:

1. 字串切片(Slicing)

-- 提取每個字串的前 10 個字元
SELECT SUBSTRING(long_text, 1, 10) FROM logs;

傳統 Utf8 的處理流程:

原始數據:
"This is a very long text that we want to slice"
 |                                              |
 0                                              47

切片操作 (取前 10 個字元):
"This is a " 
 └─> 需要複製這 10 個字節到新的緩衝區

對於 1 百萬行:
- 需要分配新的記憶體空間
- 複製 1 百萬個子字串
- 產生大量記憶體碎片

2. JOIN 操作中的字串比較

在 JOIN 時,如果連接鍵是字串,需要頻繁比較字串值:

傳統方式:
- 逐字節比較整個字串
- 對於長字串,比較開銷很大

例如: "user_12345_transaction_20231201" vs "user_12345_transaction_20231202"
     需要比較到第 25 個字元才知道不相等

3. 聚合操作中的記憶體累積

-- 按 URL 分組統計
SELECT url, COUNT(*) 
FROM access_logs 
GROUP BY url;

在 Hash Aggregation 中,需要將 URL 字串複製到 Hash Table 的鍵中,造成大量記憶體消耗。

StringView 的設計原理

StringView(在 Arrow 中稱為 Utf8View)是為了解決上述問題而設計的。它的核心思想是:

對於短字串,直接內聯存儲;對於長字串,使用「視圖」來引用原始數據,避免複製。

12-byte 記憶體布局

每個 StringView 固定佔用 128 bits (16 bytes) 的空間,布局如下:

StringView 布局 (128 bits):
┌────────────────────────────────────────────────────────────────┐
│                    Bytes 0-3 (32 bits)                         │
│                    length: u32                                 │
│                    字串的長度(字節數)                          │
├────────────────────────────────────────────────────────────────┤
│                    Bytes 4-15 (96 bits)                        │
│                                                                │
│  根據長度,有兩種不同的解釋:                                      │
│                                                                │
│  ┌────────────────────────────────────────────────────────┐  │
│  │ 情況 1: length <= 12                                    │  │
│  │ ┌───────────────────────────────────────────────────┐ │  │
│  │ │  Inline Data (12 bytes)                           │ │  │
│  │ │  直接存儲字串內容 (不使用 buffer_index 和 offset)   │ │  │
│  │ └───────────────────────────────────────────────────┘ │  │
│  └────────────────────────────────────────────────────────┘  │
│                                                                │
│  ┌────────────────────────────────────────────────────────┐  │
│  │ 情況 2: length > 12                                     │  │
│  │ ┌──────────────┬──────────────┬──────────────────────┐ │  │
│  │ │ Prefix       │ buffer_index │ offset               │ │  │
│  │ │ (4 bytes)    │ (4 bytes)    │ (4 bytes)            │ │  │
│  │ │              │              │                      │ │  │
│  │ │ 前 4 個字元   │ 引用哪個 buffer│ buffer 中的偏移量  │ │  │
│  │ └──────────────┴──────────────┴──────────────────────┘ │  │
│  └────────────────────────────────────────────────────────┘  │
└────────────────────────────────────────────────────────────────┘

內聯短字串(Inline Short Strings)

當字串長度 ≤ 12 字節時,直接將字串內容存儲在 view 結構中:

例如: "Hello"

StringView:
┌────────┬──────────────────────────────┐
│ length │        inline data           │
│   5    │ "Hello" + 7 bytes padding    │
└────────┴──────────────────────────────┘

優點:
✓ 零額外記憶體分配
✓ 無需通過指針訪問
✓ 緩存友好 (數據就在本地)

視圖引用(View Reference)

當字串長度 > 12 字節時,使用引用方式:

例如: "This is a long string that needs reference"

StringView:
┌────────┬────────┬──────────┬────────┐
│ length │ prefix │ buf_idx  │ offset │
│   44   │ "This" │    2     │  1024  │
└────────┴────────┴──────────┴────────┘
            ↓          ↓          ↓
         前4字元    引用 Buffer 2  偏移量 1024

實際數據存儲在共享的 Buffer 中:
Buffer[2]:
  [... | "This is a long string that needs reference" | ...]
         ↑
    offset=1024

關鍵設計點:

  1. Prefix (前綴):存儲前 4 個字節,用於快速比較
  2. buffer_index:指向數據存儲在哪個 buffer
  3. offset:數據在 buffer 中的起始位置

零拷貝字串切片

StringView 最強大的特性是零拷貝切片。讓我們看一個實際例子:

SELECT SUBSTRING(url, 1, 20) FROM access_logs;

傳統 Utf8 的處理方式

原始字串: "https://example.com/api/v1/users/12345"
           |                                      |
           0                                     39

SUBSTRING(url, 1, 20) 產生: "https://example.com/"

步驟:
1. 分配新的 20 字節記憶體空間
2. 複製字節 0-19 到新空間
3. 將新字串添加到結果數組

對於 1 百萬行:
- 分配 1 百萬個新字串
- 複製 20M 字節數據
- 時間: ~50ms

StringView 的處理方式

原始 StringView:
┌────────┬────────┬──────────┬────────┐
│   39   │ "http" │    0     │   100  │  (假設 offset 是 100)
└────────┴────────┴──────────┴────────┘
            ↓
  指向 Buffer[0] 的 offset=100 處,長度 39

SUBSTRING 操作後的新 StringView:
┌────────┬────────┬──────────┬────────┐
│   20   │ "http" │    0     │   100  │  ← 只改變了 length!
└────────┴────────┴──────────┴────────┘
            ↓
  指向同一個 Buffer[0] 的 offset=100 處,但只讀取前 20 字節

步驟:
1. 創建新的 StringView 結構
2. 設置 length = 20
3. 複製 buffer_index 和 offset (無需複製實際數據!)

對於 1 百萬行:
- 創建 1 百萬個 128-bit 的 view 結構
- 零數據複製
- 時間: ~5ms (快 10 倍!)

DataFusion 原始碼實作

// 從 datafusion/functions/src/strings.rs

pub fn make_and_append_view(
    views_buffer: &mut Vec<u128>,
    null_builder: &mut NullBufferBuilder,
    original_view: &u128,
    substr: &str,
    start_offset: u32,
) {
    let substr_len = substr.len();
    let sub_view = if substr_len > 12 {
        // 長字串: 創建新的 view,引用同一個 buffer
        let view = ByteView::from(*original_view);
        make_view(
            substr.as_bytes(),
            view.buffer_index,        // 複用原 buffer_index
            view.offset + start_offset, // 調整 offset
        )
    } else {
        // 短字串: 直接內聯
        make_view(substr.as_bytes(), 0, 0)
    };
    views_buffer.push(sub_view);
    null_builder.append_non_null();
}

注意:判斷閾值是 12 字節,這是內聯數據的最大長度。

效能優勢分析

1. 減少記憶體分配

場景: 處理 1M 行,每行提取 10 字元子字串

Utf8:
- 記憶體分配次數: 1,000,000 次
- 分配總量: ~10MB (數據) + 4MB (offsets)
- 分配開銷: 顯著

StringView:
- 記憶體分配次數: 0 (複用原 buffer)
- 新增 views 數組: 16MB (1M * 16 bytes)
- 分配開銷: 最小

2. 快速字串比較

StringView 存儲了前綴(前 4 個字節),可以快速進行比較:

// 偽代碼示意
fn compare_string_views(view1: &StringView, view2: &StringView) -> Ordering {
    // 第一步: 比較長度
    match view1.length.cmp(&view2.length) {
        Ordering::Equal => {},
        other => return other,
    }
    
    // 第二步: 如果長度相同,先比較 prefix (前 4 字節)
    // 這步驟非常快,因為數據就在 view 結構中
    match view1.prefix.cmp(&view2.prefix) {
        Ordering::Equal => {},
        other => return other, // 大部分情況在這裡就能得出結果!
    }
    
    // 第三步: 只有 prefix 相同時,才需要比較完整字串
    // (這種情況較少)
    full_string_compare(view1, view2)
}

優勢:

  • 長度不同: O(1) 立即返回
  • Prefix 不同: O(1) 比較 4 字節
  • 只有兩者都相同時才需要完整比較

在 Hash Join 和 Hash Aggregation 中,這能顯著減少字串比較開銷。

3. 緩存友好性

StringView 的固定大小(128 bits)使得 views 數組非常緊湊:

Views Array (StringView):
┌─────────┬─────────┬─────────┬─────────┐
│ View 0  │ View 1  │ View 2  │ View 3  │  ← 64 bytes (4個 views)
│ 16B     │ 16B     │ 16B     │ 16B     │     一個緩存行!
└─────────┴─────────┴─────────┴─────────┘

Offsets Array (Utf8):
┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
│ O0 │ O1 │ O2 │ O3 │ O4 │ O5 │ O6 │ O7 │ O8 │ O9 │O10 │O11 │
│ 4B │ 4B │ 4B │ 4B │ 4B │ 4B │ 4B │ 4B │ 4B │ 4B │ 4B │ 4B │
└────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
  ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓
  還需要跳轉到 Data Buffer 讀取實際數據 (緩存不友好)

StringView 將元數據(長度、前綴)和引用信息緊密打包,提高了緩存命中率。

在 DataFusion 中使用 StringView

預設啟用

從 DataFusion 49.0.0 開始,StringView 已成為預設的字串類型:

// 預設配置
let config = SessionConfig::new();
// map_string_types_to_utf8view = true (預設)

let ctx = SessionContext::new_with_config(config);

// 創建表時,VARCHAR/TEXT/STRING 會自動映射到 Utf8View
ctx.sql("CREATE TABLE users (name VARCHAR, email TEXT)").await?;

顯式使用 StringView

-- 使用 arrow_cast 顯式轉換為 Utf8View
CREATE TABLE logs_view AS
SELECT 
    arrow_cast(url, 'Utf8View') as url,
    arrow_cast(user_agent, 'Utf8View') as user_agent
FROM logs;

-- 查詢時轉換
SELECT arrow_cast(name, 'Utf8View') as name_view
FROM users;
// 在 Rust 代碼中配置
let config = SessionConfig::new()
    .set_str("datafusion.sql_parser.map_string_types_to_utf8view", "false");

類型轉換

StringView 和 Utf8 可以相互轉換:

-- Utf8 → Utf8View
SELECT arrow_cast(utf8_column, 'Utf8View') FROM table1;

-- Utf8View → Utf8
SELECT arrow_cast(utf8view_column, 'Utf8') FROM table2;

StringView 的限制與注意事項

1. 記憶體碎片化風險

StringView 引用原始 buffer,如果只使用少量字串,整個 buffer 仍然會被保留:

場景: 從 1GB 的日誌文件中過濾出 1MB 的數據

Utf8: 
  ✓ 只保留 1MB 數據在記憶體中
  
StringView:
  ✗ 1MB 的 StringView 仍然引用原始 1GB buffer
  ✗ 整個 1GB buffer 無法釋放
  
結果: 記憶體使用 999MB 增加!

2. Garbage Collection 機制

DataFusion 實現了 GC 機制來處理這個問題:

// 從 datafusion/physical-plan/src/coalesce/mod.rs

fn gc_string_view_batch(batch: &RecordBatch) -> RecordBatch {
    let new_columns: Vec<ArrayRef> = batch
        .columns()
        .iter()
        .map(|c| {
            let Some(s) = c.as_string_view_opt() else {
                return Arc::clone(c);
            };

            // 計算理想的 buffer 大小 (只計算長字串)
            let ideal_buffer_size: usize = s
                .views()
                .iter()
                .map(|v| {
                    let len = (*v as u32) as usize;
                    if len > 12 {  // 只有長字串需要 buffer
                        len
                    } else {
                        0
                    }
                })
                .sum();

            let actual_buffer_size = s.data_buffers()
                .iter()
                .map(|b| b.capacity())
                .sum::<usize>();

            // 如果實際 buffer 大小超過理想大小的 2 倍,觸發 GC
            if actual_buffer_size > (ideal_buffer_size * 2) {
                // 重新創建數組,只複製實際需要的數據
                // (省略具體實現)
            } else {
                Arc::clone(c)  // 不需要 GC
            }
        })
        .collect();
    
    RecordBatch::try_new(batch.schema(), new_columns).unwrap()
}

GC 策略:

  • 檢測 buffer 利用率
  • 如果實際 buffer 大小 > 理想大小 × 2,觸發 GC
  • 重新打包數據,釋放未使用的 buffer

3. 何時選擇 StringView vs Utf8

場景 推薦類型 原因
大量字串切片操作 StringView ✓ 零拷貝優勢明顯
字串 JOIN/聚合 StringView ✓ 前綴比較快速
過濾後數據量很小 Utf8 ⚠️ 避免 buffer 碎片化
字串長度都很短 (<12字節) 兩者皆可 StringView 內聯,性能相似
需要長期持有結果 Utf8 ⚠️ StringView 可能保留大 buffer
臨時查詢處理 StringView ✓ 處理速度快

4. 與外部系統的兼容性

某些系統可能不支援 StringView 類型:

// 導出給不支援 StringView 的系統時,需要轉換
let df = ctx.sql("SELECT * FROM table_with_stringview").await?;

// 轉換為 Utf8
let df = df.with_column(
    "name",
    cast(col("name"), DataType::Utf8)
)?;

實戰案例: URL 分析

讓我們通過一個實際案例來看 StringView 的優勢:

-- 分析網站訪問日誌
CREATE TABLE access_logs (
    timestamp TIMESTAMP,
    url VARCHAR,  -- 自動映射為 Utf8View (如果啟用)
    user_agent VARCHAR,
    ip_address VARCHAR
);

-- 查詢 1: 提取域名
SELECT 
    SUBSTRING(url, 1, POSITION('/' IN SUBSTRING(url, 9))) as domain,
    COUNT(*) as visit_count
FROM access_logs
GROUP BY domain;

性能對比

數據: 1000 萬行訪問日誌
平均 URL 長度: 80 字節

使用 Utf8:
  - SUBSTRING 操作: 複製 1000 萬個子字串
  - 記憶體分配: ~300MB
  - GROUP BY: 全字串比較
  - 執行時間: 8.5 秒

使用 StringView:
  - SUBSTRING 操作: 零拷貝,創建新 views
  - 記憶體分配: ~160MB (views 數組)
  - GROUP BY: 前綴快速比較
  - 執行時間: 3.2 秒

性能提升: 2.7x

優化建議

-- 如果需要長期保存結果,轉換回 Utf8 以釋放 buffer
CREATE TABLE domain_stats AS
SELECT 
    arrow_cast(domain, 'Utf8') as domain,  -- 轉換為 Utf8
    visit_count
FROM (
    SELECT 
        SUBSTRING(url, 1, POSITION('/' IN SUBSTRING(url, 9))) as domain,
        COUNT(*) as visit_count
    FROM access_logs
    GROUP BY domain
);

小結

今天我們深入探討了 StringView 的字串處理方式。明天我們將探討統計資訊收集與 Cost-Based Optimization,了解 DataFusion 如何利用統計資訊來做出更智能的查詢優化決策。

參考資料

  1. Apache Arrow StringView Specification
  2. DataFusion StringView Support
  3. Arrow Rust StringView Implementation
  4. DataFusion Upgrading Guide - StringView

上一篇
Day 27: 記憶體管理與 Spilling - 在有限資源下處理大量數據
下一篇
Day 29: 統計資訊收集與 Cost-Based Optimization - 讓優化器更聰明地做決策
系列文
DataFusion 闖關攻略:30 天學習 Rust 查詢引擎之旅30
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言