分页 & QueryKey & 预取

分页 & QueryKey & 预取

数据库分页查询一般分为两步，
(1)根据查询条件，count 记录总数
(2)根据当前页的数据范围(起始位置offset, 每页数据个数span)，从符合查询条件的记录集 取出对应范围的数据。

一、根据范围取数据的方法
如果单纯用JDBC从ResultSet中取出一个指定范围（offset, span）的数据，可以采用这样的方法。
[code:1]
ps = con.prepareStatement(sql, ResultSet.TYPE_SCROLL_INSENSITIVE, ResultSet.CONCUR_READ_ONLY)；
ps.setMaxRows(offset + span)；
rs = ps.executeQuery();
rs.absolute(offset);
while(rs.next())...
[/code:1]

数据量大的时候，页数很多，offset很大，这种方法不太适合。这时候，需要使用各数据库的native SQL特性。
我们来看Hibernate dialect package的类，支持了各种数据库的getLimitString方法。这里举Mysql和Oracle的例子。假设查询语句为
[code:1]
Select * from message where forum_id = ? and created_time > ? order by created_time desc
[/code:1]

Mysql 的limit SQL为
[code:1]
Select * from message where forum_id = ? and created_time > ? order by created_time desc
limit ?, ?
[/code:1]
后面的两个limit ?, ? 分别为 offset, span。

Oracle的limit SQL为
[code:1]
select * from ( select row_.*, rownum rownum_ from (
Select * from message where forum_id = ? and created_time > ? order by created_time desc
) row_ where rownum <= ?) where rownum_ > ?
[/code:1]
后面的两个limit ?, ? 分别为 offset + span, offset。

二、缓存 & QueryKey
count语句可以根据查询语句自动生成，比如
[code:1]
Select count(*) from (
Select * from message where forum_id = ? and created_time > ? order by created_time desc
)
[/code:1]

这样的自动count语句有些浪费，用了子查询不说，还保留了没有必要的order by。最好还是另外提供一个count语句。
[code:1]
Select count(*) from message where forum_id = ? and created_time > ?
[/code:1]

在多页翻动的情况下，这个count语句要被反复执行。为了提高效率，我把这个count结果保存在全局缓存中，不仅本Session用户可以重复使用，其他用户在根据同样条件翻找message的时候，也可以重复使用这个结果。

我在持久层中使用通用的QueryKey做为缓存键值。
QueryKey分成三个部分，SQL, Parameters, Range。比如：
[code:1]
Query Key:
SQL : Select count(*) from message where forum_id = ? and created_time > ?
Parameters : [buaawhl, time long value]
Range: (0, 1)
[/code:1]

这个QueryKey的效率很关键。主要是hashCode和equals两个方法的效率。
我们知道，当key放在Map等Hash数据结构中，首先hashCode，然后用equals比较hashCode后面的一串key。
举个例子。Key1和key2 的hashCode一样，都和key3的hashCode不一样。
[code:1]
…
[ 101 ] -> key1 -> key2
…
[ 666 ] -> key3
…
[/code:1]

可以看到，hashCode，equals，这两个方法都是每次查找缓存都要调用的方法。尤其是equals方法更是重中之重，很可能需要被调用多次。
hashCode的优化实现相对来说比较简单，只要根据QueryKey中各部分的不同，尽量实现hashCode取值的扩散化，降低hashCode的重复率就可以了。
关键是equals的实现方案。这里有个原则，越小的结构越先比较，可以提高比较速度。
QueryKey中的parameters和range比较好办。每次equals比较的时候，先比较range，如果不相等，返回false; 如果相等，再比较Parameters，如果有一个parameter value不相等，返回false。这样，我们可以用很短的时间开销 过滤掉一大批不相等的QueryKey。
但是parameters和range都相等的时候，我们还是无可避免的要比较SQL。String的equals方法如下：
[code:1] // from jdk src
//这个方法没有比较hashCode，直接比较长度和字符
    public boolean equals(Object anObject) {
if (this == anObject) {
    return true;
}
if (anObject instanceof String) {
    String anotherString = (String)anObject;
    int n = count;
    if (n == anotherString.count) {
char v1[] = value;
char v2[] = anotherString.value;
int i = offset;
int j = anotherString.offset;
while (n-- != 0) {
    if (v1[i++] != v2[j++])
return false;
}
return true;
    }
}
return false;
    }
[/code:1]
我们看到，当SQL String很长的时候，长度相等，前面大部分字符相同的时候，(最极端的情况下，两个不同reference的String的字符完全相等)，这个比较是相当消耗时间的。比如，
[code:1]
Select * from message where forum_id = ? and created_time > ? order by created_time desc
[/code:1]
和
[code:1]
Select * from message where forum_id = ? and created_time > ? order by updated_time desc
[/code:1]
两个String的长度相等，前面大部分也相等，只有走到cre 和 upd 的时候，才能比较出不相同。如果两个字符串内容一样，那更是要走到头，才能判断出两个字符串完全一样了。

我的第一个做法就是，尽量使用static final String做为QueryKey的SQL。这样两个SQL的reference如果相等，那么可以迅速判断出两个SQL相同。
这个做法只能处理事先定义好的SQL语句，但实际需求中，存在很多需要动态拼接SQL的情况，不可能做到所有相同的SQL具有相同的reference。
当然大部分不同的SQL都具有不同的长度，即使长度相同，前面走不了几个字符，就可以判断出不相同。所以做法一已经能够解决95%以上的SQL效率问题。

不过，为了解决这剩下的5%情况，我又采取了第二个做法：分而治之，把一个SQL String拆分成多个SQL常量的数组;泛化SQL的类型，SQL不限制为String类型，也可以是String[]类型。
比如。
[code:1]
String[] sql1 = {
“Select * from message where forum_id = ?”，
“ and created_time > ?”,
“ order by ”,
“created_time”,
“desc”
};
[/code:1]
和
[code:1]
String[] sql2 = {
“Select * from message where forum_id = ?”，
“ and created_time > ?”,
“ order by ”,
“created_time”,
“desc”
};
[/code:1]
和
[code:1]
String[] sql3 = {
“Select * from message where forum_id = ?”，
“ and created_time > ?”,
“ order by ”,
“updated_time”,
“desc”
};
[/code:1]

这个时候，比较sql1和sql2和sql3的效率就会大大提高，虽然sql1 和 sql2两个数组的长度相等，还是要一个元素一个元素的比较，但由于里面大量用到了String常量，相同的String常量具有相同的reference，所以5步下来，就可以判断出sql1和sql2数组的元素是完全相等的；4步下来，加上第一个字符的比较，就可以判断sql1和sql3的第4个元素是不相等的。

我们看到，做法1和做法2，能够100%的提高SQL的比较效率，大部分情况下，也许比parameters的比较还快。

三、定长预取
多用户访问同一页面的可能性比较大的情况下，比如，论坛的某些热门话题，很可能被多人同时翻阅。这时候，如果把根据范围取出的数据对象List也按照QueryKey存入缓存中，那么就可以大大提高响应速度，减轻数据服务器负担，当然，你的Web Server的内存负担也大大增加了。:-)
我们进一步考虑下面两种情况：
1. 用户自定义页面记录数
一般来说，用户可以自定义自己的每页显示记录个数，比如，有些用户喜欢每页20条，有的喜欢每页10条。
假设用户A翻到一个论坛的第一页，显示1 – 20条信息；用户B翻到同一个论坛的第一页，显示1 – 10条信息。这个时候，缓存的命中率是很低的。用户A和用户B无法共享缓存信息。因为他们的range(的span)总是不同，QueryKey永远不可能相同。

2. 记录很多、每页记录数过少
假设一个论坛里面有1000条信息，每页显示10条，那么共有100页。如果用户一页一页的翻动，每次程序发出一个span大小为10的Query请求，取出10条记录，根据QueryKey缓存起来。由于页面记录数过少，每次数据库查询的效率很低，缓存命中率也很低。

为了提高缓存命中率，并且顺便实现数据预取功能，我们可以采取 同一定长Span的方案。比如，还是上面的例子，我们在程序中设定统一Span大小为100。
当用户A请求1 – 10的记录的时候，程序判断这个落在 1 – 100的范围内，那么用range (1, 100)获取100条记录，把前面的10条返回给用户。当用户A翻了一页，请求11 – 20的记录的时候，程序判断还是落在 1 – 100的范围内，而且已经存在于缓存中，那么直接把对应的11 – 20条返回给用户A就可以。
当用户B 请求1 – 20的记录的时候，程序判断这个落在 1 – 100的范围内，而且已经存在于缓存中，那么直接把对应的1 – 20条返回给用户B就可以。

可以看到，这种定长预取方案能够大大提高数据库查询的效率和缓存的命中率。

关于Cache & QueryKey 部分，偶有1个问题：你是如何做到cache的自动清理和聪明地清理？

举个例子
假设有这样的查询语句：select * from message where message_to = ?
执行了2次值不同的操作：'buaawhl' 和 'Readonly'
那么就有2个不同QueryKey对应到Cache里的对象。

这个时候再执行一个write的操作：往message表里面插入了一条message_to等于‘buaawhl’的记录，那么之前在Cache里QueryKey为'buaawhl'的对象会不会自动失效？而QueryKey为'Readonly'的对象是否还能保持有效呢？

应该没这么智能吧！evict掉全部包含了表message的query

确实没有这么智能。我现在无法做到 cache的自动清理和聪明地清理。
我现在做的持久层本身是不做cache的清理管理工作，这个工作交给 调用程序自己去做。cache也需要用户自己实现，并且明确提供。
查询的时候，需要指定cache
[code:1]
finder.setRowClass(Message.class);
finder.setCache(cache);
finder.queryRowsRange(conP, sql, params, offset, span);
[/code:1]

这个时候，finder会用 QueryKey(sql, params, offset, span) 作为Key,
从指定的cache里面，查找对应的记录集合。
如果查不到，从conP真正获取一个connection，连接并查找数据库，把结果放到cache里面。
这里有个优化，如果指定了缓存，而且只有当缓存中不存在目标数据的时候，才真正地从连接池中获取connection。主要是考虑到连接池的大小总是有限的，如果并发用户多的话，这样就可以节省连接池里的connection的分配。

---
update, delete, update的时候，用户需要手动自己清理cache的内容。
[code:1]
persister.insertRow(con, message);
cache.clear();
// 或者更智能的操作, 比如, 根据message的message_to value,
// 清理Cache里面的符合下列条件的QueryKey
// (sql 包含 message_to = ?,  并且 params[0] = buaawhl)
[/code:1]

我做的持久层，由于直接使用SQL，在 自动智能过滤缓存数据 方面，具有先天的缺陷。
因为SQL可以写的很复杂，比HQL复杂很多。而且还有各种 Native SQL特性，没有一个统一的中间语言（比如HQL）， 解析起来也相当复杂。
即使有这么一个中间语言，解析处理的代价和难度也相当大。相当于实现了一个小型的HSQL级别的内存数据库。

而对于用户来说，定义DAO方法的时候，很清楚自己SQL的语义，实现智能缓存处理更容易一些，所以干脆把cache的管理交给用户自己。
这样做的另一个目的是，我想把 对应的页面缓存也放到同一个cache中去。
还有一种情况，比如，user, group, group user, 三个不同的Data Object类，由于相互关联，那么用户可以指定这三个类使用同一个cache，简化管理。
还有一种情况，比如，我想用message类，同时对应 站内短信，和论坛帖子两个对象，我也可以为这两种不同的情况，指定不同cache。

---
Hibernate如果想实现 自动智能过滤缓存数据 方面，那么具有天生的优势。
因为本来Hibernate就是要 解析HQL的，而且Hibernate管理数据类本身及其之间的关联。什么信息都有了，做起来也相对容易很多。
当然Hibernate并没有做这个工作。Hibernate只提供了一个evictQueries()方法，不分类型地清理所有的cached query.
Hibernate的QueryKey也是直接使用结果SQL，而不是HQL。

[code:1] // from hibernate 2.7
public class QueryKey implements Serializable {
private final String sqlQueryString;
private final Type[] types;
private final Object[] values;
private final Integer firstRow;
private final Integer maxRows;
private final Map namedParameters;
...
public boolean equals(Object other) {
QueryKey that = (QueryKey) other;
if ( !sqlQueryString.equals(that.sqlQueryString) ) return false;
if ( !EqualsHelper.equals(firstRow, that.firstRow) || !EqualsHelper.equals(maxRows, that.maxRows) ) return false;
...
return true;
}
[/code:1]

可以看到，hibernate query key 直接比较结果SQL。而且我们知道，这个SQL是HQL转换过来的结果，reference一定不会相等。
假设这个SQL很长的时候，而两个SQL又相同，这个比较就会比较消耗时间。而且，这个QueryKey占的空间也比较大。
（在我的持久层里面，SQL尽量采用常量字符串、或常量字符串数组，在一定程度上解决这个问题。当然，这需要用户在使用的时候，有意识的支持）

我想了一下，为什么hibernate QueryKey直接采用结果SQL，而不用HQL。
这个SQL是HQL的解析结果，直接使用结果，节省了解析时间。比如，From A where id = 1 和 from A WHERE ID = '1'，两个HQL字符串不相同，但语义相同，转换出来的SQL一定相同。

如果Hibernate要加入智能管理QueryCache的功能，需要在QueryKey里面加入更多的信息（比如，HQL的解析结果的条件过滤部分），这样QueryKey的占用空间就会进一步加大。

使用hibernate的 interceptor来对缓存进行更新??

有一个hibernate cache讨论。
http://forum.javaeye.com/viewtopic.php?t=6593

我的另一个帖子里面也有介绍。
http://forum.javaeye.com/viewtopic.php?t=9706

Hibernate主要的缓存是ID缓存（二级缓存），而QueryCache缓存的支持非常初级。
ID缓存的Key非常简单，就是persistent class + entity identifier。
具体来说，每个不同的persistent class有独立的ID缓存，该独立ID缓存的key就是 entity identifier。

ID缓存的管理是不是在 Method Interceptor里面管理的。我从hibernate代码中看不出这一点。也许在Hibernate自定义的Event中处理。
我大致猜测一下，Hibernate把updated, inserted, deleted Entities(对于用户来说，就是PO；对于Hibernate来说，就是Entity, Proxy)都保存在内部的一个Collection结构里面。在最后Session.flush()的时候，统一处理，同步更新数据库状态，和ID缓存状态。

如果持久层本身不能做cache的自动清理工作，那么这个cache功能还是不要加在持久层比较好。
因为你写代码的时候，还得去看过别人写的所有代码，是否有cache你做了操作的东东，然后再来决定是否要添加cache.clear()这行代码。
或者你在写代码的时候，不需要clear cache，但是以后别人加了某些功能，用了finder.setCache(cache)，他还得去找到你的这些代码，然后再加上cache.clear()。

偶觉得这样的做法是不可接受的......

我的DAO写法一般是这样的。
[code:1]
public class MessageDAO{
public static final ICache cache = new Cache();
public static final ICachedFinder cachedFinder = factory.cachedFinder (Message.class, cache);
// 里面调用了finder.setCache(cache);
// 如果不用Cache, 那么IFinder finder = factory.finder(Message.class); 
public static final IPersister persister = factory.persister();

public List getMessages(conP,  forumId, filterDate) ..{
Object[] params = {forumId, filterDate};
return finder.queryRows(conP, sql, params);
}

public void saveMessage(con, message){
if(... ){persister.updateRow();finder.cacheRow(message);}
else  {persister.insertRow();cache.clear();}
};
[/code:1]

这里关于message的cache操作都集中在MessageDAO里面。
MessageDAO的每个方法确实应该清楚知道发生在Message Cache上面的所有事情。
如果这里用到的是ID Cache，那么很简单，persister操作数据的时候，直接根据ID，更新或删除Cache中对应的数据。正如Hibernate操作ID缓存一样。
由于这里用到的是QueryCache，因为涉及到查询条件，只能放权给用户自己处理。
比如，上面的例子中，查询条件包括created_date > filter_date。
用户知道update Message的时候，不会更新created_date这个字段，所以，不用清理整个Message Query Cache，只要更新缓存中Message ID对应的数据即可。
用户知道insert/delete Message的时候，getMessages()的Query Cache需要清空。

我想，你的主要论点是从持久层的功能的完整性出发：既然持久层不能完全管理Cache，那么干脆就完全不提供Cache接口或相关操作。

这里的cache不由持久层控制，是由用户用setCache()挂接到cached finder里面的。finder也分为两层，基层就是一个只查询数据库的finder，上面又包了一层cachedFinder作为cache的方便操作，可以作持久层的一个扩展。在cachedFinder上面又进一步提供了Paginator，作为持久层的进一步扩展。

扩展部分的cachedFinder和Paginator都只是作为cache的操作者之一，并不能完全控制cache。因为涉及到的是Query Cache，控制比较复杂。
关于Query Cache的完整控制，你有什么好的建议？

Hibernate的Query Cache好像也没有办法做到完整的控制，也向外部用户暴露了两个操作Query Cache的方法，evictQueries() 和setCacheRegion()。
另外，关于Hibernate ID Cache。如果在Hibernate之外又用了JDBC 执行update / delete / insert 语句，需要手动清除Hibernate ID Cache里面的 脏数据，我们也不得不深入到其中，获取对应的Cache。比如，如果用EHCache，需要调用cache = CacheManager.getInstance().getCache(entity mapped class name ?); 获取对应的Cache，然后调用cache.clear()。这完全取决于你需要的控制级别。
我的假设是，我的用户都是需要完全控制Query cache能力的高级用户，那么索性就把cache直接暴露给用户。cache这东西本来就属于难以控制，封也封不好的那一类操作，我能做多少，就做多少。
而且，我一向鼓励对开源项目的“白盒”应用（了解基本的内部实现原理，以便更好的应用），而不仅仅是“黑盒”应用。
完整的测试分为“白盒”和“黑盒”，开源项目的应用，同样的，也应该两者兼顾，才能获得完整的应用效果。

除了Query Cache的非完整控制，我做的持久层还有更多的“不可接受”的地方。
1．Finder可以接受而且鼓励用户尽量用常量字符串、或者常量字符串数组作为SQL输入。这需要用户理解一定的内部机制，并配合使用。
2. No support for Plain Object. 需要用户理解各基类的区别和一定的内部机制。
如果要发布，这些地方都要在 Doc + API + Samples 里面大书特书。

我这里用“持久层”这个词，主要是为了遵守习惯。其实，这个东西只是定位为一个可以和JDBC配合使用的辅助lib，根本称不上一个“层”。设计思路是尽量暴露给用户尽量多的控制能力，帮助用户更好的认识并应用JDBC/SQL的高级功能，而不是封装底层JDBC/SQL的细节。
数据库是空间时间效率都很关键的资源，特别是到了真正的关键应用的时候，很多高级需求是封也封不住的。
比如，数据对象的级联关系的实现难度很大，需要考虑到方方面面。Hibernate已经做的相当好了，但还是经常听到很多人的抱怨： 这里想outer join，却inner join了；这里想删，却没删；那里不想删，却删了。具体的需求是多样的，封装有些时候会起反作用，抹杀并阻碍多样性的需求实现。
其实，我一直很疑惑，级联关系带来的好处有多大，值得付出这些头痛的代价？以前用Entity Bean的时候，关联起来的一堆Entity Bean一定要部署在同一个jar里面。从此对关联很敬畏。

我做的这个东西还有一个典型的“非（经）典”的应用方式：竟然出现了ResultSet。用在批量处理几十万条结果集的时候。
[code:1]
sql = “select A.*, B.*, C.* from A, B, C where ….. ”;
rs = ps.executeQuery(); // 几十万条结果
A a = new A();
B b = new B();
C c = new C();

while(rs.next()){ // 循环几十万次
  a.populate(rs);
  b.populate(rs);
  c.populate(rs);

  business.process (a, b, c);
}
[/code:1]

在这个过程中，数据库查询只要一次，a, b, c三个数据对象，也只需要new 一次。空间、时间效率很高，和直接使用JDBC一样，但同时也做到了O/R Mapping.-- 把ResultSet 映射为Object。
其实，这种使用方式也可以支持PO。比如，做一个setBeanPropeties(bean, resultSet);在循环里面调用，
setBeanProperties(a, rs);
setBeanProperties(b, rs);
setBeanProperties(c, rs);

当然，做几十万次reflection也是令人不快的。那么在循环外面直接用CGLIB生成dynamic proxy
A a = Enhancer. create(…. new A() ….);
B b = Enhancer. create(…. new B() ….);
C c = Enhancer. create(…. new C() ….);

不过我估计没有人会采用这种用法。因为这种用法暴露了ResultSet（意味着前面暴露了PreparedStatement，和Connection），违反了封装性原则。
这不就让用户（Business Logic那部分程序）知道自己在用JDBC操作数据库了吗？那用O/R还有什么意义？直接传ResultSet得了。
但我觉得，从编程的角度来看，O/R的主要意义就在于：用户使用Object的getter(), setter()， O/R则用户产生并执行update, delete, insert SQL，并帮助用户从ResultSet获得带有getter(), setter()的Object。

Hibernate的Query Cache策略就是和CafeBabe说的一样，给本次操作中用到的所有Entity做上失效的标志，具体的代码在net.sf.hibernate.cache.UpdateTimestampsCache

在使用Hibernate的Query Cache时候，不需要担心会发生Cache和数据库不一致的情况，Hibernate会帮偶们处理。但是如果不通过Hibernate代码，直接修改数据库内容，Hibernate的Cache就一无所知了，所以Hibernate暴露了Cache的清除方法，给偶们一个擦屁股的机会。

关于智能的Cache clear的问题，是偶在实际开发中遇到的：系统的读/写操作比例比较低的时候，Hibernate会做频繁的Cache失效判断，以及Cache的清除，Cache带来的性能提高不是很明显。后来偶们讨论的结果是：持久层透明支持智能的Cache clear是不可能的任务......偶们是把这个Cache移到业务层，然后自己加代码做人工的智能清除

多谢关于UpdateTimestampsCache的提示。
我虽然看到了StandardQueryCache里面调用了UpdateTimestampsCache的isUpdateToDate()，但没有进行特别的关注。
现在我要从UpdateTimestampsCache开始，好好调查一下整个思路。

下面是UpdateTimestampsCache的注释。
[code:1]
/**
* Tracks the timestamps of the most recent updates to particular tables. It is
* important that the cache timeout of the underlying cache implementation be set
* to a higher value than the timeouts of any of the query caches. In fact, we
* recommend that the the underlying cache not be configured for expiry at all.
* Note, in particular, that an LRU cache expiry policy is never appropriate.
* @author Gavin King, Mikheil Kapanadze
*/
public class UpdateTimestampsCache {

[/code:1]

注释里面建议，that the the underlying cache not be configured for expiry at all。

你们的做法是，
1. cache not be configured for expiry，然后自己用evictQueries()做手工清理的工作？
还是
2. 不用hibernate underlying cache，在Hibernate之上，另外提供了自己的一套cache机制？