本节书摘来自异步社区出版社《七周七数据库》一书中的第2章,第2.4节,作者: 【美】Eric Redmond,更多章节内容可以访问云栖社区“异步社区”公众号查看。
###2.4 第3天:全文检索和多维查询
七周七数据库
第3天我们将要学习如何使用多个工具,建立一个电影查询系统。首先,使用PostgreSQL自带的多种模糊字串匹配功能,搜索演员/电影的名字。然后,创建一个根据我们喜欢电影的风格进行推荐的系统,以学习cube扩展模块。所有这些都是PostgreSQL特有的扩展模块,不是SQL标准定义的内容。
在设计关系数据库的数据模式时,通常会从实体关系图开始。对将要创建的管理电影、电影风格和演员的个人电影推荐系统,建立如图2-10的实体模型。
提醒一下,在第1天,我们安装了几个扩展模块。今天我们会全部用到。我们需要用到的扩展模块列表如下:tablefunc、dict_xsyn、fuzzystrmatch、pg_trgm和cube。
首先创建数据库。一般来说,最好在外键上创建索引以加快反向查找(如通过演员信息,反向查找到其参演的所有电影)。除此之外也需要在movies_actors这样的联接表上设置一个UNIQUE约束,以避免重复的联接值。
postgres/create_movies.sql
CREATE TABLE genres (
name text UNIQUE,
position integer
);
CREATE TABLE movies (
movie_id SERIAL PRIMARY KEY,
title text,
genre cube
);
CREATE TABLE actors (
actor_id SERIAL PRIMARY KEY,
name text
);
CREATE TABLE movies_actors (
movie_id integer REFERENCES movies NOT NULL,
actor_id integer REFERENCES actors NOT NULL,
UNIQUE (movie_id, actor_id)
);
CREATE INDEX movies_actors_movie_id ON movies_actors (movie_id);
CREATE INDEX movies_actors_actor_id ON movies_actors (actor_id);
CREATE INDEX movies_genres_cube ON movies USING gist (genre);
你也可以下载本书配套的movies_data.sql脚本,并将其导入到数据库来创建相关的表。关于genre cube的任何问题,将在本节稍后讨论。
2.4.1 模糊搜索
系统能够支持文本检索功能,就意味系统要面对不确切的输入。你必须能够接受“Brid of Frankstein”这样的错别字。有时候,用户可能不记得“J. Roberts”的全名。在另一些时候,我们只是不知道如何拼写“Benn Aflek”。我们会看到通过一些PostgreSQL扩展包,可以使全文检索变得方便。值得注意的是,随着讨论的深入,这种字符串匹配的功能模糊了关系查询和Lucene1这样的搜索框架之间的差异。虽然有些人可能会觉得全文搜索这样的功能属于应用程序代码,但将这些扩展模块放到存放数据的数据库中,可以带来性能和管理上的好处。
2.4.2 SQL标准的字符串匹配
PostgreSQL有很多方法进行文本匹配,但两大默认方法是LIKE和正则表达式。
1.LIKE和ILIKE
LIKE和ILIKE(不区分大小写的LIKE)是文本搜索最简单的形式。它们在关系数据库中是相当普遍的。LIKE比较列值和给定的模式字符串。%和_字符是通配符。%表示匹配任意数量的任何字符,而_表示只匹配一个字符。
SELECT title FROM movies WHERE title ILIKE 'stardust%';
title
-------------------
Stardust
Stardust Memories
有个小技巧,如果想确保子串stardust不在字符串的末尾,可以使用下划线(_)字符。
SELECT title FROM movies WHERE title ILIKE 'stardust_%';
title
-------------------
Stardust
Stardust Memories
虽然在简单的场景下,这个功能非常有用,但是LIKE只能用于简单的通配符。
2.正则表达式
更强大的字符串匹配语法是正则表达式(regex)。因为许多数据库都支持它们正则表达式在本书中常常出现。正则表达式涉及的内容很广且复杂甚至还有一些书专门介绍如何编写强大的表达式。所以本书很难对这方面内容深入讨论。PostgreSQL(基本上)采用POSIX风格的正则表达式。
在Postgres里,正则表达式的匹配字串由~运算符开始,还可以带有可选的!(意思是不匹配)和*(意思是不区分大小写)。因此,要统计所有不以the开始的电影(不区分大小写),可以用下面的查询。匹配字符串内的字符是正则表达式。.
SELECT COUNT(*)FROM movies WHERE title !~* '^the.*';
可以为匹配前面查询的模式创建字符串索引,方法是创建一个text_pattern_ops运算符类索引,只要值以小写形式索引。
CREATE INDEX movies_title_pattern ON movies (lower(title) text_pattern_ops);
因为标题是文本类型,所以使用了text_pattern_ops类型的索引。如果需要对varchar、char或name类型的字串进行索引,可以使用下面的类型:varchar_pattern_ops、bpchar_pattern_ops和name_pattern_ops。
2.4.3 字符串相似比较算法levenshtein
levenshtein是一个字符串比较算法,它能够计算一个字符串需要经过多少步才能变成另一个字符串,从而可以比较两个字符串的相似程度。变换过程中,每个被替换的、缺失的或多出来的字符算作一个步骤,所有步骤的和算作是两个字符串的距离。在PostgreSQL中,levenshtein()函数由fuzzystrmatch扩展模块提供。
假设有字符串bat和字符串fads。
SELECT levenshtein('bat', 'fads');
因为fads与字符串bat相比,替换了两个字母(b=>f,t=>d),添加了一个字母(+s),每变换一次距离就会递增,所以它们间的levenshtein距离是3。我们可以看到,每变换一步,字串的距离会交短,通过变换,距离最后会逐步减少到零(即两个字符串变成一样)。
C
大小写的变化也算是一个步骤,所以比较的时候最好把所有字符串转为相同的大小写。
SELECT movie_id, title FROM movies
WHERE levenshtein(lower(title), lower('a hard day nght')) <= 3;
movie_id | title
----------+-------------------
245 | A Hard Day’s Night
这确保只有细微的差别的字符串不会算成有很长的距离。
2.4.4 三连词
三连词(trigram)是从一个字符串中取出包含三个连续字符的词。pg_trgm扩展模块可以将一个字符串分解为尽可能多的三连词。
C
找到一个匹配的字符串的过程可以简化,只需要统计匹配的三字母结构个数。匹配数最多的字符串就是最相似的。对于容忍小的拼写错误、甚至漏掉不重要的单词的搜索,这种查询方法是非常有用的。字符串越长,三字词就越多,则匹配的可能性就越大。它们很适合长度相近的电影片名这样的查询。
首先,将对电影的名字创建三连词索引(使用通用索引搜索树[Generalized Index Search Tree,GIST],这是由PostgreSQL引擎提供的一个通用索引API。
CREATE INDEX movies_title_trigram ON movies
USING gist (title gist_trgm_ops);
现在,即便在查询时带一点拼写错误,仍可得到不错的结果。
SELECT title
FROM movies
WHERE title % 'Avatre';
title
---------
Avatar
对于接受用户输入的字符匹配查询,三连词无需考虑复杂的通配符,是最好的选择。
2.4.5 全文检索
接下来,我们想让用户基于单词匹配进行全文检索,其中输入的单词可能会是复数。有时候,用户要通过几个记得的词搜索电影标题,Postgres可以支持简单的自然语言查询处理。
1.TSVector和TSQuery
我们来查找名字中包含单词night和day的电影,这种查找是全文检索的强项,我们可以用@@这个全文查询运算符进行文本搜索。
SELECT title
FROM movies
WHERE title @@ 'night & day';
title
-------------------------------
A Hard Day’s Night
Six Days Seven Nights
Long Day’s Journey Into Night
尽管返回结果的单词Day是所有格形式,而且这两个词的顺序颠倒了,该查询返回了像《A Hard Day’s Night》这样的电影名。@@运算符将电影名字段转换成tsvector结构体,并将查询转换成一个tsquery结构体。
tsvector是一种数据类型,它将字符串分解成单词的数组(或向量),再在输入的查询字串里搜索这些单词;而tsquery则是基于某种语言的查询,如英语或法语。每种语言对应一个相应的字典(我们会在后面几段看到更多相关内容)。如果系统语言设置为英语,前一个查询相当于下面的语句:
SELECT title
FROM movies
WHERE to_tsvector(title) @@ to_tsquery('english', 'night & day');
你可以看一看,通过在字符串上彻底运行转换函数,向量和查询如何将值分开。
SELECT to_tsvector('A Hard Day''s Night'), to_tsquery('english', 'night & day');
to_tsvector | to_tsquery
----------------------------+-----------------
'day':3 'hard':2 'night':5 | 'night' & 'day'
tsvector上的单词称为词素(lexeme),同时它还包含该词原来短语中的位置。
你可能已经注意到,《A Hard Day’s Night》的tsvector不包含单词a,而且,所有像a这样的简单英文单词会在查询的时候被忽略。
C
像a这样的常用词称为无用词(stop word),一般在执行查询时会被忽略。解析器会使用英语词典对字符串整型,将其转换成有意义的英语单元。可以在终端屏幕里查看tsearch_data目录下的英语无用词。
cat `pg_config --sharedir`/tsearch_data/english.stop
我们也可以从列表中删除a,或者用其他字典(如simple字典),这个字典会把字符串分解成由非单词字符间隔开的词,并把它们转为小写。比较这两个向量:
SELECT to_tsvector('english', 'A Hard Day''s Night');
to_tsvector
----------------------------
'day':3 'hard':2 'night':5
SELECT to_tsvector('simple', 'A Hard Day''s Night');
to_tsvector
----------------------------------------
'a':1 'day':3 'hard':2 'night':5 's':4
使用simple字典可以查询包含词素a的任何电影。
2.其他语言
因为Postgres在这里进行着某种自然语言处理,所以只有用不同的语言配置对应不同的语言,才有可能进行这样的处理。下面的命令可以查看所有已安装的语言配置:
book=# \dF
Postgres利用字典生成tsvector词素,除了利用无用词,还用到其他前面没有提到的称为解析器(parser)和模板(template)的分词规则,可以通过下面的命令查看系统的规则列表:
book=# \dFd
还可以直接调用ts_lexize()函数来对任何字典进行测试。下面的例子中,我们找到字符串Day’s的英语词干。
SELECT ts_lexize('english_stem', 'Day''s');
ts_lexize
-----------
{day}
最后,前面的全文检索也适用于其他语言。如果你安装了德语字典,可以试试这个:
SELECT to_tsvector('german', 'was machst du gerade?');
to_tsvector
--------------------
'gerad':4 'mach':2
因为was(what)和du(you)很常见,所以它们在德语字典中标记为无用词,而machst(doing)和gerade(now)被整型了。
3.对词素索引
全文检索虽然功能强大。但是,如果不为相应的表建立索引,检索的速度会很慢。EXPLAIN命令是一个功能强大的工具,通过它可以查看数据库内部对查询生成什么样的计划树。
EXPLAIN
SELECT *
FROM movies
WHERE title @@ 'night & day';
QUERY PLAN
---------------------------------------------------------------------------
Seq Scan on movies (cost=10000000000.00..10000000001.12 rows=1 width=68)
Filter: (title @@ 'night & day'::text)
请注意Seq Scan on movies这一行。这在查询中基本上不是好兆头,因为它意味着读取表的每一行。因此,需要建立正确的索引。
我们将使用通用反向索引GIN(Generalized Inverted iNdex,GIN),对我们要查询的词素创建索引,GIN和GIST类似,也是索引的API。如果你使用过像Lucene或Sphinx这样的搜索引擎,你会对反向索引(inverted index)比较熟悉。它是一种常见的用于对全文检索进行索引的数据结构。
CREATE INDEX movies_title_searchable ON movies
USING gin(to_tsvector('english', title));
现在有了索引,再搜索一次。
EXPLAIN
SELECT *
FROM movies
WHERE title @@ 'night & day';
QUERY PLAN
---------------------------------------------------------------------------
Seq Scan on movies (cost=10000000000.00..10000000001.12 rows=1 width=68)
Filter: (title @@ 'night & day'::text)
看到了什么?什么也没变。索引是存在的,但是Postgres没有用它。这是因为GIN索引需要使用english的全文检索配置构造其tsvectors向量,但我们在查询里面没有指明该向量。现在我们需要在查询的WHERE子句中指定它。
EXPLAIN
SELECT *
FROM movies
WHERE to_tsvector('english',title) @@ 'night & day';
QUERY PLAN
--------------------------------------------------------------------------------
Bitmap Heap Scan on movies (cost=4.26..8.28 rows=1 width=68)
Recheck Cond: (to_tsvector('english'::regconfig, title) @@ '''day'''::tsquery)
-> Bitmap Index Scan on movies_title_searchable (cost=0.00..4.26 rows=1 width=0)
Index Cond: (to_tsvector('english'::regconfig, title) @@ '''day'''::tsquery)
EXPLAIN很重要,它可以确保按你希望方式使用索引。否则,索引只是无谓的开销。
4.发音码metaphone
我们朝着匹配不太具体的输入迈出了一小步。LIKE和正则表达式需要创建匹配模式,根据模式指定要求的格式准确匹配相应的字符串。levenshtein距离可以匹配有微小拼写错误的字符串,但要求必须是非常相似的字符串。要找到合理范围内的拼写错误的匹配,三连词是很好的选择。最后,全文检索允许有自然语言的灵活性,因为它可以忽略a和the这样不重要的单词,并能处理复数形式。有时候,我们只是不知道如何正确拼写单词,但是我们知道它们的读音。
我们喜爱布鲁斯·威利斯(Bruce Willis),很想知道他参演什么样的电影。遗憾的是,我们忘了如何拼写他的名字,所以我们只能尽可能地把它拼写出来。
SELECT *
FROM actors
WHERE name = 'Broos Wils';
即使三连词在这里也用处不大(使用%而不是=)。
SELECT *
FROM actors
WHERE name % 'Broos Wils';
这里可以用(metaphone),它们是用来生成代表单词发音的发音码的算法。你可以指定输出的发音码中有多少个字符,例如,Aaron Eckhart的7个字符的发音码是ARNKHRT。
为了找到名字的发音像Broos Wils的人参演的所有电影,可以在查询中使用metaphone输出的发音码。请注意,NATURAL JOIN是INNER JOIN的一种,自动以列名相同的列进行联接(例如,movies.actor_id= movies_actors.actor_id)。
SELECT title
FROM movies NATURAL JOIN movies_actors NATURAL JOIN actors
WHERE metaphone(name, 6) = metaphone('Broos Wils', 6);
title
-----------------------------
The Fifth Element
Twelve Monkeys
Armageddon
Die Hard
Pulp Fiction
The Sixth Sense
:
如果你看看在线文档,会发现扩展模块fuzzystrmatch还有另外的函数:dmetaphone()(双发音码)、dmetaphone_alt()(替代发音)和soundex()(19世纪80年代的美国人口普查创立的、用来对比常见的美国人姓氏的古老算法)。
可以输出各函数的结果,来详细研究这些函数结果的表示方式。
SELECT name, dmetaphone(name), dmetaphone_alt(name),
metaphone(name, 8), soundex(name)
FROM actors;
name | dmetaphone | dmetaphone_alt | metaphone | soundex
--------------------+--------------+------------------+---------------+--------
50 Cent | SNT | SNT | SNT | C530
Aaron Eckhart | ARNK | ARNK | ARNKHRT | A652
Agatha Hurle | AK0R | AKTR | AK0HRL | A236
:
没有哪个函数是最好的,根据你的数据集做出最优化选择。
2.4.6 组合使用字符串匹配方法
有了这些字符串检索的方法,就可以用有趣的方式组合着来用。
发音码最灵活的方面之一是其输出就是字符串。这让你能与其他字符串匹配方法混合着使用。例如,可以对metaphone()输出结果使用三连词运算符,并按最短的Levenshtein距离排序结果。这意味着“找到发音像Robin Williams的名字,并按顺序排列。”
SELECT * FROM actors
WHERE metaphone(name,8) % metaphone('Robin Williams',8)
ORDER BY levenshtein(lower('Robin Williams'), lower(name));
actor_id | name
----------+-----------------
4093 | Robin Williams
2442 | John Williams
4479 | Steven Williams
4090 | Robin Shou
需要注意的是,结果并不完美。Robin Williams排到了第三位。滥用这种灵活性可能产生其他有趣的结果,所以要小心。
SELECT * FROM actors WHERE dmetaphone(name) % dmetaphone('Ron');
actor_id | name
----------+-------------
3911 | Renji Ishibashi
3913 | Renée Zellweger
:
组合方式非常多,只受限于你的实验。
2.4.7 把电影风格表示成多维超立方体
最后介绍的扩展模块是cube。用cube数据类型,将一部电影的风格类型映射到一个多维向量。然后在超级立方体内,通过一些方法,查询与给定的点最接近的点,从而给出和当前电影风格类似的所有电影的列表。
你可能注意到,在本节开始时,我们创建了一个名为genres的列,其数据类型是cube,其值是18维空间中的一个点,每个维度代表一种风格。为什么用n维空间中的点代表电影风格?因为电影分类不是一门精确的科学,很多电影不是100%的喜剧或悲剧,它们介乎其中。
在系统中,基于某种电影属于某种风格的强度,对电影进行评分,分数从(完全任意的数字)0到10,0表示完全属于该风格,10表示最强。
《星球大战》(Star Wars)的风格向量是(0,7,0,0,0,0,0,0,0,7,0,0,0,0,10,0,0,0)。genres向量表里的值是向量中每个维度的位置。可以用每个genres.position提取cube_ur_coord(vector,dimension),解释它的风格值。为清楚起见,我们过滤掉得分0的风格。
SELECT name,
cube_ur_coord('(0,7,0,0,0,0,0,0,0,7,0,0,0,0,10,0,0,0)', position) as score
FROM genres g
WHERE cube_ur_coord('(0,7,0,0,0,0,0,0,0,7,0,0,0,0,10,0,0,0)', position) > 0;
name | score
------------------+-------
Adventure | 7
Fantasy | 7
SciFi | 10
只要找到最近的点,我们可以找到风格相似的电影。要理解为什么这样是可行的,可以看看图2-11。如果你最喜欢的电影是《动物之家》(Animal House),你可能喜欢的是《四十岁的老处男》(The 40 Year Old Virgin),而不是《俄狄浦斯》(Oedipus),因为它明显缺乏喜剧元素。在二维空间中,可以把寻找相似的匹配简单地转化为最近邻搜索。
还可以推广到更多的维度,代表更多的风格,如2维、3维或18维。其原理是相同的:最近邻匹配就是风格空间中最近点,也就是最接近的风格匹配。
风格向量的最近匹配可以通过cube_distance(point1,point2)搜索得到。这里,我们可以找到所有电影到《星球大战》的风格向量的距离,最近的排在前面。
SELECT *,
cube_distance(genre, '(0,7,0,0,0,0,0,0,0,7,0,0,0,0,10,0,0,0)') dist
FROM movies
ORDER BY dist;
前面创建表时,创建了movies_genres_cube立方体索引。然而,即使使用索引,这个查询仍然比较缓慢,因为它需要全表扫描。它计算每一行的距离,然后将它们排序。
与其每一个点都计算距离,不如集中在一个比较可能的有界立方体 (bounding
cube`),计算里面的点的距离。正如在找5个最近的镇的时候,在州的地图上找要比在世界地图上寻找更快,因为框定一个边界的话,可以减少需要看的点。
使用cube·enlarge
·(·cube
·,·radius
·,·dimensions
·)建立一个18维的立方体,其边长(半径)大于一个点。我们来看一个更简单的例子,如果围绕点(1,1)建立一个单位二维正方形,正方形的左下角是(0,0),右上角是(2,2)。
SELECT cube_enlarge('(1,1)',1,2);
cube_enlarge
---------------
(0,0),(2,2)
同样的原则适用于任何维度。我们可以对一个有界的超立方框使用一个特殊的cube运算符“@>”,意思是包含。
下面这个查询已算出以《星球大战》(Star Wars)的风格代表的点为中心、5单位立方体内包含的所有点的距离。
SELECT title, cube_distance(genre, '(0,7,0,0,0,0,0,0,0,7,0,0,0,0,10,0,0,0)') dist
FROM movies
WHERE cube_enlarge('(0,7,0,0,0,0,0,0,0,7,0,0,0,0,10,0,0,0)'::cube, 5, 18) @> genre
ORDER BY dist;
title | dist
----------------------------------------------------+------------------
Star Wars | 0
Star Wars: Episode V - The Empire Strikes Back | 2
Avatar | 5
Explorers | 5.74456264653803
Krull | 6.48074069840786
E.T. The Extra-Terrestrial | 7.61577310586391
可以由电影名得到风格,然后,直接执行针对该风格的计算(把子查询的结果当作一个表,并给其起个别名)。
SELECT m.movie_id, m.title
FROM movies m, (SELECT genre, title FROM movies WHERE title = 'Mad Max') s
WHERE cube_enlarge(s.genre, 5, 18) @> m.genre AND s.title <> m.title
ORDER BY cube_distance(m.genre, s.genre)
LIMIT 10;
movie_id | title
----------+----------------------------
1405 | Cyborg
1391 | Escape from L.A.
1192 | Mad Max Beyond Thunderdome
1189 | Universal Soldier
1222 | Soldier
1362 | Johnny Mnemonic
946 | Alive
418 | Escape from New York
1877 | The Last Starfighter
1445 | The Rocketeer
虽然这种电影的推荐方法并不完美,但它是一个好的开始。我们将在后面的章节,如在MongoDB中的二维地理搜索(参见5.4.3节),看到更多的维度查询。
2.4.8 第3天总结
今天,我们深入体验了PostgreSQL在字符串搜索方面的灵活性,使用了多维搜索的cube包。最重要的是,我们体验了PostgreSQL的一些非标准扩展模块,正是这些扩展让PostgreSQL领先于其他开源RDBMS。还有几十(甚至几百)个扩展可供自由使用,如从地理存储到加密函数、自定义数据类型和语言扩展等。除了SQL核心能力之外,这些扩展模块让PostgreSQL光芒闪耀。
第3天作业
求索
1.从官方在线文档中找到Postgres自带的所有可扩展包。
2.找到网上的POSIX正则表达式的文档(可供后续章节中使用)。
实践
1.创建一个存储过程,可以输入你喜欢的电影或演员的名字,它根据演员曾主演过的或类似风格的电影,返回5个最好的推荐。
2.扩展电影数据库,记录用户的评论并提取关键字(除去英语的忽略字)。对比演员姓氏和相关关键字,尝试找到被谈论最多的演员。