Skip to content

Commit fab2502

Browse files
petergeogheganpetergeoghegan
committed
Consider secondary factors during nbtree splits.
Teach nbtree to give some consideration to how "distinguishing" candidate leaf page split points are. This should not noticeably affect the balance of free space within each half of the split, while still making suffix truncation truncate away significantly more attributes on average. The logic for choosing a leaf split point now uses a fallback mode in the case where the page is full of duplicates and it isn't possible to find even a minimally distinguishing split point. When the page is full of duplicates, the split should pack the left half very tightly, while leaving the right half mostly empty. Our assumption is that logical duplicates will almost always be inserted in ascending heap TID order with v4 indexes. This strategy leaves most of the free space on the half of the split that will likely be where future logical duplicates of the same value need to be placed. The number of cycles added is not very noticeable. This is important because deciding on a split point takes place while at least one exclusive buffer lock is held. We avoid using authoritative insertion scankey comparisons to save cycles, unlike suffix truncation proper. We use a faster binary comparison instead. Note that even pg_upgrade'd v3 indexes make use of these optimizations. Benchmarking has shown that even v3 indexes benefit, despite the fact that suffix truncation will only truncate non-key attributes in INCLUDE indexes. Grouping relatively similar tuples together is beneficial in and of itself, since it reduces the number of leaf pages that must be accessed by subsequent index scans. Author: Peter Geoghegan Reviewed-By: Heikki Linnakangas Discussion: https://postgr.es/m/CAH2-WzmmoLNQOj9mAD78iQHfWLJDszHEDrAzGTUMG3mVh5xWPw@mail.gmail.com
1 parent dd299df commit fab2502

File tree

6 files changed

+961
-291
lines changed

6 files changed

+961
-291
lines changed

‎src/backend/access/nbtree/Makefile

+1-1
Original file line numberDiff line numberDiff line change
@@ -13,6 +13,6 @@ top_builddir = ../../../..
1313
include $(top_builddir)/src/Makefile.global
1414

1515
OBJS = nbtcompare.o nbtinsert.o nbtpage.o nbtree.o nbtsearch.o \
16-
nbtutils.o nbtsort.o nbtvalidate.o nbtxlog.o
16+
nbtsplitloc.o nbtutils.o nbtsort.o nbtvalidate.o nbtxlog.o
1717

1818
include $(top_srcdir)/src/backend/common.mk

‎src/backend/access/nbtree/README

+44-3
Original file line numberDiff line numberDiff line change
@@ -143,9 +143,9 @@ Lehman and Yao assume fixed-size keys, but we must deal with
143143
variable-size keys. Therefore there is not a fixed maximum number of
144144
keys per page; we just stuff in as many as will fit. When we split a
145145
page, we try to equalize the number of bytes, not items, assigned to
146-
each of the resulting pages. Note we must include the incoming item in
147-
this calculation, otherwise it is possible to find that the incoming
148-
item doesn't fit on the split page where it needs to go!
146+
pages (though suffix truncation is also considered). Note we must include
147+
the incoming item in this calculation, otherwise it is possible to find
148+
that the incoming item doesn't fit on the split page where it needs to go!
149149

150150
The Deletion Algorithm
151151
----------------------
@@ -649,6 +649,47 @@ variable-length types, such as text. An opclass support function could
649649
manufacture the shortest possible key value that still correctly separates
650650
each half of a leaf page split.
651651

652+
There is sophisticated criteria for choosing a leaf page split point. The
653+
general idea is to make suffix truncation effective without unduly
654+
influencing the balance of space for each half of the page split. The
655+
choice of leaf split point can be thought of as a choice among points
656+
*between* items on the page to be split, at least if you pretend that the
657+
incoming tuple was placed on the page already (you have to pretend because
658+
there won't actually be enough space for it on the page). Choosing the
659+
split point between two index tuples where the first non-equal attribute
660+
appears as early as possible results in truncating away as many suffix
661+
attributes as possible. Evenly balancing space among each half of the
662+
split is usually the first concern, but even small adjustments in the
663+
precise split point can allow truncation to be far more effective.
664+
665+
Suffix truncation is primarily valuable because it makes pivot tuples
666+
smaller, which delays splits of internal pages, but that isn't the only
667+
reason why it's effective. Even truncation that doesn't make pivot tuples
668+
smaller due to alignment still prevents pivot tuples from being more
669+
restrictive than truly necessary in how they describe which values belong
670+
on which pages.
671+
672+
While it's not possible to correctly perform suffix truncation during
673+
internal page splits, it's still useful to be discriminating when splitting
674+
an internal page. The split point that implies a downlink be inserted in
675+
the parent that's the smallest one available within an acceptable range of
676+
the fillfactor-wise optimal split point is chosen. This idea also comes
677+
from the Prefix B-Tree paper. This process has much in common with what
678+
happens at the leaf level to make suffix truncation effective. The overall
679+
effect is that suffix truncation tends to produce smaller, more
680+
discriminating pivot tuples, especially early in the lifetime of the index,
681+
while biasing internal page splits makes the earlier, smaller pivot tuples
682+
end up in the root page, delaying root page splits.
683+
684+
Logical duplicates are given special consideration. The logic for
685+
selecting a split point goes to great lengths to avoid having duplicates
686+
span more than one page, and almost always manages to pick a split point
687+
between two user-key-distinct tuples, accepting a completely lopsided split
688+
if it must. When a page that's already full of duplicates must be split,
689+
the fallback strategy assumes that duplicates are mostly inserted in
690+
ascending heap TID order. The page is split in a way that leaves the left
691+
half of the page mostly full, and the right half of the page mostly empty.
692+
652693
Notes About Data Representation
653694
-------------------------------
654695

‎src/backend/access/nbtree/nbtinsert.c

+1-286
Original file line numberDiff line numberDiff line change
@@ -28,26 +28,6 @@
2828
/* Minimum tree height for application of fastpath optimization */
2929
#define BTREE_FASTPATH_MIN_LEVEL 2
3030

31-
typedef struct
32-
{
33-
/* context data for _bt_checksplitloc */
34-
Size newitemsz; /* size of new item to be inserted */
35-
int fillfactor; /* needed when splitting rightmost page */
36-
bool is_leaf; /* T if splitting a leaf page */
37-
bool is_rightmost; /* T if splitting a rightmost page */
38-
OffsetNumber newitemoff; /* where the new item is to be inserted */
39-
int leftspace; /* space available for items on left page */
40-
int rightspace; /* space available for items on right page */
41-
int olddataitemstotal; /* space taken by old items */
42-
43-
bool have_split; /* found a valid split? */
44-
45-
/* these fields valid only if have_split is true */
46-
bool newitemonleft; /* new item on left or right of best split */
47-
OffsetNumber firstright; /* best split point */
48-
int best_delta; /* best size delta so far */
49-
} FindSplitData;
50-
5131

5232
static Buffer _bt_newroot(Relation rel, Buffer lbuf, Buffer rbuf);
5333

@@ -73,13 +53,6 @@ static Buffer _bt_split(Relation rel, BTScanInsert itup_key, Buffer buf,
7353
Size newitemsz, IndexTuple newitem, bool newitemonleft);
7454
static void _bt_insert_parent(Relation rel, Buffer buf, Buffer rbuf,
7555
BTStack stack, bool is_root, bool is_only);
76-
static OffsetNumber _bt_findsplitloc(Relation rel, Page page,
77-
OffsetNumber newitemoff,
78-
Size newitemsz,
79-
bool *newitemonleft);
80-
static void _bt_checksplitloc(FindSplitData *state,
81-
OffsetNumber firstoldonright, bool newitemonleft,
82-
int dataitemstoleft, Size firstoldonrightsz);
8356
static bool _bt_pgaddtup(Page page, Size itemsize, IndexTuple itup,
8457
OffsetNumber itup_off);
8558
static bool _bt_isequal(TupleDesc itupdesc, BTScanInsert itup_key,
@@ -1003,7 +976,7 @@ _bt_insertonpg(Relation rel,
1003976

1004977
/* Choose the split point */
1005978
firstright = _bt_findsplitloc(rel, page,
1006-
newitemoff, itemsz,
979+
newitemoff, itemsz, itup,
1007980
&newitemonleft);
1008981

1009982
/* split the buffer into left and right halves */
@@ -1687,264 +1660,6 @@ _bt_split(Relation rel, BTScanInsert itup_key, Buffer buf, Buffer cbuf,
16871660
return rbuf;
16881661
}
16891662

1690-
/*
1691-
* _bt_findsplitloc() -- find an appropriate place to split a page.
1692-
*
1693-
* The idea here is to equalize the free space that will be on each split
1694-
* page, *after accounting for the inserted tuple*. (If we fail to account
1695-
* for it, we might find ourselves with too little room on the page that
1696-
* it needs to go into!)
1697-
*
1698-
* If the page is the rightmost page on its level, we instead try to arrange
1699-
* to leave the left split page fillfactor% full. In this way, when we are
1700-
* inserting successively increasing keys (consider sequences, timestamps,
1701-
* etc) we will end up with a tree whose pages are about fillfactor% full,
1702-
* instead of the 50% full result that we'd get without this special case.
1703-
* This is the same as nbtsort.c produces for a newly-created tree. Note
1704-
* that leaf and nonleaf pages use different fillfactors.
1705-
*
1706-
* We are passed the intended insert position of the new tuple, expressed as
1707-
* the offsetnumber of the tuple it must go in front of. (This could be
1708-
* maxoff+1 if the tuple is to go at the end.)
1709-
*
1710-
* We return the index of the first existing tuple that should go on the
1711-
* righthand page, plus a boolean indicating whether the new tuple goes on
1712-
* the left or right page. The bool is necessary to disambiguate the case
1713-
* where firstright == newitemoff.
1714-
*/
1715-
static OffsetNumber
1716-
_bt_findsplitloc(Relation rel,
1717-
Page page,
1718-
OffsetNumber newitemoff,
1719-
Size newitemsz,
1720-
bool *newitemonleft)
1721-
{
1722-
BTPageOpaque opaque;
1723-
OffsetNumber offnum;
1724-
OffsetNumber maxoff;
1725-
ItemId itemid;
1726-
FindSplitData state;
1727-
int leftspace,
1728-
rightspace,
1729-
goodenough,
1730-
olddataitemstotal,
1731-
olddataitemstoleft;
1732-
bool goodenoughfound;
1733-
1734-
opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1735-
1736-
/* Passed-in newitemsz is MAXALIGNED but does not include line pointer */
1737-
newitemsz += sizeof(ItemIdData);
1738-
1739-
/* Total free space available on a btree page, after fixed overhead */
1740-
leftspace = rightspace =
1741-
PageGetPageSize(page) - SizeOfPageHeaderData -
1742-
MAXALIGN(sizeof(BTPageOpaqueData));
1743-
1744-
/* The right page will have the same high key as the old page */
1745-
if (!P_RIGHTMOST(opaque))
1746-
{
1747-
itemid = PageGetItemId(page, P_HIKEY);
1748-
rightspace -= (int) (MAXALIGN(ItemIdGetLength(itemid)) +
1749-
sizeof(ItemIdData));
1750-
}
1751-
1752-
/* Count up total space in data items without actually scanning 'em */
1753-
olddataitemstotal = rightspace - (int) PageGetExactFreeSpace(page);
1754-
1755-
state.newitemsz = newitemsz;
1756-
state.is_leaf = P_ISLEAF(opaque);
1757-
state.is_rightmost = P_RIGHTMOST(opaque);
1758-
state.have_split = false;
1759-
if (state.is_leaf)
1760-
state.fillfactor = RelationGetFillFactor(rel,
1761-
BTREE_DEFAULT_FILLFACTOR);
1762-
else
1763-
state.fillfactor = BTREE_NONLEAF_FILLFACTOR;
1764-
state.newitemonleft = false; /* these just to keep compiler quiet */
1765-
state.firstright = 0;
1766-
state.best_delta = 0;
1767-
state.leftspace = leftspace;
1768-
state.rightspace = rightspace;
1769-
state.olddataitemstotal = olddataitemstotal;
1770-
state.newitemoff = newitemoff;
1771-
1772-
/*
1773-
* Finding the best possible split would require checking all the possible
1774-
* split points, because of the high-key and left-key special cases.
1775-
* That's probably more work than it's worth; instead, stop as soon as we
1776-
* find a "good-enough" split, where good-enough is defined as an
1777-
* imbalance in free space of no more than pagesize/16 (arbitrary...) This
1778-
* should let us stop near the middle on most pages, instead of plowing to
1779-
* the end.
1780-
*/
1781-
goodenough = leftspace / 16;
1782-
1783-
/*
1784-
* Scan through the data items and calculate space usage for a split at
1785-
* each possible position.
1786-
*/
1787-
olddataitemstoleft = 0;
1788-
goodenoughfound = false;
1789-
maxoff = PageGetMaxOffsetNumber(page);
1790-
1791-
for (offnum = P_FIRSTDATAKEY(opaque);
1792-
offnum <= maxoff;
1793-
offnum = OffsetNumberNext(offnum))
1794-
{
1795-
Size itemsz;
1796-
1797-
itemid = PageGetItemId(page, offnum);
1798-
itemsz = MAXALIGN(ItemIdGetLength(itemid)) + sizeof(ItemIdData);
1799-
1800-
/*
1801-
* Will the new item go to left or right of split?
1802-
*/
1803-
if (offnum > newitemoff)
1804-
_bt_checksplitloc(&state, offnum, true,
1805-
olddataitemstoleft, itemsz);
1806-
1807-
else if (offnum < newitemoff)
1808-
_bt_checksplitloc(&state, offnum, false,
1809-
olddataitemstoleft, itemsz);
1810-
else
1811-
{
1812-
/* need to try it both ways! */
1813-
_bt_checksplitloc(&state, offnum, true,
1814-
olddataitemstoleft, itemsz);
1815-
1816-
_bt_checksplitloc(&state, offnum, false,
1817-
olddataitemstoleft, itemsz);
1818-
}
1819-
1820-
/* Abort scan once we find a good-enough choice */
1821-
if (state.have_split && state.best_delta <= goodenough)
1822-
{
1823-
goodenoughfound = true;
1824-
break;
1825-
}
1826-
1827-
olddataitemstoleft += itemsz;
1828-
}
1829-
1830-
/*
1831-
* If the new item goes as the last item, check for splitting so that all
1832-
* the old items go to the left page and the new item goes to the right
1833-
* page.
1834-
*/
1835-
if (newitemoff > maxoff && !goodenoughfound)
1836-
_bt_checksplitloc(&state, newitemoff, false, olddataitemstotal, 0);
1837-
1838-
/*
1839-
* I believe it is not possible to fail to find a feasible split, but just
1840-
* in case ...
1841-
*/
1842-
if (!state.have_split)
1843-
elog(ERROR, "could not find a feasible split point for index \"%s\"",
1844-
RelationGetRelationName(rel));
1845-
1846-
*newitemonleft = state.newitemonleft;
1847-
return state.firstright;
1848-
}
1849-
1850-
/*
1851-
* Subroutine to analyze a particular possible split choice (ie, firstright
1852-
* and newitemonleft settings), and record the best split so far in *state.
1853-
*
1854-
* firstoldonright is the offset of the first item on the original page
1855-
* that goes to the right page, and firstoldonrightsz is the size of that
1856-
* tuple. firstoldonright can be > max offset, which means that all the old
1857-
* items go to the left page and only the new item goes to the right page.
1858-
* In that case, firstoldonrightsz is not used.
1859-
*
1860-
* olddataitemstoleft is the total size of all old items to the left of
1861-
* firstoldonright.
1862-
*/
1863-
static void
1864-
_bt_checksplitloc(FindSplitData *state,
1865-
OffsetNumber firstoldonright,
1866-
bool newitemonleft,
1867-
int olddataitemstoleft,
1868-
Size firstoldonrightsz)
1869-
{
1870-
int leftfree,
1871-
rightfree;
1872-
Size firstrightitemsz;
1873-
bool newitemisfirstonright;
1874-
1875-
/* Is the new item going to be the first item on the right page? */
1876-
newitemisfirstonright = (firstoldonright == state->newitemoff
1877-
&& !newitemonleft);
1878-
1879-
if (newitemisfirstonright)
1880-
firstrightitemsz = state->newitemsz;
1881-
else
1882-
firstrightitemsz = firstoldonrightsz;
1883-
1884-
/* Account for all the old tuples */
1885-
leftfree = state->leftspace - olddataitemstoleft;
1886-
rightfree = state->rightspace -
1887-
(state->olddataitemstotal - olddataitemstoleft);
1888-
1889-
/*
1890-
* The first item on the right page becomes the high key of the left page;
1891-
* therefore it counts against left space as well as right space. When
1892-
* index has included attributes, then those attributes of left page high
1893-
* key will be truncated leaving that page with slightly more free space.
1894-
* However, that shouldn't affect our ability to find valid split
1895-
* location, because anyway split location should exists even without high
1896-
* key truncation.
1897-
*/
1898-
leftfree -= firstrightitemsz;
1899-
1900-
/* account for the new item */
1901-
if (newitemonleft)
1902-
leftfree -= (int) state->newitemsz;
1903-
else
1904-
rightfree -= (int) state->newitemsz;
1905-
1906-
/*
1907-
* If we are not on the leaf level, we will be able to discard the key
1908-
* data from the first item that winds up on the right page.
1909-
*/
1910-
if (!state->is_leaf)
1911-
rightfree += (int) firstrightitemsz -
1912-
(int) (MAXALIGN(sizeof(IndexTupleData)) + sizeof(ItemIdData));
1913-
1914-
/*
1915-
* If feasible split point, remember best delta.
1916-
*/
1917-
if (leftfree >= 0 && rightfree >= 0)
1918-
{
1919-
int delta;
1920-
1921-
if (state->is_rightmost)
1922-
{
1923-
/*
1924-
* If splitting a rightmost page, try to put (100-fillfactor)% of
1925-
* free space on left page. See comments for _bt_findsplitloc.
1926-
*/
1927-
delta = (state->fillfactor * leftfree)
1928-
- ((100 - state->fillfactor) * rightfree);
1929-
}
1930-
else
1931-
{
1932-
/* Otherwise, aim for equal free space on both sides */
1933-
delta = leftfree - rightfree;
1934-
}
1935-
1936-
if (delta < 0)
1937-
delta = -delta;
1938-
if (!state->have_split || delta < state->best_delta)
1939-
{
1940-
state->have_split = true;
1941-
state->newitemonleft = newitemonleft;
1942-
state->firstright = firstoldonright;
1943-
state->best_delta = delta;
1944-
}
1945-
}
1946-
}
1947-
19481663
/*
19491664
* _bt_insert_parent() -- Insert downlink into parent after a page split.
19501665
*

0 commit comments

Comments
 (0)