Улучшить производительность агрегации матриц / таблиц и поиска - PullRequest
Новая
       5

Улучшить производительность агрегации матриц / таблиц и поиска

1 голос
/ 01 ноября 2010

Существует матрица возможностей продукта.Он имеет тысячи строк (продуктов) и сотни функций.У него есть двоичные значения, которые показывают, есть ли у продукта эта функция или нет.Таким образом, это может быть таблица из 40 000 строк и 900 столбцов.

<strong>Product-feature matrix</strong><br/> pr f1 f2 f3 fn ...<br/> 01 0 1 1 1<br/> 02 0 0 0 0<br/> 03 1 0 1 0<br/> 04 1 0 1 0<br/> .....

Сначала я должен найти продукты, которые имеют заданный набор функций QEg Q = (f1 = 1, f5 = 1, f27 = 1).Проще говоря, найди синий авто, хэтчбек, 3-х дверный.

<strong>Result 1</strong><br/> Given Q=(f1=1, f5=1, f27=1)<br/> Relevant products: 03, 04, 08...

Во-вторых, и самое главное, я должен выяснить, сколько продуктов, которые имеют набор функций Q, также имеют функцию f_i (где i - 1..n),Другими словами, мы выбираем строки, которые удовлетворяют Q, и подсчитываем, сколько 1 в каждом столбце (производим суммирование SUM).Например, сколько синих автомобилей, хэтчбек, 3-дверный также имеет: дизельный двигатель, бензиновый двигатель, ксеноновые фары.

<strong>Result 2</strong><br/> Given Q=(f1=1, f5=1, f27=1)<br/> sum f2 = 943<br/> sum f3 = 543<br/> sum f4 = 7<br/> sum f6 = 432<br/> ....

Конечно, это можно решить с помощью RDBMSно это не так эффективно - в общем случае это потребует полного сканирования как для поиска товаров, так и для агрегации в каждом столбце.По крайней мере, я не знаю, как построить эффективный индекс b-дерева для этой задачи.Индекс растрового изображения Oracle может помочь, но я не могу использовать Oracle.

В настоящее время мы используем MySQL для этой задачи, но она не дает хороших результатов.На самом деле мы используем целочисленное представление (мы сгруппировали объекты и храним целые числа в столбцах, а не в значениях bool), чтобы уменьшить количество столбцов.

Возможно рассматривать эту матрицу как разреженную двоичную матрицу.И это не большая проблема, чтобы сохранить его полностью в памяти.И мне интересно, можно ли применить некоторые алгоритмы для работы с разреженными матрицами, векторным пространством (SVD, умножение матрицы на вектор и так далее).Но это, вероятно, помогает в поиске продуктов, которые удовлетворяют вектору Q, а не в агрегации.Проблема заключается скорее во времени агрегации, а не в пространстве.

Вероятно, возможно сохранить матрицу в виде многосвязного списка, который поможет находить продукты и производить агрегацию для каждого столбца.

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

Ответы [ 3 ]

1 голос
/ 01 ноября 2010

пожалуйста, посмотрите на этот пример, который я делал некоторое время назад, он следует тому, что правильно изложил Джейди, но более подробно и против 125 миллионов poster_categories (car_features) со временем выполнения 0,02 секунды - ваш, наихудший случай - 40 К ++ * 900 кол = 36 миллионов строк, т. Е. Это ребенок!

Перезапись mysql select для сокращения времени и записи tmp на диск 

select count(*) from category
count(*)
========
500,000


select count(*) from poster
count(*)
========
1,000,000

select count(*) from poster_category
count(*)
========
125,675,688

select count(*) from poster_category where cat_id = 623
count(*)
========
342,820

explain
select
 p.*,
 c.*
from
 poster_category pc
inner join category c on pc.cat_id = c.cat_id
inner join poster p on pc.poster_id = p.poster_id
where
 pc.cat_id = 623
order by
 p.name
limit 32;

id  select_type table   type    possible_keys   key     key_len ref                         rows
==  =========== =====   ====    =============   ===     ======= ===                         ====
1   SIMPLE      c       const   PRIMARY         PRIMARY 3       const                       1   
1   SIMPLE      p       index   PRIMARY         name    257     null                        32  
1   SIMPLE      pc      eq_ref  PRIMARY         PRIMARY 7       const,foo_db.p.poster_id    1   

select
 p.*,
 c.*
from
 poster_category pc
inner join category c on pc.cat_id = c.cat_id
inner join poster p on pc.poster_id = p.poster_id
where
 pc.cat_id = 623
order by
 p.name
limit 32;

0.021: Query OK
1 голос
/ 01 ноября 2010

Вы можете расположить ваши данные по столбцам. то есть есть один BitSet для столбца со списком машин / рядов, которые имеют эту функцию.

Это позволяет вам использовать преимущества быстрых и / или операций, предоставляемых BitSet.

Используя эти функции, вы сможете достичь менее 2 микросекунд для поиска и подсчета каждой функции.

Для набора данных 40 000 * 900 следующие отпечатки 

average search time 1396 ns.
average count time 1234 ns.

Это должно быть на несколько порядков быстрее, чем вы можете получить с базой данных RDBMS. Даже один миллион строк занимает менее 50 микросекунд каждая. 

public static void main(String... args) throws IOException {
    final int rows = 40 * 1000;
    final int cols = 900;

    List<BitSet> features = new ArrayList<BitSet>();
    features.add(new BitSet(rows));
    features.add(new BitSet(rows));
    for (int i = 2; i < cols; i++) {
        final BitSet bs = new BitSet(rows);
        for (int j = 0; j < rows; j++)
            bs.set(j, j % i == 0);
        features.add(bs);
    }

    // perform the search
    int[] factors = new int[]{2, 5, 7};
    BitSet matches = new BitSet();
    long runs =  1000*1000;
    {
        long start = System.nanoTime();
        for (int i = 0; i < runs; i++) {
            // perform lookup.
            lookup(matches, features, factors);
        }
        long avgTime = (System.nanoTime() - start) / runs;
        System.out.println("average search time " + avgTime  + " ns.");
    }
    {
        long start = System.nanoTime();
        int count9 = 0;
        BitSet col9matched = new BitSet(cols);
        for (int i = 0; i < runs; i++) {
            final int index = 9;
            final BitSet feature = features.get(index);
            count9 = countMatches(col9matched, matches, feature);
        }
        long avgTime = (System.nanoTime() - start) / runs;
        System.out.println("average count time " + avgTime + " ns.");
    }
}

private static int countMatches(BitSet scratch, BitSet matches, BitSet feature) {
    // recycle.
    scratch.clear();
    scratch.or(matches);
    scratch.and(feature);
    return scratch.cardinality();
}

private static void lookup(BitSet matches, List<BitSet> data, int[] factors) {
    matches.clear();
    matches.or(data.get(factors[0]));
    for (int i = 1, factorsLength = factors.length; i < factorsLength; i++) {
        matches.and(data.get(factors[i]));
    }
}
1 голос
/ 01 ноября 2010

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

Как насчет трех таблиц

"products" (product_ref, product_name) index product_ref (список продуктов)

"индекс «features» (feature_ref, description) index feature_ref (список возможных функций)

и

«productfeatures» (product_ref, feature_ref) index product_ref, feature_ref и feature_ref, product_ref (каждая строка представляетособенность продукта)

Затем можно выполнить объединение между таблицами

выбрать * из продуктов t1 объединить особенности продукта t2 объединить особенности продукта t3, где t1.product_ref = t2.product_ref и t1.product_ref =t3.product_ref и t2.feature_ref = 45 и t3.feature_ref = 67 и т. д.

...