Incorrect Comparison Logic for Strings

[apavlo]

The logic for our VarlenType comparison types are incorrect.We use memcmp, which causes it to incorrectly say that one string is less than another if it is shorter:

https://github.com/cmu-db/peloton/blob/master/src/include/type/type_util.h#L42

This is because we need to do a comparison of strings that are not null terminated.

I'm not sure what the SQL standard says but I suspect that Postgres is doing it correctly. Here are some other examples of string comparisons in other systems. Note that sqlite doesn't follow the standard either.

Postgres

pavlo=# SELECT 'aaaaa' < 'Z';
 ?column? 
----------
 t
(1 row)

MySQL

mysql> SELECT 'aaaaa' < 'Z';
+---------------+
| 'aaaaa' < 'Z' |
+---------------+
|             1 |
+---------------+

SQLite

sqlite> SELECT 'aaaaa' < 'Z';
'aaaaa' < 'Z'
-------------
0

[allisonwang]

@apavlo I looked into this issue and figured out that memcmp / strcmp are ASCII based sorting, and Postgres and MySQL might be using natural sort. However, when I tried the example above in Postgres (10), it returns:

Allison=# SELECT 'aaaaa' < 'Z';
 ?column?
----------
 f
(1 row)

[allisonwang]

I think the result depends on OS. I saw this in PostgresSQL wiki:

It is not in ASCII/byte order. No, it's not, it's not supposed to be. ASCII is an encoding, not a sort order. If you want this, you can use the C locale, but then you use the ability to non-ASCII characters.
That said, if you are on Mac OS X or a BSD-family operating system, and you are using UTF-8, then give up. The locale definitions on those operating systems are broken.

I am using UTF8 on Mac OS X.

 lc_collate
-------------
 en_US.UTF-8