在ArangoDB中,将使用过滤器从邻居查询是否在O(n)中完成？

Question

我一直在阅读Aql 图形操作和 图形,并没有找到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) ,与Ñ是文档的数量在地点(O(1)对于图遍历,O(n)的索引扫描)？

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

Answer 1

我将使用 ArangoDB 2.8 遍历来解释这一点来解释这一点。

我们使用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 步，并且我们对路径不感兴趣，所以我们只返回第三层：

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是德国的员工数量；它们中的每一个都可以在常数时间内遍历。->这一步的O(m) 。

• 在恒定时间内返回结果 -> O(1)

  总而言之，我们需要O(m)，其中我们期望m小于SQL 遍历中使用的n（员工数量）。