Hi, On 2016-06-24 16:29:53 -0700, Andres Freund wrote: > 4) Various missing micro optimizations have to be performed, for more > architectural issues to become visible. E.g. [2] causes such bad > slowdowns in hash-agg workloads, that other bottlenecks are hidden.
One such issue is the usage of dynahash.c in tidbitmap.c. In many queries, e.g. tpch q7, the bitmapscan is often the bottleneck. Profiling shows that this is largely due to dynahash.c being slow. Primary issues are: a) two level structure doubling the amount of indirect lookups b) indirect function calls c) using separate chaining based conflict resolution d) being too general. I've quickly hacked up an alternative linear addressing hashtable implementation. And the improvements are quite remarkable. Example Query: EXPLAIN ANALYZE SELECT SUM(l_extendedprice) FROM lineitem WHERE (l_shipdate >= '1995-01-01'::date) AND (l_shipdate <= '1996-12-31'::date); before: ┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐ │ QUERY PLAN │ ├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤ │ Aggregate (cost=942046.72..942046.73 rows=1 width=8) (actual time=4647.908..4647.909 rows=1 loops=1) │ │ -> Bitmap Heap Scan on lineitem (cost=193514.84..919246.17 rows=9120222 width=8) (actual time=2667.821..3885.598 rows=9113219 loops=1) │ │ Recheck Cond: ((l_shipdate >= '1995-01-01'::date) AND (l_shipdate <= '1996-12-31'::date)) │ │ Heap Blocks: exact=585542 │ │ -> Bitmap Index Scan on i_l_shipdate (cost=0.00..191234.78 rows=9120222 width=0) (actual time=2461.622..2461.622 rows=9113219 loops=1) │ │ Index Cond: ((l_shipdate >= '1995-01-01'::date) AND (l_shipdate <= '1996-12-31'::date)) │ │ Planning time: 0.170 ms │ │ Execution time: 4648.921 ms │ └──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘ timing without analyze: 4136.425 4101.873 4177.441 after: ┌────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐ │ QUERY PLAN │ ├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤ │ Aggregate (cost=942046.72..942046.73 rows=1 width=8) (actual time=3218.422..3218.423 rows=1 loops=1) │ │ -> Bitmap Heap Scan on lineitem (cost=193514.84..919246.17 rows=9120222 width=8) (actual time=1153.707..2430.500 rows=9113219 loops=1) │ │ Recheck Cond: ((l_shipdate >= '1995-01-01'::date) AND (l_shipdate <= '1996-12-31'::date)) │ │ Heap Blocks: exact=585542 │ │ -> Bitmap Index Scan on i_l_shipdate (cost=0.00..191234.78 rows=9120222 width=0) (actual time=952.161..952.161 rows=9113219 loops=1) │ │ Index Cond: ((l_shipdate >= '1995-01-01'::date) AND (l_shipdate <= '1996-12-31'::date)) │ │ Planning time: 1.075 ms │ │ Execution time: 3221.861 ms │ └────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘ (8 rows) timing without analyze: 2647.364 2674.456 2680.197 as you can see the the time for the bitmap index scan goes from 2461.622 to 952.161. I'm not proposing to apply the patch as-is, but I think it's a good starting point to discuss how to evolve our use of hash tables. I'm wondering whether we can do 'macro based templates' or something. I.e. have something like the simplehash in the patch in simplehash.h, but the key/value widths, the function names, are all determined by macros (oh, this would be easier with C++ templates...). Does anybody have a better idea? The major issue with the simplehash implementation in the path is probably the deletion; which should rather move cells around, rather than use toombstones. But that was too complex for a POC ;). Also, it'd likely need a proper iterator interface. FWIW, the dynahash usage in nodeAgg.c is a major bottleneck in a number of other queries. Regards, Andres
>From 7c43245b80a7b278bbee3ec40dad9377296b1e41 Mon Sep 17 00:00:00 2001 From: Andres Freund <and...@anarazel.de> Date: Thu, 7 Jul 2016 14:47:19 -0700 Subject: [PATCH 08/20] WIP: Use more efficient hashtable for tidbitmap.c --- src/backend/nodes/tidbitmap.c | 357 +++++++++++++++++++++++++++++++++++++++++- 1 file changed, 355 insertions(+), 2 deletions(-) diff --git a/src/backend/nodes/tidbitmap.c b/src/backend/nodes/tidbitmap.c index dfeb7d5..26b8f7a 100644 --- a/src/backend/nodes/tidbitmap.c +++ b/src/backend/nodes/tidbitmap.c @@ -97,6 +97,7 @@ typedef struct PagetableEntry { BlockNumber blockno; /* page number (hashtable key) */ + char status; bool ischunk; /* T = lossy storage, F = exact */ bool recheck; /* should the tuples be rechecked? */ bitmapword words[Max(WORDS_PER_PAGE, WORDS_PER_CHUNK)]; @@ -129,6 +130,7 @@ struct TIDBitmap MemoryContext mcxt; /* memory context containing me */ TBMStatus status; /* see codes above */ HTAB *pagetable; /* hash table of PagetableEntry's */ + struct simplehash *pagetable2; int nentries; /* number of entries in pagetable */ int maxentries; /* limit on same to meet maxbytes */ int npages; /* number of exact entries in pagetable */ @@ -168,6 +170,237 @@ static void tbm_mark_page_lossy(TIDBitmap *tbm, BlockNumber pageno); static void tbm_lossify(TIDBitmap *tbm); static int tbm_comparator(const void *left, const void *right); +#define USE_SIMPLEHASH + +typedef struct simplehash +{ + uint32 size; + uint32 members; + uint32 deleted; + PagetableEntry *data; + MemoryContext ctx; + bool resizing; +} simplehash; + + +static inline uint32 +hash_blockno(BlockNumber b) +{ + uint32 h = b; + h ^= h >> 16; + h *= 0x85ebca6b; + h ^= h >> 13; + h *= 0xc2b2ae35; + h ^= h >> 16; + return h; +} + +static PagetableEntry * +simplehash_insert(simplehash *tb, BlockNumber key, bool *found); + +static simplehash * +simplehash_create(MemoryContext ctx, uint32 size) +{ + simplehash *tb; + + /* FIXME: assert size is a power of two */ + tb = MemoryContextAllocZero(ctx, sizeof(simplehash)); + tb->ctx = ctx; + tb->size = size; + tb->data = MemoryContextAllocZero(ctx, sizeof(PagetableEntry) * tb->size); + + return tb; +} + +static void +simplehash_destroy(simplehash *tb) +{ + pfree(tb->data); + pfree(tb); +} + +static void +simplehash_resize(simplehash *tb, uint32 newsize) +{ + uint32 oldsize = tb->size; + PagetableEntry *olddata = tb->data; + int i; + + Assert(!tb->resizing); + tb->resizing = true; + tb->size = newsize; + tb->data = MemoryContextAllocExtended(tb->ctx, sizeof(PagetableEntry) * tb->size, + MCXT_ALLOC_HUGE | MCXT_ALLOC_ZERO); + + ereport(DEBUG2, + (errmsg("resizing: %u to %u", oldsize, tb->size), + errhidestmt(true))); + + for (i = 0; i < oldsize; i++) + { + PagetableEntry *oldentry = &olddata[i]; + if (oldentry->status == 1) + { + PagetableEntry *newentry; + bool found; + newentry = simplehash_insert(tb, oldentry->blockno, &found); + if (found) + elog(ERROR, "duplicate during resizing"); + + memcpy(newentry, oldentry, sizeof(PagetableEntry)); + } + } + + pfree(olddata); + tb->resizing = false; + tb->deleted = 0; +} + +static PagetableEntry * +simplehash_insert(simplehash *tb, BlockNumber key, bool *found) +{ + uint32 hash = hash_blockno(key); + uint32 startelem; + uint32 curelem; + +restart: + startelem = hash & (tb->size - 1); + curelem = startelem; + + /* 10% toombstones */ + if (!tb->resizing && + tb->deleted * 10 >= tb->size) + { + elog(LOG, "compacting"); + simplehash_resize(tb, tb->size); + } + + while(true) + { + PagetableEntry *entry = &tb->data[curelem]; + + if (entry->status == 0) + { + /* resize at 75% */ + if (!tb->resizing && + ((tb->members + 1) * 4 > tb->size * 3)) + { + simplehash_resize(tb, tb->size * 2); + + /* start again */ + goto restart; + } + + tb->members++; + *found = false; + entry->blockno = key; + entry->status = 1; + return entry; + } + else if (entry->status == 2) + { + /* deleted entry, unusable without checking later keys */ + } + else if (entry->blockno == key) + { + Assert(entry->status == 1); + *found = true; + return entry; + } + + curelem++; + + if (curelem == startelem) + { + elog(ERROR, "full?"); + } + else if (curelem >= tb->size) + { + curelem = 0; + } + } +} + + +static PagetableEntry * +simplehash_lookup(simplehash *tb, BlockNumber key) +{ + uint32 hash = hash_blockno(key); + const uint32 startelem = hash & (tb->size - 1); + uint32 curelem = startelem; + + while(true) + { + PagetableEntry *entry = &tb->data[curelem]; + + if (entry->status == 0) + { + return NULL; + } + + if (entry->status == 1 && entry->blockno == key) + { + return entry; + } + + curelem++; + + if (curelem == startelem) + { + elog(LOG, "lookup wrapped"); + /* XXX: shouldn't, ever happen, no? */ + return NULL; + } + else if (curelem >= tb->size) + { + curelem = 0; + } + } +} + +static bool +simplehash_delete(simplehash *tb, BlockNumber key) +{ + uint32 hash = hash_blockno(key); + uint32 startelem = hash & (tb->size - 1); + uint32 curelem = startelem; + + while(true) + { + PagetableEntry *entry = &tb->data[curelem]; + + if (entry->status == 0) + return false; + + if (entry->status == 1 + && entry->blockno == key) + { + /* + * XXX: Moving neighbouring entries would likely be the better + * implementation. + */ + entry->status = 2; + tb->members--; + tb->deleted++; + + return true; + } + + curelem++; + + if (curelem == startelem) + { + /* XXX: shouldn't, ever happen, no? */ + elog(LOG, "delete wrapped"); + return false; + } + else if (curelem >= tb->size) + { + curelem = 0; + } + } +} + /* * tbm_create - create an initially-empty bitmap @@ -212,9 +445,13 @@ tbm_create(long maxbytes) static void tbm_create_pagetable(TIDBitmap *tbm) { +#ifndef USE_SIMPLEHASH HASHCTL hash_ctl; +#endif Assert(tbm->status != TBM_HASH); + +#ifndef USE_SIMPLEHASH Assert(tbm->pagetable == NULL); /* Create the hashtable proper */ @@ -239,6 +476,25 @@ tbm_create_pagetable(TIDBitmap *tbm) Assert(!found); memcpy(page, &tbm->entry1, sizeof(PagetableEntry)); } +#else + Assert(tbm->pagetable2 == NULL); + tbm->pagetable2 = simplehash_create(tbm->mcxt, 128); + + if (tbm->status == TBM_ONE_PAGE) + { + PagetableEntry *page; + bool found; + char oldstatus; + + page = simplehash_insert(tbm->pagetable2, + tbm->entry1.blockno, + &found); + Assert(!found); + oldstatus = page->status; + memcpy(page, &tbm->entry1, sizeof(PagetableEntry)); + page->status = oldstatus; + } +#endif tbm->status = TBM_HASH; } @@ -249,8 +505,13 @@ tbm_create_pagetable(TIDBitmap *tbm) void tbm_free(TIDBitmap *tbm) { +#ifndef USE_SIMPLEHASH if (tbm->pagetable) hash_destroy(tbm->pagetable); +#else + if (tbm->pagetable2) + simplehash_destroy(tbm->pagetable2); +#endif if (tbm->spages) pfree(tbm->spages); if (tbm->schunks) @@ -357,13 +618,27 @@ tbm_union(TIDBitmap *a, const TIDBitmap *b) tbm_union_page(a, &b->entry1); else { +#ifndef USE_SIMPLEHASH HASH_SEQ_STATUS status; +#else + int i; +#endif PagetableEntry *bpage; Assert(b->status == TBM_HASH); +#ifndef USE_SIMPLEHASH hash_seq_init(&status, b->pagetable); while ((bpage = (PagetableEntry *) hash_seq_search(&status)) != NULL) tbm_union_page(a, bpage); +#else + for (i = 0; i < b->pagetable2->size; i++) + { + bpage = &b->pagetable2->data[i]; + if (bpage->status != 1) + continue; + tbm_union_page(a, bpage); + } +#endif } } @@ -449,13 +724,26 @@ tbm_intersect(TIDBitmap *a, const TIDBitmap *b) } else { +#ifndef USE_SIMPLEHASH HASH_SEQ_STATUS status; +#else + int i; +#endif PagetableEntry *apage; Assert(a->status == TBM_HASH); +#ifndef USE_SIMPLEHASH hash_seq_init(&status, a->pagetable); while ((apage = (PagetableEntry *) hash_seq_search(&status)) != NULL) +#else + for (i = 0; i < a->pagetable2->size; i++) +#endif { +#ifdef USE_SIMPLEHASH + apage = &a->pagetable2->data[i]; + if (apage->status != 1) + continue; +#endif if (tbm_intersect_page(a, apage, b)) { /* Page or chunk is now empty, remove it from a */ @@ -464,10 +752,15 @@ tbm_intersect(TIDBitmap *a, const TIDBitmap *b) else a->npages--; a->nentries--; +#ifndef USE_SIMPLEHASH if (hash_search(a->pagetable, (void *) &apage->blockno, HASH_REMOVE, NULL) == NULL) elog(ERROR, "hash table corrupted"); +#else + if (!simplehash_delete(a->pagetable2, apage->blockno)) + elog(ERROR, "hash table corrupted"); +#endif } } } @@ -606,7 +899,11 @@ tbm_begin_iterate(TIDBitmap *tbm) */ if (tbm->status == TBM_HASH && !tbm->iterating) { +#ifndef USE_SIMPLEHASH HASH_SEQ_STATUS status; +#else + int i; +#endif PagetableEntry *page; int npages; int nchunks; @@ -620,10 +917,19 @@ tbm_begin_iterate(TIDBitmap *tbm) MemoryContextAlloc(tbm->mcxt, tbm->nchunks * sizeof(PagetableEntry *)); - hash_seq_init(&status, tbm->pagetable); npages = nchunks = 0; +#ifndef USE_SIMPLEHASH + hash_seq_init(&status, tbm->pagetable); while ((page = (PagetableEntry *) hash_seq_search(&status)) != NULL) +#else + for (i = 0; i < tbm->pagetable2->size; i++) +#endif { +#ifdef USE_SIMPLEHASH + page = &tbm->pagetable2->data[i]; + if (page->status != 1) + continue; +#endif if (page->ischunk) tbm->schunks[nchunks++] = page; else @@ -791,9 +1097,13 @@ tbm_find_pageentry(const TIDBitmap *tbm, BlockNumber pageno) return page; } +#ifndef USE_SIMPLEHASH page = (PagetableEntry *) hash_search(tbm->pagetable, (void *) &pageno, HASH_FIND, NULL); +#else + page = simplehash_lookup(tbm->pagetable2, pageno); +#endif if (page == NULL) return NULL; if (page->ischunk) @@ -833,16 +1143,22 @@ tbm_get_pageentry(TIDBitmap *tbm, BlockNumber pageno) tbm_create_pagetable(tbm); } +#ifndef USE_SIMPLEHASH /* Look up or create an entry */ page = (PagetableEntry *) hash_search(tbm->pagetable, (void *) &pageno, HASH_ENTER, &found); +#else + page = simplehash_insert(tbm->pagetable2, pageno, &found); +#endif } /* Initialize it if not present before */ if (!found) { + char oldstatus = page->status; MemSet(page, 0, sizeof(PagetableEntry)); + page->status = oldstatus; page->blockno = pageno; /* must count it too */ tbm->nentries++; @@ -869,9 +1185,15 @@ tbm_page_is_lossy(const TIDBitmap *tbm, BlockNumber pageno) bitno = pageno % PAGES_PER_CHUNK; chunk_pageno = pageno - bitno; + +#ifndef USE_SIMPLEHASH page = (PagetableEntry *) hash_search(tbm->pagetable, (void *) &chunk_pageno, HASH_FIND, NULL); +#else + page = simplehash_lookup(tbm->pagetable2, chunk_pageno); +#endif + if (page != NULL && page->ischunk) { int wordnum = WORDNUM(bitno); @@ -912,6 +1234,7 @@ tbm_mark_page_lossy(TIDBitmap *tbm, BlockNumber pageno) */ if (bitno != 0) { +#ifndef USE_SIMPLEHASH if (hash_search(tbm->pagetable, (void *) &pageno, HASH_REMOVE, NULL) != NULL) @@ -920,17 +1243,30 @@ tbm_mark_page_lossy(TIDBitmap *tbm, BlockNumber pageno) tbm->nentries--; tbm->npages--; /* assume it must have been non-lossy */ } +#else + if (simplehash_delete(tbm->pagetable2, pageno)) + { + /* It was present, so adjust counts */ + tbm->nentries--; + tbm->npages--; /* assume it must have been non-lossy */ + } +#endif } +#ifndef USE_SIMPLEHASH /* Look up or create entry for chunk-header page */ page = (PagetableEntry *) hash_search(tbm->pagetable, (void *) &chunk_pageno, HASH_ENTER, &found); - +#else + page = simplehash_insert(tbm->pagetable2, chunk_pageno, &found); +#endif /* Initialize it if not present before */ if (!found) { + char oldstatus = page->status; MemSet(page, 0, sizeof(PagetableEntry)); + page->status = oldstatus; page->blockno = chunk_pageno; page->ischunk = true; /* must count it too */ @@ -939,8 +1275,10 @@ tbm_mark_page_lossy(TIDBitmap *tbm, BlockNumber pageno) } else if (!page->ischunk) { + char oldstatus = page->status; /* chunk header page was formerly non-lossy, make it lossy */ MemSet(page, 0, sizeof(PagetableEntry)); + page->status = oldstatus; page->blockno = chunk_pageno; page->ischunk = true; /* we assume it had some tuple bit(s) set, so mark it lossy */ @@ -962,7 +1300,11 @@ tbm_mark_page_lossy(TIDBitmap *tbm, BlockNumber pageno) static void tbm_lossify(TIDBitmap *tbm) { +#ifndef USE_SIMPLEHASH HASH_SEQ_STATUS status; +#else + int i; +#endif PagetableEntry *page; /* @@ -977,9 +1319,18 @@ tbm_lossify(TIDBitmap *tbm) Assert(!tbm->iterating); Assert(tbm->status == TBM_HASH); +#ifndef USE_SIMPLEHASH hash_seq_init(&status, tbm->pagetable); while ((page = (PagetableEntry *) hash_seq_search(&status)) != NULL) +#else + for (i = 0; i < tbm->pagetable2->size; i++) +#endif { +#ifdef USE_SIMPLEHASH + page = &tbm->pagetable2->data[i]; + if (page->status != 1) + continue; +#endif if (page->ischunk) continue; /* already a chunk header */ @@ -996,7 +1347,9 @@ tbm_lossify(TIDBitmap *tbm) if (tbm->nentries <= tbm->maxentries / 2) { /* we have done enough */ +#ifndef USE_SIMPLEHASH hash_seq_term(&status); +#endif break; } -- 2.8.1
-- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers