Najlepsze dopasowanie reguły?

Szukam inspiracji/nazwania problemu/algorytmu dla poniższego przypadku.

Mam tabelę z danymi referencyjnymi/konfiguracją, która ma 25k elementów i zwartość się nie zmienia (zmienia, ale bardzo rzadko).

W aplikacji, per request, dostaję od kilku rekordów do kilkuset tysięcy rekordów do przetworzenia. Rekordy przychodzą z różnymi wartościami atrybutów: r_attr1,r_attr2,r_attr3,r_attr4,r_attr5
Wartość "ANY" w konfiguracji ma specjalne znaczenie i mówi "wszystko jedno jaka wartość atrybutu w rekordzie".

Dla każdego rekordu muszę w konfiguracji wyszukać rekord o najlepszym dopasowaniu (tj. o najmniejszej liczbie atrybutów dopasowanych via "ANY").
Przykład:

rekord=(attr1='X',attr2=1,attr3=A,attr4=B,attr5='C') pasuje do wszystkich Rule#A..D
rekord=(attr1='X',attr2=1,attr3=A,attr4=Z,attr5='D') pasuje tylko do Rule#C

To czego szukam, to struktura danych, która będzie miała najniższą złożoność wyszukiwania najlepszej reguły dla wskazanego rekordu.

Tablica z haszowaniem

Dla każdego atrybutu stworzyłbym tablicę której kluczem jest wartość atrybutu a wartością reguły które posiadają tą wartość. Czyli:

ATTR1[ANY] = A,B,C
ATTR1[X] = D

ATTR2[ANY] = B,C
ATTR2[1] = A,D

itd..

Gdy przychodzi request to sprawdzam co jest pod daną wartością tzn, dla:

rekord=(attr1='X',attr2=1,attr3=A,attr4=B,attr5='C') 

sprawdzam po kolei wszystkie atrybuty:

attr1='X' czyli w tablicy pod 'X' mam D
ale muszę uwzględnić ANY czyli A,B,C

attr2=1 czyli w tablicy pod '1' mam A i D
ale muszę uwzględnić ANY czyli B,C

itd.

Czas dostępu do tablicy to O(1).

Potrzebujesz wykonywać operację typu like?

@Wilktar: tylko to mi daje indeks dla każdego atrybutu, czyli otrzymam 5 zbiorów z regułami i muszę określić:
a) część wspólną
b) uszeregować część wspólną względem ilości "ANY" (to może być atrybutem reguły, liczone na starcie)

To by mi dawało złożoność O( min(#set1, #set2,.., #set5) ). Jest to jakiś wariant do przetestowania.

Użycie haszy może jednak być wolniejsze niż to o czym pisał @Patryk27 (ale post zniknął :-) ) Czyli przeglądanie posortowanej listy. Możliwe, że porównywania wartości będą szybsze niż liczenia hasza.

W każdym razie mam dwa warianty do przetestowania.

yarel napisał(a):

Mam tabelę z danymi referencyjnymi/konfiguracją, która ma 25k elementów i zwartość się nie zmienia (zmienia, ale bardzo rzadko).

To jest tabela w bazie danych, dane w pamięci, w pliku? Bo nie do końca wiedziałem gdzie trzymasz te dane dlatego dałem taki ogólny opis.

Jeżeli to są dane w pamięci to z wyznaczeniem części wspólnej i uszeregowanie nie będzie problemu.

Jeżeli to jest baza danych:

select * from rules 
where 
	attr1 IN ('X', 'ANY') 
	and attr2 IN ( '1', 'ANY')

I mając już te dane w pamięci sprawdzasz która została dopasowana ze względu na najmniejszą ilość ANY (tak chyba byłoby najprościej).

To by dawało złożoność O(1) dla każdego atrybutu dla pięciu byłoby 5 * O(1).
Wyszukiwanie po posortowanym zbiorze to O(log(n)) czyli sumarycznie będzie 5 * O(log(n)). Wyszukiwanie

5 * O(1) vs 5 * O(log(n))

Indeks - w standardowym rozumieniu i implementacji w bazach danych to b-tree czyli wyszukiwanie na poziomie O(log(n)), chyba że mówisz o hash index?

Jeżeli to jest baza danych:

Biorąc pod uwagę per request, dostaję od kilku rekordów do kilkuset tysięcy rekordów do przetworzenia to chyba trochę ciężko będzie w sensownym czasie strzelić kilkaset tysięcy zapytań do bazy danych, c'nie?

@Patryk27: Racja, ale właśnie nie rozumiem o jaki indeks chodzi? Nie potrzebnie się zasugerowałem że chodzi o bazę.

yarel napisał(a):

@Wilktar: tylko to mi daje indeks dla każdego atrybutu, czyli otrzymam 5 zbiorów z regułami i muszę określić:

Przykład kodu w c# wyglądałby mniej więcej tak:

// See https://aka.ms/new-console-template for more information

//List<string> request = new List<string>() { "X", "1", "A", "B", "C" };
List<string> request = new List<string>() { "X", "1", "A", "Z", "D" };

List<Dictionary<string, List<string>>> attributes = new List<Dictionary<string, List<string>>>()
{
    //1 attribute
    new Dictionary<string, List<string>>()
    {
        {"ANY", new List<string>() { "A", "B", "C" } },
        {"X", new List<string>() { "D", } }
    },

    //2 attribute
    new Dictionary<string, List<string>>()
    {
        {"ANY", new List<string>() { "B", "C" } },
        {"1", new List<string>() { "A", "D" } }
    },

    //3 attributes
    new Dictionary<string, List<string>>()
    {
        {"ANY", new List<string>() { "B", "C" } },
        {"A", new List<string>() { "A", "D" } },
    },

    //4 attributes
    new Dictionary<string, List<string>>()
    {
        {"ANY", new List<string>() { "C" } },
        {"B", new List<string>() { "A", "B", "D" } },
    },

    //5 attributes
    new Dictionary<string, List<string>>()
    {
        {"ANY", new List<string>() { "C" } },
        {"C", new List<string>() { "A", "B", "D" } }
    },
};

List<List<string>> rules = new List<List<string>>();
for (int i = 0; i < request.Count; i++)
{
    rules.Add(GetRulesForAttribute(request, attributes, i));
}

List<string> result = rules[0];
for (int i = 1; i  < request.Count; i++)
{
    result = result.Intersect(rules[i]).ToList();
}

foreach(var rule in result)
{
    Console.WriteLine(rule);
}

Console.ReadLine();

static List<string> GetRulesForAttribute(List<string> request, List<Dictionary<string, List<string>>> attributes, int i)
{
    List<string> rules = new List<string>();
    var value = request[i];
    if (attributes[i].ContainsKey(value))
    {
        rules.AddRange(attributes[i][value]);
    }

    if (attributes[i].ContainsKey("ANY"))
    {
        rules.AddRange(attributes[i]["ANY"]);
    }
    return rules;
}

Zostaje jeszcze kwestia zliczania ile razy dla danej reguły było "ANY".

1. Wszystko w pamięci. Jeśli chodzi o indeks, to w znaczeniu takim jak w skorowidzach nazw w książce ( pojęcie -> numery stron na których występuje). Tworzenia takiego hashsetu dla atrybutu to tworzenie indeksu. Logicznie dla 5 atrybutów tworzymy 5 indeksów i bierzemy ich iloczyn logiczny (AND). Tak zrozumiałem propozycję algorytmu.

2. Moja obecna implementacja daje średnio 8.75ms per lookup, wstępna implementacja w oparciu o hashset + przecięcie zbiorów -> 3ms per lookup. Wstępna, bo nie przetestowana pod kątem poprawności i nie wpięta w całość przetwarzania. Jest lepiej, ale celuję wyżej ;) Tu widzę pewne możliwości poprawy, ale kosztem większego nakładu pracy i braku pewności czy będzie lepiej (zamiast list trzymać wektory bitów i liczyć, że operacje AND na wektorach bitów będą realizowane szybciej).

1. Tak, dobrze się zrozumieliśmy :)
2. Wektory bitowe powinny pomóc ale na ile to ciężko powiedzieć :), atrybutów jest faktycznie 5? Czy 5 jest tylko dla przykładu?

yarel napisał(a):

ATTR1	ATTR2	ATTR3	ATTR4	ATTR5	OUTPUT	Rule
ANY	1	A	B	C	2	Rule#A
ANY	ANY	ANY	B	C	3	Rule#B
ANY	ANY	ANY	ANY	ANY	5	Rule#C
X	1	A	B	C	8	Rule#D

Dla każdego rekordu muszę w konfiguracji wyszukać rekord o najlepszym dopasowaniu (tj. o najmniejszej liczbie atrybutów dopasowanych via "ANY").

Żeby to osiągnąć to można wpierw posortować tą tabelę tak że reguły które mają więcej ANY były by na końcu, czyli kolejność: D,A,B,C:

Jeżeli na podstawie takiej tabeli zbuduję się (indeks/słownik/hashset/tablica haszowaniem - jak zwał tak zwał :))

To każdy element w indeksie będzie w optymalnej kolejności (wpierw reguły który mają mniej ANY). Jeżeli weźmiemy z tych zbiorów część wspólną (nie zmieniając kolejności) to otrzymamy znowu optymalną kolejność.

Jednorazowe posortowanie tablicy przed budowaniem tablicy z haszowaniem powinno rozwiązać problem szukania najlepszej reguły.

Niestety problemem jest jeżeli tabela jest aktualizowana, ale jeżeli nie dzieję się to czysto to możliwe że najlepiej będzie przebudować całą tabelę jeszcze raz niż bawić się w aktualizowanie.

Jeżeli weźmiemy z tych zbiorów część wspólną (nie zmieniając kolejności) to otrzymamy znowu optymalną kolejność.

Hmm, w jaki sposób możesz zbudować hashset/btreeset bez zmiany kolejności elementów / tak, aby iterowanie nad takim zbiorem zwróciło elementy w oryginalnej kolejności?

Tzn. zgaduję, że można by trzymać drugi zbiór, w stylu element => pozycja w oryginalnej liście...

Spróbuj zrobić coś takiego:

SELECT 
	rt.RULE,
	(rt.priority1 + rt.priority2 + rt.priority3) AS priority
FROM (
	SELECT inner.*, 
		IF (inner.ATTR1 = 'ANY', 0, 4) priority1, 
		IF (inner.ATTR2 = 'ANY', 0, 2) priority2,
		IF (inner.ATTR3 = 'ANY', 0, 1) priority3
	FROM RulesTable inner 
	WHERE 1=1
	AND (ATTR1 = :attr1 OR ATTR1 = 'ANY') 
	AND (ATTR2 = :attr2 OR ATTR2 = 'ANY') 
	AND (ATTR3 = :attr3 OR ATTR3 = 'ANY') 
) rt
ORDER BY priority DESC;

I wyciągnij sobie pierwszy wiersz. W zależności od składni możesz zmienić sobie IFa na CASE, ewentualnie zrobić to jakoś mądrzej jak twoja baza ogarnia coś ciekawszego.
Oczywiście założyłem, że ATTR1 jest najbardziej priorytetowy, ATTR3 - najmniej.

Można to oczywiście optymalizować, tj. dorzucić kolumnę z priorytetem wyliczaną wcześniej.

@wartek01: mam praktycznie identyczną implementację w in-memory database :-) Niestety jest to wąskie gardło na ścieżce przetwarzania i dlatego szukam alternatywy.

Problemem z in-memory db jest to, że robi hash-joina (prawidłowo), ale ilość elementów wynikowych + FILTR ( (r.ATTR1 = '*' or r.ATTR1 = d.ATTR1)) wychodzi słabiej niż oczekuję.
Idę w kierunku takim, żeby nie robić tego hash joina, tylko dla każdego rekordu wołać funkcję, która wyciągnie odpowiednią regułę dla atrybutów rekordu (z nadzieję, że przy odpowiedniej implementacji funkcji będzie to szybsze niż hashjoin + filtr)

select * from (
	select
		d.*,
		r.*
		row_number() over (
							partition by d.record_id, r.rule_type /* rule_type to coś innego niż record_type */
							order by 
										decode(r.ATTR1,'*',0,1) + 
										decode(r.ATTR2,'*',0,1) + 
										decode(r.ATTR3,'*',0,1) + 
										decode(r.ATTR4,'*',0,1) + 
										decode(r.ATTR5,'*',0,1) 
		) rule_priority
	from data d
	inner join  rules r on 
	       r.RECORD_TYPE = d.RECORD_TYPE 
	  and (r.ATTR1 = '*' or r.ATTR1 = d.ATTR1)
	  and (r.ATTR2 = '*' or r.ATTR2 = d.ATTR2)
	  and (r.ATTR3 = '*' or r.ATTR3 = d.ATTR3)
	  and (r.ATTR4 = '*' or r.ATTR4 = d.ATTR4)
	  and (r.ATTR5 = '*' or r.ATTR5 = d.ATTR5)
	)
) where rule_priority=1

To pytanie zmienia się do "dlaczego taki prosty join jest wąskim gardłem". Te pięć kolumn nie powinno być jakieś superciężkie, natomiast kawałek, który wrzuciłeś stworzy ci w pamięci tabelę 25 tys. x count(d.record_id). Czyli jak przyjdzie ci np. 100 tys. rekordów to w pamięci stworzy ci 2,5 miliarda rekordów - a trzeba pamiętać, że czasem przerobienie miliarda rekordów może trwać dłużej niż przerobienie miliona rekordów tysiąc razy. Zwłaszcza, gdy mówimy o in-memory db gdzie nie ma narzutu na IO, ale za to pamięć bywa wąskim gardłem.

W pierwszej kolejności sprawdziłbym, czy robienie tego w mniejszych batchach nie załatwi sprawy (nawet wołanie zapytania dla każdego rekordu oddzielnie).

Pozwolę sobie zuważyć, motywując to lematem, że nie ma jednego dobrego algorytmu i struktury danych do każdego typu danych które byłyby tak samo efektywne na wszystkich maszynach, że brak jest dość istotnych informacji.

1. W czymś konkretnym? Środowisko, język itd - czy tworzenie od podstaw wchodzi w grę czy ma to być jakiś dialekt SQL dla konkretnego środowiska czy szyjesz jakieś bespoke pod zadane parametry?
2. Na czym to ma działać? Jakie gabaryty maszyny - jakiś mocniejszy serwer z hektolitrami RAM i setkami rdzeni CPU czy stacja robocza, a może coś bliższe do systemu sterowania czymś czy kasy fiskalnej?
3. Czy istnieją jakieś z góry dane lub praktyczne z natury źródła danych limity w ilości danych? Czy podane 25k to jakiś typowy rozmiar, czy maksymalnie skrajny przypadek?
4. Czy dane mają jakąś znaną mniej więcej entropię/gęstość czy jakie tam u ciebie metryki da się przyblizyć lub określić teoretycznie lub empirycznie?
5. Jak często coś jest wyszukiwane? Czy to ma być katowane tysiąc odpytań na minutę, czy raz na kilka-kilkanascie minut.
6. Czy dane są aktualizowane raz na kilka dni czy napływają równolegle do zapytań i musi to być brane pod uwagę.

Niestety "bardzo rzadko" będzie co innego oznaczało dla różnych osób.

Jak masz kilka ciężarówek RAM do dyspozycji to możesz tworzyć sobie wszlkiej maści struktury trzymające kolejność przeszukiwania po różnych atrybutach jeśli istnieje jakieś konkretne uporządkowanie możliwe do realizacji po tym atrybucie.

Jak możliwościom maszyny bliżej do pudełka na buty to trzebe będzie jak już wspomniał @wartek01 "kroić". Inna sprawa jak masz coś na 2 Terabajty RAM i możesz tam sobie w pamięci trzymać różne złożenia przez dłuższy czas jeśli masz tylko epizodyczne updaty bazy raz na miesiąc.

Jeśli jakieś dane są bardziej "popularne" możesz zaimplementować jakiś cache który trzyma sobie uporządkowane dane i odpytuje resztę większej bazy tylko jak nie znajdzie odpowiedzi w cache.

Czy interesuje cię weryfikacja poprawności danych i wykrywanie bitflipów czy też działasz na RAM ze sprzętowym ECC i jemu zostawiasz martwienie się o to. Czy też można kompletnie tą kwestię olać.

I tak dalej. I tak dlej. Im więcej sobie jesteś w stanie zadać tego typu pytań tym potencjalnie bliżej będziesz do odpowiedzi. Potencjalnie.