Count 问题

我们开始着手优化这个问题。羊毛出在羊身上，我们用的是 Postgresql 的数据库，当然会想到使用 Postgres 的一些功能去做这个事情。很快我们在 Google 搜索到了 Postgresql 的 Count estimate 机制。它通过获取 pg_class 这张元表纪录的信息来得到一个表里面大致的数据量。这种方法非常快，速度可达到毫秒级。但它有以下缺点：1.无法精确统计（从 estimate 这个词的意思就能看出来） 2.只能获取整张表的大致数量，无法做 where 条件过滤。问题到这里似乎还是没有解决。

从程序开发的角度来看，这个问题最好的解决方式是使用一个变量用来保存表的 Count，每次插入删除时需要对这个 Count 变量进行 +1/-1 操作。这样每次需要获取的 Count 时算法复杂度就会降到 O(1)，但从整体上看这个问题其实根本没有得到解决。数据库里面一张大表在做 Insert/Remove 时本身已经很慢了，维护这个 Count 变量需要保证原子操作。这么做不仅非常麻烦，还会增加 Insert/Remove 的开销。这里是具体的做法。事情到这里已经很明显了，对于数据库精确的 Count，我们是没有办法开发出一种低于 O(n) 复杂度的算法。但这个问题真的无解了吗？

现在的问题焦点全部都集中在 Count 上面，这个问题看起来是只要 Count 的性能快了，就能解决这个问题。但上面已经说，我们是无法开发出低于 O(n) 复杂度的 Count 算法。1kw 的数据量 O(n) 是无论如何也快不到哪里去的。跳出这个点来看，我们最终要解决的问题是什么？这个 count 的精确数字对用户来说真的能重要到牺牲等待时间来获取吗？其实在这个功能里面我们只所以需要 Count 这个数字仅仅是在做分页时精确需要计算出有多少页，尾页的数字是多少。所以影响这个问题的关键根本不是用户的需求，而是我们在程序开发时所追求的精确。只需要把这个 count 数字去掉就可以了，这将会让列表的操作速度大大的提升。实际上搜索引擎就是这么干的。以 Google 搜索为例，我们在搜索引擎随便输入点东西进行搜索得到得结果是海量的，它只会告诉你“大约”得到多少个结果，结果页展示一页，你并不会知道尾页在哪里（也不需要知道）。