Re: use radix tree for bitmap heap scan

>> I'm not familiar with the radix tree code, but why does specifically
>> intersection need deletion?
>
> Currently, tbm_intersect_page() already reports that a page can be
> deleted so that the caller can delete it, so I was just continuing
> that practice.

It seems like some of the TIDBitmap operations might be better
implemented differently on top of a radix tree. For example union and
intersection could profit from iterating both trees to compute the
intersection / union in the spirit of a merge sort.

But I can see the appeal to make TIDBitmap first work as is on top of
the radix tree, as long as it doesn't put hard-to-implement requirements
on the radix tree.

> BTW, my local branch has deletion-during-iteration working, and it's
> not too ugly.

Nice!

>> Before spending more time on getting the details right, I would be
>> interested in some performance numbers about raw insert / construction
>> performance without lossification. Saving the sort (which is parallel
>> with [1]) and being better in the lossy-case is great but only as long
>> as we don't regress the common case.
>
> Already on my get-back-to list, maybe in November. (note for would-be
> volunteers: the latest patch in this thread is _not_ ready for
> testing.)

I'm ready to help, once you have a patch that is ready for testing. Let
me know.

>> One more property of the hash map based TIDBitmap to consider is its
>> incremental growth:
>>
>> So I'm wondering: what is the (re-)allocation pattern of the radix tree?
>> Is it incrementally resized, e.g. node by node? If so, the amortized
>> insertion cost might be lower than we think with increasing number of TIDs.
>>
>> This is because today, a major cost of large BitmapIndexScans is
>> repeatedly growing the simplehash.h-based hash table backing TIDBitmap
>> from initially 128 elements to its final size.
>
> How much of a major cost?

The "actual time" of the BIS in my test query dropped from 193 ms to 139
ms when reserving all memory of the final hash table upfront by passing
its final size to pagetable_create() in tbm_create_pagetable().

Part of that time is spent on page faults because the allocations are
big enough for ASET to call malloc() and for malloc() to call sbrk(),
and then in the other direction for free() to call systrim() which calls
sbrk() to shrink the heap again.

This can be seen also from the perf stat output:

3,034 page-faults # 5114.8 faults/sec page_faults_per_second

vs when reserving enough memory to avoid resizing

0 page-faults # 0.0 faults/sec page_faults_per_second

I'm not entirely sure why it has 0 page faults for successive calls when
I reserve a big hash table. It should still have to fault when writing
to the pages of the initially reserved hash map. It seems to cache the
allocation somehow as I no longer see calls to sbrk().

My take away beyond the radix tree effort is that it would be useful if
we could allocate anonymous and shared memory backed by 2 MiB huge
pages. That would help for TIDBitmap but also for large sort buffers or
large hash join hash tables. Shared allocations can end up in the main
memory segment if dynamic_shared_memory_size is picked appropriately
but, FWIR, anonymous memory is always 4k-backed.

> Related: I do suspect the lossification threshold is broken: With 4MB
> work_mem, the hash table grows from 3MB to 6MB, but the max entries
> number is computed from 4MB (accounting for the iteration arrays), so
> I believe (but haven't verified) that it starts lossifying when the
> hash table is not even close to full. But if we tried to account for
> that somehow, then we still risk the table growing from 6MB to 12MB
> because of the linear probe length threshold. That is to say, yes,
> there are multiple reasons to switch to radix tree if the challenges
> can be overcome, and I think they can.
Ahh, that's a good one. It makes sense because max entries is not
updated when simplehash.h grows. Then the lossification will start too
early.

What would be useful is a list of shortcomings of simplehash.h-based
TIDBitmap and how the radix tree would overcome those. It doesn't have
to complete but I feel like I'm not having the whole picture. We could
then see if there are more areas where a radix tree would help (e.g. how
certain TBMBitmap operations are implemented, etc.).

--
David Geier