On Wed, Jul 17, 2019 at 3:37 AM Andres Freund <and...@anarazel.de> wrote:
>
> Hi,
>
> On 2019-07-13 15:55:51 +0530, Amit Kapila wrote:
> > On Fri, Jul 12, 2019 at 7:08 PM Robert Haas <robertmh...@gmail.com> wrote:
> > > > I think even if we currently go with a binary heap, it will be
> > > > possible to change it to rbtree later, but I am fine either way.
> > >
> > > Well, I don't see much point in revising all of this logic twice. We
> > > should pick the way we want it to work and make it work that way.
> > >
> >
> > Yeah, I agree. So, I am assuming here that as you have discussed this
> > idea with Andres offlist, he is on board with changing it as he has
> > originally suggested using binary_heap. Andres, do let us know if you
> > think differently here. It would be good if anyone else following the
> > thread can also weigh in.
>
> Yes, I think using an rbtree makes sense.
>
Okay.
> I'm not yet sure whether we'd want the rbtree nodes being pointed to
> directly by the hashtable, or whether we'd want one indirection.
>
> e.g. either something like:
>
>
> typedef struct UndoWorkerQueue
> {
> /* priority ordered tree */
> RBTree *tree;
> ....
> }
>
I think we also need the size of rbtree (aka how many nodes/undo
requests it has) to know whether we can add more. This information is
available in binary heap, but here I think we need to track it in
UndoWorkerQueue. Basically, at each enqueue/dequeue, we need to
increment/decrement the same.
> typedef struct UndoWorkerQueueEntry
> {
> RBTNode tree_node;
>
> /*
> * Reference hashtable via key, not pointers, entries might be
> * moved.
> */
> RollbackHashKey rollback_key
> ...
> } UndoWorkerQueueEntry;
>
In UndoWorkerQueueEntry, we might also want to include some other info
like dbid, request_size, next_retry_at, err_occurred_at so that while
accessing queue entry in comparator functions or other times, we don't
always need to perform hash table search. OTOH, we can do hash_search
as well, but may be code-wise it will be better to keep additional
information.
Another thing is we need some freelist/array for
UndoWorkerQueueEntries equivalent to size of three queues?
> typedef struct RollbackHashEntry
> {
> ...
> UndoWorkerQueueEntry *queue_memb_size;
> UndoWorkerQueueEntry *queue_memb_age;
> UndoWorkerQueueEntry *queue_memb_error;
> }
>
> and call rbt_delete() for any non-NULL queue_memb_* whenever an entry is
> dequeued via one of the queues (after setting the one already dequeued
> from to NULL, of course). Which requires - as Robert mentioned - that
> rbtree pointers remain stable after insertions.
>
Right.
BTW, do you have any preference for using dynahash or simplehash for
RollbackHashTable?
>
> Alternatively we can have a more complicated arrangement without the
> "stable pointer" requirement (which'd also similarly work for a binary
> heap):
>
>
> I think the first approach is clearly preferrable from a simplicity POV,
> but the second approach would be a bit more generic (applicable to heap
> as well) and wouldn't require adjusting the rbtree code.
>
+1 for the first approach, the second one appears to be quite
complicated as compared to first.
--
With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com
