-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbloom.html
More file actions
216 lines (216 loc) · 19.2 KB
/
bloom.html
File metadata and controls
216 lines (216 loc) · 19.2 KB
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>F.5. bloom</title><link rel="stylesheet" type="text/css" href="stylesheet.css" /><link rev="made" href="pgsql-docs@postgresql.org" /><meta name="generator" content="DocBook XSL Stylesheets V1.79.1" /><link rel="prev" href="auto-explain.html" title="F.4. auto_explain" /><link rel="next" href="btree-gin.html" title="F.6. btree_gin" /><meta name="viewport" content="width=device-width,initial-scale=1.0" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="4" align="center"><a accesskey="h" href="index.html">PostgreSQL 10.5文書</a></th></tr><tr><td width="10%" align="left"></td><td width="10%" align="left"></td><td width="60%" align="center"><a href="contrib.html" title="付録F 追加で提供されるモジュール">付録F 追加で提供されるモジュール</a></td><td width="20%" align="right"><div class="actions"><a class="issue" title="github" href="https://github.com/pgsql-jp/jpug-doc/issues/new?title=version 10.5 bloom.html">誤訳等の報告
</a></div></td></tr><tr><td width="10%" align="left"><a accesskey="p" href="auto-explain.html" title="F.4. auto_explain">前へ</a> </td><td width="10%" align="left"><a accesskey="u" href="contrib.html" title="付録F 追加で提供されるモジュール">上へ</a></td><td width="60%" align="center">F.5. bloom</td><td width="20%" align="right"> <a accesskey="n" href="btree-gin.html" title="F.6. btree_gin">次へ</a></td></tr></table><hr /></div><div class="sect1" id="BLOOM"><div class="titlepage"><div><div><h2 class="title" style="clear: both">F.5. bloom</h2></div></div></div><a id="id-1.11.7.14.2" class="indexterm"></a><p><span class="original">
<literal>bloom</> provides an index access method based on
<ulink url="http://en.wikipedia.org/wiki/Bloom_filter">Bloom filters</ulink>.
</span> <code class="literal">bloom</code>は、<a class="ulink" href="http://en.wikipedia.org/wiki/Bloom_filter" target="_top">ブルームフィルター</a>によるインデックスのアクセスメソッドを提供します。
</p><p><span class="original">
A Bloom filter is a space-efficient data structure that is used to test
whether an element is a member of a set. In the case of an index access
method, it allows fast exclusion of non-matching tuples via signatures
whose size is determined at index creation.
</span>ブルームフィルターは、空間効率の良いデータ構造で、ある要素が集合のメンバーかどうかをテストするのに用いられます。
インデックスのアクセスメソッドとして使用する場合、インデックス作成時に大きさが決まるシグネチャーを使って、条件を満たさないタプルを高速に除外することができます。
</p><p><span class="original">
A signature is a lossy representation of the indexed attribute(s), and as
such is prone to reporting false positives; that is, it may be reported
that an element is in the set, when it is not. So index search results
must always be rechecked using the actual attribute values from the heap
entry. Larger signatures reduce the odds of a false positive and thus
reduce the number of useless heap visits, but of course also make the index
larger and hence slower to scan.
</span>シグネチャーはインデックス化された属性を非可逆的に表現するもので、その性質上、擬陽性の結果を出すことがあります。
すなわち、集合の中にない要素が、集合の中にあると報告するかもしれません。
ですから、インデックスの検索結果は、ヒープエントリ中の実際の属性値を使って、必ず再検査しなければなりません。
シグネチャーが大きくなれば擬陽性の可能性が下がるので不必要なヒープの検索は減りますが、もちろんそうなるとインデックスが大きくなるので、スキャンが遅くなります。
</p><p><span class="original">
This type of index is most useful when a table has many attributes and
queries test arbitrary combinations of them. A traditional btree index is
faster than a bloom index, but it can require many btree indexes to support
all possible queries where one needs only a single bloom index. Note
however that bloom indexes only support equality queries, whereas btree
indexes can also perform inequality and range searches.
</span>この種のインデックスは、テーブルに多数の属性があり、その任意の組み合わせを検索する問い合わせを実行するときにもっとも有効です。
伝統的なbtreeインデックスはブルームインデックスよりも高速ですが、可能なすべての問い合わせをサポートするためには多数のbtreeインデックスが必要なのに対し、ブルームインデックスでは、たった一つのブルームインデックスだけで事足ります。
しかし、ブルームインデックスでは等価検索だけをサポートすることに注意してください。
btreeインデックスでは、等価だけでなく、範囲検索も実行できます。
</p><div class="sect2" id="id-1.11.7.14.7"><div class="titlepage"><div><div><h3 class="title">F.5.1. パラメータ</h3></div></div></div><span class="original">
<title>Parameters</title>
</span><p><span class="original">
A <literal>bloom</> index accepts the following parameters in its
<literal>WITH</> clause:
</span><code class="literal">bloom</code>インデックスは、<code class="literal">WITH</code>句中の以下のパラメータを受け付けます。
</p><div class="variablelist"><dl class="variablelist"><dt><span class="term"><code class="literal">length</code></span></dt><dd><p><span class="original">
Length of each signature (index entry) in bits. The default
is <literal>80</> bits and maximum is <literal>4096</>.
</span>ビット単位の個々のシグネチャー（インデックスエントリー）の長さ。
デフォルトは<code class="literal">80</code>ビットで、最大値は<code class="literal">4096</code>です。
</p></dd></dl></div><div class="variablelist"><dl class="variablelist"><dt><span class="term"><code class="literal">col1 — col32</code></span></dt><dd><p><span class="original">
Number of bits generated for each index column. Each parameter's name
refers to the number of the index column that it controls. The default
is <literal>2</> bits and maximum is <literal>4095</>. Parameters for
index columns not actually used are ignored.
</span>各インデックスカラムに対して生成するビット数。
各々のパラメータ名は、管理対象のインデックスカラムの番号です。
デフォルトは<code class="literal">2</code>ビットで、最大値は<code class="literal">4095</code>です。
実際には使用されないインデックスカラムについてのパラメータは無視されます。
</p></dd></dl></div></div><div class="sect2" id="id-1.11.7.14.8"><div class="titlepage"><div><div><h3 class="title">F.5.2. Examples</h3></div></div></div><p><span class="original">
This is an example of creating a bloom index:
</span>ブルームインデックスの作成例です。
</p><pre class="programlisting">CREATE INDEX bloomidx ON tbloom USING bloom (i1,i2,i3)
WITH (length=80, col1=2, col2=2, col3=4);</pre><p><span class="original">
The index is created with a signature length of 80 bits, with attributes
i1 and i2 mapped to 2 bits, and attribute i3 mapped to 4 bits. We could
have omitted the <literal>length</>, <literal>col1</>,
and <literal>col2</> specifications since those have the default values.
</span>このインデックスは80ビット長のシグネチャーで作成され、属性i1とi2は2ビットに、i3は4ビットにマップされます。
<code class="literal">length</code>、<code class="literal">col1</code>、<code class="literal">col2</code>指定はデフォルト値を使っているので、省略しても構いません。
</p><p><span class="original">
Here is a more complete example of bloom index definition and usage, as
well as a comparison with equivalent btree indexes. The bloom index is
considerably smaller than the btree index, and can perform better.
</span>より完全なブルームインデックスの定義と使用法を示します。
比較のために、これと同等のbtreeインデックスも併せて示します。
ブルームインデックスはbtreeインデックスよりもかなり小さく、また、より良い性能を発揮できるかもしれません。
</p><pre class="programlisting">=# CREATE TABLE tbloom AS
SELECT
(random() * 1000000)::int as i1,
(random() * 1000000)::int as i2,
(random() * 1000000)::int as i3,
(random() * 1000000)::int as i4,
(random() * 1000000)::int as i5,
(random() * 1000000)::int as i6
FROM
generate_series(1,10000000);
SELECT 10000000
=# CREATE INDEX bloomidx ON tbloom USING bloom (i1, i2, i3, i4, i5, i6);
CREATE INDEX
=# SELECT pg_size_pretty(pg_relation_size('bloomidx'));
pg_size_pretty
----------------
153 MB
(1 row)
=# CREATE index btreeidx ON tbloom (i1, i2, i3, i4, i5, i6);
CREATE INDEX
=# SELECT pg_size_pretty(pg_relation_size('btreeidx'));
pg_size_pretty
----------------
387 MB
(1 row)</pre><p><span class="original">
A sequential scan over this large table takes a long time:
</span>これだけ大きなテーブルに対するシーケンシャルスキャンは長い時間がかかります。
</p><pre class="programlisting">=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
------------------------------------------------------------------------------------------------------------
Seq Scan on tbloom (cost=0.00..213694.08 rows=1 width=24) (actual time=1445.438..1445.438 rows=0 loops=1)
Filter: ((i2 = 898732) AND (i5 = 123451))
Rows Removed by Filter: 10000000
Planning time: 0.177 ms
Execution time: 1445.473 ms
(5 rows)</pre><p>
</p><p><span class="original">
So the planner will usually select an index scan if possible.
With a btree index, we get results like this:
</span>ですので、もし利用可能ならば、プランナは通常、インデックススキャンを選択します。
btreeインデックスですと、このような結果になります。
</p><pre class="programlisting">=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------
Index Only Scan using btreeidx on tbloom (cost=0.56..298311.96 rows=1 width=24) (actual time=445.709..445.709 rows=0 loops=1)
Index Cond: ((i2 = 898732) AND (i5 = 123451))
Heap Fetches: 0
Planning time: 0.193 ms
Execution time: 445.770 ms
(5 rows)</pre><p>
</p><p><span class="original">
Bloom is better than btree in handling this type of search:
</span>ブルームは、btreeよりもこの種の検索をうまく扱います。
</p><pre class="programlisting">=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on tbloom (cost=178435.39..178439.41 rows=1 width=24) (actual time=76.698..76.698 rows=0 loops=1)
Recheck Cond: ((i2 = 898732) AND (i5 = 123451))
Rows Removed by Index Recheck: 2439
Heap Blocks: exact=2408
-> Bitmap Index Scan on bloomidx (cost=0.00..178435.39 rows=1 width=0) (actual time=72.455..72.455 rows=2439 loops=1)
Index Cond: ((i2 = 898732) AND (i5 = 123451))
Planning time: 0.475 ms
Execution time: 76.778 ms
(8 rows)</pre><p><span class="original">
Note the relatively large number of false positives: 2439 rows were
selected to be visited in the heap, but none actually matched the
query. We could reduce that by specifying a larger signature length.
In this example, creating the index with <literal>length=200</>
reduced the number of false positives to 55; but it doubled the index size
(to 306 MB) and ended up being slower for this query (125 ms overall).
</span>
比較的大きい擬陽性の数に注意してください。
2439行が検索され、ヒープからアクセスされました。
しかし、クエリにマッチした行はありませんでした。
シグネチャー長をより大きく指定することにより、擬陽性を減らすことができます。
この例では、<code class="literal">length=200</code>と指定してインデックスを作成することにより、擬陽性が55まで減りました。
しかし、インデックスのサイズは（306 MBへと）2倍になってしまいました。
結果として、このクエリは（全体で125 msへと）遅くなってしまいました。
</p><p><span class="original">
Now, the main problem with the btree search is that btree is inefficient
when the search conditions do not constrain the leading index column(s).
A better strategy for btree is to create a separate index on each column.
Then the planner will choose something like this:
</span>btree検索の主要な問題は、検索条件が、先頭（そしてそれに続く）インデックスカラムを使用しないときに、効率が悪くなってしまうことです。
btreeでは各々のカラムに対して別々のインデックスを作るのが良い戦略です。
するとプランはこのような選択をします。
</p><pre class="programlisting">=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on tbloom (cost=9.29..13.30 rows=1 width=24) (actual time=0.148..0.148 rows=0 loops=1)
Recheck Cond: ((i5 = 123451) AND (i2 = 898732))
-> BitmapAnd (cost=9.29..9.29 rows=1 width=0) (actual time=0.145..0.145 rows=0 loops=1)
-> Bitmap Index Scan on tbloom_i5_idx (cost=0.00..4.52 rows=11 width=0) (actual time=0.089..0.089 rows=10 loops=1)
Index Cond: (i5 = 123451)
-> Bitmap Index Scan on tbloom_i2_idx (cost=0.00..4.52 rows=11 width=0) (actual time=0.048..0.048 rows=8 loops=1)
Index Cond: (i2 = 898732)
Planning time: 2.049 ms
Execution time: 0.280 ms
(9 rows)</pre><p><span class="original">
Although this query runs much faster than with either of the single
indexes, we pay a large penalty in index size. Each of the single-column
btree indexes occupies 214 MB, so the total space needed is over 1.2GB,
more than 8 times the space used by the bloom index.
</span>
個別のインデックスのどれかを使うよりもこのクエリはずっと高速に実行できますが、インデックスのサイズに大きなペナルティーを払わなければなりません。
各々の単一カラムのbtreeインデックスは、214MBになります。
ですから、全体で必要なスペースは1.2GBを超えます。
ブルームインデックスで使用するスペースの8倍以上です。
</p></div><div class="sect2" id="id-1.11.7.14.9"><div class="titlepage"><div><div><h3 class="title">F.5.3. 演算子クラスインターフェイス</h3></div></div></div><span class="original">
<title>Operator Class Interface</title>
</span><p><span class="original">
An operator class for bloom indexes requires only a hash function for the
indexed data type and an equality operator for searching. This example
shows the operator class definition for the <type>text</> data type:
</span>ブルームインデックスの演算子クラスには、インデックス対象のデータ型に対するハッシュ関数と、検索のための等価演算子だけが必要です。
この例では、<code class="type">text</code>データ型に対する演算子クラスの定義を示します。
</p><pre class="programlisting">CREATE OPERATOR CLASS text_ops
DEFAULT FOR TYPE text USING bloom AS
OPERATOR 1 =(text, text),
FUNCTION 1 hashtext(text);</pre></div><div class="sect2" id="id-1.11.7.14.10"><div class="titlepage"><div><div><h3 class="title">F.5.4. 制限事項</h3></div></div></div><span class="original">
<title>Limitations</title>
</span><p> </p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p><span class="original">
Only operator classes for <type>int4</> and <type>text</> are
included with the module.
</span>このモジュールには、<code class="type">int4</code>と<code class="type">text</code>に対する演算子クラスだけが含まれています。
</p></li><li class="listitem"><p><span class="original">
Only the <literal>=</literal> operator is supported for search. But
it is possible to add support for arrays with union and intersection
operations in the future.
</span><code class="literal">=</code>演算子だけが検索ではサポートされています。
しかし、配列の和、積演算のサポートを将来追加することは可能です。
</p></li></ul></div><p>
</p></div><div class="sect2" id="id-1.11.7.14.11"><div class="titlepage"><div><div><h3 class="title">F.5.5. 著者</h3></div></div></div><span class="original">
<title>Authors</title>
</span><p> Teodor Sigaev <code class="email"><<a class="email" href="mailto:teodor@postgrespro.ru">teodor@postgrespro.ru</a>></code>,
Postgres Professional, Moscow, Russia
</p><p> Alexander Korotkov <code class="email"><<a class="email" href="mailto:a.korotkov@postgrespro.ru">a.korotkov@postgrespro.ru</a>></code>,
Postgres Professional, Moscow, Russia
</p><p> Oleg Bartunov <code class="email"><<a class="email" href="mailto:obartunov@postgrespro.ru">obartunov@postgrespro.ru</a>></code>,
Postgres Professional, Moscow, Russia
</p></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="auto-explain.html">前へ</a> </td><td width="20%" align="center"><a accesskey="u" href="contrib.html">上へ</a></td><td width="40%" align="right"> <a accesskey="n" href="btree-gin.html">次へ</a></td></tr><tr><td width="40%" align="left" valign="top">F.4. auto_explain </td><td width="20%" align="center"><a accesskey="h" href="index.html">ホーム</a></td><td width="40%" align="right" valign="top"> F.6. btree_gin</td></tr></table></div></body></html>