MySQL Bugs: #90878: sort_keys comparator does not obey strict weak ordering

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	Email Updates:
Status:	Won't fix	Impact on me:	None
Category:	MySQL Server: Compiling	Severity:	S3 (Non-critical)
Version:	8.0.11	OS:	Any
Assigned to:		CPU Architecture:	Any
Tags:	contributions

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;
}

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.

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

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.

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

    Bug #25965593: REPLACE MY_QSORT WITH STD::SORT

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

    Change-Id: I28f98415da992fe56ac93ae89c87b480506a4c7b

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)