Bug #90878 sort_keys comparator does not obey strict weak ordering

• Submitted: 15 May 2018 22:53
• Modified: 5 Feb 2020 15:32
• Reporter: David Gow (OCA)
• Status: Won't fix
• Category: MySQL Server: Compiling
• Severity: S3 (Non-critical)
• Version: 8.0.11
• OS: Any
• CPU Architecture: Any
• Tags: contributions

[15 May 2018 22:53] David Gow

Description:
Comparators passed to std::sort need to obey a strict weak ordering, and sort_keys() does not. In particular, it is not irreflexive: sort_keys(x,x) can be true, implying x < x. This occurs when x is a primary key (i.e. x.name == primary_key_name).

Some std::sort implementations may crash or produce incorrect results if given this comparator.

How to repeat:
Code inspection or use of an std::sort implementation which verifies strict weak ordering of comparators.

A simple reproducible test case could look something like:

KEY x;
x.name = primary_key_name;
assert(sort_keys(x, x) != true); //Asserts

Suggested fix:
In sql_table.cc:3366 (sort_keys::operator()):

Rework the "if (a.name == primary_key_name) return true;" code to only return true if a != b.

The solution we're using is below:
// Sort PRIMARY KEY before other UNIQUE NOT NULL.
if (a.name != b.name)
{
  if (a.name == primary_key_name) return true;
  if (b.name == primary_key_name) return false;
}

[15 May 2018 22:58] David Gow

Patch to fix sort_keys comparator when both inputs are primary keys.

Attachment: 0001-Make-sort_keys-comparator-irreflexive-bug-90878.patch (text/x-patch), 1.34 KiB.

[16 May 2018 4:48] MySQL Verification Team

Hello David Gow,

Thank you for the report, supplying patch along with it.
Please ensure to re-send the patch via "Contributions" tab. Otherwise we would not be able to accept it.

Thanks,
Umesh

[16 May 2018 16:45] David Gow

Patch to fix sort_keys comparator when both inputs are primary keys.

(*) I confirm the code being submitted is offered under the terms of the OCA, and that I am authorized to contribute it.

Contribution: 0001-Make-sort_keys-comparator-irreflexive-bug-90878.patch (text/x-patch), 1.34 KiB.

[14 Sep 2018 11:52] Dyre Tjeldvoll

Posted by developer:
 
Appears to have been introduced by

commit e025a331c7889c0554fcc5c4926a542e2a63bebd
Author: Steinar H. Gunderson <[e-mail]>
Date:   Thu Apr 27 11:17:35 2017 +0200

    Bug #25965593: REPLACE MY_QSORT WITH STD::SORT

    Convert all the simple my_qsort and my_qsort2 cases to std::sort.

    Change-Id: I28f98415da992fe56ac93ae89c87b480506a4c7b

[6 Mar 2019 12:25] Tor Didriksen

Posted by developer:
 
Technically, you are right, it does not obey strict weak ordering.
However: "Patch to fix sort_keys comparator when both inputs are primary keys."
There cannot be more than one primary key, so the situation will never occur.
What we *could* do I guess, is DBUG_ASSERT(a.name != b.name)