Bug #90878 sort_keys comparator does not obey strict weak ordering
Submitted: 15 May 2018 22:53 Modified: 5 Feb 15:32
Reporter: David Gow (OCA) Email Updates:
Status: Won't fix Impact on me:
Category:MySQL Server: Compiling Severity:S3 (Non-critical)
Version:8.0.11 OS:Any
Assigned to: CPU Architecture:Any
Tags: contributions

[15 May 2018 22:53] David Gow
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] Umesh Shastry
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.

[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 <steinar.gunderson@oracle.com>
Date:   Thu Apr 27 11:17:35 2017 +0200


    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)