Python 中的辅助内存索引表示

Question

我正在寻找一种有效的解决方案，使用 numpy 和 arrow 等高级优化数学包在 Python 中构建辅助内存索引。出于性能原因，我将 pandas 排除在外。

定义

"A secondary index contains an entry for each existing value of the attribute to be indexed. This entry can be seen as a key/value pair with the attribute value as key and as value a list of pointers to all records in the base table that have this value." - JV. D'Silva et al. (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
  ]

我已经打开了一个问题here

因此，问题在于使用 Python 数据结构在内存中构建二级索引的速度有多快，以有效地保存值和索引。但这只是故事的一半，因为如果索引能很好地服务于过滤查询（点、范围）和转换——重建行、列和关联 a.k.a TRIADB 中的超边，那么索引将很有用。甚至这里的快速描述也没有涵盖更新这种索引有多么容易。

出于多种原因，我已经开始研究一种可能的 PyArrow 开源解决方案。排序的字典编码表示通常应该满足问题的要求，它具有较小的内存占用和 faster/flexible 零复制 I/O 处理的完美组合。

Answer 1

解决方案

我过去和现在都在寻找这个问题的开源解决方案，但我没有找到一个满足我胃口的。这次我决定开始构建我自己的并公开讨论它的实现，它也涵盖了 null 案例，即缺失数据场景。

请注意，二级索引非常接近邻接表表示，这是我 TRIADB 项目中的核心元素，也是寻找解决方案的主要原因。

让我们从使用 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 的值在范围 (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 等人

去掉nan
计算二级索引的唯一值
对于每个唯一值，计算 table 中包含该值的所有行的主键索引列表

具有邻接列表的唯一二级索引

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]

讨论

在实践中，使用具有重复值的二级索引的表示比使用 table 的记录指针列表的表示更快，但第二个具有有趣的属性更接近我在 TRIADB.

中使用的超图表示

该解决方案中描述的二级索引更适合table用于分析，过滤内存中不适合但以列存储格式存储在磁盘上的大数据集。在这种情况下，对于一组特定的列，可以重建内存（列存储）格式的记录子集，甚至可以将其呈现在超图上（敬请期待 TRIADB 的下一个版本）

Python 中的辅助内存索引表示

Secondary in-memory index representations in Python

python

numpy

adjacency-list

pyarrow

secondary-indexes

定义

解决方案

更快的解决方案（不太通用）

具有邻接列表的唯一二级索引

讨论