duckdb · Mytherin · Jan 22, 2024 · Aug 25, 2023 · Aug 25, 2023 · Aug 25, 2023
diff --git a/benchmark/micro/compression/alp/alp_read.benchmark b/benchmark/micro/compression/alp/alp_read.benchmark
@@ -0,0 +1,24 @@
+# name: benchmark/micro/compression/alp/alp_read.benchmark
+# description: Scanning a large amount of doubles
+# group: [alp]
+
+name Alp Scan
+group alp
+storage persistent
+require parquet
+require httpfs
+
+load
+DROP TABLE IF EXISTS integers;
+PRAGMA force_compression='alp';
+CREATE TABLE temperatures (
+	temperature DOUBLE
+);
+INSERT INTO temperatures SELECT temp FROM 'https://github.com/duckdb/duckdb-data/releases/download/v1.0/city_temperature.parquet' t(temp), range(28);
+checkpoint;
+
+run
+select avg(temperature) from temperatures;
+
+result I
+56.028391124637494
diff --git a/benchmark/micro/compression/alp/alp_read_best_case.benchmark b/benchmark/micro/compression/alp/alp_read_best_case.benchmark
@@ -0,0 +1,16 @@
+# name: benchmark/micro/compression/alp/alp_read_best_case.benchmark
+# description: ALP best case scenario is when it founds low precision decimals within a limited absolute range
+# group: [alp]
+
+name Alp Scan
+group alp
+storage persistent
+
+load
+DROP TABLE IF EXISTS alp_random_doubles;
+PRAGMA force_compression='alp';
+create table alp_random_doubles as select round(random(), 1)::DOUBLE as data from range(200000000) tbl(i);
+checkpoint;
+
+run
+select avg(data) from alp_random_doubles;
diff --git a/benchmark/micro/compression/alp/alp_read_worst_case.benchmark b/benchmark/micro/compression/alp/alp_read_worst_case.benchmark
@@ -0,0 +1,16 @@
+# name: benchmark/micro/compression/alp/alp_read_worst_case.benchmark
+# description: ALP slowest scenario is when it founds high precision decimals. Here, ALP achieves no compression and everything is encoded as exception
+# group: [alp]
+
+name Alp Scan
+group alp
+storage persistent
+
+load
+DROP TABLE IF EXISTS alp_random_doubles;
+PRAGMA force_compression='alp';
+create table alp_random_doubles as select random()::DOUBLE as data from range(200000000) tbl(i);
+checkpoint;
+
+run
+select avg(data) from alp_random_doubles;
diff --git a/benchmark/micro/compression/alp/alp_store.benchmark b/benchmark/micro/compression/alp/alp_store.benchmark
@@ -0,0 +1,21 @@
+# name: benchmark/micro/compression/alp/alp_store.benchmark
+# description: Scanning a large amount of doubles
+# group: [alp]
+
+name Alp Insert
+group alp
+storage persistent
+require_reinit
+require parquet
+require httpfs
+
+load
+PRAGMA force_compression='alp';
+DROP TABLE IF EXISTS temperatures;
+CREATE TABLE temperatures (
+	temperature DOUBLE
+);
+
+run
+INSERT INTO temperatures SELECT temp FROM 'https://github.com/duckdb/duckdb-data/releases/download/v1.0/city_temperature.parquet' t(temp), range(28);
+checkpoint;
diff --git a/benchmark/micro/compression/alp/alp_store_best_case.benchmark b/benchmark/micro/compression/alp/alp_store_best_case.benchmark
@@ -0,0 +1,16 @@
+# name: benchmark/micro/compression/alp/alp_store_best_case.benchmark
+# description: ALP best case scenario is when it founds low precision decimals within a limited absolute range.
+# group: [alp]
+
+name Alp Insert
+group alp
+storage persistent
+require_reinit
+
+load
+PRAGMA force_compression='alp';
+DROP TABLE IF EXISTS alp_random_doubles;
+
+run
+create table alp_random_doubles as select round(random(), 1)::DOUBLE as data from range(50000000) tbl(i);
+checkpoint;
diff --git a/benchmark/micro/compression/alp/alp_store_worst_case.benchmark b/benchmark/micro/compression/alp/alp_store_worst_case.benchmark
@@ -0,0 +1,16 @@
+# name: benchmark/micro/compression/alp/alp_store_worst_case.benchmark
+# description: ALP slowest scenario is when it founds high precision decimals. Here, ALP achieves no compression and everything is encoded as exception
+# group: [alp]
+
+name Alp Insert
+group alp
+storage persistent
+require_reinit
+
+load
+PRAGMA force_compression='alp';
+DROP TABLE IF EXISTS alp_random_doubles;
+
+run
+create table alp_random_doubles as select random()::DOUBLE as data from range(50000000) tbl(i);
+checkpoint;
diff --git a/benchmark/micro/compression/alprd/alprd_read.benchmark b/benchmark/micro/compression/alprd/alprd_read.benchmark
@@ -0,0 +1,24 @@
+# name: benchmark/micro/compression/alprd/alprd_read.benchmark
+# description: Scanning a large amount of doubles
+# group: [alprd]
+
+name Alprd Scan
+group alprd
+storage persistent
+require parquet
+require httpfs
+
+load
+DROP TABLE IF EXISTS integers;
+PRAGMA force_compression='alprd';
+CREATE TABLE temperatures (
+	temperature DOUBLE
+);
+INSERT INTO temperatures SELECT temp FROM 'https://github.com/duckdb/duckdb-data/releases/download/v1.0/city_temperature.parquet' t(temp), range(28);
+checkpoint;
+
+run
+select avg(temperature) from temperatures;
+
+result I
+56.028391124637494
diff --git a/benchmark/micro/compression/alprd/alprd_read_best_case.benchmark b/benchmark/micro/compression/alprd/alprd_read_best_case.benchmark
@@ -0,0 +1,16 @@
+# name: benchmark/micro/compression/alprd/alprd_read_best_case.benchmark
+# description: ALPRD best case scenario is when all the floats share their front bits
+# group: [alprd]
+
+name Alprd Scan
+group alprd
+storage persistent
+
+load
+DROP TABLE IF EXISTS alprd_random_doubles;
+PRAGMA force_compression='alprd';
+create table alprd_random_doubles as select (random() + 10)::DOUBLE as data from range(200000000) tbl(i);
+checkpoint;
+
+run
+select avg(data) from alprd_random_doubles;
diff --git a/benchmark/micro/compression/alprd/alprd_read_worst_case.benchmark b/benchmark/micro/compression/alprd/alprd_read_worst_case.benchmark
@@ -0,0 +1,16 @@
+# name: benchmark/micro/compression/alprd/alprd_read_worst_case.benchmark
+# description: ALPRD worst case scenario is when all the float have unique front bits. Multiplying by different powers of two ensures us unique front bits
+# group: [alprd]
+
+name Alprd Scan
+group alprd
+storage persistent
+
+load
+DROP TABLE IF EXISTS alprd_random_doubles;
+PRAGMA force_compression='alprd';
+create table alprd_random_doubles as select (random() * pow(2, (i % 1000)) * (CASE WHEN i%2=0 THEN 1 ELSE -1 END))::DOUBLE as data from range(200000000) tbl(i);
+checkpoint;
+
+run
+select avg(data) from alprd_random_doubles;
diff --git a/benchmark/micro/compression/alprd/alprd_store.benchmark b/benchmark/micro/compression/alprd/alprd_store.benchmark
@@ -0,0 +1,21 @@
+# name: benchmark/micro/compression/alprd/alprd_store.benchmark
+# description: Scanning a large amount of doubles
+# group: [alprd]
+
+name Alprd Insert
+group alprd
+storage persistent
+require_reinit
+require parquet
+require httpfs
+
+load
+PRAGMA force_compression='alprd';
+DROP TABLE IF EXISTS temperatures;
+CREATE TABLE temperatures (
+	temperature DOUBLE
+);
+
+run
+INSERT INTO temperatures SELECT temp FROM 'https://github.com/duckdb/duckdb-data/releases/download/v1.0/city_temperature.parquet' t(temp), range(28);
+checkpoint;
diff --git a/benchmark/micro/compression/alprd/alprd_store_best_case.benchmark b/benchmark/micro/compression/alprd/alprd_store_best_case.benchmark
@@ -0,0 +1,17 @@
+# name: benchmark/micro/compression/alprd/alprd_store_best_case.benchmark
+# description: ALPRD best case scenario is when all the floats share their front bits.
+# group: [alprd]
+
+name Alprd Insert
+group alprd
+storage persistent
+require_reinit
+
+load
+DROP TABLE IF EXISTS alprd_random_doubles;
+PRAGMA force_compression='alprd';
+checkpoint;
+
+run
+create table alprd_random_doubles as select (random() + 10)::DOUBLE as data from range(50000000) tbl(i);
+checkpoint;
diff --git a/benchmark/micro/compression/alprd/alprd_store_worst_case.benchmark b/benchmark/micro/compression/alprd/alprd_store_worst_case.benchmark
@@ -0,0 +1,17 @@
+# name: benchmark/micro/compression/alprd/alprd_store_worst_case.benchmark
+# description: ALPRD worst case scenario is when all the float have unique front bits. Multiplying by different powers of two ensures us unique front bits
+# group: [alprd]
+
+name Alprd Insert
+group alprd
+storage persistent
+require_reinit
+
+load
+DROP TABLE IF EXISTS alprd_random_doubles;
+PRAGMA force_compression='alprd';
+checkpoint;
+
+run
+create table alprd_random_doubles as select (random() * pow(2, (i % 1000)) * (CASE WHEN i%2=0 THEN 1 ELSE -1 END))::DOUBLE as data from range(50000000) tbl(i);
+checkpoint;
diff --git a/src/common/enum_util.cpp b/src/common/enum_util.cpp
@@ -1033,6 +1033,10 @@ const char* EnumUtil::ToChars<CompressionType>(CompressionType value) {
 		return "COMPRESSION_CHIMP";
 	case CompressionType::COMPRESSION_PATAS:
 		return "COMPRESSION_PATAS";
+	case CompressionType::COMPRESSION_ALP:
+		return "COMPRESSION_ALP";
+	case CompressionType::COMPRESSION_ALPRD:
+		return "COMPRESSION_ALPRD";
 	case CompressionType::COMPRESSION_COUNT:
 		return "COMPRESSION_COUNT";
 	default:
@@ -1072,6 +1076,12 @@ CompressionType EnumUtil::FromString<CompressionType>(const char *value) {
 	if (StringUtil::Equals(value, "COMPRESSION_PATAS")) {
 		return CompressionType::COMPRESSION_PATAS;
 	}
+	if (StringUtil::Equals(value, "COMPRESSION_ALP")) {
+		return CompressionType::COMPRESSION_ALP;
+	}
+	if (StringUtil::Equals(value, "COMPRESSION_ALPRD")) {
+		return CompressionType::COMPRESSION_ALPRD;
+	}
 	if (StringUtil::Equals(value, "COMPRESSION_COUNT")) {
 		return CompressionType::COMPRESSION_COUNT;
 	}

diff --git a/src/common/enums/compression_type.cpp b/src/common/enums/compression_type.cpp
@@ -34,6 +34,10 @@ CompressionType CompressionTypeFromString(const string &str) {
 		return CompressionType::COMPRESSION_CHIMP;
 	} else if (compression == "patas") {
 		return CompressionType::COMPRESSION_PATAS;
+	} else if (compression == "alp") {
+		return CompressionType::COMPRESSION_ALP;
+	} else if (compression == "alprd") {
+		return CompressionType::COMPRESSION_ALPRD;
 	} else {
 		return CompressionType::COMPRESSION_AUTO;
 	}
@@ -61,6 +65,10 @@ string CompressionTypeToString(CompressionType type) {
 		return "Chimp";
 	case CompressionType::COMPRESSION_PATAS:
 		return "Patas";
+	case CompressionType::COMPRESSION_ALP:
+		return "ALP";
+	case CompressionType::COMPRESSION_ALPRD:
+		return "ALPRD";
 	default:
 		throw InternalException("Unrecognized compression type!");
 	}

diff --git a/src/function/compression_config.cpp b/src/function/compression_config.cpp
@@ -23,6 +23,8 @@ static DefaultCompressionMethod internal_compression_methods[] = {
      DictionaryCompressionFun::TypeIsSupported},
     {CompressionType::COMPRESSION_CHIMP, ChimpCompressionFun::GetFunction, ChimpCompressionFun::TypeIsSupported},
     {CompressionType::COMPRESSION_PATAS, PatasCompressionFun::GetFunction, PatasCompressionFun::TypeIsSupported},
+    {CompressionType::COMPRESSION_ALP, AlpCompressionFun::GetFunction, AlpCompressionFun::TypeIsSupported},
+    {CompressionType::COMPRESSION_ALPRD, AlpRDCompressionFun::GetFunction, AlpRDCompressionFun::TypeIsSupported},
     {CompressionType::COMPRESSION_FSST, FSSTFun::GetFunction, FSSTFun::TypeIsSupported},
     {CompressionType::COMPRESSION_AUTO, nullptr, nullptr}};
 
@@ -76,6 +78,8 @@ vector<reference<CompressionFunction>> DBConfig::GetCompressionFunctions(Physica
 	TryLoadCompression(*this, result, CompressionType::COMPRESSION_DICTIONARY, data_type);
 	TryLoadCompression(*this, result, CompressionType::COMPRESSION_CHIMP, data_type);
 	TryLoadCompression(*this, result, CompressionType::COMPRESSION_PATAS, data_type);
+	TryLoadCompression(*this, result, CompressionType::COMPRESSION_ALP, data_type);
+	TryLoadCompression(*this, result, CompressionType::COMPRESSION_ALPRD, data_type);
 	TryLoadCompression(*this, result, CompressionType::COMPRESSION_FSST, data_type);
 	return result;
 }

diff --git a/src/include/duckdb/common/enums/compression_type.hpp b/src/include/duckdb/common/enums/compression_type.hpp
@@ -24,6 +24,8 @@ enum class CompressionType : uint8_t {
 	COMPRESSION_FSST = 7,
 	COMPRESSION_CHIMP = 8,
 	COMPRESSION_PATAS = 9,
+	COMPRESSION_ALP = 10,
+	COMPRESSION_ALPRD = 11,
 	COMPRESSION_COUNT // This has to stay the last entry of the type!
 };
 

diff --git a/src/include/duckdb/function/compression/compression.hpp b/src/include/duckdb/function/compression/compression.hpp
@@ -48,6 +48,16 @@ struct PatasCompressionFun {
 	static bool TypeIsSupported(PhysicalType type);
 };
 
+struct AlpCompressionFun {
+	static CompressionFunction GetFunction(PhysicalType type);
+	static bool TypeIsSupported(PhysicalType type);
+};
+
+struct AlpRDCompressionFun {
+	static CompressionFunction GetFunction(PhysicalType type);
+	static bool TypeIsSupported(PhysicalType type);
+};
+
 struct FSSTFun {
 	static CompressionFunction GetFunction(PhysicalType type);
 	static bool TypeIsSupported(PhysicalType type);

diff --git a/src/include/duckdb/storage/compression/alp/algorithm/LICENSE b/src/include/duckdb/storage/compression/alp/algorithm/LICENSE
@@ -0,0 +1,21 @@
+MIT License
+
+Copyright (c) 2023 CWI, Azim Afroozeh,  Leonardo Xavier Kuffo Rivero
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.