Content deleted Content added
m convert special characters (via WP:JWB) |
m →Design |
||
| (5 intermediate revisions by 4 users not shown) | |||
Line 1:
{{Short description|Database indexing technique}}
A '''Block Range Index''' or '''BRIN''' is a [[database index]]ing technique. They are intended to improve performance with extremely large{{efn-lr|'Large' here refers to the number of rows in a [[database table|table]], rather than the field sizes or overall size.}} tables.
Line 27 ⟶ 28:
|title=Chapter 62. BRIN Indexes
|url=http://www.postgresql.org/docs/9.5/static/brin-intro.html
}}</ref> Other vendors have described some similar features,<ref name="Herrera, 2013"/> including [[Oracle database|Oracle]],<ref name="Oracle, Exadata Storage Indexes"/><ref name=Solarwinds/> [[Netezza]] 'zone maps',<ref>{{cite web|url=http://nztips.com/2010/11/netezza-integer-join-keys/ |publisher=Netezza|title=With Netezza Always Use Integer Join Keys For Good Compression, Zone Maps, And Joins|year=2010}}</ref> [[Infobright]] 'data packs',<ref>{{cite web|title=Data packs|publisher=[[Infobright]]|url=http://www.infobright.org/Blog/Entry/organizing_data_and_more_about_rough_data_contest/|archive-url=https://web.archive.org/web/20090627103453/http://www.infobright.org/Blog/Entry/organizing_data_and_more_about_rough_data_contest
== Design ==
[[File:B-tree.svg|thumb|B-tree index structure]]
[[File:BRIN index.svg|thumb|BRIN index structure]]BRIN operate by "summarising" large blocks of data into a compact form, which can be efficiently tested to exclude many of them from a database query, early on. These tests exclude a large block of data for each comparison. By reducing the data volume so early on, both by representing large blocks as small tuples, and by eliminating many blocks, BRIN substantially reduce the amount of detailed data that must be examined by the database node on a row-by-row basis.<ref>{{Cite web |last1=Herrera |first1=Alvaro |date=7 November 2014 |title=commitdiff - BRIN: Block Range Indexes |url=https://git.postgresql.org/gitweb/?p=postgresql.git;a=commitdiff;h=7516f5259411c02ae89e49084452dc342aadb2ae |website=git.postgresql.org |
Data storage in large databases is layered and chunked, with the table storage arranged into 'blocks'. Each block contains perhaps 1MB in each chunk{{efn-lr| PostgreSQL has a default BRIN chunk size of 128× 8k pages, or 1MB.<ref name="Wahts new"/> Oracle terms these 'storage regions' and gives them a default size of 1MB.<ref>{{cite web|title=When is Exadata's storage indexes used?|website=OakTable.net|url=http://www.oaktable.net/blog/when-exadata%E2%80%99s-storage-indexes-used?page=2}}</ref>}}<ref name="Richard Foote, 2012, I"/> and they are retrieved by requesting specific blocks from a disk-based storage layer. BRIN are a lightweight in-memory summary layer above this: each tuple in the index summarises one block as to the range of the data contained therein: its minimum and maximum values, and if the block contains any non-null data for the column(s) of interest.<ref name="Wong, 2015">{{Cite web
Line 46:
Some simple benchmarks suggest a five-fold improvement in search performance with an index scan, compared to the unindexed table.<ref name="Wahts new"/> Compared to B-trees, they avoid their maintenance overhead.<ref name="Herrera, 2013"/>
As BRIN are so lightweight, they may be held entirely in memory, thus avoiding disk overhead during the scan. The same may not be true of B-tree: B-tree requires a tree node for every approximately ''N rows'' in the table, where N is the capacity of a single node, thus the index size is large. As BRIN only requires a tuple for each block (of many rows), the index becomes sufficiently small to make the difference between disk and memory. For a 'narrow' table{{efn-lr|The table columns are barely wider than the indexed columns.}} the B-tree index volume approaches that of the table itself; the BRIN may be only
|title= Block Range (BRIN) Indexes in PostgreSQL 9.5
|date=May 22, 2015
Line 67:
|url=http://axleproject.eu/2014/11/30/progress-on-online-upgrade/}}</ref>
With BRIN, the slowdown from maintaining the index is much reduced compared to B-tree.<ref>{{cite
|title=Index Overhead on a Growing Table
|date=10 October 2014
|author=Mark Wong
|newspaper=2Ndquadrant | Postgresql
|url=http://blog.2ndquadrant.com/index-overhead-growing-table/
}}</ref> Wong reports that B-tree slowed down additions to an unindexed 10GB table by 85%, but a comparable BRIN only had an overhead of 11%.<ref name="Wong, 2014" />
Line 104 ⟶ 105:
}}</ref> Exadata has the strong concept of a 'storage layer' in its architecture stack. Table data is held in blocks or 'storage cells' on the storage servers. These storage cells are [[block-level storage|opaque to the storage server]] and are returned to the database engine on request, by their identifier. Previously, the database nodes must request all the storage cells in order to scan them.<ref name=Solarwinds>{{cite web
|title=Understanding Storage Indexes in Oracle Exadata
|date=2 June 2015
|url=http://logicalread.solarwinds.com/storage-indexes-oracle-exadata-mc05/#.Vpjbp27fXU8
}}</ref>
Line 139 ⟶ 141:
|website=PostgreSQL
| url = http://www.postgresql.org/message-id/E1XmpRL-0001Zh-Sd@gemulon.postgresql.org
|
== See also ==
| |||