graph-databases - 在 ArangoDB 中，是否会在 O(n) 中使用过滤器从邻居中进行查询？

Question

我一直在阅读 Aql Graph Operation和 Graphs ，并没有找到SQL-Traverse的用例的具体例子和性能说明。 .

例如:

如果我有一个集合用户，它与集合公司有公司关系

收款公司与收款地点有关系；

收集位置可以是城市、国家或地区，并且与城市、国家、地区有关。

现在，我想查询属于德国或欧盟公司的所有用户。

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

或者

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

假设 Location.name 已编入索引，我是否可以使用 O(n) 执行上述两个查询，其中 n 是 Location 中的文档数(O(1) 用于图形遍历，O(n) 用于索引扫描)？

当然，我可以直接在 company 中保存 regionName 或 countryName，因为这些城市和国家在欧盟，不像在……其他地方，可能不会改变，但是如果……你知道我的意思(开玩笑的) ，如果我有其他需要不断更新的用例怎么办)

Answer 1

我要解释这个using the ArangoDB 2.8 Traversals .
我们使用 arangosh 创建这些集合以匹配您的 shema :

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})

在 AQL 中，我们将以相反的方式编写此查询。
我们从恒定时间 FILTER 开始在索引属性上 name并从那里开始我们的遍历。
因此，我们过滤国家“德国”:

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

现在我们有了经过良好过滤的起始节点，我们进行反向图遍历。既然我们知道 Employees距离起始顶点正好 3 步，我们对路径不感兴趣，我们只返回第 3 层:

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

关于此查询性能的一些话:

我们使用哈希索引定位德国是常数时间 -> O(1)

基于此，我们要遍历 m 条路径，其中 m 是德国的员 worker 数；它们中的每一个都可以在恒定时间内遍历。
-> O(米)在这一步。

以恒定时间返回结果 -> O(1)
全部加起来我们需要 O(米)我们期望 m 小于 SQL 遍历中使用的 n(员工数量)。