Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitd09dbeb

Browse files
committed
Speedup hash index builds by skipping needless binary searches
When building hash indexes using the spool method, tuples are added to theindex page in hashkey order. Because of this, we can safely skipperforming the binary search on the existing tuples on the page to findthe location to insert the tuple based on its hashkey value. For thiscase, we can just always put the tuple at the end of the item array as thetuples will always arrive in hashkey order.Testing has shown that this can improve hash index build speeds by 5-15%with a unique set of integer values.Author: Simon RiggsReviewed-by: David RowleyTested-by: David Zhang, Tomas VondraDiscussion:https://postgr.es/m/CANbhV-GBc5JoG0AneUGPZZW3o4OK5LjBGeKe_icpC3R1McrZWQ@mail.gmail.com
1 parentd46ad72 commitd09dbeb

File tree

4 files changed

+41
-13
lines changed

4 files changed

+41
-13
lines changed

‎src/backend/access/hash/hash.c

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -231,7 +231,7 @@ hashbuildCallback(Relation index,
231231
itup=index_form_tuple(RelationGetDescr(index),
232232
index_values,index_isnull);
233233
itup->t_tid=*tid;
234-
_hash_doinsert(index,itup,buildstate->heapRel);
234+
_hash_doinsert(index,itup,buildstate->heapRel, false);
235235
pfree(itup);
236236
}
237237

@@ -265,7 +265,7 @@ hashinsert(Relation rel, Datum *values, bool *isnull,
265265
itup=index_form_tuple(RelationGetDescr(rel),index_values,index_isnull);
266266
itup->t_tid=*ht_ctid;
267267

268-
_hash_doinsert(rel,itup,heapRel);
268+
_hash_doinsert(rel,itup,heapRel, false);
269269

270270
pfree(itup);
271271

‎src/backend/access/hash/hashinsert.c

Lines changed: 33 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -32,9 +32,12 @@ static void _hash_vacuum_one_page(Relation rel, Relation hrel,
3232
*
3333
*This routine is called by the public interface routines, hashbuild
3434
*and hashinsert. By here, itup is completely filled in.
35+
*
36+
* 'sorted' must only be passed as 'true' when inserts are done in hashkey
37+
* order.
3538
*/
3639
void
37-
_hash_doinsert(Relationrel,IndexTupleitup,RelationheapRel)
40+
_hash_doinsert(Relationrel,IndexTupleitup,RelationheapRel,boolsorted)
3841
{
3942
Bufferbuf=InvalidBuffer;
4043
Bufferbucket_buf;
@@ -198,7 +201,7 @@ _hash_doinsert(Relation rel, IndexTuple itup, Relation heapRel)
198201
START_CRIT_SECTION();
199202

200203
/* found page with enough space, so add the item here */
201-
itup_off=_hash_pgaddtup(rel,buf,itemsz,itup);
204+
itup_off=_hash_pgaddtup(rel,buf,itemsz,itup,sorted);
202205
MarkBufferDirty(buf);
203206

204207
/* metapage operations */
@@ -263,21 +266,43 @@ _hash_doinsert(Relation rel, IndexTuple itup, Relation heapRel)
263266
*
264267
* Returns the offset number at which the tuple was inserted. This function
265268
* is responsible for preserving the condition that tuples in a hash index
266-
* page are sorted by hashkey value.
269+
* page are sorted by hashkey value, however, if the caller is certain that
270+
* the hashkey for the tuple being added is >= the hashkeys of all existing
271+
* tuples on the page, then the 'appendtup' flag may be passed as true. This
272+
* saves from having to binary search for the correct location to insert the
273+
* tuple.
267274
*/
268275
OffsetNumber
269-
_hash_pgaddtup(Relationrel,Bufferbuf,Sizeitemsize,IndexTupleitup)
276+
_hash_pgaddtup(Relationrel,Bufferbuf,Sizeitemsize,IndexTupleitup,
277+
boolappendtup)
270278
{
271279
OffsetNumberitup_off;
272280
Pagepage;
273-
uint32hashkey;
274281

275282
_hash_checkpage(rel,buf,LH_BUCKET_PAGE |LH_OVERFLOW_PAGE);
276283
page=BufferGetPage(buf);
277284

278-
/* Find where to insert the tuple (preserving page's hashkey ordering) */
279-
hashkey=_hash_get_indextuple_hashkey(itup);
280-
itup_off=_hash_binsearch(page,hashkey);
285+
/*
286+
* Find where to insert the tuple (preserving page's hashkey ordering). If
287+
* 'appendtup' is true then we just insert it at the end.
288+
*/
289+
if (appendtup)
290+
{
291+
itup_off=PageGetMaxOffsetNumber(page)+1;
292+
293+
/* ensure this tuple's hashkey is >= the final existing tuple */
294+
Assert(PageGetMaxOffsetNumber(page)==0||
295+
_hash_get_indextuple_hashkey((IndexTuple)
296+
PageGetItem(page,PageGetItemId(page,
297+
PageGetMaxOffsetNumber(page)))) <=
298+
_hash_get_indextuple_hashkey(itup));
299+
}
300+
else
301+
{
302+
uint32hashkey=_hash_get_indextuple_hashkey(itup);
303+
304+
itup_off=_hash_binsearch(page,hashkey);
305+
}
281306

282307
if (PageAddItem(page, (Item)itup,itemsize,itup_off, false, false)
283308
==InvalidOffsetNumber)

‎src/backend/access/hash/hashsort.c

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -145,7 +145,8 @@ _h_indexbuild(HSpool *hspool, Relation heapRel)
145145
Assert(hashkey >=lasthashkey);
146146
#endif
147147

148-
_hash_doinsert(hspool->index,itup,heapRel);
148+
/* the tuples are sorted by hashkey, so pass 'sorted' as true */
149+
_hash_doinsert(hspool->index,itup,heapRel, true);
149150

150151
pgstat_progress_update_param(PROGRESS_CREATEIDX_TUPLES_DONE,
151152
++tups_done);

‎src/include/access/hash.h

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -390,9 +390,11 @@ extern void hashadjustmembers(Oid opfamilyoid,
390390
/* private routines */
391391

392392
/* hashinsert.c */
393-
externvoid_hash_doinsert(Relationrel,IndexTupleitup,RelationheapRel);
393+
externvoid_hash_doinsert(Relationrel,IndexTupleitup,RelationheapRel,
394+
boolsorted);
394395
externOffsetNumber_hash_pgaddtup(Relationrel,Bufferbuf,
395-
Sizeitemsize,IndexTupleitup);
396+
Sizeitemsize,IndexTupleitup,
397+
boolappendtup);
396398
externvoid_hash_pgaddmultitup(Relationrel,Bufferbuf,IndexTuple*itups,
397399
OffsetNumber*itup_offsets,uint16nitups);
398400

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp