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

Question

Мой стол:

CREATE TABLE `beer`.`matches` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `hashId` int(10) unsigned NOT NULL,
  `ruleId` int(10) unsigned NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;

Если хеш соответствует правилу, в этой таблице есть запись.

1) Подсчитайте, сколько существует хеш-идентификаторов для каждого уникального идентификатора правила (AKA «сколько хеш-значений соответствует каждому правилу»)

SELECT COUNT(*), ruleId FROM `beer`.`matches` GROUP BY ruleId ORDER BY COUNT(*)

2) Выберите 10 лучших правил (ruleIds), то есть выберите 10 правил, которые в совокупности соответствуют наибольшему количеству уникальных хэшей. Это означает, что правило, которое соответствует большому количеству хэшей, не обязательно является хорошим правилом, если другое правило охватывает все те же хэши. В основном я хочу выбрать 10 ruleIds, которые ловят самые уникальные hashIds.

?

РЕДАКТИРОВАТЬ : По сути, у меня есть неоптимальное решение в PHP / SQL здесь , но в зависимости от данных это не обязательно дает мне лучший ответ на вопрос 2) , Я был бы заинтересован в лучшем решении. Прочитайте комментарии для получения дополнительной информации.

Answer 1

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

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

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

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

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

---

РЕДАКТИРОВАТЬ

---

Вот непроверенная реализация решения, где ruleIds выбирается по 1 за раз, с каждой итерациейвыбор того, что 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;

Answer 2

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

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

  m! / (n! (mn)!) => м! / (10! (м-10!)) где!Факториал: м!= 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.Во всяком случае, у основного все еще гигантская стоимость.

Answer 3

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

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

---

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

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

---

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

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

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

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

Answer 4

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

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

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

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

Вот код, который создаст тестовую установку, протестированную в 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

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

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

Answer 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 к ОТ, чтобы добавить четвертое соединение и т. Д. До 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

Добавить 3-е совпадение правил просто, добавив 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

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

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

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