digoal
2022-12-08
PostgreSQL , PolarDB , pg_rational , Stern-Brocot trees
PolarDB 的云原生存算分离架构, 具备低廉的数据存储、高效扩展弹性、高速多机并行计算能力、高速数据搜索和处理; PolarDB与计算算法结合, 将实现双剑合璧, 推动业务数据的价值产出, 将数据变成生产力.
本文将介绍PolarDB 开源版通过pg_rational插件支持Stern-Brocot trees , 实现高效自定义顺序和调整顺序需求.
测试环境为macos+docker, polardb部署请参考:
pg_rational扩展使用 Stern-Brocot 树找到有效的中间点作为最低项的分数。它可以根据任何实际应用的需要继续在分数之间进行更深的拆分。实现高效自定义顺序和调整顺序需求.
pg_rational特性:
- 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
1、安装pg_rational
git clone --depth 1 https://github.com/begriffs/pg_rational
cd pg_rational/
USE_PGXS=1 make
USE_PGXS=1 make install
export PGHOST=127.0.0.1
USE_PGXS=1 make installcheck
/home/postgres/tmp_basedir_polardb_pg_1100_bld/lib/pgxs/src/makefiles/../../src/test/regress/pg_regress --inputdir=./ --bindir='/home/postgres/tmp_basedir_polardb_pg_1100_bld/bin' --dbname=contrib_regression pg_rational_test
(using postmaster on 127.0.0.1, default port)
============== dropping database "contrib_regression" ==============
DROP DATABASE
============== creating database "contrib_regression" ==============
CREATE DATABASE
ALTER DATABASE
============== running regression test queries ==============
test pg_rational_test ... ok
==========================================================
All 1 tests passed.
POLARDB:
All 1 tests, 0 tests in ignore, 0 tests in polar ignore.
==========================================================
2、加载pg_rational插件
psql
psql (11.9)
Type "help" for help.
postgres=# create extension pg_rational;
CREATE EXTENSION
3、基本操作, pg_rational可以和浮点、整型相互转换.
-- 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
4、调整顺序测试, 不需要指定值, 只需要指定你要插入到哪两个rational value之间, pg_rational扩展使用 Stern-Brocot 树找到有效的中间点作为最低项的分数。从而实现了快速的顺序调整.
postgres=# create sequence todos_seq;
CREATE SEQUENCE
postgres=# create table todos (
prio rational unique
default nextval('todos_seq')::float8::rational,
what text not null
);
CREATE TABLE
postgres=# insert into todos (what) values
postgres-# ('install extension'),
postgres-# ('read about it'),
postgres-# ('try it'),
postgres-# ('profit?');
INSERT 0 4
postgres=#
-- put "try" between "install" and "read"
postgres=# 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?
(4 rows)
-- put "read" back between "install" and "try"
postgres=# update todos
postgres-# set prio = rational_intermediate(1,2) -- 1为install extension, 2为read about it. 根据Stern-Brocot 树找到1,2之间的3/2分数.
postgres-# where prio = 3;
UPDATE 1
postgres=# 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?
(4 rows)
postgres=# update todos
postgres-# set prio = rational_intermediate(1,'3/2') -- 1为install extension, 3/2为try it. 根据Stern-Brocot 树找到1,3/2之间的4/3分数.
postgres-# where prio = 2;
UPDATE 1
postgres=# 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?
(4 rows)
https://github.com/begriffs/pg_rational
