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

[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 <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
[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)

Portions of this website are copyright © 2001, 2002 The PHP Group

Page generated in 0.058 sec. using MySQL 8.4.7-u6-cloud

Timestamp references displayed by the system are UTC.
Content reproduced on this site is the property of the respective copyright holders.
It is not reviewed in advance by Oracle and does not necessarily represent the opinion of Oracle or any other party.