关于PostgreSQL的GiST索引之二-阿里云开发者社区

开发者社区> 数据库> 正文

关于PostgreSQL的GiST索引之二

简介: 2. 全文检索的GiST索引实现 PostgreSQL的全文检索有GiST和GIN两种索引方式,应该选择哪种索引类型有时让人困惑。 还好,PG手册中有一段指导很有帮助。 http://58.58.27.50:8079/doc/html/9.3.1_zh/ ------------------------------------------------------------ 在选择要使用的索引类型时,GiST或者GIN考虑这些性能上的差异:GIN索引查找比GiST快约三倍GIN索引建立比GIST需要大约三倍的时间。

2. 全文检索的GiST索引实现

PostgreSQL的全文检索有GiST和GIN两种索引方式,应该选择哪种索引类型有时让人困惑。

还好,PG手册中有一段指导很有帮助。
http://58.58.27.50:8079/doc/html/9.3.1_zh/
------------------------------------------------------------
在选择要使用的索引类型时,GiST或者GIN考虑这些性能上的差异:
GIN索引查找比GiST快约三倍
GIN索引建立比GIST需要大约三倍的时间。
GIN索引更新比GiST索引速度慢,但如果快速更新支持无效,则慢了大约10倍(详情请见节Section 57.3.1)
GIN索引比GiST索引大两到三倍
一般来说,GIN索引对静态数据是最好的,因为查找速度很快。对于动态数据, GiST索引更新比较快。具体而言,GiST索引非常适合动态数据,并且如果独特的字(词)在100,000以下, 则比较快,而GIN索引将处理100,000+词汇,但是更新比较慢。
------------------------------------------------------------

以上是一些经验上的认识,为了更好理解GiST如何在全文检索中发挥作用,下面了解一下GiST索引的具体算法。
(GIN采用的是倒排索引算法,倒排索引在全文检索中应用太广了,就没必要多说了。)

2.1 算法概述

PostgreSQL的全文检索会把文档切成由若干词元(keyword)组成的向量,即tsvector。tsvector的GiST操作符类采用类似签名文件索引的算法实现。大致如下
1.存储结构
a)页节点的索引项
页节点的索引项有3种存储格式
ARRKEY
  为tsvector中的每个词元生成一个4字节的Sign值(哈希值),索引项存储这些Sign值的数组。
SIGNKEY
  当词元太多导致ARRKEY形式的索引项大小超过TOAST_INDEX_TARGET(大约500多个字节),则采用SIGNKEY形式的存储。
  SIGNKEY形式的存储是一个992bit的Bit向量,把每个词元的Sign值对992取模值,模值对应的SIGNKEY的Bit位置1。
ALLISTRUE
  如果在SIGNKEY形式的存储下,所有的Bit位都是1,那么采用ALLISTRUE格式,表示匹配所有关键字。ALLISTRUE格式不需要保存实际的Bit向量,可节省空间。

b)非页节点的索引项
 非页节点的索引项只有SIGNKEY和ALLISTRUE 2种存储格式。

2.索引项插入节点分裂
当插入一个新的索引项时,选择一个插入后需要由0置1的索引项bit位数最少的子树作为插入位置。
当一个节点的元素满了,需要进行分裂时。选择一个能使分裂后2个子树不同的bit位最多的分裂方案。
这样可保持索引树的平衡。

2.2.相关代码实现

src/backend/utils/adt/tsgistidx.c

相关宏定义

点击(此处)折叠或打开

  1. ...
  2. #define SIGLENINT 31            /* >121 => key will toast, so it will not work
  3.                                  * !!! */

  4. #define SIGLEN    ( sizeof(int32) * SIGLENINT )
  5. #define SIGLENBIT (SIGLEN * BITS_PER_BYTE)

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

  8. ...

  9. /*
  10.  * type of GiST index key
  11.  */

  12. typedef struct
  13. {
  14.     int32        vl_len_;        /* varlena header (do not touch */
  15.     int32        flag;
  16.     char        data[1];
  17. } SignTSVector;

  18. #define ARRKEY        0x01
  19. #define SIGNKEY        0x02
  20. #define ALLISTRUE    0x04

  21. #define ISARRKEY(x) ( ((SignTSVector*)(x))->flag & ARRKEY )
  22. #define ISSIGNKEY(x)    ( ((SignTSVector*)(x))->flag & SIGNKEY )
  23. #define ISALLTRUE(x)    ( ((SignTSVector*)(x))->flag & ALLISTRUE )

索引的存储格式

点击(此处)折叠或打开

  1. Datum
  2. gtsvector_compress(PG_FUNCTION_ARGS)
  3. {
  4.     GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
  5.     GISTENTRY *retval = entry;

  6.     if (entry->leafkey)
  7.     {                            /* tsvector */
  8.         SignTSVector *res;
  9.         TSVector    val = DatumGetTSVector(entry->key);
  10.         int32        len;
  11.         int32     *arr;
  12.         WordEntry *ptr = ARRPTR(val);
  13.         char     *words = STRPTR(val);
  14. //对tsvector中的每个keywork,生成4字节的哈希值(sign),放到SignTSVector中,SignTSVector的flag是ARRKEY,大小为keywork数。
  15.         len = CALCGTSIZE(ARRKEY, val->size);
  16.         res = (SignTSVector *) palloc(len);
  17.         SET_VARSIZE(res, len);
  18.         res->flag = ARRKEY;
  19.         arr = GETARR(res);
  20.         len = val->size;
  21.         while (len--)
  22.         {
  23.             pg_crc32    c;

  24.             INIT_CRC32(c);
  25.             COMP_CRC32(c, words + ptr->pos, ptr->len);
  26.             FIN_CRC32(c);

  27.             *arr = *(int32 *) &c;
  28.             arr++;
  29.             ptr++;
  30.         }
  31. //去除重复Sign
  32.         len = uniqueint(GETARR(res), val->size);
  33.         if (len != val->size)
  34.         {
  35.             /*
  36.              * there is a collision of hash-function; len is always less than
  37.              * val->size
  38.              */
  39.             len = CALCGTSIZE(ARRKEY, len);
  40.             res = (SignTSVector *) repalloc((void *) res, len);
  41.             SET_VARSIZE(res, len);
  42.         }

  43. //如果Sign向量大于进行TOAST的阈值,再对Sign向量生成一个大的SIGNKEY,SIGNKEY由124(124=31*32)个字节992个bit组成,针对每个Sign值对992取模值,模值对应的SIGNKEY的Bit位置1。
  44.         /* make signature, if array is too long */
  45.         if (VARSIZE(res) > TOAST_INDEX_TARGET)
  46.         {
  47.             SignTSVector *ressign;

  48.             len = CALCGTSIZE(SIGNKEY, 0);//sizeof(int32)*31
  49.             ressign = (SignTSVector *) palloc(len);
  50.             SET_VARSIZE(ressign, len);
  51.             ressign->flag = SIGNKEY;
  52.             makesign(GETSIGN(ressign), res);
  53.             res = ressign;
  54.         }

  55.         retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
  56.         gistentryinit(*retval, PointerGetDatum(res),
  57.                      entry->rel, entry->page,
  58.                      entry->offset, FALSE);
  59.     }
  60.     else if (ISSIGNKEY(DatumGetPointer(entry->key)) &&
  61.              !ISALLTRUE(DatumGetPointer(entry->key)))
  62.     {
  63.         int32        i,
  64.                     len;
  65.         SignTSVector *res;
  66.         BITVECP        sign = GETSIGN(DatumGetPointer(entry->key));
  67. //对BIT向量,如果所有BIT位都置为1了,生成一个只有数据头的SignTSVector,并设置ALLISTRUE标志,减少索引的存储空间占用。
  68.         LOOPBYTE
  69.         {
  70.             if ((sign[i] & 0xff) != 0xff)
  71.                 PG_RETURN_POINTER(retval);
  72.         }

  73.         len = CALCGTSIZE(SIGNKEY | ALLISTRUE, 0);
  74.         res = (SignTSVector *) palloc(len);
  75.         SET_VARSIZE(res, len);
  76.         res->flag = SIGNKEY | ALLISTRUE;

  77.         retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
  78.         gistentryinit(*retval, PointerGetDatum(res),
  79.                      entry->rel, entry->page,
  80.                      entry->offset, FALSE);
  81.     }
  82.     PG_RETURN_POINTER(retval);
  83. }

特定索引项目是否满足查询条件的判断

点击(此处)折叠或打开

  1. Datum
  2. gtsvector_consistent(PG_FUNCTION_ARGS)
  3. {
  4.     GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
  5.     TSQuery        query = PG_GETARG_TSQUERY(1);

  6.     /* StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); */
  7.     /* Oid        subtype = PG_GETARG_OID(3); */
  8.     bool     *recheck = (bool *) PG_GETARG_POINTER(4);
  9.     SignTSVector *key = (SignTSVector *) DatumGetPointer(entry->key);

  10.     /* All cases served by this function are inexact */
  11.     *recheck = true;

  12.     if (!query->size)
  13.         PG_RETURN_BOOL(false);

  14.     if (ISSIGNKEY(key))
  15.     {
  16.         if (ISALLTRUE(key))
  17.             PG_RETURN_BOOL(true);

  18.         PG_RETURN_BOOL(TS_execute(
  19.                                  GETQUERY(query),
  20.                                  (void *) GETSIGN(key), false,
  21.                                  checkcondition_bit
  22.                                  ));
  23.     }
  24.     else
  25.     {                            /* only leaf pages */
  26.         CHKVAL        chkval;

  27.         chkval.arrb = GETARR(key);
  28.         chkval.arre = chkval.arrb + ARRNELEM(key);
  29.         PG_RETURN_BOOL(TS_execute(
  30.                                  GETQUERY(query),
  31.                                  (void *) &chkval, true,
  32.                                  checkcondition_arr
  33.                                  ));
  34.     }
  35. }
  36. ...
  37. //对SIGNKEY形式的索引项。在索引项中找到query单词的sign对应的bit位。为1则匹配。
  38. static bool
  39. checkcondition_bit(void *checkval, QueryOperand *val)
  40. {
  41.     /*
  42.      * we are not able to find a a prefix in signature tree
  43.      */
  44.     if (val->prefix)
  45.         return true;
  46.     return GETBIT(checkval, HASHVAL(val->valcrc));
  47. }

  48. //对ARRKEY形式的索引项,二分查找遍历索引项中的所有key的sign,如存在一致的返回true。
  49. /*
  50.  * is there value 'val' in array or not ?
  51.  */
  52. static bool
  53. checkcondition_arr(void *checkval, QueryOperand *val)
  54. {
  55.     int32     *StopLow = ((CHKVAL *) checkval)->arrb;
  56.     int32     *StopHigh = ((CHKVAL *) checkval)->arre;
  57.     int32     *StopMiddle;

  58.     /* Loop invariant: StopLow = val StopHigh */

  59.     /*
  60.      * we are not able to find a a prefix by hash value
  61.      */
  62.     if (val->prefix)
  63.         return true;

  64.     while (StopLow StopHigh)
  65.     {
  66.         StopMiddle = StopLow + (StopHigh - StopLow) / 2;
  67.         if (*StopMiddle == val->valcrc)
  68.             return (true);
  69.         else if (*StopMiddle val->valcrc)
  70.             StopLow = StopMiddle + 1;
  71.         else
  72.             StopHigh = StopMiddle;
  73.     }

  74.     return (false);
  75. }

key集合的合并
通过BIT向量的各bit的或操作合并key。所有非页节点的索引项的key都是BIT向量(SIGNKEY)形式。

点击(此处)折叠或打开

  1. static int32
  2. unionkey(BITVECP sbase, SignTSVector *add)
  3. {
  4.     int32        i;

  5.     if (ISSIGNKEY(add))
  6.     {
  7.         BITVECP        sadd = GETSIGN(add);

  8.         if (ISALLTRUE(add))
  9.             return 1;

  10.         LOOPBYTE
  11.             sbase[i] |= sadd[i];
  12.     }
  13.     else
  14.     {
  15.         int32     *ptr = GETARR(add);

  16.         for (i = 0; i ARRNELEM(add); i++)
  17.             HASH(sbase, ptr[i]);
  18.     }
  19.     return 0;
  20. }

  21. Datum
  22. gtsvector_union(PG_FUNCTION_ARGS)
  23. {
  24.     GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
  25.     int         *size = (int *) PG_GETARG_POINTER(1);
  26.     BITVEC        base;
  27.     int32        i,
  28.                 len;
  29.     int32        flag = 0;
  30.     SignTSVector *result;

  31.     MemSet((void *) base, 0, sizeof(BITVEC));
  32.     for (i = 0; i entryvec->n; i++)
  33.     {
  34.         if (unionkey(base, GETENTRY(entryvec, i)))
  35.         {
  36.             flag = ALLISTRUE;
  37.             break;
  38.         }
  39.     }

  40.     flag |= SIGNKEY;
  41.     len = CALCGTSIZE(flag, 0);
  42.     result = (SignTSVector *) palloc(len);
  43.     *size = len;
  44.     SET_VARSIZE(result, len);
  45.     result->flag = flag;
  46.     if (!ISALLTRUE(result))
  47.         memcpy((void *) GETSIGN(result), (void *) base, sizeof(BITVEC));

  48.     PG_RETURN_POINTER(result);
  49. }

新索引项的插入和节点分裂
新索引项的插入位置和节点分裂的策略是控制树平衡的关键。代码里通过计算Key集合签名的海明距离(对应位上编码不同的位数)来选择最优策略。。对于插入操作,尽量使插入前后的Key集合签名的海明距离最小;对于分裂操作,尽量使分裂后2个子节点间的海明距离最大。海明距离的计算通过下面的hemdistsign()函数完成。gtsvector_penalty()和gtsvector_picksplit()都调用了这个函数。

点击(此处)折叠或打开

  1. static int
  2. hemdistsign(BITVECP a, BITVECP b)
  3. {
  4.     int            i,
  5.                 diff,
  6.                 dist = 0;

  7.     LOOPBYTE
  8.     {
  9.         diff = (unsigned char) (a[i] ^ b[i]);
  10.         dist += number_of_ones[diff];
  11.     }
  12.     return dist;
  13. }


版权声明:本文首发在云栖社区,遵循云栖社区版权声明:本文内容由互联网用户自发贡献,版权归用户作者所有,云栖社区不为本文内容承担相关法律责任。云栖社区已升级为阿里云开发者社区。如果您发现本文中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,阿里云开发者社区将协助删除涉嫌侵权内容。

分享:
数据库
使用钉钉扫一扫加入圈子
+ 订阅

分享数据库前沿,解构实战干货,推动数据库技术变革

其他文章