Page MenuHomeSealhub

Optimize db queries combined with AND
ClosedPublic

Authored by piotr-ptaszynski on Mar 30 2018, 06:09.
Tags
None
Referenced Files
Unknown Object (File)
Fri, Dec 20, 20:08
Unknown Object (File)
Fri, Dec 20, 20:08
Unknown Object (File)
Fri, Dec 20, 20:08
Unknown Object (File)
Fri, Dec 20, 20:08
Unknown Object (File)
Fri, Dec 20, 20:08
Unknown Object (File)
Fri, Dec 20, 20:04
Unknown Object (File)
Fri, Dec 20, 20:04
Unknown Object (File)
Fri, Dec 20, 20:04
Subscribers

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
Branch
piopta_optimize_and_strategy (branched from alpha)
Lint
No Lint Coverage
Unit
No Test Coverage
Build Status
Buildable 723
Build 723: arc lint + arc unit

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
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 subscribed.
kuba-orlik added inline comments.
lib/app/base-chips/access-strategy-types/and.js
19–25

Albo

return new Query.and(...queries)

;)

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

(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
10

(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

46

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

135–148

(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?

135

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)

135

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

146–149

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

155

(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?

200

(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 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

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

lib/datastore/query-step.js
3

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

6

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

16–21

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

25

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

37–49

(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);
60

(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
81

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
5–9

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

15

beka :D

52–62

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
15

(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 added inline comments.
lib/datastore/query-step.js
6

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

16–21

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

25

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
52–62

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

lib/datastore/query-step.js
16–21

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

25

Hm, co masz na myśli?

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

^ to jest jeden krok agregacji, prawda?

lib/datastore/query.test.js
52–62

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 added inline comments.
lib/datastore/query-step.js
25

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ć.

lib/datastore/query-step.js
25

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

  • Change standalone function to static method
  • Optimize and query when is populated with deny all
  • Remove disturbing API

👌 👌 👌 👌 👌

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

@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

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

README.md
185

"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"

185

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

277

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

317

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
This revision is now accepted and ready to land.Jul 12 2018, 15:43
This revision was automatically updated to reflect the committed changes.