分库分表：范围查询支持

[flycash]

仅限中文

背景

在最开始的时候，我们支持了 EQ 这种写法，AND 和 OR，并且在 #167 里面提及支持 NOT 写法。现在我们要进一步考虑剩余的操作符：

• 比较操作符：>=, >, <, <=,
• IN
• BETWEEN

还有一个比较特殊的 !=，我会单独创建一个 issue，因为 != 可以看做是 NOT 的一种特殊场景。在 != 之下，就是广播的候选节点 - （= 确定的节点）。

很明显，我们这一次打算支持的就是范围查询。

使用场景

范围查询对于不同的分库分表规则来说目标表的确定是完全不同的。

哈希分库分表

假如说我们的 order 分库分表规则是 user_id%32 来分表。那么我们会面临这种困境，假如说分库分表的条件:

• WHERE user_id < 10，那么很显然会命中 order_tab_[0, 9]
• WHERE user_id <100，那么很显然是广播
• 如果 user_id 有上限，比如说最大值是 1000，那么 WHERE user_id > 980 也只会命中部分节点
• 如果 user_id 有上限，比如说最大值是1000，那么 WHERE user_id > 100 显然是广播

这种处理方案是有缺陷的，比如说：user_id > 1000 AND user_id < 10：那么先单一一个条件考察 user_id > 1000 会命中所有的表；user_id < 10 则只会命中全部集群上的部分库(db_[0,9])和部分表。那么根据 AND 的运算规则进行求交集，最终会选择第二个条件的所有的表。但是我们手动分析就知道，这个查询条件是查询不到任何数据的。

那么有些分库分表会引入一些SQL优化，就能一定程度上解决这种问题。

分库和分集群都是类似的。

范围分库分表

假如说我们的 order 分库分表规则是 user_id 每 1000 分一段。比如说 [0, 1000) 是一段，[1000,2000) 是一段...

• WHERE user_id < 3000，那么很显然会命中 order_tab_[0, 2]
• WHERE user_id >1000，那么很显然命中除了 order_tab_0 的全部节点。这里面我们可以注意到，在范围查询里面，在不知道上限的情况下，我们只能用排除法
• WHERE user_id >1000，user_id 上限是 20000（不包含），那么就会命中 order_tab_[1, 19]

哈希分库分表

哈希分库分表规则在范围查询里面，几乎都是只能使用广播来进行处理。但是在一些边缘场景里面，存在一点优化的可能，但是实际上并没有必要去执行这种优化。

比如说对于 user_id %3 的分表，当查询条件是 user_id < 100 的时候，很显然是广播；但是如果查询条件是 user_id < 1，那么实际上我们可以确定只会命中 user_tab_0 这张表。

总结起来就是：对于哈希分库分表来说，在最大值和最小值附近，是可以不用广播的。

不过这种优化价值实在不大，所以没有什么必要去做优化。

综合分库分表

假如说我们的分库分表规则是$region.mycompany.com:3306/order_db_(@user_id%32).order_tab_(@user_id/32%32)。那么本质上还是按照 AND，OR 来组合整个分集群分库分表。而对于具体的一条规则，则是参考范围分库分表和哈希分库分表来进行处理。

设计

在考虑支持范围查询的情况下，需要对已有的接口做一个较大的改造：

type Predicate = predicate.Predicate
type ShardingAlgorithm interface {
    Sharding(ctx context.Context, where Predicate) 
}

也就是我们需要把第二个参数改造成为 Predicate。在这种情况下，意味着我们要把 AND 和 OR 的逻辑也下沉到具体的算法实现里面。

理论上来说，我们可以考虑将 AND 和 OR 抽取出来作为公共方法，但是我在尝试的时候发现本身 AND 和 OR 是一个需要递归的东西，所以稍微有点棘手。

很显然这个 Predicate 就是我们在构造 WHERE 的时候把所有的查询条件 AND 成一个之后的产物。当然，这个地方也可以考虑将 where 定义为 []Predicate。

紧接着，我们在 internal 里面新建一个包，叫做 expression，然后将 eorm 包里面的 Predicate 结构体挪下去。同时在 eorm 里面定义一个同名的结构体 Predicate：

type Predicate = expression.Predicate

这里面比较麻烦的是在 eorm 本身里面将 Predicate 定义成为了一个 binaryExpression 的衍生类型，所以在重构的时候，需要将所有的 expression 实现都挪下去。同时，在 eorm 里面定义对应的别名。

这边我认为是可以的，因为 expression 不依赖于别的东西。

而后在具体的实现里面完成分库分表的逻辑。

[Stone-afk]

如果 将 Predicate 下沉，岂不是新增一个hash实现，就要实现一次？个人倾向于把操作符下沉，到sharding里面
、、、

type Request struct {
op string
SkValues map[string]any
}

、、、

[Stone-afk]

func (h *Hash) Sharding(ctx context.Context, req sharding.Request) (sharding.Result, error) {
	if h.ShardingKey == "" {
		return sharding.EmptyResult, errs.ErrMissingShardingKey
	}
	skVal, ok := req.SkValues[h.ShardingKey]
	if !ok {
		return sharding.Result{Dsts: h.Broadcast(ctx)}, nil
	}
	if req.Op == "=" {
		
	} else if req.Op == ">" {
		
	} else if req.Op == "<" {
		
	}
	.........
	return sharding.Result{
		Dsts: []sharding.Dst{{Name: dsName, DB: dbName, Table: tbName}},
	}, nil
}

[Stone-afk]

在 sharding 里
type op Operator.Op

type Request struct {
	Op       op
	SkValues map[string]any
}

在 eorm 里
type op Operator.Op
把公共的操作符 抽象出到 Operator 包中

[Stone-afk]

对于 IN、NOT IN 是否可以分解成颗粒度更小的操作符计算

[flycash]

是的，要拆解成操作符和算法两个部分。然后算法会组装操作符

[Stone-afk]

func (h *Hash) Sharding(ctx context.Context, req sharding.Request) (sharding.Result, error) {
	if h.ShardingKey == "" {
		return sharding.EmptyResult, errs.ErrMissingShardingKey
	}
	skVal, ok := req.SkValues[h.ShardingKey]
	if !ok {
		return sharding.Result{Dsts: h.Broadcast(ctx)}, nil
	}
	var dsts []sharding.Dst
	switch req.Op {
	case operator.OpEQ:
		dbName := h.DBPattern.Name
		if !h.DBPattern.NotSharding {
			dbName = fmt.Sprintf(dbName, skVal.(int)%h.DBPattern.Base)
		}
		tbName := h.TablePattern.Name
		if !h.TablePattern.NotSharding {
			tbName = fmt.Sprintf(tbName, skVal.(int)%h.TablePattern.Base)
		}
		dsName := h.DsPattern.Name
		if !h.DsPattern.NotSharding {
			dsName = fmt.Sprintf(dsName, skVal.(int)%h.DsPattern.Base)
		}
		dsts = append(dsts, sharding.Dst{Name: dsName, DB: dbName, Table: tbName})
	case operator.OpGT:
		if !h.DBPattern.NotSharding && h.TablePattern.NotSharding && h.DsPattern.NotSharding {
			dsts = h.onlyDBroadcast(
				ctx, (skVal.(int)%h.DBPattern.Base)+1, h.DBPattern.Base)
		} else if h.DBPattern.NotSharding && !h.TablePattern.NotSharding && h.DsPattern.NotSharding {
			dsts = h.onlyTableBroadcast(
				ctx, (skVal.(int)%h.TablePattern.Base)+1, h.TablePattern.Base)
		} else if h.DBPattern.NotSharding && h.TablePattern.NotSharding && !h.DsPattern.NotSharding {
			dsts = h.onlyDataSourceBroadcast(
				ctx, (skVal.(int)%h.DsPattern.Base)+1, h.DsPattern.Base)
		} else if !h.DBPattern.NotSharding && !h.TablePattern.NotSharding && !h.DsPattern.NotSharding {
			dsts = h.allBroadcast(
				ctx, (skVal.(int)%h.DsPattern.Base)+1, h.DsPattern.Base,
				(skVal.(int)%h.DBPattern.Base)+1, h.DBPattern.Base,
				(skVal.(int)%h.TablePattern.Base)+1, h.TablePattern.Base)
		}
		dsts = h.defaultBroadcast(
			ctx, (skVal.(int)%h.DBPattern.Base)+1, h.DBPattern.Base,
			(skVal.(int)%h.TablePattern.Base)+1, h.TablePattern.Base)
	case operator.OpLT:
		if !h.DBPattern.NotSharding && h.TablePattern.NotSharding && h.DsPattern.NotSharding {
			dsts = h.onlyDBroadcast(
				ctx, 0, (skVal.(int)%h.DBPattern.Base)-1)
		} else if h.DBPattern.NotSharding && !h.TablePattern.NotSharding && h.DsPattern.NotSharding {
			dsts = h.onlyTableBroadcast(
				ctx, 0, (skVal.(int)%h.TablePattern.Base)-1)
		} else if h.DBPattern.NotSharding && h.TablePattern.NotSharding && !h.DsPattern.NotSharding {
			dsts = h.onlyDataSourceBroadcast(
				ctx, 0, (skVal.(int)%h.DsPattern.Base)-1)
		} else if !h.DBPattern.NotSharding && !h.TablePattern.NotSharding && !h.DsPattern.NotSharding {
			dsts = h.allBroadcast(
				ctx, 0, (skVal.(int)%h.DsPattern.Base)-1,
				0, (skVal.(int)%h.DBPattern.Base)-1,
				0, (skVal.(int)%h.TablePattern.Base)-1)
		}
		dsts = h.defaultBroadcast(
			ctx, 0, (skVal.(int)%h.DBPattern.Base)-1,
			0, (skVal.(int)%h.TablePattern.Base)-1)
	case operator.OpGTEQ:
		if !h.DBPattern.NotSharding && h.TablePattern.NotSharding && h.DsPattern.NotSharding {
			dsts = h.onlyDBroadcast(
				ctx, skVal.(int)%h.DBPattern.Base, h.DBPattern.Base)
		} else if h.DBPattern.NotSharding && !h.TablePattern.NotSharding && h.DsPattern.NotSharding {
			dsts = h.onlyTableBroadcast(
				ctx, skVal.(int)%h.TablePattern.Base, h.TablePattern.Base)
		} else if h.DBPattern.NotSharding && h.TablePattern.NotSharding && !h.DsPattern.NotSharding {
			dsts = h.onlyDataSourceBroadcast(
				ctx, skVal.(int)%h.DsPattern.Base, h.DsPattern.Base)
		} else if !h.DBPattern.NotSharding && !h.TablePattern.NotSharding && !h.DsPattern.NotSharding {
			dsts = h.allBroadcast(
				ctx, skVal.(int)%h.DsPattern.Base, h.DsPattern.Base,
				skVal.(int)%h.DBPattern.Base, h.DBPattern.Base,
				skVal.(int)%h.TablePattern.Base, h.TablePattern.Base)
		}
		dsts = h.defaultBroadcast(
			ctx, skVal.(int)%h.DBPattern.Base, h.DBPattern.Base,
			skVal.(int)%h.TablePattern.Base, h.TablePattern.Base)
	case operator.OpLTEQ:
		if !h.DBPattern.NotSharding && h.TablePattern.NotSharding && h.DsPattern.NotSharding {
			dsts = h.onlyDBroadcast(
				ctx, 0, skVal.(int)%h.DBPattern.Base)
		} else if h.DBPattern.NotSharding && !h.TablePattern.NotSharding && h.DsPattern.NotSharding {
			dsts = h.onlyTableBroadcast(
				ctx, 0, skVal.(int)%h.TablePattern.Base)
		} else if h.DBPattern.NotSharding && h.TablePattern.NotSharding && !h.DsPattern.NotSharding {
			dsts = h.onlyDataSourceBroadcast(
				ctx, 0, skVal.(int)%h.DsPattern.Base)
		} else if !h.DBPattern.NotSharding && !h.TablePattern.NotSharding && !h.DsPattern.NotSharding {
			dsts = h.allBroadcast(
				ctx, 0, skVal.(int)%h.DsPattern.Base,
				0, skVal.(int)%h.DBPattern.Base,
				0, skVal.(int)%h.TablePattern.Base)
		}
		dsts = h.defaultBroadcast(
			ctx, 0, skVal.(int)%h.DBPattern.Base,
			0, skVal.(int)%h.TablePattern.Base)
	default:
		return sharding.EmptyResult, errs.NewUnsupportedOperatorError(req.Op.Text)
	}
	return sharding.Result{Dsts: dsts}, nil
}

[flycash]

我觉得后面要考虑设计改成 #187 中的 aggregator 的设计。但是可能要更加难改，因为这边会涉及到递归的过程。
还有一个思路是装饰器。就是有一个 commonSharding 的东西，里面会解决 AND, OR, IN 之类的问题。那么用户就可以组合这个，或者把自己的实现作为一个参数传入进去。

又或者，我们可以考虑定义一个新接口：

type Sharding interface {
    OnEq()
    OnLt() 
}

等。

不过我大概评估了一下，都不是很容易。

后面我们实现范围分库分表的时候，再重构哈希部分，看能否找出一个更加优雅的方案