1

numpy や arrow などの高度に最適化された数学パッケージを使用して、Python でセカンダリ インメモリ インデックスを構築するための効率的なソリューションを探しています。パフォーマンス上の理由から、パンダを除外しています。

意味

「セカンダリ インデックスには、インデックスを作成する属性の既存の各値のエントリが含まれています。このエントリは、属性値をキーとして、値として、ベース テーブル内のすべてのレコードへのポインタのリストを持つキー/値のペアとして見ることができます。この価値があります。」- JV。D'Silva等。(2017)

簡単な例を見てみましょう。後でこれをスケーリングして、いくつかのベンチマークを生成できます。

import numpy as np

pk = np.array([1, 2, 3, 4, 5, 6, 7, 8, 9], dtype='uint32')
val = np.array([15.5, 3.75, 142.88, 142.88, None, None, None, 7.2, 2.1], dtype='float32')

興味深いことに、 pyarrow.Array.dictionary_encodeメソッドは、値の配列を、セカンダリ インデックスに近い辞書エンコード表現に変換できます。

val.dictionary_encode()
Out[55]: 
<pyarrow.lib.DictionaryArray object at 0x7ff430d8b4d0>
-- dictionary:
  [
    15.5,
    3.75,
    142.88,
    nan,
    7.2,
    2.1
  ]
-- indices:
  [
    0,
    1,
    2,
    2,
    3,
    3,
    3,
    4,
    5
  ]

ここで問題を開きました

したがって、問題は、値とインデックスを効率的に保持するために、Python データ構造を使用してメモリ内にセカンダリ インデックスをどれだけ速く構築できるかということです。しかし、クエリのフィルタリング (ポイント、範囲) と変換 ( TRIADBのハイパーエッジとも呼ばれる行、列、および関連付けの再構築) の両方に役立つ場合、インデックスが役立つため、これは話の半分です。また、この簡単な説明でも、この種のインデックスの更新がいかに簡単かについては触れていません。

多くの理由から、私は PyArrow オープンソース ソリューションの可能性を調査し始めました。並べ替えられた辞書エンコード表現は、通常、メモリ フットプリントの縮小と高速で柔軟なゼロ コピー I/O 処理の優れた組み合わせにより、問題の要件を満たす必要があります。

4

1 に答える 1

0

解決

過去と現在の両方で、この問題に対するオープンソースの解決策を探しましたが、私の欲求を満たすものは見つかりませんでした。今回は、独自のビルドを開始し、その実装について率直に議論することにしました。これは、nullデータの欠落シナリオなどのケースもカバーします。

セカンダリ インデックスは、私のTRIADBプロジェクトのコア要素である隣接リスト表現に非常に近いことに注意してください。これが、解決策を探す主な理由です。

を使用して1行のコードから始めましょうnumpy

idx = np.sort(np.array(list(zip(pk, val)), dtype=struct_type), order='val')

idx['val']
Out[68]: 
array([  2.1 ,   3.75,   7.2 ,  15.5 , 142.88, 142.88,    nan,    nan,
          nan], dtype=float32)

idx['pk']
Out[69]: array([8, 1, 7, 0, 2, 3, 4, 5, 6], dtype=uint32)

より高速なソリューション (一般的ではない)

これは、pk が range(n) の値を持つ特別な、しかし完全に有効なケースです。

idx_pk = np.argsort(val)
idx_pk
Out[91]: array([8, 1, 7, 0, 2, 3, 4, 5, 6])

idx_val = val[idx_pk]
idx_val
Out[93]: array([  2.1 ,   3.75,   7.2 ,  15.5 , 142.88, 142.88,    nan,    nan,   nan], dtype=float32)

JV の定義に従って、セカンダリ インデックス表現を取得するには、さらにいくつかの手順があります。D'Silva等。

  1. 取り除くnan
  2. セカンダリ インデックスの一意の値を計算する
  3. 一意の値ごとに、その値を含むテーブルのすべての行に対する主キー インデックスのリストを計算します。

隣接リストを持つ一意のセカンダリ インデックス

def secondary_index_with_adjacency_list(arr):
    idx_pk = np.argsort(arr)
    idx_val = arr[idx_pk]
    cnt = np.count_nonzero(~np.isnan(idx_val))
    usec_ndx, split_ndx, cnt_arr = np.unique(idx_val[:cnt], return_index=True, return_counts=True)
    adj_list = np.split(idx_pk[:cnt], split_ndx)[1:]

    return usec_ndx, cnt_arr, adj_list

ndx, freq, adj = secondary_index_with_adjacency_list(val)

pd.DataFrame({'val': ndx, 'freq': freq, 'adj': adj})

Out[11]: 
      val  freq     adj
0    2.10     1     [8]
1    3.75     1     [1]
2    7.20     1     [7]
3   15.50     1     [0]
4  142.88     2  [2, 3]

討論

実際には、テーブルのレコードへのポインターのリストを使用するよりも、値が繰り返されるセカンダリ インデックスの表現を使用する方が高速ですが、2 番目のインデックスには、 TRIADBで使用しているハイパーグラフ表現に近いという興味深い特性があります。

このソリューションで説明されている種類のセカンダリ インデックスは、分析、メモリに収まらないが列ストア形式でディスクに格納されているビッグ データ セットのフィルタリングに適しています。その場合、特定の列のセットについて、レコードのサブセットをメモリ (列ストア) 形式で再構築し、ハイパーグラフに表示することもできます (TRIADB の次のリリースにご期待ください)。

于 2020-01-26T12:45:04.347 に答える