RE: Improve eviction algorithm in ReorderBuffer - Mailing list pgsql-hackers

Dear Sawada-san,

I have started to read your patches. Here are my initial comments.
At least, all subscription tests were passed on my env.

A comment for 0001:

01.
```
+static void
+bh_enlarge_node_array(binaryheap *heap)
+{
+    if (heap->bh_size < heap->bh_space)
+        return;
+
+    heap->bh_space *= 2;
+    heap->bh_nodes = repalloc(heap->bh_nodes,
+                              sizeof(bh_node_type) * heap->bh_space);
+}
```

I'm not sure it is OK to use repalloc() for enlarging bh_nodes. This data
structure public one and arbitrary codes and extensions can directly refer
bh_nodes. But if the array is repalloc()'d, the pointer would be updated so that
their referring would be a dangling pointer.
I think the internal of the structure should be a private one in this case.

Comments for 0002:

02.
```
+#include "utils/palloc.h"
```

Is it really needed? I'm not sure who referrs it.

03.
```
typedef struct bh_nodeidx_entry
{
    bh_node_type    key;
    char            status;
    int                idx;
} bh_nodeidx_entry;
```

Sorry if it is a stupid question. Can you tell me how "status" is used?
None of binaryheap and reorderbuffer components refer it. 

04.
```
 extern binaryheap *binaryheap_allocate(int capacity,
                                        binaryheap_comparator compare,
-                                       void *arg);
+                                       bool indexed, void *arg);
```

I felt pre-existing API should not be changed. How about adding
binaryheap_allocate_extended() or something which can specify the `bool indexed`?
binaryheap_allocate() sets heap->bh_indexed to false.

05.
```
+extern void binaryheap_update_up(binaryheap *heap, bh_node_type d);
+extern void binaryheap_update_down(binaryheap *heap, bh_node_type d);
```

IIUC, callers must consider whether the node should be shift up/down and use
appropriate function, right? I felt it may not be user-friendly.

Comments for 0003:

06.
```
    This commit changes the eviction algorithm in ReorderBuffer to use
    max-heap with transaction size,a nd use two strategies depending on
    the number of transactions being decoded.
```

s/a nd/ and/

07.
```
    It could be too expensive to pudate max-heap while preserving the heap
    property each time the transaction's memory counter is updated, as it
    could happen very frquently. So when the number of transactions being
    decoded is small, we add the transactions to max-heap but don't
    preserve the heap property, which is O(1). We heapify the max-heap
    just before picking the largest transaction, which is O(n). This
    strategy minimizes the overheads of updating the transaction's memory
    counter.
```

s/pudate/update/

08.
IIUC, if more than 1024 transactions are running but they have small amount of
changes, the performance may be degraded, right? Do you have a result in sucha
a case?

Best Regards,
Hayato Kuroda
FUJITSU LIMITED
https://www.fujitsu.com/