《Next generation of GIN》解讀 1.壓縮存儲 2. frequent_entry & rare_entry時的快速掃描 3. 類KNN的GIN索引掃描 參考

PGConf.EU-2013的一篇名叫《Next generation of GIN》的PPT（作者Alexander Korotkov和Oleg Bartunov）中提到了GIN的幾個優化，對GIN的性能都有很大提升。概括起來主要有3點。

原來GIN索引的posting list(或posting tree)中每個ItemPointer占6個位元組，通過下面的方法最終可以壓縮到2～3個位元組。

varbyte編碼(也就是protocol buffer中的variable-length encoding)

存儲塊号的增量而不是實際塊号

當1個頻繁的key和1個稀少的key做邏輯與條件查詢時，原來要分别把它們的索引項目取出來再做與操作。由于頻繁的key比對的項目太多，導緻了大量的Page通路。優化後先從比對項目最少的索引入手，再到其它索引裡查找這些項目有沒有同時出現在其它索引裡，有的話則比對否則不比對。

這個叫法是基于我對這個優化的了解起的名字。

看下面這個TopN查詢的例子。

上面的執行計劃中，為了計算相似度，把大量的比對記錄（47855）從堆裡讀了出來，進而引起了大量的Page讀影響處理速度。 優化思路是在GIN的posting list(或posting tree)裡加入一些資訊，在這裡就是，關鍵字的位置和權重。 這樣計算相似度時，不需要再讀堆，相似度計算完後隻取最比對的3條記錄，是以最多隻要進行3次堆表的Page通路。 Patch修改後的效果如下。

根據作者的測試，使用了這個Patch之後，一些全文檢索的場景下性能可提升10多倍，比Sphinx還快。 但是由于要在索引裡追加東西，會增加索引的大小，有些場景也會有反作用。

目前上面1和2的改進早已經合并到PostgreSQL 9.4裡了，這使得GIN成為索引重複值很多的資料字段的利器（占用存儲空間小，多條件組合的支援好）；但第3個目前還沒有加到主分支，可能方案還需進一步完善吧。

http://www.sai.msu.su/~megera/postgres/talks/Next%20generation%20of%20GIN.pdf

http://www.sai.msu.su/~megera/postgres/talks/hstore-dublin-2013.pdf

http://www.pgcon.org/2014/schedule/attachments/329_PGCon2014-GIN.pdf

http://www.infoq.com/cn/news/2015/05/PostgreSQL-Lateral-Max

http://www.oschina.net/question/12_132079?sort=default&p=1

http://obartunov.livejournal.com/175235.html