{"action":"created","issue":{"url":"https://api.github.com/repos/greenplum-db/gpdb/issues/6586","repository_url":"https://api.github.com/repos/greenplum-db/gpdb","labels_url":"https://api.github.com/repos/greenplum-db/gpdb/issues/6586/labels{/name}","comments_url":"https://api.github.com/repos/greenplum-db/gpdb/issues/6586/comments","events_url":"https://api.github.com/repos/greenplum-db/gpdb/issues/6586/events","html_url":"https://github.com/greenplum-db/gpdb/issues/6586","id":394602474,"node_id":"MDU6SXNzdWUzOTQ2MDI0NzQ=","number":6586,"title":"5X_STABLE: sort order for VARCHAR is incorrect on some datasets","user":{"login":"leskin-in","id":19490926,"node_id":"MDQ6VXNlcjE5NDkwOTI2","avatar_url":"https://avatars3.githubusercontent.com/u/19490926?v=4","gravatar_id":"","url":"https://api.github.com/users/leskin-in","html_url":"https://github.com/leskin-in","followers_url":"https://api.github.com/users/leskin-in/followers","following_url":"https://api.github.com/users/leskin-in/following{/other_user}","gists_url":"https://api.github.com/users/leskin-in/gists{/gist_id}","starred_url":"https://api.github.com/users/leskin-in/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/leskin-in/subscriptions","organizations_url":"https://api.github.com/users/leskin-in/orgs","repos_url":"https://api.github.com/users/leskin-in/repos","events_url":"https://api.github.com/users/leskin-in/events{/privacy}","received_events_url":"https://api.github.com/users/leskin-in/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2018-12-28T10:20:14Z","updated_at":"2018-12-28T20:59:18Z","closed_at":null,"author_association":"CONTRIBUTOR","body":"## Summary\r\nIn Greenplum 5X_STABLE, `VARCHAR` sort order (e.g. produced by `ORDER BY`) is incorrect on certain datasets.\r\n\r\nThe error does not reproduce on `master` branch.\r\n\r\n### Description\r\nThis issue is closely related to https://github.com/greenplum-db/gpdb/issues/6585. There, a particular dataset causes `Mergejoin` node to fail with `ERROR:  Mergejoin: compareResult > 0, bad plan ? (nodeMergejoin.c:1172)`. Working on that bug, I found out its (probable) cause: [`varstr_cmp()`](https://github.com/greenplum-db/gpdb/blob/7ab79eac1c41ef4cf4e3cd0f636275862c05b795/src/backend/utils/adt/varlena.c#L1136) comparison function.\r\n\r\nThis function is used by both `Sort` and `MergeJoin` nodes; despite this, *the sort order* for tuples to be merged *seems to be incorrect* and [an assertion in `nodeMergejoin.c`](https://github.com/greenplum-db/gpdb/blob/7ab79eac1c41ef4cf4e3cd0f636275862c05b795/src/backend/executor/nodeMergejoin.c#L1171) fails.\r\n\r\nThe following queries illustrate the problem:\r\n```\r\nDROP TABLE IF EXISTS kazybek;\r\nDROP TABLE\r\nCREATE TABLE kazybek(t VARCHAR) DISTRIBUTED RANDOMLY;\r\nCREATE TABLE\r\nINSERT INTO kazybek(t) VALUES ('им'),  ('Им. Казыбек'), ('им Казыбек би'), ('Им Казыбекби');\r\nINSERT 0 4\r\nSELECT t FROM kazybek ORDER BY t ASC;\r\n       t       \r\n---------------\r\n им\r\n Им. Казыбек\r\n им Казыбек би\r\n Им Казыбекби\r\n(4 rows)\r\n\r\nSELECT 'им Казыбек би' <= 'Им Казыбекби';\r\n ?column? \r\n----------\r\n f\r\n(1 row)\r\n```\r\n\r\nNote that correct lexicographical sort order should put strings starting with `и` before ones starting with `И` or vice versa, but it must not mix them.\r\n\r\n### Sample from the dataset\r\nThe actual dataset consists of 5000 tuples, each with one of 261 town names and numbers associated with them (not listed). Multiple naming variants are allowed (thus, there may be multiple highly similar strings present in one column). The names are:\r\n```\r\nим\r\nИм. Казыбек\r\nим Казыбек би\r\nИм Казыбекби\r\nИм. Казыбек-би\r\nИм Казыбек-Би\r\nИм. Казыбек Би\r\nИм. Казыбек-Би\r\nИм.Казыбек-Би\r\nИм. Кзыбек-Би\r\n```\r\nWhen I changed the comparison function, the sort order changed, too, but it was possible to find incorrectly sorted pair in the given dataset. The bug with `median()` was not fixed, too.\r\n\r\n## Proposed solution\r\nI [tried](https://github.com/arenadata/gpdb/commits/ADBDEV-103) to fix the comparison function using different approaches. These changed the sort order in some cases, but **did not fix the error**; it was still possible to find a combination of strings (from the same dataset) on which the sort order was incorrect. The three key ideas were:\r\n* Cutting string at the point where two different strings are of equal byte length, but taking into consideration UTF-8 variable length encoding (motivation: strings of equal length are always compared correctly);\r\n* Use byte-by-byte strings comparison;\r\n* Convert all strings to wide character representation (`pg_wchar`) and compare them using `mb/pg_wchar.h` (also try symbol-by-symbol comparison).\r\n\r\n## Instance installation information\r\n* **GPDB**: [`5.8.0+dev.614.g7ab79ea build dev`](https://github.com/greenplum-db/gpdb/tree/7ab79eac1c41ef4cf4e3cd0f636275862c05b795)\r\n* **OS**: `CentOS Linux release 7.6.1810 (Core)`, `Linux mdw 3.10.0-862.11.6.el7.x86_64 #1 SMP Tue Aug 14 21:49:04 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux`\r\n* **autoconf**: `'--disable-orca' '--prefix=/usr/lib/gpdb'`\r\n* **pg_config**:\r\n```\r\nBINDIR = /usr/lib/gpdb/bin\r\nDOCDIR = /usr/lib/gpdb/doc/postgresql\r\nHTMLDIR = /usr/lib/gpdb/doc/postgresql\r\nINCLUDEDIR = /usr/lib/gpdb/include\r\nPKGINCLUDEDIR = /usr/lib/gpdb/include/postgresql\r\nINCLUDEDIR-SERVER = /usr/lib/gpdb/include/postgresql/server\r\nLIBDIR = /usr/lib/gpdb/lib\r\nPKGLIBDIR = /usr/lib/gpdb/lib/postgresql\r\nLOCALEDIR = /usr/lib/gpdb/share/locale\r\nMANDIR = /usr/lib/gpdb/share/man\r\nSHAREDIR = /usr/lib/gpdb/share/postgresql\r\nSYSCONFDIR = /usr/lib/gpdb/etc/postgresql\r\nPGXS = /usr/lib/gpdb/lib/postgresql/pgxs/src/makefiles/pgxs.mk\r\nCC = gcc\r\nCPPFLAGS = -D_GNU_SOURCE -I/usr/lib/gpdb/include\r\nCFLAGS = -O3 -std=gnu99 -Wall -Wmissing-prototypes -Wpointer-arith -Wendif-labels -Wformat-security -fno-strict-aliasing -fwrapv -fexcess-precision=standard -fno-aggressive-loop-optimizations -Wno-unused-but-set-variable -Wno-address -I/usr/lib/gpdb/include\r\nCFLAGS_SL = -fpic\r\nLDFLAGS = -Wl,--as-needed -Wl,-rpath,'/usr/lib/gpdb/lib',--enable-new-dtags -L/usr/lib/gpdb/lib\r\nLDFLAGS_SL = \r\nLIBS = -lpgport -lrt -lcrypt -ldl -lm -L/usr/lib/gpdb/lib\r\nVERSION = PostgreSQL 8.3.23\r\n```"},"comment":{"url":"https://api.github.com/repos/greenplum-db/gpdb/issues/comments/450426397","html_url":"https://github.com/greenplum-db/gpdb/issues/6586#issuecomment-450426397","issue_url":"https://api.github.com/repos/greenplum-db/gpdb/issues/6586","id":450426397,"node_id":"MDEyOklzc3VlQ29tbWVudDQ1MDQyNjM5Nw==","user":{"login":"hlinnaka","id":191602,"node_id":"MDQ6VXNlcjE5MTYwMg==","avatar_url":"https://avatars2.githubusercontent.com/u/191602?v=4","gravatar_id":"","url":"https://api.github.com/users/hlinnaka","html_url":"https://github.com/hlinnaka","followers_url":"https://api.github.com/users/hlinnaka/followers","following_url":"https://api.github.com/users/hlinnaka/following{/other_user}","gists_url":"https://api.github.com/users/hlinnaka/gists{/gist_id}","starred_url":"https://api.github.com/users/hlinnaka/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/hlinnaka/subscriptions","organizations_url":"https://api.github.com/users/hlinnaka/orgs","repos_url":"https://api.github.com/users/hlinnaka/repos","events_url":"https://api.github.com/users/hlinnaka/events{/privacy}","received_events_url":"https://api.github.com/users/hlinnaka/received_events","type":"User","site_admin":false},"created_at":"2018-12-28T20:59:18Z","updated_at":"2018-12-28T20:59:18Z","author_association":"MEMBER","body":"Hmm. What locale are you using (`show lc_collate`)? `SELECT 'им Казыбек би' <= 'Им Казыбекби'` returns true for me, on both en_GB.utf8 and ru_RU.utf8 locales.\r\n\r\nI find it hard to believe that varstr_cmp() would be broken. It's identical to upstream's.\r\n\r\nTo narrow this down, can you reproduce this if you `set gp_enable_mk_sort = off` and/or `set gp_enable_motion_mk_sort=off`? "}}
{"actor":{"display_login":"hlinnaka"}}