Python中的二级内存索引表示形式

Question

我正在寻找一种有效的解决方案，以使用高级优化的数学程序包（例如numpy和arrow）在Python中构建二级内存索引。由于性能原因，我将熊猫排除在外。

定义

“辅助索引包含要索引的属性的每个现有值的条目。此条目可以看作是键/值对，属性值作为键，并且值表示指向基础中所有记录的指针列表具有此值的表。” -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数据结构在内存中建立二级索引的速度有多快，以有效地保存值和索引。但这只是故事的一半，因为如果索引可以很好地过滤查询（点，范围）和转换（重构行，列和关联，也称为TRIADB中的超边缘），将很有用。而且，即使是此处的简短说明也无法涵盖更新这种索引的难易程度。

由于许多原因，我已经开始研究可能的PyArrow开源解决方案。经过排序的字典编码表示形式通常应以较小的内存占用量和更快/灵活的零拷贝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的值在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)

根据合资企业的定义，还有更多步骤来获得二级索引表示。 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]

讨论

实际上，使用具有重复值的二级索引表示要比使用具有表记录指针列表的指针的表示更快，但是第二个具有有趣的特性，即它更接近于我在[ C0]。

解决方案中描述的辅助索引的类型更适合于分析，过滤不适合内存但以列存储格式存储在磁盘上的大数据集。在那种情况下，对于一组特定的列，可以以内存（列存储）格式重建记录的子集，甚至可以将其显示在超图上。