SQL, чтобы выбрать набор из 10 записей, которые в совокупности лучше всего соответствуют критерию

Ответ 1

Если вы действительно хотите найти оптимальное решение (оптимальное решение), проблема в том, что вам нужно проверить все возможные комбинации из 10 правил и найти, сколько хэш-индексов возвращается каждой из этих возможных комбинаций. Проблема состоит в том, что количество комбинаций сильно отличается от числа правил ^ 10 (на самом деле число меньше, если вы считаете, что не можете повторять те же самые правила в комбинациях... его комбинация из m элементов, взятых в группы из 10).

• ПРИМЕЧАНИЕ. Точнее, количество возможных комбинаций

  m!/(n! (m-n)!) = > m!/(10! (m-10!)), где! факториал: m!= m * m-1 * m-2... * 3 * 2 * 1

Чтобы сделать эти комбинации, вы должны присоединиться к своей таблице с собой, в 10 раз, исключая предыдущие комбинации правил, примерно так:

select m1.ruleid r1, m2.ruleid r2, m3.ruleid r3 ...
from matches m1 inner join matches m2 on m2<>m1 
   inner join matches m3 on m3 <> m1 and m3 <> m2
     ...

Затем вам нужно найти наивысший счет

select r1, r2, r3..., count(distinct hashid) 
from ("here the combinations of 10 ruleIds define above") G10
inner join M
  on ruleid = r1 or ruleid = r2 or ruleid=r3...
group by r1, r2, r3...

Этот гигантский запрос займет много времени.

Там могут быть намного более быстрые процедуры, которые дадут вам субоптимальные результаты.

НЕКОТОРЫЕ ОПТИМИЗАЦИИ:

Это может быть несколько оптимизировано в зависимости от формы данных, ища группы, которые равны или включены в другие группы. Для этого потребовалось бы меньше, чем (m * (m + 1))/2 операций, что по сравнению с другим числом, это очень важно, особенно если довольно вероятно найти несколько групп, которые можно отбросить, что приведет к снижению m. Во всяком случае, основной все еще стоит гигантская стоимость.

Ответ 2

Я думаю, что ваша проблема - это вариация проблемы с рюкзаком.

Я думаю, вы уже понимаете, что не можете просто выбрать ruleIds для ruleIds больше hashIds, как показывают другие ответы, потому что, когда каждый из этих ruleIds соответствует 100 hashIds, они могут все сопоставьте тот же 100 hashIds... но если вы выбрали 10 других ruleIds, которые соответствуют только 25 hashIds, но с каждым из hashIds, сопоставляемым каждым ruleId уникальный, вы получите более уникальный hashIds с этим набором.

Чтобы решить эту проблему, вы можете начать с выбора того, что ruleId соответствует наибольшему числу hashIds, а затем затем выбрать, что ruleId соответствует самому hashIds, которые не включены в hashIds, которые соответствуют previous ruleIds... продолжение этого процесса, пока вы не выбрали 10 ruleIds.

В вашем распределении данных могут быть аномалии, из-за которых это не приведет к созданию оптимального набора ruleIds... поэтому, если вы хотите сходить с ума, вы можете рассмотреть возможность внедрения генетического алгоритма, чтобы попытаться улучшить "фитнес" вашего набора 10 ruleIds.

Это не задача, которую SQL особенно хорошо подходит для обработки но вот пример проблемы с рюкзаком, решаемой с помощью генетического алгоритма, написанного на SQL (!)

ИЗМЕНИТЬ

Здесь непроверенная реализация решения, в которой ruleIds выбирается по одному за раз, причем каждая итерация, выбрав любую ruleId, имеет самый уникальный hashIds, который ранее не был покрыт любым другим выбранным ruleIds:

--------------------------------------------------------------------------
-- Create Test Data
--------------------------------------------------------------------------
create create matches (
  id  int(10) unsigned not null auto_increment,
  hashId int(10) unsigned not null,
  ruleId int(10) unsigned not null,
  primary key (id)
);

insert into matches (hashid, ruleid)
values 
(1,1), (2,1), (3,1), (4,1), (5,1), (6,1), (7,1), (8,1), (9,1), (10,1),
(1,2), (2,2), (3,2), (4,2), (5,2), (6,2), (7,2), (8,2), (9,2), (10,2),
(1,3), (2,3), (3,3), (4,3), (5,3), (6,3), (7,3), (8,3), (9,3), (10,3),
(1,4), (2,4), (3,4), (4,4), (5,4), (6,4), (7,4), (8,4), (9,4), (10,4),
(1,5), (2,5), (3,5), (4,5), (5,5), (6,5), (7,5), (8,5), (9,5), (10,5),
(1,6), (2,6), (3,6), (4,6), (5,6), (6,6), (7,6), (8,6), (9,6), (10,6),
(1,7), (2,7), (3,7), (4,7), (5,7), (6,7), (7,7), (8,7), (9,7), (10,7),
(1,8), (2,8), (3,8), (4,8), (5,8), (6,8), (7,8), (8,8), (9,8), (10,8),
(1,9), (2,9), (3,9), (4,9), (5,9), (6,9), (7,9), (8,9), (9,9), (10,9),
(11,10), (12,10), (13,10), (14,10), (15,10),
(11,11), (12,11), (13,11), (14,11), (15,11),
(16,12), (17,12), (18,12), (19,12), (20,12),
(21,13), (22,13), (23,13), (24,13), (25,13),
(26,14), (27,14), (28,14), (29,14), (30,14),
(31,15), (32,15), (33,15), (34,15), (35,15),
(36,16), (37,16), (38,16), (39,16), (40,16),
(41,17), (42,17), (43,17), (44,17), (45,17),
(46,18), (47,18), (48,18), (49,18), (50,18),
(51,19), (52,19), (53,19), (54,19), (55,19),
(56,20), (57,20), (58,20), (59,20), (60,20)
--------------------------------------------------------------------------
-- End Create Test Data
--------------------------------------------------------------------------

create table selectedRules (
  ruleId int(10) unsigned not null
);

set @rulesSelected = 0;

while (@rulesSelected < 10) do
  insert into selectedRules (ruleId)
  select m.ruleId
  from 
    matches m left join (
      select distinct m2.hashId
      from
        selectedRules sr join
        matches m2 on m2.ruleId = sr.ruleId
      ) prev on prev.hashId = m.hashId
  where prev.hashId is null
  group by m.ruleId
  order by count(distinct m.hashId) desc
  limit 1;

  set @rulesSelected = @rulesSelected + 1;
end while;

select ruleId from selectedRules;

Ответ 3

Хотя я пришел из мира PostgreSQL, я нашел этот вопрос действительно интересным и не торопился изучить его.

Я разбил весь процесс на 2 подпрограммы:

• во-первых, требуется подзапрос (или функция), что для данной комбинации ruleId (array) будут возвращены все возможные (массивные) + элементы с идентификатором ruleId с количеством уникальных hashId (count), найденным для записи;
• тогда следует запросить max (count) из # 1 и получить список комбинаций array + ruleId из # 1. Для этого я использовал рекурсивную функцию. Если текущий уровень рекурсии соответствует требуемому количеству правил (10), возвращайте найденные комбинации array + ruleId, иначе рекурсивно переходите к этому же шагу (# 2), предоставляя найденную комбинацию в качестве входных данных.

В результате вторая функция вернет все комбинации, которые дадут вам максимальное количество уникального hashId для данного значения count.

Здесь приведен код, который будет создавать тестовую настройку, PostgreSQL 9.1. Поскольку исходный вопрос для MySQL, я прокомментирую, что там происходит:

create table matches (
  id        int4   not null,
  hashId    int4   not null,
  ruleId    int4   not null,
  primary key (id)
);

insert into matches
SELECT generate_series(1,200), (random()*59+1)::int4, (random()*19+1)::int4;
-- This query will generate a 200-rows table, with:
-- - first column having values in 1-200 range (id)
-- - second column will have random numbers in 1-60 range (hashId)
-- - third column will have random numbers in 1-20 range (ruleId)

Функция для фазы 1 (довольно простая):

CREATE OR REPLACE FUNCTION count_matches(i_array int4[],
    OUT arr int4[], OUT cnt int4) RETURNS SETOF record
AS $$
DECLARE
    rec_o   record;
    rec_i   record;

BEGIN
    -- in the outer loop, we're going over all the combinations of input array
    -- with the ruleId appended
    FOR rec_o IN SELECT DISTINCT i_array||ruleId AS rules
        FROM matches ORDER BY 1
    LOOP
        -- in the inner loop we're counting the distinct hashId combinations
        -- for the outer loop provided array
        -- and returning the new array + count
        FOR rec_i IN SELECT count(distinct hashId) AS cnt
            FROM matches WHERE ruleId = ANY(rec_o.rules)
        LOOP

            arr := rec_o.rules;
            cnt := rec_i.cnt;
            RETURN NEXT ;
        END LOOP;
    END LOOP;

    RETURN ;
END;
$$ LANGUAGE plpgsql;

Если вы дадите пустой массив в качестве входных данных для этой функции, вы получите те же результаты, что и в случае № 1 начального вопроса:

SELECT COUNT(*), ruleId FROM `beer`.`matches` GROUP BY ruleId ORDER BY COUNT(*);
-- both queries yields same results
SELECT cnt, arr FROM count_matches(ARRAY[]::int4[]);

Теперь основная рабочая функция:

-- function receives 3 parameters, 2 of them have default values
-- which makes it possible to query: max_matches(10)
-- to obtain results from the initial question
CREATE OR REPLACE FUNCTION max_matches(maxi int4,
    arri int4[] DEFAULT array[]::int4[],
    curi int4 DEFAULT 1, OUT arr int4[]) RETURNS SETOF int4[]
AS $$
DECLARE
    maxcnt  int4;
    a       int4[];
    b       int4[];

BEGIN
    -- Fall out early for "easy" cases
    IF maxi < 2 THEN
        RAISE EXCEPTION 'Too easy, do a GROUP BY query instead';
    END IF;

    a = array[]::int4[];

    -- first, we find out what is the maximal possible number of hashIds
    -- on a given level
    SELECT max(cnt) INTO maxcnt FROM count_matches(arri);
    -- then we check each combination that yield the found number
    -- of unique hashIds
    FOR arr IN SELECT cm.arr FROM count_matches(arri) cm
       WHERE cm.cnt = maxcnt
    LOOP
        -- if we're on the deepest level of recursion,
        -- we just return back the found combination
        IF curi = maxi THEN
            RETURN NEXT ;
        ELSE
            -- otherwise we ask further down
            FOR b IN SELECT * FROM max_matches(maxi, arr, curi+1) LOOP
            -- this loop and IF clause are required to eliminate
            -- equal arrays, so that if we get {6,14} and {14,6} returned
            -- we will use only one of the two, as they're the same
                IF NOT a @> b THEN
                    a = array_cat(a, b);
                    RETURN QUERY SELECT b;
                END IF;
            END LOOP;
        END IF;
    END LOOP;

    RETURN ;
END;
$$ LANGUAGE plpgsql;

К сожалению, этот подход требует много времени. Для моей тестовой установки у меня есть следующая производительность, которая кажется излишней, чтобы потратить 8 секунд на 200-строчную "большую" таблицу.

select * from max_matches(10);
             arr
-----------------------------
 {6,14,4,16,8,1,7,10,11,18}
 {6,14,4,16,8,1,7,11,12,18}
 {6,14,4,16,8,7,10,11,15,18}
 {6,14,4,16,11,10,1,7,18,20}
(4 rows)

Time: 8034,700 ms

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

И спасибо за вопрос, у меня было очень хорошее время, пытаясь его решить!

Ответ 4

Подход, который, как я думаю, будет работать лучше всего для этого, основан на той же логике/методе, который использует анализ многофакторных кофакторов в статистической системе.

То есть вместо того, чтобы пытаться решить неотъемлемую комбинаторную проблему "Какая комбинация из 10 факторов (или" правил "для вашей проблемы) из существующих правил, лучше всего подходит какой-то критерий?", она постепенно отвечает гораздо проще вопрос "Учитывая то, что у меня уже есть, какой дополнительный фактор (" правило ") лучше всего улучшает, насколько хорошо выполняется критерий?"

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

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

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

• Это O (n * k), где 'k' - количество правил, которые вы хотите найти. Комбинаторные подходы имеют тенденцию быть не полиномиальными, как O (2 ^ n) или O (n!), Которые крайне нежелательны, по производительности.

• Возможно, что этот подход не даст абсолютных * лучших * 10 правил для вашего критерия. Однако, по моему опыту, он обычно делает очень в реальных случаях таких проблем. Обычно это не более одного или двух правил с абсолютного 10 лучших.

• Код SQL для инкрементного поиска очень прост (у вас уже есть большая часть его). Но код SQL, который на самом деле делает это N = 10 раз, по своей сути является процедурным и, следовательно, требует менее стандартных/более специфических частей SQL (перевод: я знаю, как это сделать в TSQL, но не в MySql).

  /li >

Ответ 5

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

Идея зверски проста: создайте представление, чтобы явно показать все возможности, а затем объединить все их и найти лучшее, заказав. Аналогичные правила допускаются, поскольку определенное правило само по себе может быть более эффективным, чем комбинация других.

На основе таблицы, аналогичной той, которую вы описали выше, с столбцами с именем "id", "hash_id" и "rule_id", создайте вспомогательный вид (таким образом, проще протестировать/отладить), используя следующий выбор:

SELECT `t1`.`hash_id` AS `h1`,`t2`.`hash_id` AS `h2`,`t3`.`hash_id` AS `h3`,`t1`.`rule_id` AS `r1`,`t2`.`rule_id` AS `r2`,`t3`.`rule_id` AS `r3` from (`hashTable` `t1` join `hashTable` `t2` join `hashTable` `t3`)

В приведенном выше представлении настроено создание таблицы тройного соединения. Вы можете добавить t4.hash_id as h4,t4.rule_id as r4 в SELECT и join hashTable t4 в FROM, чтобы добавить четвертое соединение и т.д. До 10.

После создания представления следующий запрос дает комбинацию из 2 лучших правил с их явным отображением:

select group_concat(distinct h1),concat(r1, r2) from (select distinct h1,r1,r2 from hashView union distinct select distinct h2,r1,r2 from hashView) as uu group by concat(r1,r2)

Если вам не нужно видеть покрытие хэшей, это может быть лучше:

select count(distinct h1) as cc,concat(r1, r2) from (select distinct h1,r1,r2 from hashView union distinct select distinct h2,r1,r2 from hashView) as uu group by concat(r1,r2) order by cc

Добавление третьего соответствия правила просто, добавив h3 и r3 в объединение и группировку, используя его:

select count(distinct h1),concat(r1, r2, r3) from (select distinct h1,r1,r2,r3 from hashView union distinct select distinct h2,r1,r2,r3 from hashView union distinct select distinct h3,r1,r2,r3 from hashView) as uu group by concat(r1,r2,r3)

Если вам не нужна опция выбора количества совпадающих верхних правил, вы можете выполнить concat() в самом представлении и сэкономить некоторое время на союзных запросах.

Возможное увеличение производительности - исключение перестановленных идентификаторов правил.

Все вышеперечисленные были проверены только с использованием идентификаторов идентификаторов с одной цифрой, поэтому вместо concat() вы, вероятно, должны использовать concat_ws(), как это, для предварительно согласованного представления:

select `t1`.`hash_id` AS `h1`,`t2`.`hash_id` AS `h2`,`t3`.`hash_id` AS `h3`,concat_ws(",",`t1`.`rule_id`,`t2`.`rule_id`,`t3`.`rule_id`) AS `r` from (`hashTable` `t1` join `hashTable` `t2` join `hashTable` `t3`)

И затем запрос объединения:

select count(distinct h1) as cc,r from (select distinct h1,r from hashView union distinct select distinct h2,r from hashView union distinct select distinct h3,r from hashView) as uu group by r order by cc

Знайте, если это решает проблему или если есть дополнительные ограничения, которые ранее не были раскрыты.

В зависимости от количества правил и хэшей вы также можете всегда отменить отношение правила ↔ hash и вместо этого создавать представления, основанные на хеше.

Лучшей идеей, вероятно, является сочетание этого подхода с эвристикой в ​​реальной жизни.