メモリ構造

メモリ構造#

PolarsのDataFrameの裏側には、Apache Arrow形式の配列が存在します。これにより、メモリ効率が高く、同時に高速なデータアクセスと操作が可能になります。Apache Arrowは、データ分析や処理に特化した列指向のメモリ形式であり、以下の特徴を持ちます。

  1. メモリ効率: Apache Arrowは、データを連続したメモリブロックに格納するため、キャッシュ効率が高くなります。これにより、大量のデータを扱う際にもメモリの使用量が最小限に抑えられます。

  2. 互換性: Arrow形式は、多くのデータ分析ツールやライブラリと互換性があります。これにより、異なるツール間でのデータの移動がシームレスに行えます。

  3. 高速なデータアクセス: 列指向のデータ格納形式は、特定の列へのアクセスや操作を非常に高速に行うことができます。これは、大規模なデータセットに対して特定の列を頻繁に操作する場合に特に有効です。

  4. 豊富なデータ型のサポート: Arrowは、NULL、リスト、構造体、文字列など、多種多様なデータ型をサポートしています。これにより、複雑なデータ構造を簡単に表現し、操作することができます。

本章では、NULL、文字列、配列、リスト、構造体などのデータ型を表現するためのメモリ構造について詳述します。

import struct
import polars as pl

データの管理#

Polarsでは、最も低レベルのデータ管理にpyarrowのBufferを使用しています。以下のコードでは、df['A']を2回実行して、それぞれのSeriesオブジェクトが同一かどうかをid()関数で確認します。

df = pl.DataFrame({
    "A": [1, 2, 3, 4],
    "B": [5, 6, 7, 8]
})

# Seriesオブジェクトを2回取得
s1 = df['A']
s2 = df['A']
print(id(s1), id(s2))

2105964530064 2105964497872

結果として、取得した2つのSeriesオブジェクトは同一ではありません。PolarsのSeries内部では、Rustで実装されたPySeriesが使用されています。しかし、このPySeriesもそれぞれ異なるオブジェクトです。

print(id(s1._s), id(s2._s))

2105964328640 2105968588192

各SeriesオブジェクトをPyArrowの配列に変換しても、取得した配列は同一ではありません。

a1 = s1.to_arrow()
a2 = s2.to_arrow()
print(id(a1), id(a2))

2105897255552 2105897255360

PyArrow配列が内部で使用するBufferオブジェクトを取得し、IDが異なるので、Bufferオブジェクト自体も同一ではありません。address属性でそのデータアドレスを確認すると、アドレスは同一であることが分かります。次のグラフは各個オブジェクト間の関係を示します。

        flowchart LR
    s1(Series s1) -->|_s| s1s(PySeries)
    s2(Series s2) -->|_s| s2s(PySeries)
    s1s -->|"to_arrow(False)"| s1sa(pyarrow.Array)
    s2s -->|"to_arrow(False)"| s2sa(pyarrow.Array)
    s1 -->|"to_arrow()"| s1sa
    s2 -->|"to_arrow()"| s2sa
    s1sa -->|"buffers()[1]"| s1sab(pyarrow.Buffer)
    s2sa -->|"buffers()[1]"| s2sab(pyarrow.Buffer)
    s1sab -->|address| memory(Data Memory)
    s2sab -->|address| memory(Data Memory)
    
b1 = a1.buffers()[1]
b2 = a2.buffers()[1]
print(id(b1), id(b2))
print(b1.address, b2.address)

2109216777072 2109217188080
5940410323808 5940410323808

次に、インデックス操作でSeriesオブジェクトの要素を変更した後、Bufferオブジェクトのデータアドレスを再確認します。

s1[1] = 100
print(s1.to_arrow().buffers()[1].address)

5940410323968

結果として、データのアドレスが変更されていることが分かります。つまり、この操作では、同じアドレス上のデータが上書きされるのではなく、新しいアドレスにデータが保存されるように更新されています。このため、s2やdfは元のデータを保持しており、s1の変更内容が反映されないことが分かります。

NULLの保存方法#

Polarsは、PyArrowsのデータ型を使用してデータを保存します。特に、NULL値を含む配列の保存には、二つのバッファ（buffer）が使用されます。これにより、NULL値を効率的に管理しつつ、実際のデータも確実に保持することが可能です。

  • マスクバッファ: このバッファは、各データ要素がNULLかどうかをビット単位で記録します。具体的には、各ビットがデータ要素に対応し、ビットが1の場合その要素は非NULL、0の場合はNULLを示します。この方法はメモリ効率が良く、大量のデータにおいてもNULL情報を最小限のメモリで管理できます。

  • データバッファ: こちらのバッファには実際のデータが格納されます。NULL値の代わりに、一般的には0やその他のプレースホルダーが用いられ、実際のデータ要素が連続して保存されます。

以下に、具体的な例を示します。

s = pl.Series([1, None, None, 3, 4, None, 8, 9], dtype=pl.Int16)
a = s.to_arrow()
buf_mask, buf_data = a.buffers()

buf_maskはNULL値のフラグをビット列で表現しており、0b11011001は、各ビットが対応するデータ要素のNULL状態を示しています。最初のビット(一番右側)から順に1, 0, 0, 1, 1, 0, 1, 1となっており、2、3と6番目の要素がNULLであることが分かります。

bin(bytes(buf_mask)[0])

'0b11011001'

struct.unpack('<8h', buf_data)

(1, 0, 0, 3, 4, 0, 8, 9)

以下のコードでは、buf_dataとsが同じメモリ領域を共有していることを確認します。このコードではctypesモジュールを使用して、buf_data.addressをポインタ型のpbufに変換し、pbufを介して4番目の値を99に変更します。最後に、sの内容を出力して変更が反映されていることを確認します。

from ctypes import POINTER, c_int16, cast
pbuf = cast(buf_data.address, POINTER(c_int16))
pbuf[3] = 99
print(s)

shape: (8,)
Series: '' [i16]
[
	1
	null
	null
	99
	4
	null
	8
	9
]

String#

Polarsでは、文字列のデータ列は、メモリ効率を最大限に引き出すために、三つのバッファを使用してデータを保存します。これにより、文字列データの高速なアクセスと操作が可能になります。具体的には、以下の三つのバッファを用います。

マスクバッファ: このバッファは、各文字列要素がNULLかどうかをビット単位で記録します。各ビットは文字列要素に対応し、1がNULLでないことを、0がNULLであることを示します。これにより、NULL値の存在を効率的に管理できます。

インデックスバッファｂ: このバッファには、各文字列要素の開始インデックスと終了インデックスが保存されます。これにより、連続した文字列データから各要素を迅速に抽出することができます。具体的には、i番目の文字列の開始インデックスはbuf_index[i]、終了インデックスはbuf_index[i+1]に格納されます。

データバッファ: すべての文字列はこのバッファに連続して保存されます。文字列データを連続的に保存することで、メモリ使用量が最小化され、データアクセスが高速化されます。

以下に具体的な例を示します。

s = pl.Series(["abc", "defghi", "xyz", None, "123"])
a = s.to_arrow()
buf_mask, buf_index, buf_data = a.buffers()

buf_maskは、各ビットが文字列要素のNULL状態を示しています。最初の三つの要素はNULLではなく、4番目の要素がNULLであることを示しています。

bin(bytes(buf_mask)[0])

'0b11110111'

buf_indexに保存されているデータは[0, 3, 9, 12, 12, 15]となっています。これは、以下のように各文字列要素の開始インデックスと終了インデックスを示しています。

  • “abc”の開始インデックスは0、終了インデックスは3

  • “defghi”の開始インデックスは3、終了インデックスは9

  • NULL要素のため開始インデックスと終了インデックスは同じ12

struct.unpack('<6q', buf_index)

(0, 3, 9, 12, 12, 15)

buf_dataにはすべての文字列データが連続して保存されています。インデックスバッファを用いることで、この連続データから各文字列要素を迅速に抽出することが可能です。

buf_data.to_pybytes()

b'abcdefghixyz123'

例えば、s[2]の開始インデックスは9、終了インデックスは12で、次のようにbuf_dataからs[2]のデータを取り出します。

buf_data[9:12].to_pybytes()

b'xyz'

Array#

PolarsのArray列は、固定サイズのリストを格納するためのデータ構造であり、そのメモリ構造は他の列といくつかの共通点を持ちながらも、特有の要素があります。特に、list_size属性は重要な役割を果たします。以下のコード例を用いて、Array列のメモリ構造を詳しく説明します。

s = pl.Series([
    [1,   None, 3   ], 
    [4,   5,    None], 
    [6,   7,    8   ], 
    [9,   10,   11  ]], 
    dtype=pl.Array(pl.Int16, 3))
a = s.to_arrow()

list_size属性は各要素のサイズを表します。ます。

print(f"{a.type.list_size=}")

a.type.list_size=3

buf_maskとbuf_dataはそれぞれNULLとデータを保存するバッファです。この二つのバッファは一般列と同じです。

_, buf_mask, buf_data = a.buffers()
bin(bytes(buf_mask)[0])

'0b11011101'

struct.unpack('<12h', buf_data)

(1, 0, 3, 4, 5, 0, 6, 7, 8, 9, 10, 11)

List#

PolarsのList列のメモリ構造は、効率的なデータ管理を実現するために設計されており、特に可変長のリストを格納するための特定のバッファを使用します。この構造は、文字列列（str列）といくつかの点で類似しています。以下に、具体的なコード例と出力を用いて説明します。

s = pl.Series([
    [1, None, 3], 
    [10, 20], 
    None, 
    [100, 200, 300]], 
    dtype=pl.List(pl.Int16))
a = s.to_arrow()
buf_mask1, buf_index, buf_mask2, buf_data = a.buffers()

次のbuf_mask1は、各リスト要素がNULLかどうかをビット単位で記録します。ビットが1の場合、そのリストはNULLではなく、0の場合、そのリストはNULLであることを示します。3ビット目は0であるので、3番目の要素がNULLであることを示しています。

bin(bytes(buf_mask1)[0])

'0b11111011'

次のバッファbuf_indexは、各リスト要素の開始インデックスと終了インデックスを記録します。文字列列（str列）と同様に、このバッファを使用して、連続したデータから各リスト要素を抽出します。

s[0]のデータのインデックスは0~3、つまり、buf_data中の[1, 0, 3]です。s[1]のデータインデックスは3~5、buf_data中の[10, 20]です。

struct.unpack('<5Q', buf_index)

(0, 3, 5, 5, 8)

次のバッファは、リスト内の各要素がNULLかどうかをビット単位で記録します。2ビット目は0なので、2番目の要素（None）がNULLであることを示しています。

bin(bytes(buf_mask2)[0])

'0b11111101'

すべてのリスト要素の実際のデータがbuf_dataに連続して格納されています。NULL値はプレースホルダー（この例では0）で表現されます。

struct.unpack('<8h', buf_data)

(1, 0, 3, 10, 20, 100, 200, 300)

Struct#

Struct列は、複数のフィールドを持つデータを格納するためのデータ構造です。各フィールドは独自のデータ型とメモリ構造を持ち、これらを効率的に管理するためにいくつかのバッファを使用します。以下のコード例を用いて、Struct列のメモリ構造を詳しく説明します。

s = pl.Series([{"A": 1, "B": None}, {"A": None, "B": 20}, {"A": 3, "B": 30}, None])
a = s.to_arrow()
a.buffers()

[None,
 <pyarrow.Buffer address=0x2f78c020ae0 size=1 is_cpu=True is_mutable=False>,
 <pyarrow.Buffer address=0x2f78c0c0360 size=32 is_cpu=True is_mutable=False>,
 <pyarrow.Buffer address=0x2f78c020ae8 size=1 is_cpu=True is_mutable=False>,
 <pyarrow.Buffer address=0x2f78c0c0340 size=32 is_cpu=True is_mutable=False>]

一つのフィールドに対して、マスクと値を保存する二つのバッファを使用します。このメモリ構造により、各フィールドの値がメモリ上で連続して保存されていることがわかります。

buf_mask_A, buf_value_A = a.buffers()[1:3]
print(bin(bytes(buf_mask_A)[0]))
print(struct.unpack('<4Q', buf_value_A))

0b11110101
(1, 0, 3, 0)

buf_mask_B, buf_value_B = a.buffers()[3:5]
print(bin(bytes(buf_mask_B)[0]))
print(struct.unpack('<4Q', buf_value_B))

0b11110110
(0, 20, 30, 0)