Reimplementacja agregacji

[piotr-ptaszynski]

Myślę, że warto dla tego nietrywialnego zagadnienia założyć wątek, zwłaszcza, że mam wątpliwości co do nie których aspektów agregacji.

Motywacja

Stary Sealious nie posiada właściwych implementacji get_pre_aggregation_stage dla strategii dostępu and oraz or i chcemy to zmienić - jest duża szansa, że będzie to można wykorzystać w nowej wersji frameworka. Problem polega na tym, że and oraz or mogą przyjąć wiele strategii dostępu AS z wieloma lookupami i matchami, które mogą się powtarzać w różnych AS. W ramach optymalizacji każdy $match chcemy wykonać możliwie najwcześniej, a $lookup jak najpóźniej. Doszliśmy do wniosku, że problem sprowadza się do acyklicznego grafu zależności - trzeba będzie zbudować graf, zapuścić jakiś algorytm i powinno zadziałać

Zarys implementacji

Chcemy zakryć szczegóły implementacji obiektami Query zdefiniowanymi następująco:

• lookup()
• match()
• execute() - to jeszcze do ustalenia, bo może wolimy zewnętrzną funkcję execute_query(query)

Zatem przykładowy kod może wyglądać następująco:

const query = new Query("books");
query.lookup({
	from: "numbers",
	localField: "body.number",
	foreignField: "sealious_id",
	as: "number",
});
query.match({ "number._id": { $exists: true } });
query.execute();

Wątpliwości

• czy sytuacja kiedy najpierw zostanie wywołany match na jakimś fieldzie, a dopiero później lookup z as z tym fieldem jest błędem?
• co jeżeli ponownie wywoływany jest lookup z takimi samymi from, localField i foreignField, ale z innym as? Chyba można by wtedy dokonać konwersji nazwy pola na danym lookupie i matchach odwołujących się do nowej nazwy, tylko pytanie czy warto.

[kuba-orlik]

@piotr-ptaszynski

czy sytuacja kiedy najpierw zostanie wywołany match na jakimś fieldzie, a dopiero później lookup z as z tym fieldem jest błędem?

Trudno, aby taka sytuacja nastąpiła - bo aby $match mógł polegać na jakimś $lookupie, potrzebne jest jego id - pamiętajmy, że metoda lookup powinna zwracać id lookupa, które jest jego hashem/skrótem. Dlatego match polegający na lookupie wyglądałby tak:

const query = new Query("books");

const author_lookup_id = query.lookup({
	from: "authors",
	localField: "body.author",
	foreignField: "sealious_id",
	as: "author",
});

query.match({
	lookups: { [author_lookup_id]: { "body.name": "Mickiewicz" } },
});

To właściwie odpowiada także na Twoją drugą wątpliwość - dwa lookupy różniące się tylko as powinny dostać takie samo id - dzięki temu zostaną wysłane do bazy danych tylko raz

---

EDIT: myślę też, że warto poczytać artykuł o tym, jak Mongo automatycznie optymalizuje kroki agregacji:

Aggregation Pipeline Optimization — MongoDB Manual

Niestety nie robią za dużo w kwestii przemieszczania $match przed $lookupy. Ale warto zwrócić uwagę, że tworzymy sobie więcej okazji do optymalizacji, jeżeli rozbijamy wielopolowe $matche na kilka osobnych. Czyli jeżeli np. mamy $match, który polega zarówno na lookupie, jak i na normalnym polu:

query.match({
	"body.year": 1834,
	lookups: { [author_lookup_id]: { "body.name": "Mickiewicz" } },
});

Można rozbić (automatycznie) na osobne matche:

[
	{ $match: { "body.year": 1834 } },
	{
		$match: { lookups: { [author_lookup_id]: { "body.name": "Mickiewicz" } } },
	},
];

Dzięki temu algorytm porządkujący kroki agregacji będzie mógł część tego matcha dać przed lookupa. A mongo i tak skleja sąsiadujące $matche, więc nie będzie problemu z wydajnością

[kuba-orlik]

Trzeba też przemyśleć sprawę tego, w jaki dokładnie sposób będziemy łączyć dwie listy kroków agregacji spójnikami and lub or.

O ile w przypadku and możemy po prostu skleić dwie tablice i dowolnie mieszać kroki $match i $lookup, o tyle w przypadku or nie jest już tak fajnie, gdyż nie możemy korzystać z faktu, że gdy jedna z łączonych orem strategii dostępu odrzuci zasób, nie musimy już go sprawdzać drugą z łączonych strategii dostępu.

I tutaj ponownie przydaje nam się trochę wiedzy z uczelni Istnieje sposób na rozbicie dużej alternatywy (OR) na kilka mniejszych klauzul, które można połączyć spójnikiem AND, przy 100% zachowaniu ich wartości logicznej. Możemy skorzystać z Koniunkcyjnej Postaci Normalnej:

Koniunkcyjna postać normalna

Dzięki temu zmieniamy alternatywę (gdzie głównym operatorem jest OR) na koniunkcję (gdzie głównym operatorem jest AND) i możemy wtedy dowolnie zmieniać kolejność kolejnych kroków agregacji. Przykładowo: z wyrażenia, które jest jednym wielkim krokiem agregacji:

or(and(a,b), and(c,d))

możemy zrobić tożsame wyrażenie w postaci koniunkcyjnej:

and(or(and(a,b), c), or(and(a,b), d))

O ile taki zapis jest trochę redundantny (jest trochę powtórzeń), to głównym operatorem jest już and - dzięki temu możemy doklejać śmiało inne klauzule, zmieniać ich kolejność i dalej optymalizować zapytanie.

O ile tego typu optymalizacja jest jak najbardziej w naszym zasięgu, o tyle z uwagi na czas póki co dla strategii dostępu or zrobiłbym następujący algorytm:

1. wszystkie lookupy na początek agregacji;
2. wszystkie matche sklejone $or-em tuż po nich.

[piotr-ptaszynski]

Kurczę faktycznie - zupełnie o tym nie pomyślałem. Rozwiązanie z grafem jest świetne dla and ale lipne dla or. Jedno rozwiązanie to jest to co proponujesz, a drugie co mi przyszło do głowy to skorzystanie z prawa de Morgana, tylko pytanie czy na teraz.

or(and(a,b), and(c,d)) <=>  not(and(not(and(a,b)), not(and(c,d))))

Ale rozumiem, że dla and mogę zrobić to na grafie?

[kuba-orlik]

Na pewno graf przyda sie zarowno do or, jak i do and - tylko w rozny sposob. Byc moze po prostu najpierw przerobimy or na and, a potem zastosujemy metode z grafem.

Co do de Morgana - jezeli uda sie to tak zrobic, ze glownym operatorem jest AND, a nie NOT, to ma to przyszlosc Trzeba bedzie tez starannie przejrzec implementacje NOT-a. Czuje, ze KPN i de Morgan nie wykluczaja sie

[kuba-orlik]

Mysle, ze jest tutaj tyle do roboty, ze mozna sie nia podzielic Pomysle nad wyodrebnieniem zadan, co Ty na to?

[piotr-ptaszynski]

Pewnie, że możemy się podzielić.

Algorytm dla strategii AND

W zasadzie problem sprowadza się do odpalenia algorytmu breadth-first search na odpowiednio zbudowanym grafie. Główną trudnością jest właśnie odpowiednie budowanie grafu zależności.

1. Wstawiamy lookupy oraz matche
   1.1. Jeżeli węzeł jest typu match i podano, że jest zależny od lookupa L1 to tworzymy łuk z L1 do nowowstawionego węzła
2. Odwiedzamy wszystkie węzły typu lookup i tworzymy do nich łuki z matchów z innych grafów
   2.1 Przykład: Mamy łuk z M2 do L1 oraz z L1 do M1 i pojedyncze węzły M3 oraz M4 tworzące osobne grafy. Tworzymy zatem łuki z M3 i M4 do L1
   2.2 Węzły typu lookup musimy odwiedzić w kolejności od najmniejszej maksymalnej odległości do początku grafu. Jeżeli tak nie zrobimy istnieje ryzyko, że przy odpaleniu BFSa odwiedzimy jakiś węzeł z pominięciem jego zależności i agregacja się zrypie
3. Idziemy po grafie BFSem - budowa grafu sprawi, że najpierw będziemy odwiedzać wszystkie możliwe matche na danym poziomie, a dopiero później lookupy, co jest kolejnością zoptymalizowaną

[kuba-orlik]

Znalazłem podobny do BFS-a algorytm, w którym nie musimy martwić się o spójność grafu - co powinno uprościć zadanie

https://en.wikipedia.org/wiki/Topological_sorting#Kahn’s_algorithm

Wydaje się być swojego rodzaju uogólnieniem BFS-a na skierowane grafy, które niekoniecznie są spójne

[kuba-orlik]

Rozpisałem ten temat na taski:

https://hub.sealcode.org/T800

Na sealcallu obgadamy, jak się nimi podzielić

[piotr-ptaszynski]

Strategia AND

Problem nie polega na sortowaniu topologicznym (DFS, a nie BFS może posłużyć do tego), ale BFS też się nie do końca sprawdzi. Tzn. to nad czym myślę będzie jak sądzę uogólnionym BFSem. Postaram się wieczorem opisać o co chodzi.

Strategia OR

Wygląda na to, że jednak da się to zrobić w mongo - raczej dosyć hakierskie, ale pozostawiam Wam do oceny (zapytanie jakie jest w niniejszym przykładzie da się w miarę łatwo skonstruować automatycznie).

db.books.aggregate([
	{$facet: {
		1: [
			{$lookup: {
				from: "artists",
				localField: "artist",
				foreignField: "_id",
				as: "artist_item" }
			},
			{$unwind: "$artist_item"},
			{$match: {"artist_item._id": {$lte: 2}}}
		],
		2: [
			{$lookup: {
				from: "artists",
				localField: "artist",
				foreignField: "_id",
				as: "artist_item" }
			},
			{$unwind: "$artist_item"},
			{$match: {"artist_item._id": {$gte: 2}}}
		]	
	}},
	{$project: {results: {$concatArrays: ["$$CURRENT.1", "$$CURRENT.2"]}}},
	{$project: {
		uniqueResults: {
			$reduce: {
				input: "$results",
				initialValue: {ids: [], items: []},
				in: {
					items: {
						$cond: [
							{$in: ["$$this.sealious_id", "$$value.ids"]},
							"$$value.items",
							{$concatArrays: ["$$value.items", ["$$this"]]}
						]
					},
					ids: {$setUnion : ["$$value.ids", ["$$this.sealious_id"]]}
				}
			}
		}
	}},
	{ $unwind : "$uniqueResults.items" },
	{ $replaceRoot : {newRoot: "$uniqueResults.items" }}
]);

Nie wiem na ile jest to wydajne, ale działa

[kuba-orlik]

(Nie do końca rozumiem, jak działa ten trick z $facet, ale mega jaram się, że mamy rozwiązanie tego - dobra robota! :D)

Ok, z uwagi na presję czasu zróbmy tak: stwórzmy najpierw niezoptymalizowane wersje AND i OR:

• dla AND - po prostu sklejamy (concat) tablice z krokami agregacji, bez sortowania i conietylko;
• dla OR - robimy rozwiązanie z $facet, które przedstawiłeś powyżej.

Potem będziemy myśleć o optymalizacji - a nóż okaże się, że w ogóle optymalizować nie trzeba

Odzwierciedliłem to w Sealhubie: ⚓ T801 Interfejs "Query" (z metodami "and" i "or")

[piotr-ptaszynski]

Najlepsze jest to, że myślałem cały czas o tym grafie dla AND (zresztą sądzę, że wymyśliłem), ale jak rano się obudziłem to wyglądało na to, że mózg w nocy postanowił popracować nad OR - po prostu rano usiadłem, naklepałem to zapytanie i… zadziałało xD

[kuba-orlik]

To jest niesamowite, ile rzeczy jesteśmy w stanie przepracować “z tyłu głowy”

Jak się dzielimy? Chcesz wziąć T801, czy może wolisz abym ja to zrobił, a Ty wziąłbyś T800?

[piotr-ptaszynski]

Strategia AND

Kluczową sprawą w przechodzeniu po grafie zależności będzie fakt, że nie przechodzimy po węzłach pojedynczo, tylko zachowujemy możliwość pójścia dalej z wielu węzłów - można powiedzieć, że idziemy całym frontem (i to się chyba nawet tak fachowo nazywa):

Węzły są sortowane w kolejności dodawania do frontu. O kolejności decyduje topologia grafu (czy istnieje łuk z któregokolwiek węzłów stanowiących front) oraz priorytety przypisane węzłom. Match ma oczywiście wyższy priorytet niż lookup, zatem żaden lookup nie zostanie dodany, dopóki są jeszcze jakieś matche bezpośrednio połączone z frontem.

Na przykładzie dotchczasowa kolejność to L1,M1,M3,L2 a następne węzły jakie możemy odwiedzić to L4 oraz L6 - oba mają ten sam priorytet, więc kolejność ich odwiedzenia jest dowolna. Natomiast jest tutaj (w przyszłości, jeżeli pójdziemy tą ścieżką) pole do optymalizacji, możemy najpierw iść do lookupa, który ma lepsze dla nas poddrzewa.

Graf nie musi być spójny - w dowolnym momencie mamy możliwość wejścia do węzłów, które nie mają poprzedników (tutaj kolejność to np. M1,M6,L1,M2,M5,L3):

Głównym problemem jest dodanie query typu OR - nie możemy go rozbić na pojedyncze lookupy i matche i dodać do grafu, bo po prostu uzyskamy inną agregację niż chcemy. Natomiast wydaje się, że nic nie stoi na przeszkodzie żeby po prostu potraktować cały ten magiczny pipeline z ORa jako jeden element - czyli dodamy kolejny typ węzła:

Pytanie jest co do jego priorytetu. Jeżeli zawiera tylko matche, to rozsądne się wydaje, żeby miał wyższy niż lookup, ale niższy niż pojedynczy match, ale jeżeli zawiera jakieś lookupy to niższy również od lookupa.

[kuba-orlik]

@piotr-ptaszynski

Głównym problemem jest dodanie query typu OR - nie możemy go rozbić na pojedyncze lookupy i matche i dodać do grafu

Hm, można dokonać rozbicia:

1. wyciągamy wszystkie lookupy na zewnątrz or-a
2. rozbijamy or-a zawierającego już same $match-e za pomocą koniunkcyjnej postaci normalnej (jak opisane powyżej)
3. przenosimy wszystkie powstałe w wyniku rozbicia mniejsze $or-y tak, aby te które nie polegają na żadnym lookupie były przed lookupami

[piotr-ptaszynski]

Pytanie czy to na pewno będzie potrzebne, w końcu:

Premature optimization is the root of all evil

Nie twierdzę, że nie będzie warto tego zrobić, ale twierdzę że jeśli się na to zdecydujemy, to zasługuje to na osobnego taska

[kuba-orlik]

Myślę, że to wpisuje się w taska T798 Optymalizacja strategii dostępu “OR” - czy jestem w błędzie?

[piotr-ptaszynski]

Tak, rzeczywiście - po prostu inaczej na to patrzyłem, ale można to zrobić w ramach tego.

[piotr-ptaszynski]

@kuba-orlik (wszystkich innych zainteresowanych też zapraszam oczywiście )

https://hub.sealcode.org/D213#6158

[kuba-orlik]

U, nice catch. Dobrze, że mamy testy! Chyba uda się uniknąć ręcznego sprawdzania, czy łączone query są typu And - zob. komentarz do D213