PostgreSQL 15 釋出

PostgreSQL 15 出了:「PostgreSQL 15 Released!

先前提到過「PostgreSQL 15 將可以對透過 UNIQUE 限制 NULL 的唯一性了」,反而沒排上這次 release 的重點,翻了一下的確是排不太上 XD

第一個超大的改善是 sorting:

In this latest release, PostgreSQL improves on its in-memory and on-disk sorting algorithms, with benchmarks showing speedups of 25% - 400% based on which data types are sorted.

在「Speeding up sort performance in Postgres 15」這邊有提到四個改動,裡面很詳細的說明了改動的內容,以及 benchmark 差異。

如果以他列出來的四個進展,應該是第二個「Reduce memory consumption by using generation memory context」這個會最容易遇到,也改善最多:

另外是第三個「Add specialized sort routines for common datatypes」也會有一些:

再來是拿 PostgreSQL 當 OLAP engine 用的時候會發生的第四個「Replace polyphase merge algorithm with k-way merge」:

最開頭第一個「Improvements sorting a single column」的 SELECT col1 FROM tab ORDER BY col1; 這種 case 好像用的很少,限制 SELECT 的部份也只能出現後面 sorting 的 column,但如果遇到的話效能提昇很多:

除了 sorting 的改善以外,另外一個是 WAL 支援 LZ4zstd,這對於有寫入量很大的環境應該會有幫助:

PostgreSQL 15 adds support for LZ4 and Zstandard (zstd) compression to write-ahead log (WAL) files, which can have both space and performance benefits for certain workloads.

正式版出來後,應該會有一些整體性的 benchmark 數字可以看,再來等著看...

Golang 的排序演算法將換成 pdqsort,LLVM libc++ 換成 BlockQuicksort

Hacker News 首頁上看到的消息,Golang 將會把 sort.Sort() 換成 pdqsort (Pattern-defeating Quicksort):「Go will use pdqsort in next release (github.com/golang)」,對應的 commit 則是在「sort: use pdqsort」這邊可以看到。

然後另外是「Changing std:sort at Google’s scale and beyond (danlark.org)」這邊提到了,LLVMlibc++std::sortQuicksort 換成 BlockQuicksort。另外在文章裡面有提到一段 Knuth 老大在 TAOCP 裡講 sorting algorithm 沒有霸主的情況:

It would be nice if only one or two of the sorting methods would dominate all of the others, regardless of application or the computer being used. But in fact, each method has its own peculiar virtues. […] Thus we find that nearly all of the algorithms deserve to be remembered, since there are some applications in which they turn out to be best.

先回到 pdqsort 的部份,pdqsort 作者的 GitHub 上 (orlp/pdqsort) 可以看到他對 pdqsort 的說明:

Pattern-defeating quicksort (pdqsort) is a novel sorting algorithm that combines the fast average case of randomized quicksort with the fast worst case of heapsort, while achieving linear time on inputs with certain patterns.

看名字也可以知道 pdqsort 是從 Quicksort 改良的版本,而依照 Golang 的 commit 上的測試,與 Quicksort 相比,少數情況下會慢一點點,大多數的情況下會快一些,而在特殊情境下會讓 worst case 下降。

Golang 選擇把 unstable 的 Quicksort 換成 pdqsort,LLVM 則是選擇把 Quicksort 換成 BlockQuicksort,這邊看起來有些分歧...

反倒是各個程式語言對於 stable 的 Mergesort 陸陸續續都換成了 Timsort,看起來比較像是有個共識...

JavaScript 的 sort 變成 stable

看到「Stable Array.prototype.sort」這篇在講 JavaScript 規格書裡的 sort...

本來 JavaScript 的規格書裡,各種 sort 都沒有保證 stable,而在「[Normative] Make Array.prototype.sort stable #1340」與「[Normative] Make %TypedArray%.prototype.sort stable #1433」這兩個地方則有了變化,提案在規格裡加入 stable 的要求,可以減少開發者因為不知道 unstable 而造成的問題...

Firefox 則是很久前就決定使用 Merge sort 了 (看了一下,當時還在從 Firebird 轉換名稱到 Firefox 的時期):「Array.sort isn't a stable sort (switch to MergeSort)」。

另外這篇也剛好提到了 V8 使用 Timsort 當作 stable sorting algorithm,之前就有看到但發現沒在 blog 上提過...

Timsort 是 1993 年發明出來的演算法,與 Merge sort 的情況類似,除了 stable 外,還可以保證最差的情境下的時間複雜度是 O(n*log(n))

Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data.

這個演算法的重點是善用已經排好的子序列,藉此降低記憶體操作次數而提昇效能,符合真實環境裡常見到的資料:

The algorithm finds subsequences of the data that are already ordered, and uses that knowledge to sort the remainder more efficiently.

除了 V8 採用這個演算法以外,其他常見的包括了 PythonAndroid 上的 Java SE:

Timsort has been Python's standard sorting algorithm since version 2.3. It is also used to sort arrays of non-primitive type in Java SE 7, on the Android platform, in GNU Octave, and Google Chrome.