关于PostgreSQL的GiST索引之二

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

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

还好，PG手册中有一段指导很有帮助。

------------------------------------------------------------
在选择要使用的索引类型时，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

相关宏定义

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

#define SIGLEN    ( sizeof(int32) * SIGLENINT )
#define SIGLENBIT (SIGLEN * BITS_PER_BYTE)

typedef char BITVEC[SIGLEN];
typedef char *BITVECP;

...

/*
 * type of GiST index key
 */

typedef struct
{
    int32        vl_len_;        /* varlena header (do not touch */
    int32        flag;
    char        data[1];
} SignTSVector;

#define ARRKEY        0x01
#define SIGNKEY        0x02
#define ALLISTRUE    0x04

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

索引的存储格式

Datum
gtsvector_compress(PG_FUNCTION_ARGS)
{
    GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
    GISTENTRY *retval = entry;

    if (entry->leafkey)
    {                            /* tsvector */
        SignTSVector *res;
        TSVector    val = DatumGetTSVector(entry->key);
        int32        len;
        int32     *arr;
        WordEntry *ptr = ARRPTR(val);
        char     *words = STRPTR(val);
//对tsvector中的每个keywork，生成4字节的哈希值（sign），放到SignTSVector中，SignTSVector的flag是ARRKEY，大小为keywork数。
        len = CALCGTSIZE(ARRKEY, val->size);
        res = (SignTSVector *) palloc(len);
        SET_VARSIZE(res, len);
        res->flag = ARRKEY;
        arr = GETARR(res);
        len = val->size;
        while (len--)
        {
            pg_crc32    c;

            INIT_CRC32(c);
            COMP_CRC32(c, words + ptr->pos, ptr->len);
            FIN_CRC32(c);

            *arr = *(int32 *) &c;
            arr++;
            ptr++;
        }
//去除重复Sign
        len = uniqueint(GETARR(res), val->size);
        if (len != val->size)
        {
            /*
             * there is a collision of hash-function; len is always less than
             * val->size
             */
            len = CALCGTSIZE(ARRKEY, len);
            res = (SignTSVector *) repalloc((void *) res, len);
            SET_VARSIZE(res, len);
        }

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

            len = CALCGTSIZE(SIGNKEY, 0);//sizeof(int32)*31
            ressign = (SignTSVector *) palloc(len);
            SET_VARSIZE(ressign, len);
            ressign->flag = SIGNKEY;
            makesign(GETSIGN(ressign), res);
            res = ressign;
        }

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

        len = CALCGTSIZE(SIGNKEY | ALLISTRUE, 0);
        res = (SignTSVector *) palloc(len);
        SET_VARSIZE(res, len);
        res->flag = SIGNKEY | ALLISTRUE;

        retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
        gistentryinit(*retval, PointerGetDatum(res),
                      entry->rel, entry->page,
                      entry->offset, FALSE);
    }
    PG_RETURN_POINTER(retval);
}

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

Datum
gtsvector_consistent(PG_FUNCTION_ARGS)
{
    GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
    TSQuery        query = PG_GETARG_TSQUERY(1);

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

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

    if (!query->size)
        PG_RETURN_BOOL(false);

    if (ISSIGNKEY(key))
    {
        if (ISALLTRUE(key))
            PG_RETURN_BOOL(true);

        PG_RETURN_BOOL(TS_execute(
                                  GETQUERY(query),
                                 (void *) GETSIGN(key), false,
                                  checkcondition_bit
                                 ));
    }
    else
    {                            /* only leaf pages */
        CHKVAL        chkval;

        chkval.arrb = GETARR(key);
        chkval.arre = chkval.arrb + ARRNELEM(key);
        PG_RETURN_BOOL(TS_execute(
                                  GETQUERY(query),
                                 (void *) &chkval, true,
                                  checkcondition_arr
                                 ));
    }
}
...
//对SIGNKEY形式的索引项。在索引项中找到query单词的sign对应的bit位。为1则匹配。
static bool
checkcondition_bit(void *checkval, QueryOperand *val)
{
    /*
     * we are not able to find a a prefix in signature tree
     */
    if (val->prefix)
        return true;
    return GETBIT(checkval, HASHVAL(val->valcrc));
}

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

    /* Loop invariant: StopLow <= val < StopHigh */

    /*
     * we are not able to find a a prefix by hash value
     */
    if (val->prefix)
        return true;

    while (StopLow < StopHigh)
    {
        StopMiddle = StopLow + (StopHigh - StopLow) / 2;
        if (*StopMiddle == val->valcrc)
            return (true);
        else if (*StopMiddle < val->valcrc)
            StopLow = StopMiddle + 1;
        else
            StopHigh = StopMiddle;
    }

    return (false);
}

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

static int32
unionkey(BITVECP sbase, SignTSVector *add)
{
    int32        i;

    if (ISSIGNKEY(add))
    {
        BITVECP        sadd = GETSIGN(add);

        if (ISALLTRUE(add))
            return 1;

        LOOPBYTE
            sbase[i] |= sadd[i];
    }
    else
    {
        int32     *ptr = GETARR(add);

        for (i = 0; i < ARRNELEM(add); i++)
            HASH(sbase, ptr[i]);
    }
    return 0;
}

Datum
gtsvector_union(PG_FUNCTION_ARGS)
{
    GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
    int         *size = (int *) PG_GETARG_POINTER(1);
    BITVEC        base;
    int32        i,
                len;
    int32        flag = 0;
    SignTSVector *result;

    MemSet((void *) base, 0, sizeof(BITVEC));
    for (i = 0; i < entryvec->n; i++)
    {
        if (unionkey(base, GETENTRY(entryvec, i)))
        {
            flag = ALLISTRUE;
            break;
        }
    }

    flag |= SIGNKEY;
    len = CALCGTSIZE(flag, 0);
    result = (SignTSVector *) palloc(len);
    *size = len;
    SET_VARSIZE(result, len);
    result->flag = flag;
    if (!ISALLTRUE(result))
        memcpy((void *) GETSIGN(result), (void *) base, sizeof(BITVEC));

    PG_RETURN_POINTER(result);
}

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

static int
hemdistsign(BITVECP a, BITVECP b)
{
    int            i,
                diff,
                dist = 0;

    LOOPBYTE
    {
        diff = (unsigned char) (a[i] ^ b[i]);
        dist += number_of_ones[diff];
    }
    return dist;
}