Вторичные представления индекса в памяти в Python

Question

Я ищу эффективное решение для создания вторичного индекса в памяти в Python, используя оптимизированный математический пакет высокого уровня, такой как numpy и стрелка. Я исключаю pandas по соображениям производительности.

Определение

"Вторичный индекс содержит запись для каждого существующего значения атрибута, подлежащего индексации. Эта запись может рассматриваться как ключ / пара значений со значением атрибута в качестве ключа и в качестве значения список указателей на все записи в базовой таблице, имеющие это значение. " - СП. Д'Сильва и соавт. (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. Сортированное представление в словарном кодировании должно, как правило, удовлетворять требованиям проблемы с превосходным сочетанием меньшего объема памяти и более быстрой / гибкой обработки ввода-вывода с нулевым копированием.

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)

Более быстрое решение ( less generi c)

это особый, но вполне допустимый случай, когда 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)

Существует еще несколько шагов для получения представления вторичного индекса согласно определению СП. 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]

Обсуждение

На практике это быстрее использовать представление вторичного индекса с повторяющимися значениями, чем со списками указателей на записи таблицы, но второй обладает интересным свойством быть ближе к представлению гиперграфа, которое я использую в TRIADB .

Тип вторичного индекса, описанный в этом решении, больше подходит для анализа, фильтрации больших наборов данных, которые не помещаются в память, но хранятся на диске в формате хранилища столбцов. В этом случае для указанного c набора столбцов можно восстановить подмножество записей в формате памяти (хранилище столбцов) и даже представить его на гиперграфе (следите за обновлениями для следующего выпуска TRIADB)