Datastore的zigzag merge join查询计划的改进

2011 11 1 07:13 PM 1577次查看

分类：Google App Engine 标签：Python, Google App Engine

之前曾介绍过Datastore的zigzag merge join技术，它可以显著减少索引的数目。而今天看到《Index Selection and Advanced Search》这篇文章，才知道它又有新的改进了。

首先介绍一下之前的merge join。假设我有这样一个模型：
class Test(db.Model):
	a = db.IntegerProperty()
	b = db.IntegerProperty()
	c = db.IntegerProperty()
而我要进行如下的查询：
Test.all().filter('a =', 1).filter('b =', 2)
Test.all().filter('a =', 1).filter('c =', 3)
Test.all().filter('b =', 2).filter('c =', 3)
Test.all().filter('a =', 1).filter('b =', 2).filter('c =', 3)
如果不用merge join的话，我需要定义4个复合索引：
- kind: Test
  properties:
  - name: a
  - name: b

- kind: Test
  properties:
  - name: a
  - name: c

- kind: Test
  properties:
  - name: b
  - name: c

- kind: Test
  properties:
  - name: a
  - name: b
  - name: c
而使用merge join时，这4条索引我都不需要定义。因为a、b、c都已经有内置的索引了，查询计划器会从3条内置索引里分别找到a为1的、b为2的和c为3的，再根据key将其合并起来，这样就能返回所有符合条件的结果了。
其中的缺点就是不能有不等于和排序操作，且查询速度比复合索引快。

而经过SDK 1.5.2的优化，merge join已经能支持不等于和排序操作了。
简单来说，如果我需要这样的查询：
Test.all().filter('a =', 1).filter('c >', 1)
Test.all().filter('b =', 2).filter('c >', 1)
Test.all().filter('a =', 1).filter('b =', 2).filter('c >', 1)
Test.all().filter('a =', 1).filter('b =', 2).order('c')
原先我需要定义这样的复合索引：
- kind: Test
  properties:
  - name: a
  - name: c

- kind: Test
  properties:
  - name: b
  - name: c

- kind: Test
  properties:
  - name: a
  - name: b
  - name: c
但实际上这些操作都是对c排序的，所以可以用前2条复合索引来merge join，这样就避免了创建第3条索引。
在这个例子中，虽然节约的索引数不多，但考虑到还可能有反向排序，需要对其他属性排序，以及属性是列表的情况，这样节约的索引数就很可观了。

1条评论 你不来一发么↓ 顺序排列 倒序排列

    向下滚动可载入更多评论，或者点这里禁止自动加载。

    想说点什么呢？