Subject: [pgjdbc/pgjdbc] PR #3249: perf: optimize Set<Integer> which are used for checking if oid should be transferred with binary or text

From: "vlsi (@vlsi)" <[email-masked]>
Date: Sun, 19 May 2024 18:07:57 +0000

It looks like BitSet is faster than HashSet, so let's use it.

Unfortunately, BitSet would consume memory in case the Oid value is high, and Oids can be up to 32bit, so we limit the max OID stored in a BitSet with 8192*8, so we effectively limit the extra per-connection memory by 16KiB (8KiB for send and 8KiB for receive)

The current maximum id is 2950 (UUID), so the added overhead is about 800 bytes per connection.

Here are benchmark results with Apple M1 Max, Java 17.0.10 ARM64.

The diff is about 1ns per operation (I guess it is negligible), however, the fix makes "useBinaryForSend" disappear from async profiler results, so it might be a net win. It would be great to make an end-to-end measurement somehow (e.g. CPU% for the app)

23 is present in the set, 73 and 123456 are both absent.

```
<pre>
Benchmark                             (oid)  Mode  Cnt  Score   Error  Units
IntSetBenchmark.bitSet_contains          23  avgt   15  0,984 ± 0,009  ns/op
IntSetBenchmark.bitSet_contains          73  avgt   15  0,979 ± 0,005  ns/op
IntSetBenchmark.bitSet_contains      123456  avgt   15  0,688 ± 0,015  ns/op

IntSetBenchmark.hashSet_contains         23  avgt   15  2,026 ± 0,013  ns/op
IntSetBenchmark.hashSet_contains         73  avgt   15  1,985 ± 0,004  ns/op
IntSetBenchmark.hashSet_contains     123456  avgt   15  1,968 ± 0,032  ns/op

IntSetBenchmark.intSet_contains          23  avgt   15  1,101 ± 0,009  ns/op
IntSetBenchmark.intSet_contains          73  avgt   15  1,117 ± 0,005  ns/op
IntSetBenchmark.intSet_contains      123456  avgt   15  0,693 ± 0,010  ns/op

IntSetBenchmark.intOpenSet_contains      23  avgt   15  1,015 ± 0,011  ns/op
IntSetBenchmark.intOpenSet_contains      73  avgt   15  5,720 ± 0,596  ns/op
IntSetBenchmark.intOpenSet_contains  123456  avgt   15  8,430 ± 0,007  ns/op

IntSetBenchmark.roaring_contains         23  avgt   15  5,012 ± 0,044  ns/op
IntSetBenchmark.roaring_contains         73  avgt   15  5,561 ± 0,077  ns/op
IntSetBenchmark.roaring_contains     123456  avgt   15  1,163 ± 0,012  ns/op
```

/cc @plokhotnyuk

---

From: "davecramer (@davecramer)" <[email-masked]>
Date: Sun, 19 May 2024 20:39:24 +0000

I don't think limiting OID's to 32 bit is a good idea. There are more and more databases with very large schema's which would have considerably more OID's than 65k

---

From: "vlsi (@vlsi)" <[email-masked]>
Date: Sun, 19 May 2024 20:51:11 +0000

This PR does not limit ids, and 32bit is the protocol limit (~ 4,294,967,295 oids)

---

From: "davecramer (@davecramer)" <[email-masked]>
Date: Sun, 19 May 2024 21:18:07 +0000

> so we limit the max OID stored in a BitSet with 8192*8,

what does this mean ?

---

From: "bokken (@bokken)" <[email-masked]>
Date: Mon, 20 May 2024 00:33:56 +0000

(on pgjdbc/src/main/java/org/postgresql/util/internal/IntSet.java)

How often is asSet() actually called?
How often do expect to provide binary support for oids beyond 64k?

---

From: "bokken (@bokken)" <[email-masked]>
Date: Mon, 20 May 2024 00:35:44 +0000

Instead of this method, should IntSet implement Collection<Integer>?

---

From: "vlsi (@vlsi)" <[email-masked]>
Date: Mon, 20 May 2024 05:42:12 +0000

Implementing colection would complicate implementation and testing. At the same time, Collection requires boxing which we do not want

---

From: "plokhotnyuk (@plokhotnyuk)" <[email-masked]>
Date: Mon, 20 May 2024 06:08:08 +0000

Other options would be using or reimplantation of IntHashMap (from agrona or fastutil libraries) or RoaringBitmap (https://github.com/RoaringBitmap/RoaringBitmap).

---

From: "vlsi (@vlsi)" <[email-masked]>
Date: Mon, 20 May 2024 07:13:36 +0000

Both `RoaringBitmap` and `IntOpenHashSet` (`it.unimi.dsi:fastutil`) are somewhat slower for our use case.

---

From: "vlsi (@vlsi)" <[email-masked]>
Date: Mon, 20 May 2024 07:17:57 +0000

Well, in theory, `asSet()` is used only in deprecated method `org.postgresql.core.QueryExecutor#getBinaryReceiveOids` that is never used within the driver's code.

I guess we can make it less efficient, so we could store small values in `BitSet` and large values in `HashSet` at a cost of slower `asSet()`

---

From: "vlsi (@vlsi)" <[email-masked]>
Date: Mon, 20 May 2024 07:48:32 +0000

> so we limit the max OID stored in a BitSet with 8192*8,

It means we store small values in `BitSet` and large values (if any) in `HashSet`.

---

From: "vlsi (@vlsi)" <[email-masked]>
Date: Mon, 20 May 2024 07:54:34 +0000

>How often is asSet() actually called?

It is used in a deprecated method only, so it is there for backward compatibility. I am leaning towards we could make this method "arbitrary slow".

> How often do expect to provide binary support for oids beyond 64k?

We have a fixed set of types we currently enable for binary. The maximal one is `UUID` which is `2950`.
Users can add extra types with `binaryTransferEnable` connection property. I doubt they do so.

---

From: "plokhotnyuk (@plokhotnyuk)" <[email-masked]>
Date: Mon, 03 Jun 2024 11:06:26 +0000

@bokken Could you please review this PR to be merged and released in the next version?

---

From: "svendiedrichsen (@svendiedrichsen)" <[email-masked]>
Date: Tue, 18 Jun 2024 20:39:43 +0000

@vlsi Is there anyone else to review this? Would be great to have it in the next release.

---

From: "bokken (@bokken)" <[email-masked]>
Date: Wed, 19 Jun 2024 01:50:14 +0000

Final?

---

From: "bokken (@bokken)" <[email-masked]>
Date: Wed, 19 Jun 2024 01:51:18 +0000

(on pgjdbc/src/main/java/org/postgresql/util/internal/IntSet.java:51)

Perhaps a comment that null values are not supported.

---

From: "vlsi (@vlsi)" <[email-masked]>
Date: Sun, 23 Jun 2024 17:40:23 +0000

added `final`

---

From: "vlsi (@vlsi)" <[email-masked]>
Date: Sun, 23 Jun 2024 17:41:17 +0000

The parameter type is not nullable (`Collection<? extends Integer>` vs `Collection<? extends @Nullable Integer>`)

---

From: "vlsi (@vlsi)" <[email-masked]>
Date: Sun, 08 Dec 2024 10:39:51 +0000

This has been merged in 5e3190d5f3ad667a42210bee881b04404332cf30