In ArangoDB, l'interrogazione, con i filtri, dai vicini verrà effettuata in O (n)?

Question

Ho letto Aql Graph Operation e Graphs e non ho trovato alcun esempio concreto e spiegazione delle prestazioni per il caso d'uso di SQL-Traverse.

Esempio:

Se ho una collezione utenti, che ha un società relazione alla raccolta società

Collection società ha relazione posizione alla raccolta Località;

Collection Località è sia una città, paese, o regione, e ha relazione città, paese, regione a se stesso.

Ora, desidero interrogare tutti gli utenti che appartengono a società in Germania o UE.

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

o

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

Supponendo che Location.name è indicizzato, posso avere le due domande precedenti eseguiti con O (n), con n essendo il numero di documenti in Posizione (O (1) per attraversamento grafico, O (n) per scansione indice)?

Naturalmente, ho potuto solo salvare regionName o countryName direttamente in azienda , come queste città e paesi sono in UE, a differenza di altri posti ..., non sarà probabilmente cambierà, ma cosa succede se ... sai cosa intendo (scherzando, se ho altri casi d'uso che richiedono un aggiornamento costante)

Answer 1

Ho intenzione di spiegare questo using the ArangoDB 2.8 Traversals.

creiamo queste collezioni per abbinare il vostro Shema utilizzando 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}) 

In AQL avremmo scrivere questa query il contrario. Iniziamo con il tempo costante FILTER sull'attributo indicizzato name e iniziamo i nostri attraversamenti da lì in poi. Perciò noi filtriamo per il Paese "Germania":

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 

Ora che abbiamo il nostro nodo di inizio ben filtrato, facciamo un attraversamento grafico in senso inverso.Poiché sappiamo che Employees sono esattamente 3 passi di distanza dall'inizio Vertex, e non siamo interessati al percorso, si torna solo il 3 ° strato:

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

Alcune parole su questo interroga le prestazioni:

• noi individuare la Germania con un indice di hash è costante di tempo ->O (1)
• sulla base di che vogliamo percorrere m numerosi sentieri dove m è t numero di dipendenti in Germania; Ognuno di loro può essere attraversato in tempo costante. ->O (m) in questo passaggio.

• di ritorno il risultato in tempo costante ->O (1)

  tutto combinato dobbiamo O (m) dove ci aspettiamo m deve essere inferiore a n (il numero dei dipendenti) come usato nel tuo SQL-Traversal.