Optimizing ORDER BY/LIMIT in Sharded Databases with Cobar’s Algorithm

Background

Although Cobar is an “old” database middleware, many companies still use it, and it contains interesting algorithms and implementations. This article shares an optimization Cobar proposes for ORDER BY / LIMIT in sharding scenarios.

Original algorithm description: https://github.com/alibaba/cobar/blob/master/doc/cobarSolution.ppt

Cobar’s primary function is database and table sharding. Read‑performance bottlenecks are usually solved by adding replicas or caches, while write performance can only be improved through sharding.

When data is distributed across different databases, a single‑row query only needs to locate the corresponding shard. For multi‑row queries, Cobar must query each shard and then aggregate the results.

Example

Suppose we need to query column c1 from table tb1, ordered ascending, and retrieve the rows at indexes 4 and 5 (0‑based). With three shards, we must fetch indexes 0‑5 from each shard, resulting in three sorted lists. After discarding the first four rows from the merged list, the remaining rows correspond to the desired data.

If the query uses a deep pagination, e.g. select c1 from tb1 order by c1 limit 9999999, 4 the naïve approach would require each shard to return rows 0‑10000003 and then discard the first 9,999,998 rows, wasting roughly three times the data compared to a non‑sharded query.

Algorithm Optimization

Step 1: Split the original statement into three separate statements and send each to a shard.

Step 2: Determine the minimum and maximum values of the query result across shards (e.g., min = 3, max = 11).

Step 3: Re‑query each shard using the min and max as additional conditions.

From the returned data we can infer how many rows precede the minimum value in each shard.

Step 4: Reverse‑lookup the offset for each result, allowing us to calculate how many rows exist before the minimum value in each shard (e.g., shard 1 has 3,333,332 rows before the minimum, shard 2 has 3,333,333, etc.).

With this information we can discard the unnecessary rows (0‑9,999,998) before merging, reducing the amount of data processed dramatically.

Algorithm Analysis

Efficiency

Before optimization:

One query retrieves approximately 30 k rows and discards 9,999,999 rows.

After optimization:

First query retrieves about 10 k rows.

Second query retrieves 17 rows.

Only 3 rows are discarded.

The optimized approach dramatically reduces the total data volume and the amount of work needed to compute the discard count.

Non‑Ideal Cases

The algorithm assumes that the data distribution of the ordering column is uniform across shards. If the minimum value found in Step 4 does not allow enough rows to be discarded, or if there are many more rows before the minimum than needed, the algorithm may fail.

In such situations the algorithm cannot be applied effectively.

Prerequisites for Success

The key prerequisite is that the ordering field’s values are evenly distributed across all shards. If all data resides in a single shard, the algorithm collapses.

Conclusion

The algorithm may seem wasteful and is not used inside Cobar itself, but in scenarios where data is evenly distributed (as is common when sharding by a modulus of a field) and the query involves deep pagination, this strategy can provide significant performance gains. It should be used with a fallback to the original method when the result set does not meet expectations.

Search and follow the WeChat public account "捉虫大师" for backend technical sharing, architecture design, performance optimization, source code reading, troubleshooting, and practical experiences.