LINUX.ORG.RU

Postgres медленнее elasticsearch

 ,


0

5

Есть массивы по 4k значений. Надо посчитать разность между элементами двух масивов, возвести её в квадрат, сложить и извлечь корень. Это будет «расстояние». Задача: найти десяток массивов с минимальным расстоянием.

На тестовом примере в 6k массивов, эластик отрабатывает за 8 секунд, постгрес за двадцать.

CREATE OR REPLACE FUNCTION my_dist(l double precision[], r double precision[]) RETURNS double precision AS $$
DECLARE
  s double precision;
  al int;
BEGIN
  s := 0;
  FOR i IN 1..al LOOP
    s := s + ((l[i] - r[i]) * (l[i] - r[i]));
  END LOOP;
  RETURN sqrt(s);
END;
$$ LANGUAGE plpgsql;

Ну ок, пока я изучал, что можно исправить, выяснил, что введение доп. переменной j := j + 1 снижает производительность раза в полтора, странно, да? Отож. Тогда, я покумекал и сделал так:

CREATE OR REPLACE FUNCTION my_dist2(l double precision[], r double precision[]) RETURNS double precision AS $$
select sqrt(sum((li-ri)^2)) from unnest(l, r) as names(li, ri);
$$ LANGUAGE sql;

Эта штукенция уже отрабатывает за 11 секунд (если не в виде процедуры, а сразу встраивать в запрос, то 14-16секунд), в принципе, близко к эластику, но хотелось бы ещё быстрее. Ибо эластик для этой задачи подходит крайне хреново.

Deleted

Ответ на: комментарий от AnDoR

В запросе можно отправлять скрипты, которые будут чего-то молотить. Язык у них типа java (называется painless - йумористы), но скриптовый. Однако, куча косяков и извращений, например, массив в скрипт приходит не оригинальный а «отсортированный» и это немного треш, а оригинальный надо извлекать, через ухо.

Deleted ()
Ответ на: комментарий от x3al

Если этого мало — всегда есть c-расширения, распараллеливание, уход к gpu. Но это всё займёт гораздо больше времени, чем написать 1 функцию на жаваскрипте с plv8.

x3al ★★★★★ ()

А нельзя ли эту всю штуковину

выгрузить из базы данных и сделать в обычном языке программирования нечто, типа как преобразования изображения. Массив 6к х 4к вроде как можно побыстрее обработать, если это важно

sshestov ()
Ответ на: комментарий от maxcom
// curl -H 'Content-Type: application/json' -XPOST 'http://host:9200/index/_search?pretty=true' 
{
"query": {
    "function_score": {
      "boost_mode": "replace",
      "script_score": {
        "script": {
          "lang": "painless",
          "source": "double distance = 0; double diff = 0; List feature = params._source.feature; for(int j = 0; j < feature.size(); j++){diff = feature[j] - params.query_feature[j]; distance = distance + (diff*diff);} return Math.sqrt(distance)",
          "params": {
            "query_feature": [0.0....0.0]
          }
        }
      }
    }
  }

Как-то так, это кусок запроса. Он основан на https://discuss.elastic.co/t/problem-computing-euclidean-distance-using-script-score-query/148823 - но там автор вляпался в сортировку массивов и не докумекал, что ему мешает, всего-то надо было params._source.feature; использовать.

Deleted ()
Последнее исправление: Deleted (всего исправлений: 1)
Ответ на: комментарий от x3al

plv8 пока не нравится, тем что не на всех нужных нам платформах оно есть

Сделать aggregate

Что-то не ясно чем оно должно быть потенциально (щас проверить не могу) лучше то-го же SQL, ибо оный инлайнится (в теории). Тут навскидку, засада с массивами.

Deleted ()
Ответ на: комментарий от Deleted

Что-то не ясно чем оно должно быть потенциально (щас проверить не могу) лучше то-го же SQL, ибо оный инлайнится (в теории). Тут навскидку, засада с массивами.

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

x3al ★★★★★ ()
Ответ на: комментарий от x3al

Не, там в ячейке хранится массив. Можно его перепаковать в что-либо, но пока нет особого смысла. Разве что, если делать функцию на сях, то можно сырыми байтами жонглировать, но у нас вряд ли будет возможность подгружать сишные библиотеки для базы.

Deleted ()

На тестовом примере в 6k массивов

А я не очень понял, как ты это делаешь. Если ты перебираешь пары мыссивов «всех со всеми», то это получается 6000*(6000-1)/2 пар массивов, что равняется 17997000. И каждое сравнение — это сравнение двух массивов, состоящих из 4000 элементов double precision в каждом?

Wizard_ ★★★★★ ()

Задача по своей природе бессмысленная. Поэтому на вопрос, как её лучше решать, можно с уверенностью ответить: лучше никак.

Сравнение PostgreSQL и Elastic Search бессмысленно, так как у них разное назначение (причём оба не предназначены для математических расчётов). Но Elastic Search написан на Java. Если в PostgrSQL хранимую процедуру написать на Java, то может быть, выполнение именно этих вычислений ускорится. Но не следует делать это правилом - программировать на Java то, что вообще не нужно программировать.

Partisan ★★★ ()

На всякий:

  1. Никакие индексы тут не помогут, т.е. БД всегда должна будет прочитать все данные.

  2. С ростом кол-ва данных сложность будет расти как O(N*N*L), т.е. довольно быстро узким местом станет вычисление, а не выборка или чтение с диска.

  3. Если данных много и нужна скорость, то сами вычисления придется делать «на С» и задействовать AVX2/512 или GPU.

Соответственно, либо сделать хранимку на C (с правильной векторизацией) для postgresql, либо взять «тупой» локальный memory-mapped key-value storage.

Если нужна максимальная производительность при поиске, и нет возможности или смысла считать заранее, то придется брать libmdbx/LMDB и руками делить выборку на порции помещающиеся в L1/L2 (оптимальность зависит от CPU) и обрабатывать их параллельно (openmp), либо задействовать GPU.

Deleted ()
Последнее исправление: Deleted (всего исправлений: 1)

Мне кажется, только вылов десяти минимальных значений из результирующего массива в 17 миллионов double precision займёт несколько секунд на обычном десктопном компьютере. Что-то ты не договариваешь :)

Wizard_ ★★★★★ ()
Ответ на: комментарий от maxcom

Угу, но там пока данные влезают в память (~200мб), возможно дело в этом. Однако, и альтернатив особо нет - я не нашёл, как отключить сортировку массива (убирал индексацию поля, но сортировка всё равно оставалась).

Deleted ()
Ответ на: комментарий от Deleted

Индексы помогут, но «другие», существуют методы снижения размерности (locality-sensitive hashing, к примеру), это теоретически позволит ограничить выборку, если потребуется, но пока такой надобности нет.

Deleted ()
Ответ на: комментарий от Deleted

А почему тогда именно Eastic? Почему бы не взять H20 или Druid? Или попробовать в какой-нибудь Aerospike, который умеет в map-reduce по записям таблицы, например (в зависимости от конфигурации серверов, конечно)?

shty ★★★★★ ()
Ответ на: комментарий от maxcom

Ну, для Elastic быстро, насколько я понимаю, это ответ в течение 1 сек (без учета сетевых задержек). Всё что крутится дольше - медленно. Больше нескольких секунд - дико медленно. Так что логично.

shty ★★★★★ ()
Последнее исправление: shty (всего исправлений: 2)
Ответ на: комментарий от Deleted

Можно закодировать массив в строку как-нибудь и сделать поле keyword. Потом в скрипте скоринга раскодировать обратно. Так можно будет брать значение из doc values, а не из source.

maxcom ★★★★★ ()
Ответ на: комментарий от maxcom

Народ так и делал, я пока подожду, пока оно перестанет влезать в память и тогда уже сравню - будет ли влиять (пока что, переход на _source никак не сказался на производительности)

Deleted ()
Ответ на: комментарий от Deleted

Индексы помогут, но «другие», существуют методы снижения размерности (locality-sensitive hashing, к примеру), это теоретически позволит ограничить выборку, если потребуется, но пока такой надобности нет.

LSH поможет если в данных в принципе есть кластеры. Соответственно, нужно либо сразу знать об этом (исходя из природы данных), либо сделать кластеризацию, т.е. решить задачу кластеризации для ваших ~6К выборок для ~4К размерностей.

Нисколько не хочу вас обидеть, но (судя по показанному первоначальному подходу к решению) LSH может оказаться сильно не по зубам. Т.е. задача правильно применить LSH примерно на пару порядков сложнее, а выбора «постгря или ES2» для вычисления RMS при этом не возникает.

Deleted ()
Последнее исправление: Deleted (всего исправлений: 1)
Ответ на: комментарий от Deleted

Чуть не забыл.

  1. В актуальных версиях postgresql должен работать JIT на llvm. Я бы посмотрел собран ли постресс с поддержкой llvm и установлено ли на машине все необходимое. Т.е. нужно убедиться, что код вычислений проходит через llvm.

  2. С учетом всех бага-фичей, у меня нет уверенности, что llvm сделает авто-векторизацию цикла. Поэтому я бы сделал его ручками: выравнял (дописал нулями) блоки данных до кратности 16 (чтобы позволить avx512 для float) и сделал цикл шагами по 16.

  3. Если данные позволяют, то использовать float4. Если llvm сделает векторизацию, то это просто удвоит скорость.

Альтернативный гарантированный путь - добавить функцию «расстояния» на C, в том числе использовать libmdbx/LMDB вместо постресс.

Deleted ()