View source for Block Range Index

{{Short description|Database indexing technique}}
A '''Block Range Index''' or '''BRIN''' is a [[Database index|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 table, rather than the field sizes or overall size.}} tables.

BRIN indexes provide similar benefits to [[Horizontal partitioning|horizontal partitioning]] or sharding but without needing to explicitly declare partitions.<ref name="Wong, 2014" >{{cite web
 |title=Loading Tables and Creating B-tree and Block Range Indexes
|date=October 10, 2014
  |author=Mark Wong
|website=AXLE project
|url=http://axleproject.eu/2014/10/10/loading-tables-and-creating-b-tree-and-block-range-indexes/
}}</ref>

A BRIN is applicable to an index on a table that is large and where the index key value is easily sorted and evaluated with a MinMax function.{{efn-lr|A function which efficiently evaluates a large number of data items and returns their minimum and maximum values. The concepts of "minimum" and "maximum" are broad and may be applied to any data type, or their combinations, which is [[Sorting algorithm|sortable]].}}

BRIN were originally proposed by Alvaro Herrera of 2ndQuadrant in 2013 as 'Minmax indexes'.<ref name="Herrera, 2013">{{cite web
|title=Minmax indexes
|date=2013-06-14
|author=Alvaro Herrera
|website=Pg Hackers
|url=http://www.postgresql.org/message-id/20130614222805.GZ5491@eldon.alvh.no-ip.org
}}</ref> Implementations thus far are tightly coupled to internal implementation and storage techniques for the database tables. This makes them efficient, but limits them to particular vendors. So far [[Software:PostgreSQL|PostgreSQL]] is the only vendor to have announced a live product with this specific feature, in PostgreSQL&nbsp;9.5.<ref name="Wahts new">{{cite web
  |title=What's new in PostgreSQL 9.5
|website=PostgreSQL
|date=
|url=https://wiki.postgresql.org/wiki/What%27s_new_in_PostgreSQL_9.5#BRIN_Indexes
}}</ref><ref name="PG, BRIN">{{cite web
|date=2016
|work=PostgreSQL 9.5.0 Documentation
|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 [[Software:Oracle database|Oracle]],<ref name="Oracle, Exadata Storage Indexes"/><ref name=Solarwinds/> [[Company:Netezza|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> [[Company:Infobright|Infobright]] 'data packs',<ref>{{cite web|title=Data packs|publisher=[[Company:Infobright|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|archive-date=2009-06-27}}</ref> [[Software:MonetDB|MonetDB]]<ref>{{cite CiteSeerX |title=Cooperative Scans: Dynamic Bandwidth Sharing in a DBMS|year=2007|pages=723–734 |citeseerx=10.1.1.108.2662}}</ref> and [[Software:Apache Hive|Apache Hive]] with ORC/Parquet.<ref>{{cite web|title=Hive Optimizations with Indexes, Bloom-Filters and Statistics|year=2015|publisher=Jörn Franke|url=https://snippetessay.wordpress.com/2015/07/25/hive-optimizations-with-indexes-bloom-filters-and-statistics/|access-date=2016-05-24|archive-date=2016-03-04|archive-url=https://web.archive.org/web/20160304183122/https://snippetessay.wordpress.com/2015/07/25/hive-optimizations-with-indexes-bloom-filters-and-statistics/|url-status=dead}}</ref>

== 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 |access-date=2017-10-03}}</ref>

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
  |title=PostgreSQL Performance Presentation
  |author=Mark Wong
  |date=10 March 2015
  |pages=7–10
  |url=https://axleproject2015.files.wordpress.com/2015/03/postgresql-performance-presentation-sfpgday2015.pdf
}}</ref>

Unlike a traditional index which ''locates'' the regions of the table containing values of interest, BRIN act as "negative indexes",<ref name="Oracle, Exadata Storage Indexes"/> showing the blocks that are definitely ''not'' of interest and thus do not need to be processed further.

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 5-15% of it.<ref name="Python Sweetness">{{cite web
 |title= Block Range (BRIN) Indexes in PostgreSQL 9.5
 |date=May 22, 2015
|website=Python Sweetness
|url=http://pythonsweetness.tumblr.com/post/119568339102/block-range-brin-indexes-in-postgresql-95
}}</ref>

== Advantages ==

=== Search and index scan ===
A large database index would typically use [[B-tree]] algorithms. BRIN is not always a substitute for B-tree, it is an improvement on sequential scanning of an index, with particular (and potentially large) advantages when the index meets particular conditions for being ordered and for the search target to be a narrow set of these values. In the general case, with random data, B-tree may still be superior.<ref name="Wahts new"/>

A particular advantage of the BRIN technique, shared with Oracle Exadata's Smart Scanning,<ref name=Solarwinds/> is in the use of this type of index with Big Data or data warehousing applications, where it is known that almost all of the table is irrelevant to the range of interest. BRIN allows the table to be queried in such cases by only retrieving blocks that ''may'' contain data of interest and excluding those which are clearly outside the range, or contain no data for this column.

=== Insert ===
A regular problem with the processing of large tables is that retrieval requires the use of an index, but maintaining this index slows down the addition of new records. Typical practices have been to group additions together and add them as a single bulk transaction, or to drop the index, add the batch of new records and then recreate the index. Both of these are disruptive to simultaneous read / write operations and may not be possible in some continuously-operating businesses.<ref>{{cite web|title=Progress on online upgrade
|author= Petr Jelinek
|date=28 November 2014
|website=AXLE project
|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 news
|title=Index Overhead on a Growing Table
|date=10 October 2014
|author=Mark Wong
|newspaper=2Ndquadrant &#124; 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" />

=== Index creation ===
BRIN may be created for extremely large data where B-tree would require horizontal partitioning.<ref name="Wong, 2015"/>

Creating the BRIN is also much faster than for a B-tree, by 80%.<ref name="Wong, 2014" /> This would be a useful improvement to [[Code refactoring|refactoring]] existing database applications that use the drop-add-reindex approach, without requiring code changes.

== Implementation ==

=== Dependence on table ordering ===
Multiple BRIN may be defined for different columns on a single table. However, there are restrictions.

BRIN are only efficient if the ordering of the key values follows the organisation of blocks in the storage layer.<ref name="Richard Foote, 2012, I"/><ref name="Python Sweetness"/> In the simplest case, this could require the physical ordering of the table, which is often the creation order of the rows within it, to match the key's order. Where this key is a creation date, that may be a trivial requirement.<ref name="Wong, 2015"/>{{rp|9}}

If the data is truly random, or if there is much churn of the key values in a 'hot' database, the assumptions underlying BRIN may break down. All blocks contain entries "of interest" and so few may be excluded early on by the BRIN range filter.

In most cases, BRIN is restricted to a single index per table. Multiple BRIN may be defined, but only one is likely to have suitable ordering. If two (or more) indexes have similar ordering behaviour, it may be possible and useful to define multiple BRIN on the same table. An obvious example is where both a creation date and a record_id column both increase monotonically with the record creation sequence.  In other cases, the key value may not be monotonic, but provided that there is still a strong grouping within the record's physical order, BRIN is effective.

=== Exadata Storage Indexes ===
BRIN have some similarities to [[Software:Oracle Exadata|Oracle Exadata]] "[[Storage Index]]es".<ref name="Herrera, 2013"/><ref name="Oracle, Exadata Storage Indexes">{{cite journal
|title=Smart Scans Meet Storage Indexes
|author=Arup Nanda
|date=May–June 2011
|journal=Oracle Magazine
|publisher=[[Company:Oracle Corporation|Oracle]]
|url=http://www.oracle.com/technetwork/issue-archive/2011/11-may/o31exadata-354069.html
}}</ref><ref>{{cite web
|title=Oracle Sun Database Machine Application Best Practices for Data Warehousing
|id=1094934.1
|publisher=Oracle
}}</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>

Storage Indexes provides data pruning at this layer: efficiently indicating sections that are of no further interest.<ref name="Richard Foote, 2012, I">{{cite web
|title=Exadata Storage Indexes – Part I 
|author=Richard Foote
|date=4 October 2012
|url=https://richardfoote.wordpress.com/2012/10/04/exadata-storage-indexes-part-i-beginning-to-see-the-light/
}}</ref>{{efn-lr|Foote<ref name="Richard Foote, 2012, I"/> describes the Index as holding "a flag to denote whether any Nulls exist". This is probably a typo: Oracle describes them as, "negative indexes" where "they identify the areas that definitely will not contain the values"<ref name="Oracle, Exadata Storage Indexes"/> In such a case, the flag would be more clearly described as denoting either "''Only'' Nulls exist" or if "Any ''non-''Nulls exist".}}<ref>{{cite web
 |title=Exadata's Best Kept Secret: Storage Indexes
|author=Marc Fielding
|date=July 20, 2010
|url=http://www.pythian.com/blog/exadata-storage-indexes/
}}</ref> The Storage Index is loaded into memory on the storage server, so that when a request for cells is issued it may be predicated with search values. These are compared to the Storage Index and then only the relevant cells need be returned to the database node.

Performance advantages with a Storage Index are most evident when the indexed column contains many nulls. Massive performance advantages are gained when scanning across [[Sparse matrix|sparse data]].<ref>{{cite web
|title=Oracle Exadata – Storage Indexes
|author=Kerry Osborne
|date=August 10, 2010
|url=http://kerryosborne.oracle-guy.com/2010/08/oracle-exadata-storage-indexes/
}}</ref>

== Development ==
Development for PostgreSQL was carried out as part of the AXLE project (Advanced Analytics for Extremely Large European Databases)<ref>{{Cite web |title=AXLE project (Advanced Analytics for Extremely Large European Databases) |year=2014 |url=http://axleproject.eu/}}</ref> This work was partially funded by the European Union's Seventh Framework Programme (FP7/2007-2013).<ref>{{Cite web
 |title=European Union's Seventh Framework Programme (FP7/2007-2013) under grant agreement n° 318633.
|url=
}}</ref>

== PostgreSQL ==
Implementation for PostgreSQL was first evident in 2013.<ref name="Herrera, 2013"/> BRIN appeared in release 9.5 of [[Software:PostgreSQL|PostgreSQL]] at the start of 2016.<ref name="Python Sweetness"/><ref name="brin_indexes">{{ cite web 
| date = 2014-11-07
 | title = BRIN: Block Range Indexes
  |author=Alvaro Herrera
|website=PostgreSQL
 | url = http://www.postgresql.org/message-id/E1XmpRL-0001Zh-Sd@gemulon.postgresql.org 
| access-date = 2016-01-14 }}</ref>

== See also ==
* Sharding

== Notes ==
{{notelist-lr}}

== References ==
{{Reflist|30em}}

[[Category:Database index techniques]]
[[Category:PostgreSQL]]

{{Sourceattribution|Block Range Index}}