1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
|
## Precise fractions for PostgreSQL
An efficient custom type. Perfect for exact arithmetic or user-specified
table row ordering. Holds values as big as an integer, with matching
precision in the denominator.
### Features
* Stores fractions in exactly 64 bits (same size as float)
* Written in C for high performance
* Detects and halts arithmetic overflow for correctness
* Uses native CPU instructions for fast overflow detection
* Defers GCD calculation until requested or absolutely required
* Supports btree and hash indices
* Implements Stern-Brocot trees for finding intermediate points
* Coercion from integer/bigint/tuple
* Custom aggregate
### Motivation
See my blog post about [User-Defined Order in
SQL](https://begriffs.com/posts/2018-03-20-user-defined-order.html).
### Usage
Basics
```sql
-- fractions are precise
-- this would not work with a float type
select 1::rational / 3 * 3 = 1;
-- => t
-- provides the usual operations, e.g.
select '1/3'::rational + '2/7';
-- => 13/21
-- helper "ratt' type to coerce from tuples
select 1 + (i,i+1)::ratt from generate_series(1,5) as i;
-- => 3/2, 5/3, 7/4, 9/5, 11/6
-- simplify if desired
select rational_simplify('36/12');
-- => 3/1
-- convert float to rational
select 0.263157894737::float::rational;
-- => 5/19
-- convert rational to float
select '-1/2'::rational::float;
-- => -0.5
```
Reorder items without renumbering surrounding items.
```sql
create sequence todos_seq;
create table todos (
prio rational unique
default nextval('todos_seq'),
what text not null
);
insert into todos (what) values
('install extension'),
('read about it'),
('try it'),
('profit?');
select * from todos order by prio asc;
/*
┌──────┬───────────────────┐
│ prio │ what │
├──────┼───────────────────┤
│ 1/1 │ install extension │
│ 2/1 │ read about it │
│ 3/1 │ try it │
│ 4/1 │ profit? │
└──────┴───────────────────┘
*/
-- put "try" between "install" and "read"
update todos
set prio = rational_intermediate(1,2)
where prio = 3;
select * from todos order by prio asc;
/*
┌──────┬───────────────────┐
│ prio │ what │
├──────┼───────────────────┤
│ 1/1 │ install extension │
│ 3/2 │ try it │
│ 2/1 │ read about it │
│ 4/1 │ profit? │
└──────┴───────────────────┘
*/
-- put "read" back between "install" and "try"
update todos
set prio = rational_intermediate(1,'3/2')
where prio = 2;
select * from todos order by prio asc;
/*
┌──────┬───────────────────┐
│ prio │ what │
├──────┼───────────────────┤
│ 1/1 │ install extension │
│ 4/3 │ read about it │
│ 3/2 │ try it │
│ 4/1 │ profit? │
└──────┴───────────────────┘
*/
```
This extension uses Stern-Brocot trees to find efficient intermediate points as fractions in lowest terms. It can continue to split deeper between fractions as much as any practical application requires.
Using floats, on the other hand, and picking the midpoints between adjacent values runs out of space rapidly (you only need 50-odd inserts at the wrong spot to start hitting problems).
### Installation
Clone this repo, go inside and simply run:
```bash
make
sudo make install
```
Then, in your database:
```sql
create extension pg_rational;
```
### Caveats
The `rational_intermediate` function is super fast on typical intervals, but the narrower the range between arguments the longer it takes. We may want to add a max search depth parameter to prevent malicious values from hogging the server.
### Thanks
This is my first PostgreSQL extension, and these resources were helpful in learning to write it.
* https://www.postgresql.org/docs/10/static/extend-extensions.html
* https://www.postgresql.org/docs/10/static/xtypes.html
* http://big-elephants.com/2015-10/writing-postgres-extensions-part-i/
* https://wiki.postgresql.org/wiki/User-specified_ordering_with_fractions
* #postgresql and ##c channels on freenode
|
