关于PostgreSQL的GiST索引之四

3. hstore的GiST索引

hstore的GiST索引实现和全文检索的tsvector的GiST索引的实现差不过,都是签名文件索引。

3.1 GiST索引项的存储

1)所有索引项都采用签名向量压缩
2)hstore中的所有键和所有值都进行哈希设置bit位得到一个签名向量
3)签名向量的大小为128bit

3.2 性能推论

1)索引尺寸比较小(因为签名向量的大小是固定的而且一般比原始数据小)
2)每次查询要扫描的索引页很多(20%~40%索引页
3)每次键查询(?操作符)至少要recheck 1.6%(2/128)以上的数据行
  每条记录包含的键值对越多,需要recheck的数据行越多
4)每次键值查询(@>操作符)至少要recheck 0.02%((2/128) * (2/128))以上的数据行
  每条记录包含的键值对越多,需要recheck的数据行越多

假设每条记录平均包含10条键值对,需要recheck的数据行估算如下
键查询(?操作符)匹配:7.5%的数据行

点击(此处)折叠或打开

  1. testdb=# with recursive tx1(n,sign_bits) as
  2. testdb-# (select 1 n,1.0 sign_bits
  3. testdb(# union all
  4. testdb(# select n+1, sign_bits + 1 - sign_bits/128 from tx1 where n<=10
  5. testdb(# )
  6. testdb-# select n,sign_bits,sign_bits/128 scan_probability from tx1 where n in(10);
  7.  n | sign_bits | scan_probability
  8. ----+------------------------+------------------------
  9.  10 | 9.65566251563533320389 | 0.07543486340340104066
  10. (1 row)
由此可见对键查询(多个键的?&查询另当别论),hstore的GiST索引的查询效率是比较低的。不过,从另外一个角度考虑,通常的应用场景下,不同的key值数本来就不会很多,就不是索引的用武之地。

键值查询(@>操作符)匹配:0.57%(0.57%=0.07543486340340104066*0.07543486340340104066)

但是这只是理论上的平均值,由于签名向量的冲突,个别查询的效率可能会很低。比如,如果大部分数据记录都包含某个key,而查询这个键值对的时候,碰巧它的值在签名向量中对应的bit位和这个很常用的key相同,那么大部分数据记录都要进行recheck

3.3 相关代码

contrib/hstore/hstore_gist.c

点击(此处)折叠或打开

  1. /* bigint defines */
  2. #define BITBYTE 8
  3. #define SIGLENINT 4            /* >122 => key will toast, so very */
  4. #define SIGLEN    ( sizeof(int)*SIGLENINT )
  5. #define SIGLENBIT (SIGLEN*BITBYTE)

  6. typedef char BITVEC[SIGLEN];
  7. typedef char *BITVECP;

  8. ...
  9. Datum
  10. ghstore_compress(PG_FUNCTION_ARGS)
  11. {
  12.     GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
  13.     GISTENTRY *retval = entry;

  14.     if (entry->leafkey)
  15.     {
  16.         GISTTYPE *res = (GISTTYPE *) palloc0(CALCGTSIZE(0));
  17.         HStore     *val = DatumGetHStoreP(entry->key);
  18.         HEntry     *hsent = ARRPTR(val);
  19.         char     *ptr = STRPTR(val);
  20.         int            count = HS_COUNT(val);
  21.         int            i;

  22.         SET_VARSIZE(res, CALCGTSIZE(0));

  23. //遍历所有KV对
  24.         for (i = 0; i < count; ++i)
  25.         {
  26.             int            h;
  27. //对key做哈希
  28.             h = crc32_sz((char *) HS_KEY(hsent, ptr, i), HS_KEYLEN(hsent, i));
  29.             HASH(GETSIGN(res), h);
  30.             if (!HS_VALISNULL(hsent, i))
  31.             {
  32. //对value做哈希
  33.                 h = crc32_sz((char *) HS_VAL(hsent, ptr, i), HS_VALLEN(hsent, i));
  34.                 HASH(GETSIGN(res), h);
  35.             }
  36.         }

  37.         retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
  38.         gistentryinit(*retval, PointerGetDatum(res),
  39.                      entry->rel, entry->page,
  40.                      entry->offset,
  41.                      FALSE);
  42.     }
  43.     else if (!ISALLTRUE(DatumGetPointer(entry->key)))
  44.     {
  45.         int32        i;
  46.         GISTTYPE *res;
  47.         BITVECP        sign = GETSIGN(DatumGetPointer(entry->key));

  48.         LOOPBYTE
  49.         {
  50.             if ((sign[i] & 0xff) != 0xff)
  51.                 PG_RETURN_POINTER(retval);
  52.         }

  53.         res = (GISTTYPE *) palloc(CALCGTSIZE(ALLISTRUE));
  54.         SET_VARSIZE(res, CALCGTSIZE(ALLISTRUE));
  55.         res->flag = ALLISTRUE;

  56.         retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
  57.         gistentryinit(*retval, PointerGetDatum(res),
  58.                      entry->rel, entry->page,
  59.                      entry->offset,
  60.                      FALSE);
  61.     }

  62.     PG_RETURN_POINTER(retval);
  63. }


3.4 性能验证

1)环境
CentOS 6.5
PostgreSQL 9.4.0


2)测试数据准备
点击(此处)折叠或打开
  1. testdb=# create extension hstore;
  2. CREATE EXTENSION
  3. Time: 235.391 ms
  4. testdb=# create table tbhs(id serial,hs hstore);
  5. CREATE TABLE
  6. Time: 17.459 ms
  7. testdb=# insert into tbhs select id,hstore(id::text, md5(id::text)) from generate_series(1,100000) id;
  8. INSERT 0 100000
  9. Time: 970.613 ms
  10. testdb=# select pg_relation_size(‘tbhs‘);
  11.  pg_relation_size
  12. ------------------
  13.           8445952
  14. (1 row)

  15. Time: 0.643 ms
  16. testdb=# select * from tbhs limit 5;
  17.  id | hs
  18. ----+-----------------------------------------
  19.   1 | "1"=>"c4ca4238a0b923820dcc509a6f75849b"
  20.   2 | "2"=>"c81e728d9d4c2f636f067f89cc14862c"
  21.   3 | "3"=>"eccbc87e4b5ce2fe28308fd9f2a7baf3"
  22.   4 | "4"=>"a87ff679a2f3e71d9181a67b7542122c"
  23.   5 | "5"=>"e4da3b7fbbce2345d7772b0674a318d5"
  24. (5 rows)

  25. Time: 1.147 ms
注)上面每个记录只有一个键值对,且每个key都是唯一的,这样的数据模型就不适合使用hstore存储,本文故意这么做只是为了验证性能。


2)无索引的查询
点击(此处)折叠或打开
  1. testdb=# explain (analyze,buffers) select * from tbhs where hs ? ‘10‘;
  2.                                              QUERY PLAN
  3. -----------------------------------------------------------------------------------------------------
  4.  Seq Scan on tbhs (cost=0.00..2281.00 rows=100 width=53) (actual time=0.025..31.587 rows=1 loops=1)
  5.    Filter: (hs ? ‘10‘::text)
  6.    Rows Removed by Filter: 99999
  7.    Buffers: shared hit=1031
  8.  Planning time: 0.055 ms
  9.  Execution time: 31.619 ms
  10. (6 rows)

  11. Time: 32.150 ms

3)建立GiST索引再查询

点击(此处)折叠或打开

  1. testdb=# create index tbhs_idx_gist on tbhs using gist(hs);
  2. CREATE INDEX
  3. Time: 6243.003 ms
  4. testdb=# analyze tbhs;
  5. ANALYZE
  6. Time: 77.956 ms
  7. testdb=# select pg_relation_size(‘tbhs_idx_gist‘),pg_relation_size(‘tbhs_idx_gist‘)/8192 index_pages;
  8.  pg_relation_size | index_pages
  9. ------------------+-------------
  10.           4825088 | 589
  11. (1 row)

  12. Time: 0.456 ms

?查询扫描了45%(265/589)的索引页,Recheck了1.6%的数据行。

点击(此处)折叠或打开

  1. testdb=# explain (analyze,buffers) select * from tbhs where hs ? ‘10‘;
  2.                                                         QUERY PLAN
  3. ---------------------------------------------------------------------------------------------------------------------------
  4.  Bitmap Heap Scan on tbhs (cost=5.06..302.42 rows=100 width=53) (actual time=3.003..4.637 rows=1 loops=1)
  5.    Recheck Cond: (hs ? ‘10‘::text)
  6.    Rows Removed by Index Recheck: 1558
  7.    Heap Blocks: exact=863
  8.    Buffers: shared hit=1128
  9.    -> Bitmap Index Scan on tbhs_idx_gist (cost=0.00..5.03 rows=100 width=0) (actual time=2.869..2.869 rows=1559 loops=1)
  10.          Index Cond: (hs ? ‘10‘::text)
  11.          Buffers: shared hit=265
  12.  Planning time: 0.153 ms
  13.  Execution time: 5.073 ms
  14. (10 rows)

  15. Time: 6.209 ms

@>查询扫描了19%(114/589)的索引页,Recheck了0.012%的数据行。

点击(此处)折叠或打开

  1. testdb=# explain (analyze,buffers) select * from tbhs where hs @> ‘1=>c4ca4238a0b923820dcc509a6f75849b‘;
  2.                                                        QUERY PLAN
  3. -------------------------------------------------------------------------------------------------------------------------
  4.  Bitmap Heap Scan on tbhs (cost=5.06..302.42 rows=100 width=53) (actual time=2.123..2.205 rows=1 loops=1)
  5.    Recheck Cond: (hs @> ‘"1"=>"c4ca4238a0b923820dcc509a6f75849b"‘::hstore)
  6.    Rows Removed by Index Recheck: 11
  7.    Heap Blocks: exact=12
  8.    Buffers: shared hit=126
  9.    -> Bitmap Index Scan on tbhs_idx_gist (cost=0.00..5.03 rows=100 width=0) (actual time=2.097..2.097 rows=12 loops=1)
  10.          Index Cond: (hs @> ‘"1"=>"c4ca4238a0b923820dcc509a6f75849b"‘::hstore)
  11.          Buffers: shared hit=114
  12.  Planning time: 0.407 ms
  13.  Execution time: 2.294 ms
  14. (10 rows)

  15. Time: 3.332 ms

4)建立GIN索引再查询
建立GIN索引对比一下。

点击(此处)折叠或打开

  1. testdb=# drop index tbhs_idx_gist;
  2. DROP INDEX
  3. Time: 7.036 ms
  4. testdb=# create index tbhs_idx_gin on tbhs using gin(hs);
  5. CREATE INDEX
  6. Time: 2244.241 ms
  7. testdb=# analyze tbhs;
  8. ANALYZE
  9. Time: 64.608 ms
  10. testdb=# select pg_relation_size(‘tbhs_idx_gin‘),pg_relation_size(‘tbhs_idx_gin‘)/8192 index_pages;
  11.  pg_relation_size | index_pages
  12. ------------------+-------------
  13.          17629184 | 2152
  14. (1 row)

  15. Time: 0.641 ms
  16. testdb=# explain (analyze,buffers) select * from tbhs where hs ? ‘10‘;
  17.                                                        QUERY PLAN
  18. ------------------------------------------------------------------------------------------------------------------------
  19.  Bitmap Heap Scan on tbhs (cost=16.77..314.14 rows=100 width=53) (actual time=0.096..0.097 rows=1 loops=1)
  20.    Recheck Cond: (hs ? ‘10‘::text)
  21.    Heap Blocks: exact=1
  22.    Buffers: shared hit=5
  23.    -> Bitmap Index Scan on tbhs_idx_gin (cost=0.00..16.75 rows=100 width=0) (actual time=0.086..0.086 rows=1 loops=1)
  24.          Index Cond: (hs ? ‘10‘::text)
  25.          Buffers: shared hit=4
  26.  Planning time: 0.349 ms
  27.  Execution time: 0.144 ms
  28. (9 rows)

  29. Time: 1.014 ms
  30. testdb=# explain (analyze,buffers) select * from tbhs where hs @> ‘1=>c4ca4238a0b923820dcc509a6f75849b‘;
  31.                                                        QUERY PLAN
  32. ------------------------------------------------------------------------------------------------------------------------
  33.  Bitmap Heap Scan on tbhs (cost=28.77..326.14 rows=100 width=53) (actual time=0.070..0.071 rows=1 loops=1)
  34.    Recheck Cond: (hs @> ‘"1"=>"c4ca4238a0b923820dcc509a6f75849b"‘::hstore)
  35.    Heap Blocks: exact=1
  36.    Buffers: shared hit=8
  37.    -> Bitmap Index Scan on tbhs_idx_gin (cost=0.00..28.75 rows=100 width=0) (actual time=0.047..0.047 rows=1 loops=1)
  38.          Index Cond: (hs @> ‘"1"=>"c4ca4238a0b923820dcc509a6f75849b"‘::hstore)
  39.          Buffers: shared hit=7
  40.  Planning time: 0.131 ms
  41.  Execution time: 0.105 ms
  42. (9 rows)

  43. Time: 0.661 ms
GIN索引的查询效率相当不错。GIN的缺点是:索引比较大,对更新速度有一定影响。

3.5 参考

http://blog.chinaunix.net/uid-20726500-id-4884626.html
http://blog.chinaunix.net/uid-20726500-id-4884681.html
http://blog.chinaunix.net/uid-20726500-id-4886571.html
http://blog.chinaunix.net/uid-259788-id-4279627.html


郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。