海鷗航際

分頁 & QueryKey & 預取

數據庫分頁查詢一般分為兩步，
(1)根據查詢條件，count 記錄總數
(2)根據當前頁的數據范圍(起始位置offset, 每頁數據個數span)，從符合查詢條件的記錄集取出對應范圍的數據。

一、根據范圍取數據的方法
如果單純用JDBC從ResultSet中取出一個指定范圍（offset, span）的數據，可以采用這樣的方法。

java代碼:

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())... 

數據量大的時候，頁數很多，offset很大，這種方法不太適合。這時候，需要使用各數據庫的native SQL特性。
我們來看Hibernate dialect package的類，支持了各種數據庫的getLimitString方法。這里舉Mysql和Oracle的例子。假設查詢語句為

java代碼:

Select * from message where forum_id = ? and created_time > ? order by created_time desc 

Mysql 的limit SQL為

java代碼:

Select * from message where forum_id = ? and created_time > ? order by created_time desc 
limit ?, ? 

后面的兩個limit ?, ? 分別為 offset, span。

Oracle的limit SQL為

java代碼:

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_ > ? 

后面的兩個limit ?, ? 分別為 offset + span, offset。

二、緩存 & QueryKey
count語句可以根據查詢語句自動生成，比如

java代碼:

Select count(*) from ( 
Select * from message where forum_id = ? and created_time > ? order by created_time desc 
) 

這樣的自動count語句有些浪費，用了子查詢不說，還保留了沒有必要的order by。最好還是另外提供一個count語句。

java代碼:

Select count(*) from message where forum_id = ? and created_time > ? 

在多頁翻動的情況下，這個count語句要被反復執行。為了提高效率，我把這個count結果保存在全局緩存中，不僅本Session用戶可以重復使用，其他用戶在根據同樣條件翻找message的時候，也可以重復使用這個結果。

我在持久層中使用通用的QueryKey做為緩存鍵值。
QueryKey分成三個部分，SQL, Parameters, Range。比如：

java代碼:

Query Key: 
SQL : Select count(*) from message where forum_id = ? and created_time > ? 
Parameters : [buaawhl, time long value] 
Range: (0, 1) 

這個QueryKey的效率很關鍵。主要是hashCode和equals兩個方法的效率。
我們知道，當key放在Map等Hash數據結構中，首先hashCode，然后用equals比較hashCode后面的一串key。
舉個例子。Key1和key2 的hashCode一樣，都和key3的hashCode不一樣。

java代碼:

… 
[ 101 ] -> key1 -> key2 
… 
[ 666 ] -> key3 
… 

可以看到，hashCode，equals，這兩個方法都是每次查找緩存都要調用的方法。尤其是equals方法更是重中之重，很可能需要被調用多次。
hashCode的優化實現相對來說比較簡單，只要根據QueryKey中各部分的不同，盡量實現hashCode取值的擴散化，降低hashCode的重復率就可以了。
關鍵是equals的實現方案。這里有個原則，越小的結構越先比較，可以提高比較速度。
QueryKey中的parameters和range比較好辦。每次equals比較的時候，先比較range，如果不相等，返回false; 如果相等，再比較Parameters，如果有一個parameter value不相等，返回false。這樣，我們可以用很短的時間開銷過濾掉一大批不相等的QueryKey。
但是parameters和range都相等的時候，我們還是無可避免的要比較SQL。String的equals方法如下：

java代碼:

// 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; 
    } 

我們看到，當SQL String很長的時候，長度相等，前面大部分字符相同的時候，(最極端的情況下，兩個不同reference的String的字符完全相等)，這個比較是相當消耗時間的。比如，

java代碼:

Select * from message where forum_id = ? and created_time > ? order by created_time desc 

和

java代碼:

Select * from message where forum_id = ? and created_time > ? order by updated_time desc 

兩個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[]類型。
比如。

java代碼:

String[] sql1 = { 
“Select * from message where forum_id = ?”， 
“ and created_time > ?”, 
“ order by ”, 
“created_time”, 
“desc” 
}; 

和

java代碼:

String[] sql2 = { 
“Select * from message where forum_id = ?”， 
“ and created_time > ?”, 
“ order by ”, 
“created_time”, 
“desc” 
}; 

和

java代碼:

String[] sql3 = { 
“Select * from message where forum_id = ?”， 
“ and created_time > ?”, 
“ order by ”, 
“updated_time”, 
“desc” 
}; 

這個時候，比較sql1和sql2和sql3的效率就會大大提高，雖然sql1 和 sql2兩個數組的長度相等，還是要一個元素一個元素的比較，但由于里面大量用到了String常量，相同的String常量具有相同的reference，所以5步下來，就可以判斷出sql1和sql2數組的元素是完全相等的；4步下來，加上第一個字符的比較，就可以判斷sql1和sql3的第4個元素是不相等的。

我們看到，做法1和做法2，能夠100%的提高SQL的比較效率，大部分情況下，也許比parameters的比較還快。

三、定長預取
多用戶訪問同一頁面的可能性比較大的情況下，比如，論壇的某些熱門話題，很可能被多人同時翻閱。這時候，如果把根據范圍取出的數據對象List也按照QueryKey存入緩存中，那么就可以大大提高響應速度，減輕數據服務器負擔，當然，你的Web Server的內存負擔也大大增加了。 Smile
我們進一步考慮下面兩種情況：
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'的對象是否還能保持有效呢？

沒有這么智能。我現在無法做到 cache的自動清理和聰明地清理。
我現在做的持久層本身是不做cache的清理管理工作，這個工作交給調用程序自己去做。cache也需要用戶自己實現，并且明確提供。
查詢的時候，需要指定cache

java代碼:

finder.setRowClass(Message.class);
finder.setCache(cache);
finder.queryRowsRange(conP, sql, params, offset, span);

這個時候，finder會用 QueryKey(sql, params, offset, span) 作為Key,
從指定的cache里面，查找對應的記錄集合。
如果查不到，從conP真正獲取一個connection，連接并查找數據庫，把結果放到cache里面。
這里有個優化，如果指定了緩存，而且只有當緩存中不存在目標數據的時候，才真正地從連接池中獲取connection。主要是考慮到連接池的大小總是有限的，如果并發用戶多的話，這樣就可以節省連接池里的connection的分配。

---
update, delete, update的時候，用戶需要手動自己清理cache的內容。

java代碼:

persister.insertRow(con, message);
cache.clear();
// 或者更智能的操作, 比如, 根據message的message_to value,
// 清理Cache里面的符合下列條件的QueryKey
// (sql 包含 message_to = ?, 并且 params[0] = buaawhl)

我做的持久層，由于直接使用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。

java代碼:

// 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;
}

可以看到，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 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緩存狀態。

海鷗航際

導航

常用鏈接

留言簿(4)

隨筆檔案

文章分類

文章檔案

相冊

搜索

最新評論

閱讀排行榜

評論排行榜

分頁 & QueryKey & 預取