1

我正在寻找一种有效的解决方案，使用 numpy 和 arrow 等高级优化数学包在 Python 中构建二级内存索引。出于性能原因，我不包括熊猫。

定义

“二级索引包含要索引的属性的每个现有值的条目。这个条目可以看作是一个键/值对，属性值为键，值是指向基表中所有记录的指针列表有这个价值。” -合资企业。德席尔瓦等人。(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项目中的核心元素，这是寻找解决方案的主要原因。

让我们从一行代码开始使用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 的定义，还有几个步骤可以获得二级索引表示。德席尔瓦等人。

  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]

讨论

实际上，使用具有重复值的二级索引表示比使用指向表记录的指针列表的表示更快，但第二个具有更接近我在TRIADB中使用的超图表示的有趣特性。

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

于 2020-01-26T12:45:04.347 回答