From: Jeff Davis <pgsql@j-davis.com>
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Cc: pgsql-hackers@postgresql.org
Subject: Re: Trouble with hashagg spill I/O pattern and costing
Date: Thu, 21 May 2020 14:16:37 -0700
Message-ID: <8619437df796903e64c8479e299d13ebacb5fbe0.camel@j-davis.com> (raw)
In-Reply-To: <20200521191318.gw3xjivrxracvzmg@development>
References: <20200519151202.u2p2gpiawoaznsv2@development>
<88dd39d782178539d7ee46f98b98579940e2a12e.camel@j-davis.com>
<20200519175320.tl4qm6le5dbg2pcf@development>
<acad6f2ba8d560b9dfa9a564c7b7d3162abf8347.camel@j-davis.com>
<20200521191318.gw3xjivrxracvzmg@development>
On Thu, 2020-05-21 at 21:13 +0200, Tomas Vondra wrote:
> 2) We could make it self-tuning, by increasing the number of blocks
> we pre-allocate. So every time we exhaust the range, we double the
> number of blocks (with a reasonable maximum, like 1024 or so). Or we
> might just increment it by 32, or something.
Attached a new version that uses the doubling behavior, and cleans it
up a bit. It also returns the unused prealloc blocks back to lts-
>freeBlocks when the tape is rewound for reading.
> IIUC the danger of pre-allocating blocks is that we might not fill
> them,
> resulting in temp file much larger than necessary. It might be
> harmless
> on some (most?) current filesystems that don't actually allocate
> space
> for blocks that are never written, but it also confuses our
> accounting
> of temporary file sizes. So we should try to limit that, and growing
> the
> number of pre-allocated blocks over time seems reasonable.
There's another danger here: it doesn't matter how well the filesystem
deals with sparse writes, because ltsWriteBlock fills in the holes with
zeros anyway. That's potentially a significant amount of wasted IO
effort if we aren't careful.
Regards,
Jeff Davis
Attachments:
[text/x-patch] logtape-prealloc-v2.patch (4.8K, ../8619437df796903e64c8479e299d13ebacb5fbe0.camel@j-davis.com/2-logtape-prealloc-v2.patch)
download | inline diff:diff --git a/src/backend/utils/sort/logtape.c b/src/backend/utils/sort/logtape.cindex bc8d56807e2..84f9d6d2358 100644--- a/src/backend/utils/sort/logtape.c+++ b/src/backend/utils/sort/logtape.c@@ -110,6 +110,8 @@ typedef struct TapeBlockTrailer
#define TapeBlockSetNBytes(buf, nbytes) \
(TapeBlockGetTrailer(buf)->next = -(nbytes))
+#define TAPE_WRITE_PREALLOC_MIN 8+#define TAPE_WRITE_PREALLOC_MAX 128
/*
* This data structure represents a single "logical tape" within the set
@@ -151,6 +153,21 @@ typedef struct LogicalTape
int max_size; /* highest useful, safe buffer_size */
int pos; /* next read/write position in buffer */
int nbytes; /* total # of valid bytes in buffer */
++ /*+ * When multiple tapes are being written to concurrently (as in HashAgg),+ * avoid excessive fragmentation by preallocating block numbers to+ * individual tapes. The preallocated block numbers are held in an array+ * sorted in descending order; blocks are consumed from the end of the+ * array (lowest block numbers first).+ *+ * No filesystem operations are performed for preallocation; only the+ * block numbers are reserved. This may lead to sparse writes, which will+ * cause ltsWriteBlock() to fill in holes with zeros.+ */+ long *prealloc;+ int nprealloc; /* number of elements in list */+ int prealloc_size; /* number of elements list can hold */
} LogicalTape;
/*
@@ -198,6 +215,7 @@ struct LogicalTapeSet
static void ltsWriteBlock(LogicalTapeSet *lts, long blocknum, void *buffer);
static void ltsReadBlock(LogicalTapeSet *lts, long blocknum, void *buffer);
static long ltsGetFreeBlock(LogicalTapeSet *lts);
+static long ltsGetPreallocBlock(LogicalTapeSet *lts, LogicalTape *lt);
static void ltsReleaseBlock(LogicalTapeSet *lts, long blocknum);
static void ltsConcatWorkerTapes(LogicalTapeSet *lts, TapeShare *shared,
SharedFileSet *fileset);
@@ -397,6 +415,51 @@ ltsGetFreeBlock(LogicalTapeSet *lts)
return blocknum;
}
+/*+ * Return the lowest free block number from the tape's preallocation list.+ * Refill the preallocation list if necessary.+ */+static long+ltsGetPreallocBlock(LogicalTapeSet *lts, LogicalTape *lt)+{+ /* sorted in descending order, so return the last element */+ if (lt->nprealloc > 0)+ return lt->prealloc[--lt->nprealloc];++ if (lt->prealloc == NULL)+ {+ lt->prealloc_size = TAPE_WRITE_PREALLOC_MIN;+ lt->prealloc = (long *) palloc(sizeof(long) * lt->prealloc_size);+ }+ else+ {+ /* when the preallocation list runs out, double the size */+ if (lt->prealloc_size * 2 <= TAPE_WRITE_PREALLOC_MAX)+ lt->prealloc_size *= 2;+ lt->prealloc = (long *) repalloc(lt->prealloc,+ sizeof(long) * lt->prealloc_size);+ }++ /* refill preallocation list */+ lt->nprealloc = lt->prealloc_size;+ for (int i = lt->nprealloc; i > 0; i--)+ lt->prealloc[i - 1] = ltsGetFreeBlock(lts);++#ifdef USE_ASSERT_CHECKING+ {+ /* verify that list is in reverse sorted order */+ long last_block_number = -1;+ for (int i = lt->nprealloc; i > 0; i--)+ {+ Assert(lt->prealloc[i - 1] > last_block_number);+ last_block_number = lt->prealloc[i - 1];+ }+ }+#endif++ return lt->prealloc[--lt->nprealloc];+}+
/*
* Return a block# to the freelist.
*/
@@ -557,6 +620,9 @@ ltsInitTape(LogicalTape *lt)
lt->max_size = MaxAllocSize;
lt->pos = 0;
lt->nbytes = 0;
+ lt->prealloc = NULL;+ lt->nprealloc = 0;+ lt->prealloc_size = 0;
}
/*
@@ -709,7 +775,7 @@ LogicalTapeWrite(LogicalTapeSet *lts, int tapenum,
Assert(lt->firstBlockNumber == -1);
Assert(lt->pos == 0);
- lt->curBlockNumber = ltsGetFreeBlock(lts);+ lt->curBlockNumber = ltsGetPreallocBlock(lts, lt);
lt->firstBlockNumber = lt->curBlockNumber;
TapeBlockGetTrailer(lt->buffer)->prev = -1L;
@@ -733,7 +799,7 @@ LogicalTapeWrite(LogicalTapeSet *lts, int tapenum,
* First allocate the next block, so that we can store it in the
* 'next' pointer of this block.
*/
- nextBlockNumber = ltsGetFreeBlock(lts);+ nextBlockNumber = ltsGetPreallocBlock(lts, lt);
/* set the next-pointer and dump the current block. */
TapeBlockGetTrailer(lt->buffer)->next = nextBlockNumber;
@@ -835,13 +901,23 @@ LogicalTapeRewindForRead(LogicalTapeSet *lts, int tapenum, size_t buffer_size)
Assert(lt->frozen);
}
- /* Allocate a read buffer (unless the tape is empty) */
if (lt->buffer)
pfree(lt->buffer);
/* the buffer is lazily allocated, but set the size here */
lt->buffer = NULL;
lt->buffer_size = buffer_size;
++ /* free the preallocation list, and return unused block numbers */+ if (lt->prealloc != NULL)+ {+ for (int i = lt->nprealloc; i > 0; i--)+ ltsReleaseBlock(lts, lt->prealloc[i - 1]);+ pfree(lt->prealloc);+ lt->prealloc = NULL;+ lt->nprealloc = 0;+ lt->prealloc_size = 0;+ }
}
/*
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: pgsql@j-davis.com, tomas.vondra@2ndquadrant.com
Subject: Re: Trouble with hashagg spill I/O pattern and costing
In-Reply-To: <8619437df796903e64c8479e299d13ebacb5fbe0.camel@j-davis.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox