<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html>
<head profile="http://internetalchemy.org/2003/02/profile">
<link rel="foaf" type="application/rdf+xml" title="FOAF" href="http://www.openlinksw.com/dataspace/uda/about.rdf" />
<link rel="schema.dc" href="http://purl.org/dc/elements/1.1/" />
<meta name="dc.subject" content="SQL" />
<meta name="dc.subject" content="SQL Reference" />
<meta name="dc.subject" content="Select" />
<meta name="dc.subject" content="Update" />
<meta name="dc.subject" content="delete" />
<meta name="dc.subject" content="Select Statement" />
<meta name="dc.subject" content="SQL Syntax" />
<meta name="dc.subject" content="Syntax" />
<meta name="dc.title" content="8. SQL Reference" />
<meta name="dc.subject" content="8. SQL Reference" />
<meta name="dc.creator" content="OpenLink Software Documentation Team ; " />
<meta name="dc.copyright" content="OpenLink Software, 1999 - 2009" />
<link rel="top" href="index.html" title="OpenLink Virtuoso Universal Server: Documentation" />
<link rel="search" href="/doc/adv_search.vspx" title="Search OpenLink Virtuoso Universal Server: Documentation" />
<link rel="parent" href="sqlreference.html" title="Chapter Contents" />
<link rel="prev" href="GRAMMAR.html" title="SQL Grammar" />
<link rel="next" href="transitivityinsQL.html" title="Transitivity in SQL" />
<link rel="shortcut icon" href="../images/misc/favicon.ico" type="image/x-icon" />
<link rel="stylesheet" type="text/css" href="doc.css" />
<link rel="stylesheet" type="text/css" href="/doc/translation.css" />
<title>8. SQL Reference</title>
<meta http-equiv="Content-Type" content="text/xhtml; charset=UTF-8" />
<meta name="author" content="OpenLink Software Documentation Team ; " />
<meta name="copyright" content="OpenLink Software, 1999 - 2009" />
<meta name="keywords" content="SQL; SQL Reference; Select; Update; delete; Select Statement; SQL Syntax; Syntax; " />
<meta name="GENERATOR" content="OpenLink XSLT Team" />
</head>
<body>
<div id="header">
<a name="BITMAPINDICES" />
<img src="../images/misc/logo.jpg" alt="" />
<h1>8. SQL Reference</h1>
</div>
<div id="navbartop">
<div>
<a class="link" href="sqlreference.html">Chapter Contents</a> | <a class="link" href="GRAMMAR.html" title="SQL Grammar">Prev</a> | <a class="link" href="transitivityinsQL.html" title="Transitivity in SQL">Next</a>
</div>
</div>
<div id="currenttoc">
<form method="post" action="/doc/adv_search.vspx">
<div class="search">Keyword Search: <br />
<input type="text" name="q" /> <input type="submit" name="go" value="Go" />
</div>
</form>
<div>
<a href="http://www.openlinksw.com/">www.openlinksw.com</a>
</div>
<div>
<a href="http://docs.openlinksw.com/">docs.openlinksw.com</a>
</div>
<br />
<div>
<a href="index.html">Book Home</a>
</div>
<br />
<div>
<a href="contents.html">Contents</a>
</div>
<div>
<a href="preface.html">Preface</a>
</div>
<br />
<div class="selected">
<a href="sqlreference.html">SQL Reference</a>
</div>
<br />
<div>
<a href="sqlrefDATATYPES.html">Datatypes</a>
</div>
<div>
<a href="udt.html">User Defined Types</a>
</div>
<div>
<a href="sqlrefxmldatatype.html">XML Column Type</a>
</div>
<div>
<a href="catidentifiers.html">Identifier Case & Quoting</a>
</div>
<div>
<a href="wideidentifiers.html">Wide Character Identifiers</a>
</div>
<div>
<a href="QUALIFIEDNAMES.html">Qualified Names</a>
</div>
<div>
<a href="litsbraceescs.html">Literals, Brace Escapes</a>
</div>
<div>
<a href="CREATETABLE.html">CREATE TABLE Statement</a>
</div>
<div>
<a href="DROPTABLE.html">DROP TABLE Statement</a>
</div>
<div>
<a href="CREATEINDEX.html">CREATE INDEX Statement</a>
</div>
<div>
<a href="DROPINDEX.html">DROP INDEX Statement</a>
</div>
<div>
<a href="ALTERTABLE.html">ALTER TABLE Statement</a>
</div>
<div>
<a href="CREATEVIEW.html">CREATE VIEW Statement</a>
</div>
<div>
<a href="CREATEXMLSCHEMA.html">CREATE XML SCHEMA Statement</a>
</div>
<div>
<a href="DROPXMLSCHEMA.html">DROP XML SCHEMA Statement</a>
</div>
<div>
<a href="sequenceobjects.html">Sequence Objects</a>
</div>
<div>
<a href="insertSTMT.html">INSERT Statement</a>
</div>
<div>
<a href="updatestmt.html">UPDATE Statement</a>
</div>
<div>
<a href="SELECTSTMT.html">SELECT Statement</a>
</div>
<div>
<a href="COMMIT_ROLLBACK.html">COMMIT WORK, ROLLBACK WORK Statement</a>
</div>
<div>
<a href="CHECKPOINT.html">CHECKPOINT, SHUTDOWN Statement</a>
</div>
<div>
<a href="spasviewsandtables.html">Stored Procedures as Views & Derived Tables</a>
</div>
<div>
<a href="GRANT.html">GRANT, REVOKE Statement</a>
</div>
<div>
<a href="SETstmt.html">SET Statement</a>
</div>
<div>
<a href="anytimequeries.html">Anytime Queries</a>
</div>
<div>
<a href="besteffortunion.html">Best Effort Union</a>
</div>
<div>
<a href="aggregates.html">Standard and User-Defined Aggregate Functions</a>
</div>
<div>
<a href="sqloptimizer.html">Virtuoso SQL Optimization</a>
</div>
<div>
<a href="sqlinverse.html">SQL Inverse Functions</a>
</div>
<div>
<a href="GRAMMAR.html">SQL Grammar</a>
</div>
<div class="selected">
<a href="BITMAPINDICES.html">Bitmap Indices</a>
<div>
<a href="#bitmapindandtrans" title="Bitmap Indices and Transactions">Bitmap Indices and Transactions</a>
<a href="#bitmapindandperfmimpl" title="Performance Implications">Performance Implications</a>
<a href="#physicalstroverheads" title="Physical Structure and Overheads">Physical Structure and Overheads</a>
</div>
</div>
<div>
<a href="transitivityinsQL.html">Transitivity in SQL</a>
</div>
<div>
<a href="sqlreffastphrasematch.html">Fast Phrase Match Processor</a>
</div>
<br />
</div>
<div id="text">
<a name="BITMAPINDICES" />
<h2>8.31. Bitmap Indices</h2>
<p>
A bitmap index is a special type of index that is tailored for being efficient for key columns with relatively
few distinct values, i.e. low cardinality key columns. A bitmap index is created with the normal create index
statement by putting the bitmap keyword in front of index, as follows:
</p>
<div>
<pre class="programlisting">
create table customer (c_id int primary key, c_state char (2), c_gender char (1), .... );
create bitmap index c_gender on customer (c_gender);
create bitmap index c_state on customer (c_state);
</pre>
</div>
<p>
Bitmap indices offer space savings of up to 1000 x in some cases and specially for large tables the savings in I/O can be very significant.
</p>
<p>
A bitmap index can only be used on tables with an integer primary key or in other situations where the last effective key part of the
index is an integer. This is understandable since a bitmap index uses a bitmap for representing the values of the last key part,
thus having one bitmap for each distinct combination of leading key parts. In the above example, the customer table has an
integer c_id column as primary key and a character for the customer's gender and a 2 character field for the state where
the customer is located. Thus, to count all the male customers in Massachusetts, one will take the males bitmap and
the MA bitmap and perform a bitwise AND of the two. This will have a 1 bit corresponding to the c_id of each
male customer in Massachusetts.
</p>
<p>
We also note that in order to do the count, the customer table itself does not even have to be referenced, as the
bitmaps hold all the information. Even if the table did have to be referenced, for example for adding up the
outstanding credit of all male customers in Massachusetts, the bitwise AND could be done first and only the relevant
rows would have to be retrieved from the table itself.
</p>
<p>
Virtuoso's implementation of bitmap indices is designed to work efficiently even when the leading key parts have
relatively high cardinality, i.e. many distinct values, causing there to be a large number of mostly empty bitmaps.
Of course, if each bitmap has only one bit set, for example if every customer is in a different state, there is no
benefit to bitmap indices. On the other hand, there is also almost no penalty, only 6 bytes more per index entry
than for a regular index. Therefore, for any non-unique key where bitmap indices are applicable, even if there
are only a few repeated values, bitmap indices are a safe choice. If there are at least 2 times more rows than
distinct values of the keys, space savings are certain.
</p>
<p>
A bitmap index may have any number of key parts of any type, provided that the last effective part is an integer or and IRI id.
The last key parts of an index are those primary key parts that do not occur elsewhere in the key. Thus, if the primary key is
a single integer, bitmap indices are always applicable. However, supposing the primary key were an integer plus a string,
it would be possible to make a bitmap index where the string were first, followed by the integer. This would make sense and
save space if the string were not unique by itself.
As another example, the RDF_QUAD system table, the default location of the Virtuoso RDF triple store, has the columns P, G, O and S,
where all are IRI ID's, except for O which is ANY. Thus, The primary key is the concatenation of all columns, by default in
the order GSPO. There is another key in the order PGOS which can be implemented as a bitmap index because S is an IRI ID,
hence integer-like for purposes of bitmap indices.
</p>
<a name="bitmapindandtrans" />
<h3>8.31.1. Bitmap Indices and Transactions</h3>
<p>
The minimum locking unit is the row. In the case of a bitmap index, one row holds a bitmap which most often refers to many rows.
Locking is therefore less granular than with regular indices. Thus, if multiple threads insert rows with bitmap indices,
more waits may occur than if the index were not bitmapped. A single row of a bitmap index references maximally 8192 other
rows, most often however the count is much less.
</p>
<p>
In all other respects, locking and transactional behavior are identical with other indices.
</p>
<br />
<a name="bitmapindandperfmimpl" />
<h3>8.31.2. Performance Implications</h3>
<p>
The main advantage of a bitmap index is more compact size, reflected in less I/O. Inserting an entry takes on the average
10% longer than for another type of index, likewise for random lookups with exact key values. Sequential access is usually faster.
Space savings and thereby improved working set behavior can produce dramatic gains for large tables.
</p>
<br />
<a name="physicalstroverheads" />
<h3>8.31.3. Physical Structure and Overheads</h3>
<p>
Bitmap indices divide the range of signed 64 bit integer values into ranges holding 8192 (8K) values. Each such range where at least
one bit is set is represented by a compression entry (CE). Multiple CE's can be on the same row. CE's having one bit set take 4
bytes, CE's with 512 or less bits set take 4 bytes plus 2 bytes per bit, CE's with over 512 bits set take 1K byte regardless of how
many bits are set.
</p>
<p>
A bitmap index where the bitmap holds only one bit takes 6 bytes more than the corresponding non-bitmap index entry.
A second value, if it falls in the same 8K range adds 2 bytes, 4 bytes if it does not fall within in the same 8K range.
If more than 512 values fall within the same 8K range, the bits are represented as a 1K byte bitmap and adding subsequent
values takes no extra space.
</p>
<p>
Virtuoso supports bitmap indices since version 4.5.2919.
</p>
<p>
Bitmap Indices
</p>
<br />
<table border="0" width="90%" id="navbarbottom">
<tr>
<td align="left" width="33%">
<a href="GRAMMAR.html" title="SQL Grammar">Previous</a>
<br />SQL Grammar</td>
<td align="center" width="34%">
<a href="sqlreference.html">Chapter Contents</a>
</td>
<td align="right" width="33%">
<a href="transitivityinsQL.html" title="Transitivity in SQL">Next</a>
<br />Transitivity in SQL</td>
</tr>
</table>
</div>
<div id="footer">
<div>Copyright© 1999 - 2009 OpenLink Software All rights reserved.</div>
<div id="validation">
<a href="http://validator.w3.org/check/referer">
<img src="http://www.w3.org/Icons/valid-xhtml10" alt="Valid XHTML 1.0!" height="31" width="88" />
</a>
<a href="http://jigsaw.w3.org/css-validator/">
<img src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!" height="31" width="88" />
</a>
</div>
</div>
</body>
</html>
distrib
>
Fedora
>
14
>
x86_64
>
media
>
updates
>
by-pkgid
>
71d40963b505df4524269198e237b3e3
>
files
>
22
