Re: Improve eviction algorithm in ReorderBuffer

Hi, here are some review comments for v7-0002

======
Commit Message

1.
This commit adds a hash table to binaryheap in order to track of
positions of each nodes in the binaryheap. That way, by using newly
added functions such as binaryheap_update_up() etc., both updating a
key and removing a node can be done in O(1) on an average and O(log n)
in worst case. This is known as the indexed binary heap. The caller
can specify to use the indexed binaryheap by passing indexed = true.

~

/to track of positions of each nodes/to track the position of each node/

~~~

2.
There is no user of it but it will be used by a upcoming patch.

~

The current code does not use the new indexing logic, but it will be
used by an upcoming patch.

======
src/common/binaryheap.c

3.
+/*
+ * Define parameters for hash table code generation. The interface is *also*"
+ * declared in binaryheaph.h (to generate the types, which are externally
+ * visible).
+ */

Typo: *also*"

~~~

4.
+#define SH_PREFIX bh_nodeidx
+#define SH_ELEMENT_TYPE bh_nodeidx_entry
+#define SH_KEY_TYPE bh_node_type
+#define SH_KEY key
+#define SH_HASH_KEY(tb, key) \
+ hash_bytes((const unsigned char *) &key, sizeof(bh_node_type))
+#define SH_EQUAL(tb, a, b) (memcmp(&a, &b, sizeof(bh_node_type)) == 0)
+#define SH_SCOPE extern
+#ifdef FRONTEND
+#define SH_RAW_ALLOCATOR pg_malloc0
+#endif
+#define SH_DEFINE
+#include "lib/simplehash.h"

4a.
The comment in simplehash.h says
 *   The following parameters are only relevant when SH_DEFINE is defined:
 *   - SH_KEY - ...
 *   - SH_EQUAL(table, a, b) - ...
 *   - SH_HASH_KEY(table, key) - ...
 *   - SH_STORE_HASH - ...
 *   - SH_GET_HASH(tb, a) - ...

So maybe it is nicer to reorder the #defines in that same order?

SUGGESTION:
+#define SH_PREFIX bh_nodeidx
+#define SH_ELEMENT_TYPE bh_nodeidx_entry
+#define SH_KEY_TYPE bh_node_type
+#define SH_SCOPE extern
+#ifdef FRONTEND
+#define SH_RAW_ALLOCATOR pg_malloc0
+#endif

+#define SH_DEFINE
+#define SH_KEY key
+#define SH_EQUAL(tb, a, b) (memcmp(&a, &b, sizeof(bh_node_type)) == 0)
+#define SH_HASH_KEY(tb, key) \
+ hash_bytes((const unsigned char *) &key, sizeof(bh_node_type))
+#include "lib/simplehash.h"

~~

4b.
The comment in simplehash.h says that "it's preferable, if possible,
to store the element's hash in the element's data type", so should
SH_STORE_HASH and SH_GET_HASH also be defined here?

~~~

5.
+ *
+ * If 'indexed' is true, we create a hash table to track of each node's
+ * index in the heap, enabling to perform some operations such as removing
+ * the node from the heap.
  */
 binaryheap *
-binaryheap_allocate(int capacity, binaryheap_comparator compare, void *arg)
+binaryheap_allocate(int capacity, binaryheap_comparator compare,
+ bool indexed, void *arg)

BEFORE
... enabling to perform some operations such as removing the node from the heap.

SUGGESTION
... to help make operations such as removing nodes more efficient.

~~~

6.
+ heap->bh_indexed = indexed;
+ if (heap->bh_indexed)
+ {
+#ifdef FRONTEND
+ heap->bh_nodeidx = bh_nodeidx_create(capacity, NULL);
+#else
+ heap->bh_nodeidx = bh_nodeidx_create(CurrentMemoryContext, capacity,
+ NULL);
+#endif
+ }
+

The heap allocation just uses palloc instead of palloc0 so it might be
better to assign "heap->bh_nodeidx = NULL;" up-front, just so you will
never get a situation where bh_indexed is false but bh_nodeidx has
some (garbage) value.

~~~

7.
+/*
+ * Set the given node at the 'index', and updates its position accordingly.
+ *
+ * Return true if the node's index is already tracked.
+ */
+static bool
+bh_set_node(binaryheap *heap, bh_node_type node, int index)

7a.
I felt the 1st sentence should be more like:

SUGGESTION
Set the given node at the 'index' and track it if required.

~

7b.
IMO the parameters would be better the other way around (e.g. 'index'
before the 'node') because that's what the assignments look like:


heap->bh_nodes[heap->bh_size] = d;

becomes:
bh_set_node(heap, heap->bh_size, d);

~~~

8.
+static bool
+bh_set_node(binaryheap *heap, bh_node_type node, int index)
+{
+ bh_nodeidx_entry *ent;
+ bool found = false;
+
+ /* Set the node to the nodes array */
+ heap->bh_nodes[index] = node;
+
+ if (heap->bh_indexed)
+ {
+ /* Remember its index in the nodes array */
+ ent = bh_nodeidx_insert(heap->bh_nodeidx, node, &found);
+ ent->idx = index;
+ }
+
+ return found;
+}

8a.
That 'ent' declaration can be moved to the inner block scope, so it is
closer to where it is needed.

~

8b.
+ /* Remember its index in the nodes array */

The comment is worded a bit ambiguously. IMO a simpler comment would
be: "/* Keep track of the node index. */"

~~~

9.
+static void
+bh_delete_nodeidx(binaryheap *heap, bh_node_type node)
+{
+ if (!heap->bh_indexed)
+ return;
+
+ (void) bh_nodeidx_delete(heap->bh_nodeidx, node);
+}

Since there is only 1 statement IMO it is simpler to write this
function like below:

if (heap->bh_indexed)
  (void) bh_nodeidx_delete(heap->bh_nodeidx, node);

~~~

10.
+/*
+ * Replace the node at 'idx' with the given node 'replaced_by'. Also
+ * update their positions accordingly.
+ */
+static void
+bh_replace_node(binaryheap *heap, int idx, bh_node_type replaced_by)

10a.
Would 'node' or 'new_node' or 'replacement' be a better name than 'replaced_by'?

~

10b.
I noticed that the index param is called 'idx' here but in other
functions, it is called 'index'. I think either is good (I prefer
'idx') but at least everywhere should use the same name for
consistency.

~~~

11.
+static void
+bh_replace_node(binaryheap *heap, int idx, bh_node_type replaced_by)
+{
+ /* Remove overwritten node's index */
+ bh_delete_nodeidx(heap, heap->bh_nodes[idx]);
+
+ /* Replace it with the given new node */
+ if (idx < heap->bh_size)
+ {
+ bool found PG_USED_FOR_ASSERTS_ONLY;
+
+ found = bh_set_node(heap, replaced_by, idx);
+
+ /* The overwritten node's index must already be tracked */
+ Assert(!heap->bh_indexed || found);
+ }
+}

I did not understand the condition.
e.g. Can you explain when is idx NOT less than heap->bh_size?
e.g. If this condition failed then nothing gets replaced (??)

~~~

======
src/include/lib/binaryheap.h

12.
+/*
+ * Struct for A hash table element to store the node's index in the bh_nodes
+ * array.
+ */
+typedef struct bh_nodeidx_entry

/for A hash table/for a hash table/

~~~

13.
+/* define parameters necessary to generate the hash table interface */

Suggest uppercase "Define" and add a period.

~~~

14.
+
+ /*
+ * If bh_indexed is true, the bh_nodeidx is used to track of each node's
+ * index in bh_nodes. This enables the caller to perform
+ * binaryheap_remove_node_ptr(), binaryheap_update_up/down in O(log n).
+ */
+ bool bh_indexed;
+ bh_nodeidx_hash *bh_nodeidx;
 } binaryheap;

I'm wondering why the separate 'bh_indexed' is necessary at all. Can't
you just use the bh_nodeidx value? E.g. If bh_nodeidx == NULL then it
means there is no index tracking, otherwise there is.

----------
Kind Regards,
Peter Smith.
Fujitsu Australia