Page MenuHomeSealhub

Optimize db queries combined with AND
ClosedPublic

Authored by piotr-ptaszynski on Mar 30 2018, 06:09.

Details

Summary

Ref T799 T800

Add AllowAll and DenyAll as seperate classes

Add optimization for and

Apply the rest of suggestions

Add final optimization for and

Apply edge case fixes

This time merge properly

Diff Detail

Repository
rS Sealious
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
piotr-ptaszynski requested review of this revision.Mar 30 2018, 06:09
piotr-ptaszynski added a reviewer: Unknown Object (Project).Mar 30 2018, 06:10
  • Remove package-lock from diff
kuba-orlik requested changes to this revision.Apr 4 2018, 14:39
kuba-orlik added a subscriber: kuba-orlik.
kuba-orlik added inline comments.
lib/app/base-chips/access-strategy-types/and.js
18–24

Albo

return new Query.and(...queries)

;)

lib/app/base-chips/access-strategy-types/and.subtest.js
28

(should) przydałoby się dla czytelności opisać także te wewnętrzne funkcje:

collection-and(nested-and(allow, public), nested-or(allow, noone))
lib/app/base-chips/access-strategy-types/and_or_strategy_helpers.js
1–13 ↗(On Diff #722)

Ten plik nie jest używany, można go usunąć ;)

lib/datastore/graph.js
9

(could) Korzystamy tutaj z macierzy sąsiedztwa - możnaby to przerobić tak, aby po prostu utworzyć małą klasę "GraphNode", która miałaby swoje parents i children

45

(should) skoro nie robimy tego rekurencynie, to rozbicie na bestFirstSearch i _bestFirstSeacth możemy usunąć ;) Podobnie dla reszty par funkcji _fn i fn

134–147

(should) highest jest tutaj mylące, bo szukamy takiego node'a, gdzie priorytet ma najniższą liczbową wartość. albo należy odwrócić porządek priorytetów, albo zmienić tutaj nazewnictwo - np. na "best_priority", albo zmienić priority na weight

lib/datastore/query.js
16–19

Dlaczego nie zwracamy tutaj już this? Nie można przez to chainować, prawda?

134

Plik query.js stał się bardzo duży. Warto AND przenieść do osobnego pliku. Jeżeli pojawią się cykliczne zależności, to pomoże trick:

module.exports = Query;

Query.And = require("./and.js")

(module.exports przed requirem)

134

Strategii dostępu And brakuje jeszcze trochę elegancji. Podejrzewam że jest to spowodowane tym, że ta klasa ma dużo metod odpowiedzialnych za stwierdzanie, czy dany "stage" znajduje się w grafie itp. Myślę, że jak się je przeniesie do osobnej klasy odpowiedzialnej za pośrednią reprezentację "stage"'ów to niniejsza klasa zyska na elegancji

145–148

(should) dlaczego traktujemy Or wyjątkowo? Myśle, że warto unikać takich przypadków brzegowych ;)

154

(question) Z tego co widzę, nie rozbijamy tutaj query na osobne $match-e, tak jak to ma w przypadku metodu _match. Czy to jest zamierzone?

199

(should) Wciąż myli mi się, czy mamy do czynienia z stage w znaczeniu Mongowym, czy stage w znaczeniu "nasza wewnętrzna reprezentacja kroku agregacji". Myślę, że można to naprawić nazwami zmiennych - stage zostawiłbym do mongowych kroków agregacji, a dla naszej wewnętrznej stworzył nową nazwę - albo nawet klasę

This revision now requires changes to proceed.Apr 4 2018, 14:39
piotr-ptaszynski marked 10 inline comments as done.Apr 14 2018, 15:50
piotr-ptaszynski added inline comments.
lib/datastore/query.js
16–19

Wydaje mi się, że wprowadzało by to za dużo zamieszania. lookup nie może zwracać this, bo musi zwracać odpowiedniego hasza

  • Remove redundant file
  • Make or strategy and its tests more readable
  • Abstract query step from query
kuba-orlik requested changes to this revision.Apr 18 2018, 12:01

Coraz bliżej! Wyłania się bardzo ładna struktura :)

lib/datastore/query-step.js
2

(could) Aby uniknąć luźno wiszącej funkcji, przypiąłbym ją jako statyczną metodę QueryStep.hashBody

5

(should) przydałoby się dodać unorderedObjects: true, aby hash nie był wrażliwy na zmianę kolejności kluczy

15–20

(should) lepiej ustawić jedno API do tworzenia QuerySteps. Proponuję wybrać new QueryStep.Lookup i zrezygnować z QueryStep.makeMatch

24

Dlaczego zwracamy tutaj tablicę? :o Nazwa QueryStep.fromStage sugeruje, że to jest helper tworzący jeden krok

36–48

(should) Ta funkcja ma za dużo odpowiedzialności:

  • filtrowanie;
  • mapowanie;
  • sklejanie wartości dwóch różnych wartości filtra.

Myślę, że zyskałaby na czytelności i ogólności, gdyby jej użycia zastąpić prostym

steps.filter(step=>step instanceof QueryStep.Lookup).map(lookup_handler);
steps.filter(step=>step instanceof QueryStep.Match).map(match_handler);
59

(could) Skoro robimy już inną reprezentację wewnętrzną, to rozważyłbym uczynić unwind jednym z kluczy w body, zamiast osobnym argumentem do konstruktora

lib/datastore/query.js
80

Jeżeli dobrze rozumiem tę funkcję, to imho nazwa _isUnwindStage pasowałaby lepiej ;)

I mam pytanie - dlaczego poniżej sprawdzamy dokładnie wartość .$unwind? Nie wystarczyłoby sprawdzić, czy to pole istnieje?

lib/datastore/query.test.js
4–8

Aby uniknąć powtórzeń, tutaj możemy korzystać z przeniesionej do Query metody statycznej

14

beka :D

51–61

Hm, myślę i myślę i nie mogę zrozumieć, co tu się dzieje :< Jakbyś to opisał własnymi słowami?

lib/datastore/query_and.js
14

(could) można by dodać optymalizację, w której jeżeli którykolwiek element to "deny all", to wszystkie inne matche są wywalane i dalej nieprzyjmowane, a deny all jest pierwszym elementem w pipeline

This revision now requires changes to proceed.Apr 18 2018, 12:01
piotr-ptaszynski marked an inline comment as done.Apr 21 2018, 04:57
piotr-ptaszynski added inline comments.
lib/datastore/query-step.js
5

Nie jest wrażliwy - to domyślne (i zdroworozsądkowe) ustawienie ;)

15–20

Wybacz, ale nie rozumiem tego komentarza, bo odczytuję go w ten sposób, że matche też byśmy mieli tworzyć za pomocą QueryStep.Lookup, a wiem że na pewno nie to miałeś na myśli

24

To dla zapewnienia spójności z matchem. Chodzi o to, że match może mieć postać np.

{$match: {a: {$eq: 1}, {b: {$eq: 2}}}

Czyli zawierać dwa kroki agregacji, a QueryStep z założenia ma zwracać jeden. Alternatywą jest zabronienie przekazywania wielu kroków w obrębie jednego matcha

lib/datastore/query.test.js
51–61

Tak jak mówi komentarz - transformujemy pipeline z którego stworzyliśmy Query, aby był tym czego oczekujemy - czyli pola as przyjmą wartość hashy, a matche złożone, które mają więcej niż 1 krok rozbijamy na takie z pojedynczym krokiem

kuba-orlik added inline comments.Apr 21 2018, 11:41
lib/datastore/query-step.js
15–20

Chodzi o to, że mamy dwa sposoby na tworzenie QuerySteps - jedno z operatorem new QueryStep.Cośtam, a drugie za pomocą metody QueryStep.makeCośtam. Myślę, że warto to ujednolicić np do używania tylko notacji z new

24

Hm, co masz na myśli?

{$match: {a: {$eq: 1}, {b: {$eq: 2}}}

^ to jest jeden krok agregacji, prawda?

lib/datastore/query.test.js
51–61

Myślę, że w tym wypadku lepiej podać bezpośrednio obiekt w takiej formie, w jakiej go oczekujemy - w postaci zwykłego, statycznego obiektu

expected_json = JSON.stringify([{$match: ...}, ...]);

Coprawda będzie to trochę redundantne, ale pomoże czytającemu zrozumieć, co się dzieje (widzimy efekt przed i po)

piotr-ptaszynski marked an inline comment as done.Apr 21 2018, 13:41
piotr-ptaszynski added inline comments.
lib/datastore/query-step.js
24

No nie, a przynajmniej nie chcemy żeby był, bo ogranicza to możliwości optymalizacji. Zauważ, że w wypadku czegoś takiego:

[
	{lookup},
	{
		$match: {
			field: {$eq: 1},
			field_dependent_on_lookup: {$eq: 2},
		}
	},
]

Chcielibyśmy to zoptymalizować do postaci:

[
	{$match: {field: {$eq: 1}}},
	{lookup},
	{$match: {field_dependent_on_lookup: {$eq: 2}}},
]

Tak czy siak gdzieś tego rozbicia będziemy musieli dokonać.

kuba-orlik added inline comments.Apr 21 2018, 16:41
lib/datastore/query-step.js
24

I see. Nie wiedziałem, że używamy rozdrabniania do optymalizacji :D Najs. To kładzie fajny fundament pod optymalizację OR ;)

piotr-ptaszynski marked 18 inline comments as done.Apr 23 2018, 20:33
  • Change standalone function to static method
  • Optimize and query when is populated with deny all
  • Remove disturbing API
kuba-orlik accepted this revision.Apr 28 2018, 18:34

👌 👌 👌 👌 👌

This revision is now accepted and ready to land.Apr 28 2018, 18:34

Niestety optymalizacja nie jest gotowa do lądowania. Odkryłem to przy mergowaniu z alpha przy strategii when - jej testy zaczęły się wysypywać. Zapomniałem zaimplementować dump() dla Query.And, zrobiłem to już u siebie lokalnie, ale to tylko część problemu.

W strategii when mamy następujący fragment:

return new Query.Or(
	new Query.And(
		await special_filter.getFilteringQuery(collection),
		await when_true.getRestrictingQuery(context)
	),
	new Query.And(
		new Query.Not(await special_filter.getFilteringQuery(collection)),
		await when_false.getRestrictingQuery(context)
	)
);

Do tej pory w ogóle nie testowałem przypadku (wiem, mój błąd) że wkładamy Query.And do Query.Or, a okazuje się to dosyć skomplikowane. Rozwiązanie jakie przychodzi mi w tej chwili do głowy nie jest zbyt eleganckie, ale na ten moment nie mam innego pomysłu. Query.Or musi sprawdzać czy otrzymała instancję Query.And i jeżeli tak, to musi jeszcze samodzielnie przetworzyć wynik dump(). Obecnie dump() podobnie jak pipeline() z Query.And zwraca tablicę z zoptymalizowaną kolejnością (kroków z wewnętrznej reprezentacji - QueryStep, albo kroków z agregacji mongowej).

Nie można zrobić $or na różnych pipelinach (dlatego była ta magia z $facet), dlatego Query.Or musiałby taką tablicę z QuerySteps przerobić tak, że dać lookupy na początek a matche połączyć andem, co dałoby reprezentację w postaci:

all lookups
{ $match: $or: [
	{$and: [matches_from_1st_and_query]},
	{$and: [matches_from_2nd_and_query]}
	]
}

Zoptymalizowanie tego to inny task, natomiast niespecjalnie podoba mi się, że Query.Or musi wiedzieć, że przetwarza anda.

kuba-orlik changed the visibility from "All Users" to "Public (No Login Required)".Apr 29 2018, 09:08
kuba-orlik requested changes to this revision.Apr 29 2018, 09:16

@piotr-ptaszynski robię więc Request Changes. Ważna rzecz:

natomiast niespecjalnie podoba mi się, że Query.Or musi wiedzieć, że przetwarza anda.

Myślę, że OR nie musi tego wiedzieć. Cokolwiek dostanie, niech wywoła na tym dumpa, wszystkie $lookupy wypchnie na początek, a $matche z każdej z łączonych query da do osobnego $and wewnątrz $or. Intuicja podpowiada mi, że pipeline dowolnego query, które otrzyma Or można wepchnąć w $and wewnątrz $or, więc nie trzeba będzie sprawdzać, jakiego typu query dostajemy jako argument.

BTW - jak dobrze, że mamy testy :3

This revision now requires changes to proceed.Apr 29 2018, 09:16
piotr-ptaszynski mentioned this in Unknown Object (Maniphest Task).May 9 2018, 17:54
  • Merge branch 'alpha' into piopta_optimize_and_strategy
  • Fix scenario when and query is given to or query
kuba-orlik requested changes to this revision.Jun 5 2018, 17:26

Ok, przykład z OR(AND) jest obsłużony prawidłowo :3 Jeszcze trochę trzeba zmienić. Poza uwagami inline:

  1. Trzeba zmienić tytuł i opis diffa - one będą potem częścią commit message i powinno być bardziej wiadomo, co się zmienia i gdzie
  2. Bardzo przydałaby się chociaż krótka dokumentacja interfejsu Query :)
lib/datastore/query.js
119–134

Przy testach zdałem sobie sprawę, że Query.Not nie działa poprawnie:

> a = new Query();
Query { steps: [] }

> a.match({a: "A"})
undefined

> a.dump()
[ QueryStep { body: { a: 'A' } } ]

> const b = new Query()
undefined

> b.match({b: "B"})
undefined

> b.dump()
[ QueryStep { body: { b: 'B' } } ]

> new Query.Not(new Query.And(a, b)).dump()
[{"body":{"a":{"$not":"A"}}},{"body":{"b":{"$not":"B"}}}]

W skrócie: ~(a ^ b) zwraca ~a ^ ~b, kiedy powinno ~a OR ~b

Nie wiem, czy ta uwaga powinna tyczyć się tego konkretnie diffa, czy lepiej założyć na to osobnego taska - ale na pewno trzeba to poprawić. Zrób wedle uznania - jeżeli uważasz, że lepiej w osobnym tasku, to proszę od razu takowego załóż :)

This revision now requires changes to proceed.Jun 5 2018, 17:26

Ad 1. A czy masz jakąś sugestię dotyczącą innej nazwy diffa i opisu? Bo nie jest to dla mnie oczywiste.
Ad 2. Gdzie miałbym zamieścić taką dokumentację?

Ad 1. A czy masz jakąś sugestię dotyczącą innej nazwy diffa i opisu? Bo nie jest to dla mnie oczywiste.

Tytuł i opis na pewno lepiej, aby były po angielsku. W opisie coś w rodzaju "Optimize db queries combined with AND`

W opisie - jakiej metody użyłeś i po krótce jak ona działą (optymalizacja oparta o grafy i porządkowanie pipeline'a)

Ad 2. Gdzie miałbym zamieścić taką dokumentację?

README.md jest aktualnie nośnikiem dokumentacji :)

piotr-ptaszynski retitled this revision from Przygotowanie i optymalizacja Query dla AND to Optimize db queries combined with AND.Jun 19 2018, 21:22
  • Add description of new features to the readme
kuba-orlik requested changes to this revision.Jun 27 2018, 13:32

Przyczepiłem się kilku drobnych rzeczy. Myślę, że to będzie ostatnia iteracja tego diffa :)

README.md
184

"As Sealious uses MongoDB, the two main query types are" -> "Sealious communicates with mongo using mainly MongoDB Pipelines, which are represented as arrays of stages. Two main pipeline stages are"

184

Potrzebna informacj ao tym, jak taki graf zależności jest budowany

276

Czy Query na pewno jest klasą abstrakcyjną? Możemy przecież zrobić new Query(), prawda?

316

Co znaczy "multigrade" w tym kontekście? Czy jesteśmy w stanie znaleźć prostszy opis tego pojęcia?

This revision now requires changes to proceed.Jun 27 2018, 13:32
  • Improve description of new features
kuba-orlik accepted this revision.Jul 12 2018, 15:43

🆗 🛬 :33

This revision is now accepted and ready to land.Jul 12 2018, 15:43
This revision was automatically updated to reflect the committed changes.