CompareShardPlacements doesn't actually work - task assignment policies are broken
- Dominant language
- C
- Stars
- 12.8k
- Forks
- 794
- Avg merge
- 2d 14h
- Merged PRs (30d)
- 31
Description
I've notice that the code for CompareShardPlacements() isn't correct. It currently is:
```
const ShardPlacement *leftPlacement = *((const ShardPlacement **) leftElement);
const ShardPlacement *rightPlacement = *((const ShardPlacement **) rightElement);
Oid leftTupleOid = leftPlacement->tupleOid;
Oid rightTupleOid = rightPlacement->tupleOid;
/* tuples that are inserted earlier appear first */
int tupleOidDiff = leftTupleOid - rightTupleOid;
return tupleOidDiff;
```
but that's wrong, because the subtraction of two unsigned numbers will wrap around. I.e. `leftTupleOid - rightTupleOid` will never be negative (it can't, it's an unsigned integer!) here.
The only reason this sometimes gives halfway reasonable results is that we _afterwards_ _again_ cast the result to (signed) int. While that's not actually well defined behaviour:
> 6.3.1.3 Signed and unsigned integers
> 3) Otherwise, the new type is signed and the value cannot be represented in it; either the result is implementation-defined or an implementation-defined signal is raised.
On most 2's complement machines / compilers that'll kind of work:
```
5118 int tupleOidDiff = leftTupleOid - rightTupleOid;
(gdb) p leftTupleOid
$1 = 16580
(gdb) p rightTupleOid
$2 = 16581
(gdb) p leftTupleOid - rightTupleOid
$3 = 4294967295
(gdb) fin
Run till exit from #0 CompareShardPlacements (leftElement=0x289e958, rightElement=0x289e960)
at /home/andres/src/citusdb/src/backend/distributed/planner/multi_physical_planner.c:5118
Value returned is $4 = -1
```
(note the -1 returned)
This means that our comparator isn't actually guaranteed to be transitive afaics, and it means we're sometimes violating qsort's requirements, which are:
```
The comparison function must return an integer less than, equal to, or greater than zero if the first argument is considered to be respectively less
than, equal to, or greater than the second. If two members compare as equal, their order in the sorted array is undefined.
```
It's also very complicated to understand when / why this sometimes work. The only actually correct / sensible way to do this is
```
if (leftPlacementId < rightPlacementId)
{
return -1;
}
else if (leftPlacementId > rightPlacementId)
{
return 1;
}
else
{
return 0;
}
``
```
Contributor guide
Research direction
Start in src/backend/distributed/planner/multi_physical_planner.c at CompareShardPlacements(), using the issue's qsort comparator discussion as context. Inspect the ShardPlacement fields used for ordering and verify the comparator's results across adjacent and wrapped Oid values. Done means task assignment policies receive a valid, transitive ordering without relying on implementation-defined signed conversion.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- c, postgresql
- Domain
- databases
- Issue type
- Bug
- Difficulty
- 2/5
- Estimated time
- 1-3 hours
- Activity status
- Stale
- Clarity
- Clearly specified
- Newbie friendliness
- 45/100