W ArangoDB, będzie zapytań, z filtrami, od sąsiadów (s) zrobić w O (n)?

Question

Czytałem Aql Graph Operation i Graphs i nie znalazłem żadnego konkretnego przykładu i wyjaśnienia wydajności dla przypadku użycia SQL-Traverse.

Np:

Jeśli mam kolekcję Użytkownicy, która ma firmy związku z kolekcji Spółka

Collection Spółka ma związku lokalizację do zbierania Lokalizacja;

Collection Lokalizacja jest albo miasto, kraj lub region, a ma relacja miasto, kraj, regionu do siebie.

Teraz chciałbym zapytać wszystkich użytkowników, którzy należą do firm w Niemczech lub UE.

SELECT from Users where Users.company.location.city.country.name="Germany"; 
SELECT from Users where Users.company.location.city.parent.name="Germany"; 

lub

SELECT from Users where Users.company.location.city.country.region.name="europe"; 
SELECT from Users where Users.company.location.city.parent.parent.name="europe"; 

Zakładając Location.name jest indeksowany, mogę mieć dwa zapytania powyżej wykonany z O (n) z n oznacza liczbę dokumentów w lokalizacji Lokalizacja (O (1) dla przemierzania wykresu, O (n) dla skanowania indeksu)?

Oczywiście, może po prostu zaoszczędzić regionName lub COUNTRYNAME bezpośrednio w firmy, jak te miasta i kraje są w Unii Europejskiej, w przeciwieństwie do ... innych miejscach, nie będzie prawdopodobnie zmieni, ale co jeśli ... wiesz co mam na myśli (żartuję, co jeśli mam inne przypadki użycia, które wymagają ciągłej aktualizacji)

Answer 1

Wyjaśnię to using the ArangoDB 2.8 Traversals.

Tworzymy tych zbiorów, aby dopasować swój Szema użyciu arangosh:

db._create("countries") 
db.countries.save({_key:"Germany", name: "Germany"}) 
db.countries.save({_key:"France", name: "France"}) 
db.countries.ensureHashIndex("name") 

db._create("cities") 
db.cities.save({_key: "Munich"}) 
db.cities.save({_key: "Toulouse") 

db._create("company") 
db.company.save({_key: "Siemens"}) 
db.company.save({_key: "Airbus"}) 

db._create("employees") 
db.employees.save({lname: "Kraxlhuber", cname: "Xaver", _key: "user1"}) 
db.employees.save({lname: "Heilmann", cname: "Vroni", _key: "user2"}) 
db.employees.save({lname: "Leroy", cname: "Marcel", _key: "user3"}) 

db._createEdgeCollection("CityInCountry") 
db._createEdgeCollection("CompanyIsInCity") 
db._createEdgeCollection("WorksAtCompany") 


db.CityInCountry.save("cities/Munich", "countries/Germany", {label: "beautiful South near the mountains"}) 
db.CityInCountry.save("cities/Toulouse", "countries/France", {label: "crowded city at the mediteranian Sea"}) 

db.CompanyIsInCity.save("company/Siemens", "cities/Munich", {label: "darfs ebbes gscheits sein? Oder..."}) 
db.CompanyIsInCity.save("company/Airbus", "cities/Toulouse", {label: "Big planes Ltd."}) 


db.WorksAtCompany.save("employees/user1", "company/Siemens", {employeeOfMonth: true}) 
db.WorksAtCompany.save("employees/user2", "company/Siemens", {veryDiligent: true}) 
db.WorksAtCompany.save("employees/user3", "company/Eurocopter", {veryDiligent: true}) 

W AQL będziemy pisać tego zapytania na odwrót. Zaczynamy od stałego czasu FILTER na indeksowanym atrybucie name i od tego momentu uruchamiamy nasze przewijanie. Nich filtrujemy dla kraju „Niemcy”:

db._explain("FOR country IN countries FILTER country.name == 'Germany' RETURN country ") 
Query string: 
FOR country IN countries FILTER country.name == 'Germany' RETURN country 

Execution plan: 
Id NodeType  Est. Comment 
    1 SingletonNode  1 * ROOT 
    6 IndexNode   1  - FOR country IN countries /* hash index scan */ 
    5 ReturnNode   1  - RETURN country 

Indexes used: 
By Type Collection Unique Sparse Selectivity Fields  Ranges 
    6 hash countries false false  66.67 % [ `name` ] country.`name` == "Germany" 

Optimization rules applied: 
Id RuleName 
    1 use-indexes 
    2 remove-filter-covered-by-index 

Teraz, gdy mamy dobrze filtrowaną węzeł początkowy, robimy przechodzenie wykres w odwrotnym kierunku.Ponieważ wiemy, że Employees są dokładnie 3 kroków od początku Vertex, a my nie jesteśmy zainteresowani w ścieżce, tylko wrócić 3rd warstwy:

db._query("FOR country IN countries FILTER country.name == 'Germany' FOR v IN 3 INBOUND country CityInCountry, CompanyIsInCity, WorksAtCompany RETURN v") 

[ 
    { 
    "cname" : "Xaver", 
    "lname" : "Kraxlhuber", 
    "_id" : "employees/user1", 
    "_rev" : "1286703864570", 
    "_key" : "user1" 
    }, 
    { 
    "cname" : "Vroni", 
    "lname" : "Heilmann", 
    "_id" : "employees/user2", 
    "_rev" : "1286729095930", 
    "_key" : "user2" 
    } 
] 

Kilka słów o to pyta wydajność:

• Jesteśmy zlokalizować Niemcy użyciem indeksu hash jest stała czasowa ->o (1)
• na tej podstawie chcemy przemierzać m wiele ścieżek gdzie m jest t on liczba pracowników w Niemcy; Każdy z nich można przemierzać w stałym czasie. ->O (m) na tym etapie.

• zwraca wynik w stałym czasie ->O (1)

  wszystkie połączone trzeba O (m) gdzie oczekujemy m być mniejsza niż n (liczba pracowników) jak używane w twoim SQL-Traversal.