[MCOL-1089] Extent elimination for double datatype Created: 2017-12-08  Updated: 2022-11-05  Resolved: 2022-11-05

Status: Closed
Project: MariaDB ColumnStore
Component/s: ExeMgr
Affects Version/s: None
Fix Version/s: Icebox

Type: New Feature Priority: Major
Reporter: Dipti Joshi (Inactive) Assignee: Todd Stoffel (Inactive)
Resolution: Won't Do Votes: 0
Labels: Performance

Issue Links:
PartOf
is part of MCOL-1023 Add char(>8) and double to feature e... Closed
Epic Link: ColumnStore Performance Improvements

 Description   

Extent elimination for double datatype

 Comments   
Comment by Dipti Joshi (Inactive) [ 2017-12-08 ]

The float/double is a problem because the binary representation is not in order (0.1 in binary is more than 1.0 for example).
Filtering on double is not common use case - hence not planning to do this.

Comment by Sergey Zefirov [ 2021-03-26 ]

The representation choosen for doubles is sign and magnitude - highest bit is a sign and then lower bit are magnitude in "unsigned" representation.

https://en.wikipedia.org/wiki/Signed_number_representations#Signed_magnitude_representation

There are two other representations there, one's and two's complement. The latter is used in signed integer representation. The one's complement can help us with doubles.

Here's simple program that displays six floating point values, their representation as integers, transformation into one's complement form and final transformation into unsigned integers range:

#include <math.h>
 
#include <stdio.h>
 
#include <stdint.h>
 
 
 
typedef union u_u {
 
    double   dbl;
 
    uint64_t dword;
 
    int8_t   bytes[8];
 
} u;
 
 
 
void print_u(char*msg, u x) {
 
    uint64_t asonescompl = x.dword;
 
    uint64_t highbit = x.dword >> 63;
 
    uint64_t xormask = (-highbit) >> 1;
 
    uint64_t complete;
 
    asonescompl = asonescompl ^ xormask;
 
    complete = asonescompl ^ 0x8000000000000000ULL;
 
    printf("%s: double %lf, dword %016lx, dword as ones-complement %016lx, completely transformed %016lx\n", msg, x.dbl, x.dword, asonescompl, complete);
 
} /* print_u */
 
 
 
int main(void) {
 
    u x;
 
    x.dbl = 1;
 
    print_u("1.0", x);
 
    x.dbl=0.1;
 
    print_u("0.1", x);
 
    x.dbl = -1;
 
    print_u("-1.0", x);
 
    x.dbl = -0.1;
 
    print_u("-0.1", x);
 
    x.dbl=0.0;
 
    print_u("0", x);
 
    x.dbl = -0.0;
 
    print_u("-0", x);
 
    return 0;
 
} /* main */

It's output:

$ gcc -o a a.c && ./a
 
1.0: double 1.000000, dword 3ff0000000000000, dword as ones-complement 3ff0000000000000, completely transformed bff0000000000000
 
0.1: double 0.100000, dword 3fb999999999999a, dword as ones-complement 3fb999999999999a, completely transformed bfb999999999999a
 
-1.0: double -1.000000, dword bff0000000000000, dword as ones-complement c00fffffffffffff, completely transformed 400fffffffffffff
 
-0.1: double -0.100000, dword bfb999999999999a, dword as ones-complement c046666666666665, completely transformed 4046666666666665
 
0: double 0.000000, dword 0000000000000000, dword as ones-complement 0000000000000000, completely transformed 8000000000000000
 
-0: double -0.000000, dword 8000000000000000, dword as ones-complement ffffffffffffffff, completely transformed 7fffffffffffffff

First thing to note that positive doubles can be ordered by integer comparison.

For negative doubles it is not true directly. But we can apply simple transform (xor with mask derived from sign bit) and get ordering corrected.

The transformation is valid for all normalized floating point values, because exponent is in higher bits than mantissa and exponent is corrected by addition of 2^

{1024}

so that lowest exponent is represented as all zeroes and highest possible exponent is represented as all-but-one ones. Exceptions are denormalized values and NANs.

So it is quite possible to use integer arithmetic to perform comparison operations on doubles.

Comment by Todd Stoffel (Inactive) [ 2022-11-05 ]

This item is being closed because it was well passed the expiration date with no activity. If you suspect this was done in error please create a new ticket.

Generated at Thu Feb 08 02:26:06 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.