兩個 unsigned int 取平均值的方法

Hacker News Daily 上看到 Raymond Chen 在講怎麼對兩個 unsigned int 取平均值的方法:「On finding the average of two unsigned integers without overflow」,這篇裡面提到了不少有趣的歷史,另外 Hacker News 上的討論「Finding the average of two unsigned integers without overflow (microsoft.com)」也可以翻翻。

最直覺的解法會有 overflow 的問題:

unsigned average(unsigned a, unsigned b)
{
    return (a + b) / 2;
}

如果已知 a 與 b 的大小的話 (如同作者說的,蠻多時候都符合這個情況),可以用這個方法避免 integer overflow:

unsigned average(unsigned low, unsigned high)
{
    return low + (high - low) / 2;
}

另外還有個方法是有專利的 (「Calculating the average of two integer numbers rounded towards zero in a single instruction cycle」),雖然在 2016 年到期了,各除以二相加後,只有 ab 都是奇數的情況下需要補 1:

unsigned average(unsigned a, unsigned b)
{
    return (a / 2) + (b / 2) + (a & b & 1);
}

接下來的這個方法用 AND 與 XOR 搞事,其中的原理可以解釋成,相同的 bit 不動表示值不需要動,不同的 bit 表示降一位 (除以 2):

unsigned average(unsigned a, unsigned b)
{
    return (a & b) + (a ^ b) / 2;
}

最後是暴力解,用個比較大的 data type 搞定他:

unsigned average(unsigned a, unsigned b)
{
    // Suppose "unsigned" is a 32-bit type and
    // "unsigned long long" is a 64-bit type.
    return ((unsigned long long)a + b) / 2;
}

後面有很多 assembly 的妖魔鬼怪跑出來就不提了 XDDD

MySQL 的 TIME 範圍

這篇算是考古文,找出 MySQLTIME 資料型態奇怪範圍的由來:「TIME for a WTF MySQL moment」。

在官方的文件裡面可以看到 TIME 的範圍是個奇怪的數字,如果把各版本的文件都拉出來看,會發現都沒改過:「11.2.3 The TIME Type (8.0)」、「11.2.3 The TIME Type (5.7)」、「11.2.3 The TIME Type (5.6)」,「11.3.2 The TIME Type (5.5,靠 Internet Archive 的存檔頁面)」、「11.3.2 The TIME Type (5.1,靠 Internet Archive 的存檔頁面)」、「11.3.2 The TIME Type (5.0,靠 Internet Archive 的存檔頁面)」,裡面一直都是:

TIME values may range from '-838:59:59' to '838:59:59'.

這個數字看起來應該是某個限制,但作者粗粗算了幾種可能都不像,所以就一路考古,發現算是在 MySQL 3 年代因為某個特別公式留下來的遺毒,就一路用到現在了:

One of the bits was used for the sign as well, but the remaining 23 bits were an integer value produced like this: Hours × 10000 + Minutes × 100 + Seconds; in other words, the two least significant decimal digits of the number contained the seconds, the next two contained the minutes, and the remaining ones contained the hours. 223 is 83888608, i.e. 838:86:08, therefore, the maximum valid time in this format is 838:59:59.

話說回來,用 MySQL 的人還是很習慣用 INTBIGINT 來存時間,這樣可以自動遠離這些鳥問題,之前在「MySQL 裡儲存時間的方式...」與「Facebook 在 MySQL 裡存時間的型態」這邊都寫過...

不過最近用 PostgreSQL 比較多,可以比較「正常」的使用各種資料型態...

Facebook 在 MySQL 裡存時間的型態

MySQL at Facebook這邊說明提到了,Facebook 內部是使用 INT UNSIGNED 儲存時間:

Which gets us to the point that it is no different than storing INT (hello 2038?) or UNSIGNED INT (a bit later) or BIGINT (till the end of time) and possibly passing binary values in efficient protocols eventually.

If you got that far of this post, your likes in Facebook graph are stored with 'INT UNSIGNED' time field.

順道一提,INT 是 2038 年問題,INT UNSIGNED 是 2106 年問題。

而 Facebook 在 MySQL 上會選擇不使用 DATETIMETIMESTAMP 的原因其實跟技術搭不上太多關係,主因是因為 MySQL 根本沒打算修 XDDD

It is my favorite MySQL bug, simply because it forces any reasonable mind not to use TIMESTAMP, and MySQL is never going to fix it (nor will ever understand time). I lost my temper a bit on that bug: https://bugs.mysql.com/bug.php?id=38455

我的猜測是已經爛成一團了,而且大家都有 workaround (呃,其實就是 Facebook 推薦用 INT UNSIGNED 的方法),再考慮到有一票現有程式,在上面狂用 side effect 讓執行結果正確,不如就不要修這種吃力不討好的東西了 XDDD

另外一方面 timezone 資訊其實常常變化,常常需要更新 MySQL 的 timezone database (而這對於維運來說不是什麼開心的事情):

There're few ways around that. One of them is side-load and maintain timezone data inside MySQL itself - it has support for internal timezone database and tracks obscure time shifts like ones for "Pacific War Time" and "Pacific Peace Time". That is operationally feasible (you have to remind yourself to update the database whenever time rules change, and they do change a lot, if you consider every timezone in the world), but has limited value.

這就是為什麼大家遇到 MySQL 時都會推薦用 INT UNSIGNED 了...

另外可以參考三年前的文章「MySQL 裡儲存時間的方式...」,裡面引用了 Baron Schwartz 的說明:

All date and time columns shall be INT UNSIGNED NOT NULL, and shall store a Unix timestamp in UTC.

其實這已經是個 best practice 了...

MySQL 裡搜尋 CHAR/VARCHAR (String) 欄位時要注意的事情

MySQL 表格欄位是 CHAR 或 VARCHAR 時,寫搜尋條件要記得使用 string 格式,而非數字。意思是,要避免這種 SQL query:

SELECT * FROM foo WHERE `column_string` = 123456;

原因是即使 column_string 加上了 B-tree index,也無法利用這個 index 加速查詢。

原因是,除了最明確的 '123456' 會符合外,還有很多種 case 符合:

mysql> SELECT 123456 = '0123456';
+--------------------+
| 123456 = '0123456' |
+--------------------+
|                  1 |
+--------------------+
1 row in set (0.00 sec)

mysql> SELECT 123456 = ' 123456';
+--------------------+
| 123456 = ' 123456' |
+--------------------+
|                  1 |
+--------------------+
1 row in set (0.00 sec)

這使得 index 無用武之地。

但如果欄位本身是數字 (INT/BIGINT),搜尋時用字串反而沒關係:MySQL 會先把字串轉型為數字再比較,所以會用到 index。

總而言之:

  • 可以用 INT/BIGINT 時,不要用 CHAR/VARCHAR 儲存。
  • 使用 CHAR/VARCHAR 的欄位當搜尋條件時,要用字串形式當作搜尋條件。(除非你很清楚你在做什麼)

今天上場當救援投手時解掉的問題...

MySQL 裡儲存時間的方式...

這應該是 MySQL 的 best practice 之一,不知道為什麼 Baron Schwartz 又拿出來講:「A simple rule for sane timestamps in MySQL」。

MySQL 內可以儲存「日期與時間」的資料型態是 DATETIME 與 TIMESTAMP 兩種,不過 DATETIME 沒有時區觀念,而 TIMESTAMP 只能是 UTC (GMT+0)。

相較於隔壁棚 PostgreSQLDate/Time Types 就一種 TIMESTAMP,但支援 with timezone 與 without timezone 直接解決問題。

這使得 MySQL 上在儲存「日期與時間」以及處理的時候一直有種 WTF 的感覺...

就如同 Baron Schwartz 的建議,如果使用 MySQL,目前比較好的方法是用 INT UNSIGNED NOT NULL 儲存,把 timezone 的處理都放到應用程式端來處理,這樣產生的問題會比較少...

真的需要在 INSERT 或是 UPDATE 時更新欄位,可以用 trigger 處理,彈性反而比內建功能大不少。