SQL

第17章 可怜人的搜索引擎

有些人遇到问题时总是会说:“我知道,我会使用正则表达式。”然后他会碰到更多问题。-- 杰米•加文斯基

1995年,我在一家公司做技术支持,那时公司开始通过Web向客户提供信息。我们有一系列简短文档描述了常见问题的解决方案,我们想把这些文章放到Web做成一个知识库。

我们很快就意识到,随着文章数量的增长,知识库需要支持搜索功能,因为客户不想浏览几百篇文章才找到他们需要的解决方案。一个临时的应对方案是将文章分类,但即使如此,每个分类下的文章数量也很大,并且很多文章都可能属于多个分类。

我们想要让客户能够通过搜索文章,缩小候选列表。最灵活和直接的界面就是允许客户输入任意的关键字,然后给出包含这些关键字的文章。一篇文章如果和用户输入的关键字匹配度越高,则出现的越靠前。同时,我们也希望能够匹配词形变化。比如,对crash的搜索也要同时匹配crashed、crashes和crashing。当然这个搜索要能够在一个不断增长的文章集合中快速地返回结果,这样才能在一个Web程序中使用它。

如果上面这些细节描述让对你觉得多余,我并不感到惊讶。搜索技术在如今已经变得如此平常,以至于我们都回想不起来它出现之前的情况了。但是用SQL搜索关键字,同时保证快速和精确,依旧是相当地困难。

17.1 目标:全文搜索

任何存储文本的应用都有针对这个文本进行单词或词组搜索的需求。我们使用数据库存储越来越多的文本数据,同时也需要搜索速度越来越快。Web应用尤其需要高性能和高扩展性数据库搜索技术。

SQL的一个基本原理(以及SQL所继承的关系原理)就是一列中的单个数据是原子性的。也就是说,你能对两个值进行比较,但通常是把两个值当成两个整体来比较。在SQL中比较子字符串总是意味着低效和不精确。

尽管如此,我们仍旧需要一个方法来比较一个较短的字符串和一个较长的字符串,并且查看是否较短字符串是较长字符串的一个子串。我们要怎么使用SQL来实现这样的需求呢?

17.2 反模式:模式匹配断言

SQL提供了模式匹配断言来比较字符串,并且这是很多程序员用来搜索关键字的第一选择。最广泛支持的就是LIKE断言。

LIKE断言提供了一个通配符(%)用以匹配0个或者多个字符。在一个关键字之前及之后使用通配符能够匹配到包含这个关键字的任意字符串。第一个通配符匹配了关键字之前的所有文本,第二个通配符匹配了关键字之后的所有文本。

Search/anti/like.sql
SELECT * FROM Bugs WHERE description LIKE '%crash%';

正则表达式也被很多数据库所支持,尽管这不是标准。你不需要使用通配符,因为基本上正则表达式能对所有子串进行模式匹配。如下是一个使用MySQL的正则表达式的例子1:

Search/anti/regexp.sql
SELECT * FROM Bugs WHERE description REGEXP 'crash';

1 尽管SQL-99标准定义了SIMILAR TO这个断言用来匹配正则表达式,但大多数SQL数据库还是使用非标准的语法。

使用模式匹配操作符的最大缺点就在于性能问题。它们无法从传统的索引上受益,因此必须进行全表遍历。由于对一个字符串列进行匹配操作非常耗时(相对来说,和比较两个整数是否相等所耗的时间相比),全表遍历所花的总时间就非常多。

使用LIKE或者正则表达式进行模式匹配搜索的另一个问题就是,经常会返回意料之外的结果。

Search/anti/like-false-match.sql
SELECT * FROM Bugs WHERE description LIKE '%one%';

上面的这个例子是要匹配包含one这个单词的文本,同时也匹配到单词money、prone、lonely等。在关键字两端都加上空格也不能完美解决这个问题,因为无法匹配到后面直接跟着标点符号的单词或者正好在文本开头或结尾的单词。数据库支持的正则表达式可能会为单词边界提供一个模式来解决单词匹配问题2:

Search/anti/regexp-word.sql
SELECT * FROM Bugs WHERE description REGEXP '[[:<:]]one[[:>:]]';

2 本例使用的是MySQL的语法。

考虑到性能和扩展性的问题,以及预防不合理的匹配所做的工作,简单的模式匹配对于关键字搜索来说是一个糟糕的技术方案。

17.3 如何识别反模式

如下的一些问题通常预示着项目中使用了“可怜人的搜索引擎”这个反模式。

  • “我要怎么在LIKE表达式的两个通配符之间插入一个变量?”通常当程序员想要使用模式匹配对用户输入的关键字进行搜索时,会产生这个问题。
  • “我要怎么写一个正则表达式来检查一个字符串是否包含多个单词、不包含一个特定的单词,或者包含给定单词的任意形式?”如果一个复杂的问题看起来用正则表达式很难解决,那就是用了反模式了。
  • “我们网站的搜索功能在加了很多文档进去之后慢得不可理喻了。出什么问题了?”随着数据的增长,这个反模式方案就暴露出了它脆弱的扩展性问题。

17.4 合理使用反模式

在17.2节中所使用的SQL语句都是合法的,并且很简单直接。这意味着很多东西。

性能总是非常重要的,但一些查询过程很少执行,因此不需要花很多功夫对它进行优化。为一个很少使用的查询维护一个索引,可能就和用不高效的方法执行查询一样耗资源。如果这个查询是一个临时的查询,没人能保证你定义的索引能够给这个查询带来任何好处。

使用模式匹配操作进行复杂查询是很困难的,但如果你是为了一些简单的需求设计这样的模式匹配,它们就能帮助你用最少的工作量获得正确的结果。

17.5 解决方案:使用正确的工具

最好的方案就是使用特殊的搜索引擎技术,而不是SQL。另一个可选方案是将结果保存起来从而减少重复的搜索开销。

接下来的几节介绍了一些数据库的内置扩展和独立项目所提供的搜索技术。同时,我们也会设计一个完全使用SQL标准的解决方案,它显然会比使用子串匹配更高效。

17.5.1 数据库扩展

每个大品牌的数据库都有对全文搜索这个需求的解决方案,但这些方案并没有任何的标准,各个数据库的实现也互不兼容。如果只使用一种数据库品牌(或者打算使用开发商开发的特性),这些特性是获得高性能文本搜索的最佳途径,并且能和SQL查询整合得非常好。

如下是对一些SQL数据库的全文搜索技术的简要描述。具体的细节不断随数据库的版本升级而改变,因此记得要阅读一下对应当前使用版本的文档。

MySQL中的全文索引

MySQL为MyISAM存储引擎提供了一个简单地全文索引类型。你可以在一个类型为CHAR、VARCHAR或者TEXT的列上定义一个全文索引。下面这个例子在Bug的summary和description列上定义了全文索引:

Search/soln/mysql/alter-table.sql
ALTER TABLE Bugs ADD FULLTEXT INDEX bugfts (summary, description);

可以使用MATCH()函数对索引内容进行搜索。必须在匹配时指定需要全文索引的列(因而你可以在同一张表中对其他列使用不同类型的索引)。

Search/soln/mysql/match.sql
SELECT * FROM Bugs WHERE MATCH(summary, description) AGAINST ('crash');

自MySQL 4.1开始,你还能在表达式上使用简单的布尔运算来更精确地过滤查询结果。

Search/soln/mysql/match-boolean.sql
SELECT * FROM Bugs WHERE MATCH(summary, description)   AGAINST ('+crash -save' IN BOOLEAN MODE);

Oracle中的文本索引

从1997年的Oracle 8开始,Oracle就支持了文本索引特性,当时它是数据资料夹的一部分,称为ConText。这项技术在随后的版本中多次更新,现在已经被集成到数据库程序里了。Oracle中的文本索引技术复杂且强大,因此这里只能非常简单地总结一下。

CONTEXT

为单个文本列建立一个这样的索引类型,使用CONTAINS()操作符进行搜索。索引和数据不保持同步,因此你每次都得手动重建索引或者定期重建。

Search/soln/oracle/create-index.sql
CREATE INDEX BugsText ON Bugs(summary) INDEXTYPE IS CTSSYS.CONTEXT;
SELECT * FROM Bugs WHERE CONTAINS(summary, 'crash') > 0;

CTXCAT

这个类型的索引是针对短文本设计的,比如用在在线程序的分类目录上,和同一张表的其他结构化列一起。这种类型的索引会保持数据的同步。

Search/soln/oracle/ctxcat-create.sql
CTX_DDL.CREATE_INDEX_SET('BugsCatalogSet');
CTX_DDL.ADD_INDEX('BugsCatalogSet', 'status');
CTX_DDL.ADD_INDEX('BugsCatalogSet', 'priority');
CREATE INDEX BugsCatalog ON Bugs(summary) INDEXTYPE IS CTSSYS.CTXCAT PARAMETERS('BugsCatalogSet');

CATSEARCH() 操作符分别接受两个参数来搜索索引列和结构化列的集合。

Search/soln/oracle/ctxcat-search.sql
SELECT * FROM Bugs WHERE CATSEARCH(summary, '(crash save)', 'status = "NEW"') > 0;

CTXXPATH

这种类型的索引是针对XML文档搜索而设计的,使用existsNode()操作符。

Search/soln/oracle/ctxxpath.sql
CREATE INDEX BugTestXml ON Bugs(testoutput) INDEXTYPE IS CTSSYS.CTXXPATH;
SELECT * FROM Bugs WHERE testoutput.existsNode('/testsuite/test[@status="fail"]') > 0;

CTXRULE

假设在数据库中存了大量的文档,然后需要根据文档内容进行分类。

使用CTXRULE索引,你可以设计分析文档的规则并返回文档的分类信息。同时,你可以提供一些示例文档以及对应的分类概念,然后让Oracle去分析这个规则并应用到其他文档上去。你甚至可以完全让这个过程自动化,让Oracle去分析文档结构然后自动分类。

如何使用CTXRULE不在本书的讨论范围内。

Microsoft SQL Server的全文搜索

SQL Server 2000及后续版本支持全文索引,它的配置相对复杂,包括了语言、同义词库和自动数据同步选项。SQL Server提供了一系列的存储过程来创建全文索引,可以使用CONTAINS()操作符来使用全文索引。

要执行对包含crash的Bug进行搜索的例子,首先要做的就是启用全文特性,然后在数据库中定义一个目录:

Search/soln/microsoft/catalog.sql
EXEC sp_fulltext_database 'enable' EXEC sp_fulltext_catalog 'BugsCatalog', 'create'

接着,为Bugs表定义一个全文索引,将列加入到索引中,然后激活索引:

Search/soln/microsoft/create-index.sql
EXEC sp_fulltext_table 'Bugs', 'create', 'BugsCatalog', 'bug_id' EXEC sp_fulltext_column 'Bugs', 'summary', 'add', '2057' EXEC sp_fulltext_column 'Bugs', 'description', 'add', '2057' EXEC sp_fulltext_table 'Bugs', 'activate'

启用全文索引的自动同步功能,从而对索引列的操作会同时影响到索引,然后就可以开始填充索引。这会在后台执行,因而需要花点时间才能使用索引。

Search/soln/microsoft/start.sql
EXEC sp_fulltext_table 'Bugs', 'start_change_tracking' EXEC sp_fulltext_table 'Bugs', 'start_background_updateindex' EXEC sp_fulltext_table 'Bugs , 'start_full'

最后,使用CONTAINS()操作符执行查询:

Search/soln/microsoft/search.sql
SELECT * FROM Bugs WHERE CONTAINS(summary, '"crash"');

PostgreSQL的文本搜索

PostgreSQL 8.3提供了一个复杂的可大量配置的方式,来将文本转化为可搜索的词汇集合,并且让这些文档能够进行模式匹配搜索。

为了最大地提升性能,你需要将内容存两份:一份为原始文本格式,另一份为特殊的TSVECTOR类型的可搜索格式。

Search/soln/postgresql/create-table.sql
CREATE TABLE Bugs (bug_id SERIAL PRIMARY KEY, summary VARCHAR(80),   description  TEXT, ts_bugtext TSVECTOR   -- other columns
);

你需要确保TSVECTOR列的内容和你所想要搜索的列的内容同步。PostgreSQL提供了一个内置的触发器来简化这一操作:

Search/soln/postgresql/trigger.sql
CREATE TRIGGER ts_bugtext BEFORE INSERT OR UPDATE ON Bugs FOR EACH ROW EXECUTE PROCEDURE   tsvector_update_trigger(ts_bugtext, 'pg_catalog.english', summary, description);

你也应该同时在TSVECTOR列上创建一个反向索引(Gin):

Search/soln/postgresql/create-index.sql
CREATE INDEX bugs_ts ON Bugs USING GIN(ts_bugtext);

在做完这一切之后,就可以在全文索引的帮助下使用PostgreSQL的文本搜索操作符@@来高效地执行搜索查询:

Search/soln/postgresql/search.sql
SELECT * FROM Bugs WHERE ts_bugtext @@ to_tsquery('crash');

有很多其他的选项来自定义可搜索的内容、搜索查询和搜索结果。

SQLite的全文搜索(FTS)

SQLite中的标准表结构并不支持高效的全文搜索,但你可以使用SQLite的一个可选扩展组件来存储可搜索的文本。这些内容会存储在一个特殊的虚拟表结构中。它有三个版本的扩展,FTS1、FTS2和FTS3。

FTS扩展在标准的SQLite编译版本中默认是未启用的,因此你需要修改编译选项来启用FTS,并重新编译SQLite。比如,在Makefile.in中增加如下内容,然后编译SQLite。

Search/soln/sqlite/makefile.in
TCC += -DSQLITE_CORE=1 TCC += -DSQLITE_ENABLE_FTS3=1

一旦你有了一个启用FTS的SQLite版本,就可以创建一个虚拟表来存储可搜索文本。任何数据类型、约束或者其他列选项将在搜索时被忽略。

Search/soln/sqlite/create-table.sql
CREATE VIRTUAL TABLE BugsText USING fts3(summary, description);

如果你在为另一张表建立索引(比如这个例子中的Bugs表),就必须将数据复制到虚拟表中。FTS的虚拟表默认会包含一个主键列,叫做docid,因此可以将原表中的行关联起来。

Search/soln/sqlite/insert.sql
INSERT INTO BugsText (docid, summary, description)   SELECT bug_id, summary, description FROM Bugs;

现在你可以对FTS的虚拟表BugsText进行查询,使用一个高效的全文搜索断言MATCH,然后把匹配的行和原表Bugs进行联结。将FTS表的名字当成一个虚拟的列来进行针对任意列的模式匹配。

Search/soln/sqlite/search.sql
SELECT b.* FROM BugsText t JOIN Bugs b ON (t.docid = b.bug_id) WHERE BugsText MATCH 'crash';

匹配条件同时也支持功能有限的布尔表达式。

Search/soln/sqlite/search-boolean.sql
SELECT * FROM BugsText WHERE BugsText MATCH 'crash -save';

17.5.2 第三方搜索引擎

如果需要搜索功能的代码对不同的数据库都通用,那就需要一个独立于SQL数据库的搜索引擎。这一节简要介绍两个产品:Sphinx Search和Apache Lucene。

Sphinx Search(http://www.sphinxsearch.com/)是一个开源的搜索引擎,用于和MySQL及PostgreSQL配套使用。在本书出版时,一个非官方的Sphinx Search补丁支持开源的Firebird数据库。可能在将来的版本中,这个搜索引擎会考虑支持其他的数据库。

在Sphinx Search中,构建索引和搜索都很快,而且它也支持分布式查询。对于数据不常更新且要求高可扩展性的程序来说,Sphinx Search是个很好的选择。

你可以使用Sphinx Search来索引存在于MySQL数据库中的数据。通过修改sphinx.conf中的几个字段,你可以指定对应的数据库。你必须写一些SQL查询脚本为构建索引的操作获取数据。这个查询要求第一列为一个整型主键。你可以声明一些属性列来对结果进行约束或者排序。余下的列就是用来进行全文索引的。最后,另一个SQL查询脚本通过给定的主键代码$id,从数据库中获取完整的记录。

Search/soln/sphinx/sphinx.conf
source bugsrc {
  type = MySQL
  sql_user = bugsuser
  sql_pass = xyzzy
  sql_db = bugsdatabase
  sql_query = SELECT bug_id, status, date_reported, summary, description FROM Bugs
  sql_attr_timestamp = date_reported
  sql_attr_str2ordinal = status
  sql_query_info = SELECT * FROM Bugs WHERE bug_id = $id
}
index bugs {
  source = bugsrc
  path = /opt/local/var/db/sphinx/bugs
}

在配置完成sphinx.conf之后,你就可以在shell中使用indexer命令创建索引了:

Search/soln/sphinx/indexer.sh
indexer -c sphinx.conf bugs

你可以使用search命令对索引进行搜索:

Search/soln/sphinx/search.sh
search -b "crash -save"

Sphinx Search也有一个守护进程以及对应的API给常用的脚本语言(诸如PHP、Perl和Ruby)使用。当前版本的最主要问题是,目前的索引算法不支持高效的增量更新。在一个经常更新的数据源上使用Sphinx Search需要一些折中的处理办法。比如说,将可搜索表拆分成两张表,第一张表存储不变的主体历史数据,第二张表存储一个较小的当前数据的集合。当数据逐渐增长的时候,就需要重建索引。然后你的程序必须对两个Sphinx Search索引进行搜索。

Apache Lucene

Lucene(http://lucene.apache.org/)是一个针对Java程序的成熟搜索引擎。还有一些类似的项目,只是所使用的语言不同,包括C++、C#、Perl、Python、Ruby和PHP。

Lucene使用其独有的格式为文本文档创建索引。Lucene索引不和元数据保持同步。如果你插入、删除或者更新数据库中的数据,必须同时也对Lucene索引进行对应的操作。

使用Lucene搜索引擎有点像使用一台汽车发动机,必须要有一堆相关技术支持才能让它工作。Lucene不会直接从SQL数据库中读取数据集合,你必须手动往Lucene索引中写入文档。比如,你可以执行一个SQL查询,然后对结果中的每一行,创建一个Lucene文档对象然后保存到Lucene索引中。你可以通过Lucene的Java API来使用对应的功能。

所幸的是,Apache提供了另一个项目叫做Solr(http://lucene.apache.org/solr/)。Solr是一个Lucene索引的网关服务。你可以向Solr添加文档或者使用一个REST风格的接口提交查询请求,然后就可以使用任意的语言来调用Lucene的服务了。

你也可以将Solr配置成直接连接到数据库,执行一个查询操作,然后使用DataImportHandler工具来对结果进行索引。

实现自己的搜索引擎

假设你不想使用不同数据库特有的搜索特性,也不想安装一个独立的搜索引擎产品。你需要一个高效的、与数据库品牌无关的解决方案来进行文本搜索。在本节中,我们将使用一个称为反向索引的方案。基本上来说,反向索引就是一个所有可能被搜索的单词列表。在多对多的关系中,索引将这些单词和包含这些单词的文本关联起来。也就是说,crash这个单词出现在很多Bug描述中,然后每个Bug描述又包含很多别的关键字。这一节就来介绍如何设计反向索引。

首先,定义一张Keywords表来记录所有用户用来搜索的关键字,然后定义个交叉表BugsKewords来建立多对多的关系:

Search/soln/inverted-index/create-table.sql
CREATE TABLE Keywords (keyword_id SERIAL PRIMARY KEY, keyword VARCHAR(40) NOT NULL, UNIQUE KEY (keyword) );
CREATE TABLE BugsKeywords (keyword_id BIGINT UNSIGNED NOT NULL, bug_id BIGINT UNSIGNED NOT NULL, PRIMARY KEY (keyword_id, bug_id), FOREIGN KEY (keyword_id) REFERENCES Keywords(keyword_id), FOREIGN KEY (bug_id) REFERENCES Bugs(bug_id) );

接下来,将每个关键字和其所匹配到的Bug添加到BugsKeywords表中。我们可以使用LIKE或者正则表达式来执行子字符串匹配查询,获得我们所需要的匹配记录。这种方式不比在17.2节中所说的查询有更多的开销,但由于我们只执行一次这样的查询,因此省下了很多时间。如果我们将查询结果存储在交叉表中,所有之后对同一个关键字的搜索都会快很多。

接下来,我们写一个存储过程来简化对一个给定关键字的搜索3。如果给定的关键字已经被搜索过了,这个查询就会很快,因为BugsKeywords表中的记录就是包含这个给定的关键字的文章列表。如果还没人搜索过这个给定的关键字,我们就需要使用原始的方法对所有的文本记录进行全文搜索。

3 这个例子使用MySQL的语法来编写存储过程。

Search/soln/inverted-index/search-proc.sql
CREATE PROCEDURE BugsSearch(keyword VARCHAR(40)) BEGIN
    SET @keyword = keyword;
①     PREPARE s1 FROM 'SELECT MAX(keyword_id) INTO @k FROM Keywords WHERE keyword = ?';
        EXECUTE s1 USING @keyword;
        DEALLOCATE PREPARE s1;
         IF (@k IS NULL) THEN
②       PREPARE s2 FROM 'INSERT INTO Keywords (keyword) VALUES (?)'; EXECUTE s2 USING @keyword; DEALLOCATE PREPARE s2;
③ SELECT LAST_INSERT_ID() INTO @k;
④       PREPARE s3 FROM 'INSERT INTO BugsKeywords (bug_id, keyword_id)
            SELECT bug_id, ? FROM Bugs
            WHERE summary REGEXP CONCAT(''[[:<:]]'', ?, ''[[:>:]]'')
              OR description REGEXP CONCAT(''[[:<:]]'', ?, ''[[:>]]'')';
          EXECUTE s3 USING @k, @keyword, @keyword;
          DEALLOCATE PREPARE s3;
        END IF;
⑤ PREPARE s4 FROM 'SELECT b.* FROM Bugs b
          JOIN BugsKeywords k USING (bug_id)
          WHERE k.keyword_id = ?';
        EXECUTE s4 USING @k;
        DEALLOCATE PREPARE s4;
      END
  1. 搜索用户指定关键字。从keywords、keyword_id或NULL返回整型主键,如果这个词之前未出现过。
  2. 如果未找到该词,将它当做新词插入。
  3. 查询keywords生成的主键值。
  4. 通过搜索有新关键字的Bug来填入交叉表。
  5. 最后,查询符合keyword_id的整行,无论这个关键字存在或者需要当做新词条插入。

现在我们可以执行这个存储过程,然后传入想要的关键字。这个存储过程会返回匹配到的 Bug,不论它是需要搜索全表来找到匹配的Bug然后追加到交叉表中,还是直接就可以从交叉表中获取相应的结果。

Search/soln/inverted-index/search-proc.sql
CALL BugsSearch('crash');

这个方案还有一个需要注意的是:在有新文档添加到数据库中时,我们需要定义一个触发器以填充交叉表。如果你需要支持对Bug描述的更新操作,还要写一个触发器去重新分析文本,然后添加或删除BugsKeywords表中的记录。

Search/soln/inverted-index/trigger.sql
CREATE TRIGGER Bugs_Insert AFTER INSERT ON Bugs FOR EACH ROW BEGIN
   INSERT INTO BugsKeywords (bug_id, keyword_id)
SELECT NEW.bug_id, k.keyword_id FROM Keywords k
     WHERE NEW.description REGEXP CONCAT('[[:<:]]', k.keyword, '[[:>:]]')
            OR NEW.summary REGEXP CONCAT('[[:<:]]', k.keyword, '[[:>:]]');
END

这个关键字列表会随着用户不断地搜索而自动增长,因此我们不必将每个在知识库中找到的单词都加到列表中去。从另一个角度来说,如果我们可以预测一些关键字,就可以简单地在程序初始化的时候执行一下这几个关键字的搜索。这样,这部分的时间开销就不会由用户来承担了。

在本章最开始的知识库的例子中我使用了反向索引,我还在Keywords表中添加了额外的一列num_searches。这一列在每次这个关键字被搜索时会自增,我使用这一列来跟踪搜索关键字的分布。

你不必使用SQL来解决所有问题。

下一节:实体不应不必要地增殖。-- 奥卡姆