# Re: [HACKERS] GiST penalty functions [PoC]

```On 08/29/2016 09:04 AM, Andrew Borodin wrote:
```
```In this message I address only first problem. I want to construct a
penalty function that will choose:
1.    Entry with a zero volume and smallest margin, that can
accommodate insertion tuple without extension, if one exists;
2.    Entry with smallest volume, that can accommodate insertion tuple
without extension, if one exists;
3.    Entry with zero volume increase after insert and smallest margin
increase, if one exists;
4.    Entry with minimal volume increase after insert.
```

```
```
Looking at the code, by "margin", you mean the sum of all "edges", i.e. of each dimension, of the cube. I guess the point of that is to differentiate between cubes that have the same volume, but a different shape.
```
```
So, let's try to come up with a scheme that doesn't require IEEE 754 floats. Those above cases can be split into two categories, depending on whether the new value has zero volume or not. We can use a completely different scheme for the two cases, if we want, because when we're choosing a target page to insert to, penalty gets called for every original tuple, but with the same new tuple.
```
```
Here's a scheme I just came up with. There might be better ones, but it's something.
```
Let's have:

oX: Original tuple's edge sum
nX: New tuple's edge sum
dX: Edge increase

oV: Original tuple's volume
nX: New tuple's volume
dX: Volume increase

Case A: New entry has zero volume.
------

Two sub-cases:
A1: if dE > 0, use dE. dE must be in the range [0, nE]
A2: otherwise, use oE.

So how do we cram those two into a single float?

```
If we offset case A1 by n, we can use the range between [0, nE] for A2. Something like this pseudocode:
```
if (dE > 0)
return nE + dE;       /* A1, offset dE into range [nE, inf] */
else
return nE - (nE/oE);  /* A2, scale oE into range [0, nE] */

Case B: New entry has non-zero volume
------
B1: if dV > 0. use dV. dV must be in the range [0, nV].
B2: if dE > 0, use dE. dE must be in the range [0, nE].
B3: oV, otherwise.

```
By offsetting cases B1 and B2, we can again divide the range into three parts, with pseudocode like:
```
if (dV > 0)
return nV + nE + dV;   /* B1, offset dV into range [nV+nE, inf] */
else if (dE > 0)
return nV + dE;        /* B2, offset dE into range [nV, nV+nE] */
else
return nV - (nV/oV)    /* B3, scale oV into range [0, nV]

```
```I’ve tested patch performance with attached test. On my machine patch
slows index construction time from 60 to 76 seconds, reduces size of
the index from 85Mb to 82Mb, reduces time of aggregates computation
from 36 seconds to 29 seconds.
```
```
```
Hmm. That's a pretty large increase in construction time. Have you done any profiling on where the time goes?
```
```
```I do not know: should I continue this work in cube, or it’d be better
to fork cube?
```
```
```
Should definitely continue work within cube, IMHO. I don't think forking it to a new datatype would make this any easier.
```
- Heikki

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
```