Lossy Index Tuple Enhancement (LITE) - Mailing list pgsql-hackers

This proposal introduces the idea of "lossy index tuples", an idea
that provides two important optimizations for btrees and potentially
other index types stimulated by recent blog complaints.

The two optimizations are Clustered Indexes (mostly for INSERTs) and
Update Duplicate Removal (for non-HOT UPDATEs), discussed more later.
LITE can be used for either or both of those optimizations
independently, even though they are implemented in fairly similar
ways. So if one of those gets shot down the other is still potentially
valid.

If this has wings, I'll start tracking this as a wiki page. If it
doesn't have wings, at least we tried to respond with technical
solutions to external input.

=Lossy Index Tuple Enhancement=

The LITE concept is that if the 13th index tuple bit is set the index
tuple represents a collection of tuples on one heap page rather than a
pointer to a single root heap tuple. 13th bit is currently unused, so
this optimization is fully backwards compatible with all existing
indexes, we just start using them more efficiently over time.

Importantly, this means that the user doesn't need to do anything at
all to begin benefiting from LITE. It also means that much of the code
required is non-invasive to the index code. These benefits are much
better than inventing a new index type and leaving the user to figure
out how and when to use them.

We call the 13th bit the "lossy bit", using the same terminology from
bitmap index access, indicating that we no longer hold exact details
of the heap tuples the pointer refers to, nor do we do reference
counting.

When the lossy bit is set we no longer interpret the TID as a
(blocknumber, linepointer) we interpret the data as (blocknumber,
lite_flags). The lite_flags have one bit reserved to decide whether
the LITE tuple represents multiple duplicates or whether it represents
a range of values.

The remainder of the lite_flags allow us to store details of which
ranges of linepointers are covered by the LITE tuple, splitting the
block into 15 ranges of linepointers. We just XOR the new linepointer
position with the bitmap when we update the bitmask. (The ranges are
consecutive not striped, to ensure that heavily repetitive updates are
optimized). If anyone is worried about running out of index tuple
flags, then perhaps we can reserve a few of the 16 bits for additional
flags rather than use them all for lp ranges.

By splitting the index blocks into 15 ranges we will avoid the need
for scanning the whole block in most cases, so the performance
degradation from single pointer to complete-block-pointer should be
much smoother.

This optimization would still allow UNIQUE indexes. In fact this
optimization would almost never overlap with a unique index anyway,
since we seldom update the PK of a table. Lossy index tuples would not
be able to skip accessing the heap during index-only scans, but the
presence of covered index columns would increase the uniqueness and
very likely stop the index tuple being marked lossy.

The remainder of the description is split between the two use
cases/optimizations which are similar but would have different code
for each.

== Update Duplicate Removal ==

We want an optimization that reduces the effects of multiple UPDATEs
on the same block that have duplicate values caused because another
index column has been updated and a non-HOT index insert has been
generated. This optimizes the case where someone has 12 indexes yet
updates just one of them, so we optimize the 11 unnecessary updates,
if possible.

As UPDATEs occur we request inserts into the index. If a lossy index
pointer already exists that covers the new linepointer then we skip
the index insert, optimizing writes to the index. If a lossy index
pointer already exists for that value but doesn't yet cover our
linepointer then we update the bitmask. If a non-lossy index pointer
already exists we set the lossy bit and update the bitmask to reflect
which linepointers the index entry covers. If no index pointer exists
we insert one. The first update on a row will not be optimized, but
the 2nd - 16th could be. These actions optimize away most of the
writes and WAL activity to the index data block since only 1 in every
16 updates would cause changes to the block (actually about 1 in 10 on
average). Most importantly, updates will cause far fewer index block
splits and reindexing will be less needed.

The same situation can occur if we have many INSERTs with same values
on the same block. This could lead to a reduction in size of the btree
for indexes with many duplicate values.

== Clustered Index ==

We want an optimization that allows us to index a consecutive range of
values on one block. Currently if we have values 1-100 on one heap
block, we would have 100 index pointers all pointing to the one heap
block. LITE would allow that to be indexed as a single index tuple, in
the common case.

As an INSERT starts a new block we begin with a base value of N.
Frequently we have the case where the next value in the table is N+1
and is inserted into the same block (or could be arranged to do so).
After say 100 INSERTs we now have values 1-100 on the heap block.

As the first INSERT occurs we insert a normal index tuple pointing to
it. As we INSERT a new value we can mark the index tuple as being an
RLITE tuple. Further inserts with a higher value on this data block
will be optimized away, as long as there is no later tuple
e.g.
val1 -> block0
val100 -> block1
if we insert the value 85 then it would go to block0, if we insert the
value 105 it would go to block1 without creating an additional tuple.
The value -5 would create a new tuple.

Index entries that split block ranges would be more complex and
costly, though they are only seen infrequently in real world apps.
e.g. we might have values 1, 90, 91 on block0 and values 100, 105 on
block1. If we insert the value 25 into block2 we would then have an
index that looks like this
val1 -> block0
val25 -> block2
val90 -> block0
val100 -> block1
First, we would clearly benefit here if we route the heap insert for
value 25 to occur on block0. That routing may not be acceptable, or
the block itself may be full, so we must handle the block split. If a
value is inserted into a range, then we must re-read the heap block to
see how to handle it.
i.e. the index tuple val1 represents values from val1 to val100 and
points to block0. If we insert val25 then we must re-read block0 and
edit the index entries around it by creating two new index tuples val1
(representing 1-24) and val90 (representing 90-99).

This looks doable, but more complex, so I'm posting this now to allow
for discussion and for people to spot the holes.

== IndexScan ==

Note that the executor code for IndexScan appears identical between
the two optimizations. The difference between duplicate and range LITE
tuples is needed only at INSERT time (or UPDATE indexed column to a
new value).

When we do an IndexScan if we see a LITE tuple we do a scan of the
linepointer ranges covered by this index tuple (which might eventually
go to a full block scan). For example with bit1 set we would scan 16
linepointers (on an 8192 byte block) and with 2 bits set we would scan
32 linepointers etc.., not necessarily consecutive ranges. So the
IndexScan can return potentially many heap rows per index entry, which
need to be re-checked and may also need to be sorted prior to
returning them. If no rows are returned we can kill the index pointer,
just as we do now for btrees, so they will be removed eventually from
the index without the need for VACUUM. An BitmapIndexScan that sees a
lossy pointer can also use the lossy TID concept, so we can have
partially lossy bitmaps.

== VACUUM ==

VACUUM would not cause a problem since line pointer removal for
non-lossy index tuples would occur normally. Lossy index tuples would
be ignored by index vacuum, but they would not prevent removal of line
pointers from the heap.

== Code Footprint ==

All of this code is concentrated in the Scan nodes, and in btinsert().

There are no changes to WAL records or replay. The details are all in
the way we insert and interpret index tuples.

== Other designs ==

This is related in a few ways to Grouped Item Tuple indexes, a patch
Heikki worked on in 2007, but is not that close.

-- 
Simon Riggs                http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services