KY的技术小站

Cpp creates world

0%

SQLite--KeywordHash

Posted on Edited on In

SQLite 的关键字有很多个(在3.27.2版本就支持136个)。从用户侧输入一个SQL语句到Tokenize(词法分析器)的时候，SQLite如何快速判断一个单词是否是关键字呢？第一想法肯定是利用哈希表，SQLite也确实是如此。但是如何构建一个查询高效，存储占用低，而且还支持关键字”裁剪”的哈希表呢？这里从源码的角度来看，SQLite是如何一步一步的精简优化一个词法分析器的关键字查询表的。

SQLite源码的构成

SQLite本身是可以支持用cmake通过宏来裁剪功能和扩展功能的。在编译源码的过程中，会通过autoconfig生成一个Makefile。而Makefile的依赖中有一个keywordhash.h的文件。这个头文件就是用来做哈希表的构建的。可以看下Makefile中这个头文件的依赖与command。

1
2
3
keywordhash.h:	$(TOP)/tool/mkkeywordhash.c
	$(BCC) -o mkkeywordhash $(OPTS) $(TOP)/tool/mkkeywordhash.c
	./mkkeywordhash >keywordhash.h

这个文件只依赖$(TOP)/tool/mkkeywordhash.c这个文件的变更，并且command为:编译链接这个mkkeywordhash.c的源码，并且执行编译后的可执行文件，将输出重定向到keywordhash.h。那么到这里可以判断出keywordhash.h这个文件是mkkeywordhash这个程序生成的。

在keywordhash.h文件的开头注释也写的很清楚:

1
2
3
4
5
6
7
8
9
10
** The code in this file has been automatically generated by
**
**   sqlite/tool/mkkeywordhash.c
**
** The code in this file implements a function that determines whether
** or not a given identifier is really an SQL keyword.  The same thing
** might be implemented more directly using a hand-written hash table.
** But by using this automatically generated code, the size of the code
** is substantially reduced.  This is important for embedded applications
** on platforms with limited memory.

注释写到，直接用hand-written(手写)的哈希表也可以达到同一个目的。但是为了达到极致的内存和性能等，SQLite做了更多的优化。

为什么要使用mkkeywordhash？

上面提到了，SQLite完全可以通过一个纯手写的哈希表来达到快速查询一个单词是否是SQL关键字的目的。但是，使用SQLite的一般都是移动或者嵌入式设备，那么内存必然是需要考虑的一个因素。136个关键字，加上哈希表的散列，内存消耗还是非常可观的。总结使用mkkeywordhash有以下的优点:

  1. 支持裁剪。支持使用宏，动态地在编译期就可以决定SQLite支持哪些关键字(因为在编译期就会使用mkkeywordhash来动态生成源码)。
  2. 支持动态关键字压缩。mkkeywordhash压缩了所有的关键字，压缩对象为前缀与其他关键字前缀相同的关键字，或者是其他关键字子串的关键字。例:REINDEX的后缀和INDEXED的前缀一致；INDEX是REINDEX的子串
  3. 支持动态创建静态的哈希表。这句话怎么理解？静态哈希表可以理解：最终生成的哈希表肯定是静态的，因为SQLite编译后支持的关键字始终是固定的。动态创建是指，可以通过宏来动态决定这个关键字哈希表的大小，内容，以及哈希表的碰撞率。

注意这里说的动态，是指在编译期根据不同的需求，动态的来定制SQLite，而不是运行期的动态输入输出。

下面来详细看下这个mkkeywordhash.c的源码，看看SQLite在编译期间是如何动态生成需要的关键字哈希表的:

mkkeywordhash.c

关键字的数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
** All the keywords of the SQL language are stored in a hash
** table composed of instances of the following structure.
*/
typedef struct Keyword Keyword;
struct Keyword {
  char *zName;         /* The keyword name */
  char *zTokenType;    /* Token value for this keyword */
  int mask;            /* Code this keyword if non-zero */
  int id;              /* Unique ID for this record */
  int hash;            /* Hash on the keyword */
  int offset;          /* Offset to start of name string */
  int len;             /* Length of this keyword, not counting final \000 */
  int prefix;          /* Number of characters in prefix */
  int longestSuffix;   /* Longest suffix that is a prefix on another word */
  int iNext;           /* Index in aKeywordTable[] of next with same hash */
  int substrId;        /* Id to another keyword this keyword is embedded in */
  int substrOffset;    /* Offset into substrId for start of this keyword */
  char zOrigName[20];  /* Original keyword name before processing */
};

这里需要说明一下，这个数据结构是用于mkkeywordhash.c，用来组织和描述所有需要编译进去的关键字的数据结构。在最后mkkeywordhash会根据计算好的所有关键字的KeyWord对象来生成最终的keywordhash.h文件中的静态哈希表。

  • char *zName: 关键字字符串，最终会变成压缩后的关键字字符串。
  • char *zTokenType: 关键字类型，在tokenize暴露给外层类型。
  • int mask: 不同的关键字可能是属于同一个功能的，宏的控制就通过控制mask的值来开启或者关闭同一类的能力
  • int id: 关键字的id，会以关键字在数组中的索引值作为id，意义不大。
  • int hash: 关键字的哈希值
  • int offset: 关键字在压缩后的字符串表中的起始偏移
  • int len: 关键字的原始长度
  • int prefix: 关键字前缀和其他关键字后缀重叠部分的长度
  • int longestSuffix: 当前关键字后缀和其他关键字前缀重叠部分的最长长度
  • int iNext: 当哈希表发生碰撞的时候，通过链表来存储
  • int substrId: 如果当前关键字是另一个关键字子串的时候，substrId就是另一个关键字的Id
  • int substrOffset: 在substrId不为空的情况下，substrOffset标识子串开始的偏移
  • char zOrigName[20]: 关键字原始字符串

全局静态变量 aKeywordTable 存储了目前支持的所有的关键字。

1
2
3
4
5
6
7
static Keyword aKeywordTable[] = {
  { "ABORT",            "TK_ABORT",        CONFLICT|TRIGGER       },
  { "ACTION",           "TK_ACTION",       FKEY                   },
  { "ADD",              "TK_ADD",          ALTER                  },
  { "AFTER",            "TK_AFTER",        TRIGGER                },
  /* ... 136个关键字 ... */
};

基本处理流程

mkkeywordhash分成了几个步骤:

裁剪不支持的关键字

在mkkeywordhash main函数开始的第一步就是裁减掉不使用的关键字，如何裁剪？

在 aKeywordTable 和 Keyword 的数据结构里可以看到，每一个关键字都给予了一个mask，这个mask可以理解为关键字的tag，不同的mask值不一样，不同的关键字可以同时具有相同的mask，同一个mask可以具有多个mask。SQLite通过定义mask的值来确定是否需要裁剪。

1
2
3
4
5
#ifdef SQLITE_OMIT_ALTERTABLE
#  define ALTER      0
#else
#  define ALTER      0x00000001
#endif

例如，如果定义了SQLITE_OMIT_ALTERTABLE宏，那么ALTER就会被定义为0，那么只具有ALTERmask的关键字的mask值就会被标记为0。

1
2
3
4
5
6
7
8
9
/* Remove entries from the list of keywords that have mask==0 */
for(i=j=0; i<nKeyword; i++){
    if( aKeywordTable[i].mask==0 ) continue;
    if( j<i ){
      aKeywordTable[j] = aKeywordTable[i];
    }
    j++;
}
nKeyword = j;

然后通过遍历 akeywordTable 数组，过滤掉所有关键字mask为0的关键字，遍历的时候使用了快慢指针，分别指向当前遍历索引和存储的索引。

数据结构和计算哈希值

1
2
3
4
5
6
7
8
9
10
for(i=0; i<nKeyword; i++){
    Keyword *p = &aKeywordTable[i];
    p->len = (int)strlen(p->zName);
    assert( p->len<sizeof(p->zOrigName) );
    memcpy(p->zOrigName, p->zName, p->len+1);
    totalLen += p->len;
    p->hash = (charMap(p->zName[0])*4) ^
              (charMap(p->zName[p->len-1])*3) ^ (p->len*1);
    p->id = i+1;
}

在裁剪完成之后，当前aKeywordTable里的nKeyword个关键字就是SQLite本次编译需要支持的所有关键字了。

  • 以每一个关键字的索引作为id
  • p->len 存关键字的原始长度
  • p->zOrigName 存储原始字符串，也就是当前 的p->zName 字段
  • 哈希算法:(关键字的第一个字符4)^(关键字的最后一个字符3)^(关键字名字的长度)) 大致从aKeywordTable中的关键字看到，首尾字符已经可以获得很少的哈希冲突了。

完全子串的关系查找

首先可以压缩的情况就是，A串是B串的子串，这种情况下，我们只需要记录A串是B串子串的这一关系，以及A在B中起始的偏移值既可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* Sort the table from shortest to longest keyword */
/* 从关键字字符串长度的最短到最长做排序 */
qsort(aKeywordTable, nKeyword, sizeof(aKeywordTable[0]), keywordCompare1);

/* Look for short keywords embedded in longer keywords */
/* 从数组中找到，某些关键字是另一些关键字子串的情况，例如,IN是INDEX的子串，INDEX是INDEXED的子串*/
for(i=nKeyword-2; i>=0; i--){//从倒数第二个开始
    Keyword *p = &aKeywordTable[i];//p: 当前关键字
    for(j=nKeyword-1; j>i && p->substrId==0; j--){//依次判断当前关键字，是否是其他关键字(其他关键字从最后向前遍历)的子串
        Keyword *pOther = &aKeywordTable[j];
        if( pOther->substrId ) continue;
        if( pOther->len<=p->len ) continue;

        //判断 p 是不是 pOther 关键字的子串
        for(k=0; k<=pOther->len-p->len; k++){
            if( memcmp(p->zName, &pOther->zName[k], p->len)==0 ){
                p->substrId = pOther->id;
                p->substrOffset = k;
                break;
            }
        }
    }
}
  • 如果A是B的子串，那么A的长度必然不长于B。所以先按照长度，从短到长排序。
  • 如果A是B的子串，那么A的substrId会被记录为B的Id，A的substrOffset会被记录为子串的起始偏移。

前缀、后缀的进一步压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/* Compute the longestSuffix value for every word */
/* 进步压缩，除了完全包含其他关键字的以外，其他关键字中，
  每一个关键字的后缀中与其他关键字的前缀相等的最长长度是多少 */
for(i=0; i<nKeyword; i++){//遍历所有关键字
  Keyword *p = &aKeywordTable[i];
  if( p->substrId ) continue;//忽略已经是其他关键字子串的关键字。
  for(j=0; j<nKeyword; j++){//双重循环遍历
    Keyword *pOther;
    if( j==i ) continue;//不和自己比较
    pOther = &aKeywordTable[j];
    if( pOther->substrId ) continue;//同样忽略已经是其他关键字子串的关键字。

    //计算 p 的后缀和 pOther 的前缀最长多少是相同的
    for(k=p->longestSuffix+1; k<p->len && k<pOther->len; k++){
      if( memcmp(&p->zName[p->len-k], pOther->zName, k)==0 ){
        p->longestSuffix = k;
      }
    }
  }
}

  /* Sort the table into reverse order by length */
  /* 从关键字最长后缀相同长度的 最长到最短 做排序 */
  qsort(aKeywordTable, nKeyword, sizeof(aKeywordTable[0]), keywordCompare2);

除了上面一节中找出的子串关键字以外，剩下的关键字中，找出每一个关键字的后缀与其他关键字前缀相同的最长长度。最后以这个值从大到小做排序。这个步骤看似好像没有什么实际作用，但是这也是关键的一步，后续再分析为什么需要这么做。

计算压缩的最后结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/* Fill in the offset for all entries */
nChar = 0;
for(i=0; i<nKeyword; i++){
  Keyword *p = &aKeywordTable[i];
  if( p->offset>0 || p->substrId ) continue;
  p->offset = nChar;
  nChar += p->len;
  for(k=p->len-1; k>=1; k--){
    for(j=i+1; j<nKeyword; j++){
      Keyword *pOther = &aKeywordTable[j];
      if( pOther->offset>0 || pOther->substrId ) continue;
      if( pOther->len<=k ) continue;
      if( memcmp(&p->zName[p->len-k], pOther->zName, k)==0 ){
        p = pOther;
        p->offset = nChar - k;
        nChar = p->offset + p->len;
        p->zName += k;
        p->len -= k;
        p->prefix = k;
        j = i;
        k = p->len;
      }
    }
  }
}

for(i=0; i<nKeyword; i++){
  Keyword *p = &aKeywordTable[i];
  //处理带subStrId的
  if( p->substrId ){
    p->offset = findById(p->substrId)->offset + p->substrOffset;
  }
}

接下来对数组进行最后的压缩: 对数组进行遍历，遍历的目的是为了在当前关键字数组中，找到前缀与这个关键字后缀一样的关键字。并且，将这个关键字拼接在后面。

举个例子:现有关键字abcde``def``efg,因为def的前缀de与abcde的后缀相同，所以在记录第二个关键字的时候，只需要记录f，与在前一个关键字中后缀偏移3即可。

处理完所有的前后缀相接的字符串之后，再处理子串的问题，子串问题也就相对简单了。

代码中可以注意到下面这几个问题:

  1. 在上一节最后会对关键字排序，排序方法是按照每个关键字的最长相同后缀降序排列。
  2. 在比较关键字的后缀是否一致的时候，从相同长度为(k=p->len-1)开始比较。但是找到前缀与之相同的字符串之后并没有立刻break。

下面来解释这两个问题：

  • 首先SQLite希望，每次都是优先从与其他关键字前缀相同的更长后缀的的关键字中挑选出一个关键字，来拼接到关键字表后面。有点拗口，但是也不难以理解。这也就是为什么上一节中SQLite需要做一个看似“没有意义的”计算和排序。
  • 在找到一个关键字拼接的下一个关键字之后，注意p = pOther;当前的关键字p变成了下一个关键字pOther。这一步也不难理解，pOther将会变成下一步中寻找最长后缀的关键字。
  • 一直到所有的关键字都被check或者处理过(i==nKeyword)之后，才可以结束本次压缩。

计算和生成最优的哈希表

如何衡量一个哈希表是否是最优的呢？有两个指标，一个是稀疏程度，一个是表的大小。

越稀疏，肯定会让哈希表的碰撞率越低，但是随之带来的就是size变大。就像时间复杂度和空间复杂度一样，毕竟鱼和熊掌不可兼得。

那么如何去衡量这个哈希表的这两个指标呢？SQLite使用一个bestCount变量，来衡量。可以类似的理解为一个score得分。得分越高，哈希表代价(碰撞率和大小)越大，反之亦然。

如何计算这个得分呢？既然有两个因素，那么必然有权重。如果简单一点设计的话，那就是 碰撞次数 * 权值1+哈希表大小 * 权值2，其中 权值1+权值2=1。SQLite设计的时候也是这个思路，但是不是等比分配权值。它认为，比起哈希表的大小来说，碰撞的代价要高的多的多。也就是说相对来说更加希望用空间来换时间。

于是有了以下的算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* Figure out how big to make the hash table in order to minimize the
** number of collisions */
/* 计算一下 最优的哈希表大小*/
// SQLite 从 [nKeyword, 2*nKeyword]之间选择一个合适的哈希表大小
// 如何选择？选择“碰撞值”最低？如何计算碰撞值？
bestSize = nKeyword;
bestCount = nKeyword*nKeyword;
for(i=nKeyword/2; i<=2*nKeyword; i++){
  for(j=0; j<i; j++) aKWHash[j] = 0;
  for(j=0; j<nKeyword; j++){
    h = aKeywordTable[j].hash % i;
    aKWHash[h] *= 2;
    aKWHash[h]++;
  }
  for(j=count=0; j<i; j++) count += aKWHash[j];
  if( count<bestCount ){
    bestCount = count;
    bestSize = i;
  }
}

虽然希望查询速度快，但是也不能无限制大小。SQLite希望把哈希表的大小控制在[nKeyword, 2 x nKeyword]之间(毋庸置疑，最好的情况肯定是nKeyword，即所有值的哈希都不一样，一次碰撞都不发生)。在这个范围内计算每一个大小的哈希表的得分，算法为，计算所有关键字的哈希索引(即哈希值模当前的哈希表大小)，每发生一次碰撞的时候，把当前索引对应的值x2 并且加1，然后计算所有的值的总和。bestCount就存储了这个值。

具体计算步骤：

  1. aKWHash默认值全部重置为0。
  2. 依次计算关键字中的哈希值，得到每一个关键字在哈希表中的索引。
  3. 将对应索引中的值2 + 1（第一次命中的时候结果为1，第二次的时候结果为12+1=3，第三次的的时候结果为3*2+1=7）
  4. 计算所有aKWHash中值的和，这个和就是当前这个大小的aKWHash的”score得分”。
  5. 在哈希表大小为[nKeyword, 2 x nKeyword]的范围内，计算出其中”score得分最低的”一个大小。

其中 x2 是一个”放大因子”，利用 x2 这个指数的增长来放大一次碰撞带来的影响。即碰撞冲突增加的时候，这个”score”会以指数级增长。2 就可以理解为哈希表大小和哈希碰撞之间”权值”，只不过不是等比关系，而是指数关系。如果希望碰撞的影响再大，那么可以把这个值改成 3，4，5…

在keywordhash.h头文件顶部会输出当前哈希表的Hash score, 举个例子，在当前版本(3.27.2)下，如果支持所有的关键字，计算以 2 为“放大因子”的最合适的哈希表的Hash score为208。

计算生成哈希表

1
2
3
4
5
6
7
8
/* Compute the hash */
  for(i=0; i<bestSize; i++) aKWHash[i] = 0;
  for(i=0; i<nKeyword; i++) {
    //头插法..
    h = aKeywordTable[i].hash % bestSize;
    aKeywordTable[i].iNext = aKWHash[h];
    aKWHash[h] = i+1;
  }

从上一步计算的结果中可以得到，bestSize -> 最优的哈希表大小，bestCount -> 最优的哈希表得分。

依次计算所有的关键字的哈希值，每个命中的哈希值存储的是当前索引+1。一旦发生冲突的时候，使用头插法，在冲突的哈希索引值存储一个链表。iNext即为next指针。

到这里为止，整个哈希表的计算已经全部完成了……后面的代码生成也已经很简单了，纯字符串拼接。

aKeywordTable是一个对象数组，自动输出代码的时候，将整个数组拆分成了N个数组。

zKWText: 也就是aKeywordTable中每一个元素KeyWord的zName变量的拼接，即最终压缩后的所有关键字的字符。
aKWHash: 每一个哈希值(索引)对应的关键字的索引。
aKWNext: 哈希冲突时的链表。每一个索引下存储的值，表示，与该索引对应的关键字具有相同哈希值的下一个关键字的索引。
aKWLen : 表示第i个关键字的字符长度。
aKWOffset : 表示第一个关键字在zKWText字符表内的偏移长度。
aKWCode : 返回给parser模块的关键字码。

关键字的查询过程(函数keywordCode)

正向的看函数keywordCode(const char *z, int n, int *pType)，也就是上面自动生成的代码，看下是否符合之前设计的预期。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/* Check to see if z[0..n-1] is a keyword. If it is, write the
** parser symbol code for that keyword into *pType.  Always
** return the integer n (the length of the token). */
static int keywordCode(const char *z, int n, int *pType){
  int i, j;
  const char *zKW;
  if( n>=2 ){
    i = ((charMap(z[0])*4) ^ (charMap(z[n-1])*3) ^ n) % 127;//计算关键字的散列索引
    for(i=((int)aKWHash[i])-1; i>=0; i=((int)aKWNext[i])-1){
      if( aKWLen[i]!=n ) continue;
      j = 0;
      zKW = &zKWText[aKWOffset[i]];
#ifdef SQLITE_ASCII
      while( j<n && (z[j]&~0x20)==zKW[j] ){ j++; }
#endif
#ifdef SQLITE_EBCDIC
      while( j<n && toupper(z[j])==zKW[j] ){ j++; }
#endif
      if( j<n ) continue;
      testcase( i==0 ); /* REINDEX */
      testcase( i==1 ); /* INDEXED */
    //   ......
      testcase( i==135 ); /* PRIMARY */
      *pType = aKWCode[i];
      break;
    }
  }
  return n;
}

函数传入的有三个参数:第一个是需要判断的关键字的字符串的指针，第二个就是关键字的长度，第三个是函数需要返回的当前关键字的类型(也就是上面所说的，返回给parser的关键字码)。函数的返回值始终都是n，也就是关键字的长度。

  1. 关键字长度均大于2。
  2. 计算关键字的哈希值，以及哈希索引i = ((charMap(z[0])*4) ^ (charMap(z[n-1])*3) ^ n) % 127。127是当前哈希表的大小，在生成代码的时候会自动计算。
  3. 从aKWHash[i]中获取到关键字的索引，遍历当前索引对应的aKWNext的链表。
  4. 先判断关键字的长度与当前参数是否相同。
  5. 从zKWText中获取到当前关键字的字符串，根据不同的编码进行比较。
  6. 重复第3步骤，直到找到字符串与关键字相同。（因为哈希有冲突，所以需要遍历哈希值对应的整个链表）