TRAKTOR 2 is out!

Check TRAKTOR 2 - less complicated, more stable, cloud ready! Compatible with PostgreSQL 16 and 17.

TRAKTOR revisited

Working on TRAKTOR again. The good news is, it still works with PostgreSQL 17.x and I have completely replaced psycopg2 with pg8000 to remove all native dependencies. The bad news is, if you don't want to run the arbiter as superuser it's a complicated dance of permissions, some of which can only be GRANTed by a superuser, and I have to find a way to automate this as far as possible.

TRAKTOR, protection for tables in a replicaset

Altering or dropping tables which are in logical replication is not a good idea if the changes are not uniform across a TRAKTOR cluster. So, TABLEs in a replicaset are now protected against DROP TABLE and ALTER TABLE by default using PostgreSQL event triggers.

TRAKTOR, a native trigger function for the fearless

TRAKTOR uses a trigger to break replication cycles on PostgreSQL servers < 16.x. By default, the trigger function tf_break_cycle() is implemented in pl/pgSQL. But now, if you are fearless, there is a native replacement written in C available for pedal-to-the-metal performance.

TRAKTOR: Towards the cloud

TRAKTOR now has the capability to analyze the PostgreSQL server logs through file_fdw or log_fdw, without requiring direct access to the server filesystem any more.

This enables it to work with managed PostgreSQL like AWS RDS and Aurora.

File_fdw and log_fdw seem to be lacking from Azure Database for PostgreSQL.

TRAKTOR, true multimaster replication for PostgreSQL

Hi all,

after the retirement of pgchem::tigress, I stumbled over this Blog post, that showed a method to break the vicious replication cycle when using PostgreSQL logical replication in a multimaster cluster, i.e. all nodes are readers and writers.

For PostgreSQL 16.x, this is not necessary anymore, since it introduced origin=NONE, but for pre-16.x,it works quite well.

Yet, setting up a multimaster cluster is tedious and error prone, so I decided to start a new endeavour and make it easier (that was well before the introduction of pgEdge or pgactive).

So without much furter ado, TRAKTOR was released today. With the help of TRAKTOR, you can set-up true multimaster replication clusters on top of vanilla PostgreSQL servers. Notable features are:

1. Does not need anything beyond a standard PostgreSQL server. No fork, no extension.
2. Shared nothing architecture. No single point of failure,
3. Can automatically heal conflicts in case of split brain situations.
4. REST API for control and monitoring.
5. Works with extensions and custom datataypes, PostGIS and rdkit have been tested.

It does NOT help with designing a robust logical multimaster model! No fancy CRDT datatypes, no vector clocks. And it lacks a comprehensive user's guide yet, but there is a tutorial to get you started.

Static code analysis in PostgreSQL like ORACLE has.

Out of the box, PostgreSQL lacks static code analysis at compile time like ORACLE can do.

plpgsql_check provides this capability (and a profiler), but needs to be called manually. So I tried to emulate ORACLE's behavior with an event trigger.

The plpgsql_compile_check extension is experimental. You MUST preload plpgsql and plpgsql_check with shared_preload_libraries='plpgsql,plpgsql_check' in postgresql.conf, otherwise strange things happen!

How to build RDKit 2023 on Windows w/o Conda

It looks like the build instructions for RDKit on Windows have not been updated for some time, at least they did not work for me. So I dug out the correct build process out of the Conda builds:

General instructions:

https://github.com/rdkit/rdkit/blob/master/Docs/Book/Install.md

Required to run the binaries, IF you don't have the Visual Studio C++ compiler and SDK installed:

Visual Studio 2015, 2017, 2019 and 2022 redistributable

https://learn.microsoft.com/en-us/cpp/windows/latest-supported-vc-redist?view=msvc-170

Development environment:

Windows 11 x64

Microsoft Visual Studio 2022 (Community Edition or Professional)

Windows SDK version 10.0.22000.0

Compiler MSVC 19.35.32217.1

PowerShell

Directory structure:

c:\Devel\RDBuild

boost
cairo
eigen3
freetype
RDKit
zlib

RDBASE = C:\Devel\RDBuild\RDKit

RDKit source 2023_03_1:

https://codeload.github.com/rdkit/rdkit/zip/refs/tags/Release_2023_03_1

ZLib 1.2.13:

https://github.com/kiyolee/zlib-win-build

Eigen 3.4.0:

https://gitlab.com/libeigen/eigen/-/archive/3.4.0/eigen-3.4.0.zip

Cairo 1.17.2:

https://github.com/preshing/cairo-windows/releases

Boost 1.82.0:

https://sourceforge.net/projects/boost/files/boost-binaries/

freetype 2.11.1:

https://codeload.github.com/ubawurinna/freetype-windows-binaries

CMake 3.26.3:

https://github.com/Kitware/CMake/releases/download/v3.26.3/cmake-3.26.3-windows-x86_64.msi

PostgreSQL 15.2.1:

https://get.enterprisedb.com/postgresql/postgresql-15.2-1-windows-x64-binaries.zip

Python 3.10.11:

https://www.python.org/downloads/release/python-31011/

Build commands:

1.) Prepare for DLLs and Python package:

c:/cmake/bin/cmake -DRDK_BUILD_PYTHON_WRAPPERS=ON -DBOOST_ROOT=C:/Devel/RDBuild/boost -DRDK_BUILD_CAIRO_SUPPORT=ON -DRDK_BUILD_INCHI_SUPPORT=ON -DRDK_BUILD_AVALON_SUPPORT=ON -DRDK_BUILD_PGSQL=OFF -DPostgreSQL_ROOT="C:\PostgreSQL\15" -DRDK_INSTALL_INTREE=OFF -DCMAKE_INSTALL_PREFIX=c:/RDKit -DEIGEN3_INCLUDE_DIR=C:/Devel/RDBuild/eigen3 -DFREETYPE_INCLUDE_DIRS=c:/Devel/RDbuild/freetype/include -DFREETYPE_LIBRARY="c:/Devel/RDBuild/freetype/release dll/win64/freetype.lib" -DZLIB_INCLUDE_DIR=c:/Devel/RDBuild/zlib/include -DZLIB_LIBRARY=c:/Devel/RDBuild/zlib/libz.lib -DCAIRO_INCLUDE_DIRS=c:/Devel/RDBuild/cairo/include -DCAIRO_LIBRARIES=c:/Devel/RDBuild/cairo/lib/x64/cairo.lib -DRDK_BUILD_FREETYPE_SUPPORT=ON -DRDK_BUILD_COMPRESSED_SUPPLIERS=ON -DRDK_OPTIMIZE_POPCNT=ON -DRDK_INSTALL_STATIC_LIBS=OFF -DRDK_INSTALL_DLLS_MSVC=ON -DCMAKE_BUILD_TYPE=Release -DRDK_BUILD_THREADSAFE_SSS=ON -G"Visual Studio 17 2022" -A x64 ..

2.) Build & install:

C:\CMake\bin\cmake --build . --config=Release --target install

3.) Prepare for static libraries and PostgreSQL extension:

c:/cmake/bin/cmake -DRDK_BUILD_PYTHON_WRAPPERS=OFF -DBOOST_ROOT=C:/Devel/RDBuild/boost -DRDK_BUILD_CAIRO_SUPPORT=ON -DRDK_BUILD_INCHI_SUPPORT=ON -DRDK_BUILD_AVALON_SUPPORT=ON -DRDK_BUILD_PGSQL=ON -DPostgreSQL_ROOT="C:\PostgreSQL\15" -DRDK_INSTALL_INTREE=OFF -DCMAKE_INSTALL_PREFIX=c:/RDKit -DEIGEN3_INCLUDE_DIR=C:/Devel/RDBuild/eigen3 -DFREETYPE_INCLUDE_DIRS=c:/Devel/RDbuild/freetype/include -DFREETYPE_LIBRARY="c:/Devel/RDBuild/freetype/release dll/win64/freetype.lib" -DZLIB_INCLUDE_DIR=c:/Devel/RDBuild/zlib/include -DZLIB_LIBRARY=c:/Devel/RDBuild/zlib/libz.lib -DCAIRO_INCLUDE_DIRS=c:/Devel/RDBuild/cairo/include -DCAIRO_LIBRARIES=c:/Devel/RDBuild/cairo/lib/x64/cairo.lib -DRDK_BUILD_FREETYPE_SUPPORT=ON -DRDK_BUILD_COMPRESSED_SUPPLIERS=ON -DRDK_OPTIMIZE_POPCNT=ON -DRDK_INSTALL_STATIC_LIBS=ON -DRDK_INSTALL_DLLS_MSVC=OFF -DCMAKE_BUILD_TYPE=Release -DRDK_BUILD_THREADSAFE_SSS=ON -G"Visual Studio 17 2022" -A x64 ..

4.) Build & install:

C:\CMake\bin\cmake --build . --config=Release --target install

Usage:

If you want to use the PostgreSQL extension, it needs rdkit.dll, which is automatically copied to the PostgreSQL /lib directory BUT also freetype.dll, and boost_serialization-vc142-mt-x64-1_82.dll. The easiest way is to copy them to the PostgreSQL /lib directory AND set the PATH, e. g. $env:PATH+=';C:\PostgreSQL\15\lib'. You also need to define RDBASE, e. g.  $env:RDBASE='c:\RDKit'. Start PostgreSQL and 'CREATE EXTENSION IF NOT EXISTS rdkit;' should work.

If you want to use the Python package, you must point PYTHONPATH to the RDKit installation directory AND for Python < 3.8 add <where the dlls live> to the PATH OR for Python >= 3.8 add the DLL path explicitly with:

os.add_dll_directory(<where the DLLs live>)

In addition to the RDKit DLLs, freetype.dll, cairo.dll, libz.dll, boost_serialization-vc142-mt-x64-1_82.dll, boost_bzip2-vc143-mt-x64-1_82.dll, boost_iostreams-vc143-mt-x64-1_82.dll, boost_python310-vc143-mt-x64-1_82.dll, and boost_zlib-vc143-mt-x64-1_82.dll must be present.

Result:

• C++ static libraries
• C++ shared libraries
• PostgreSQL extension
• Python package

The BfArM database of essential drugs in short supply is lacking an API. So I built one.

The BfArM database of essential drugs in short supply is lacking an API. So I implemented one in about 12 hours. The source code can be found on GitHub.

tl;dr 

The state of digitalization in Germany is in dire straits, especially so when looking at the healtcare system and govenment/administration. If APIs exist, they are often difficult to discover and/or undocumented (The private bund.dev project tries to collect and document them in a central repository).

Yet I was surprised when I, inspired by an an article about the shortage of essential drugs in Germany, took a closer look at the official governmental database on this matter.

This database is hosted by the "Bundesinstitut für Arzneimittel und Medizinprodukte (BfArM)", and can be found here.

It can be accessed in two ways:

1. As filterable dynamic HTML/JavaScript table rendered using JSF.
2. As CSV download.

No API for M2M communication or the like. At least I could not find one. There is also no documentation about the data itself. 

Regarding data quality, I noticed the following issues:

1. The CSV file is encoded in ISO-8859-1 (Latin1) and not UTF-8. While this is not uncommon it is a bit unexpected, since ISO-8859-1 only covers the first 256 Unicode characters. The file encoding is not documented.
2. The CSV is actually not comma, but semicolon separated.
3. Data not available is not only NULL, it is also encoded as "N/A", "n.a.", "-", and "'-", respectively. There might me more undocumented encodings.
4. "*" encodes "Altdatenübernahme war nicht möglich", meaning that older data could not be transferred. This is documented in the legend of the table, but not what it actually means.
5. The update frequency of the data on display is not documented.

Having worked with databases for about 30 years now, this looks like this data comes directly from some kind of manually curated data set to me. There is obviously no decent data standardization process in place.

But whining alone doesn't help, so I decided to implement the missing API on a tiny server hosted in Germany. It took me about 12 hours of my private time, including implementing basic data sanitization.

The most difficult part was to automate the CSV download, since the submit button calls some JavaScript function, and thus can't be called using a HTTP request or a scraping library like beautifulsoup. I'm now using a remote controlled headless Browser via selenium. That the HTML name attribute frequently changes does not especially help, either. This has been solved with an XPATH expression on the value.

The demo API is available under https://3.73.42.17:8443/docs. You will be warned because of the self-signed SSL certificate. This is ok, AWS did not want to register a domain, so no Let's Encrypt. But this just swaps SSL with SSH semantics anyway. Since it is for demonstration purposes only, and runs on a small server, there is a rate limiter in place. Resource names and data are in German, like in the source system.

The source code can be found on GitHub. Maybe somebody at BfArM realizes that it does not cost a fortune to implement an API on top of what they already have, and finds my example useful to build on.

Public data (I assume it is public, there is no need to register) is updated daily at 11:00 UTC. In complicance with Article 4 of the GDPR, personal information (Client IP address, Telephone number and E-Mail address) is not stored or displayed. As mentioned before, the API is hosted in Germany.

I'm not intending to run this forever, and outages are possible at any time. I have shut down the service by now.

pg_sentinel - Update

In 2016 I released pg_sentinel as a proof-of-concept for implementing a sentinel value sensor deep in the PostgreSQL sever. This does not compile since PostgreSQL >= 12.x because of changes in the internal API. So I adapted my old code to make it work again.

As a bonus, it does not need SPI any more.

After 18 years, pgchem::tigress retires

To whom it may concern.

Today I will retire pgchem::tigress, the PostgreSQL chemoinformatics extension based on OpenBabel, after 18 years of service. This decision is based on three main reasons:

1. I have not touched the GIST-Index Code for at least eight years, but beginning with PostgreSQL 14.x it started to cause SIGSEVs when building the index on molecules, and I'm unable to find the cause.
2. OpenBabel 3.x made changes in their API that would require me to rewrite functions or to disable them. And those changes are not very well documented.
3. Since my recent brush with death, I have decided that there are better ways to spend my time, than chasing Signal 11s. Especially since the RDKit cartridge has come a long way, and is more powerful than pgchem::tigress ever was.

This decision was not easy, since building pgchem::tigress was a part of my life. It was the first open source ever released by Bayer AG (at least in Germany). It also is the foundation of my PhD thesis. 

The code will remain public as long as there is a way to publish it.

Native (PostgreSQL only) streaming data tables

If you want to see (and analyze) only a window of data over some continuous data stream in PostgreSQL, one way is to use a specialized tool like the PipelineDB extension. But if you can't do that, e.g. because you are stuck with AWS RDS or for some other reason, streaming data tables, or continuous views, can be implemented with pretty much PostgreSQL alone.

The basic idea is to have a table that allows for fast INSERT operations, is aggressively VACUUMed, and has some key that can be used to prune outdated entries. This table is fed with the events from the data stream and regularly pruned. Voilà: a streaming data table.

We have done some testing with two approaches on an UNLOGGED table, prune on every INSERT, and pruning at reqular intervals. UNLOGGED is not a problem here, since a view on a data stream can be considered pretty much as ephemeral.

The timed variant is about 5x - 8x faster on INSERTs. And if you balance the timing and the pruning interval right, the window size is almost as stable.

The examples are implemented in Python3 with psycopg2. Putting an index on the table can help or hurt performance, INSERT might get slower but pruning with DELETE faster, depending on the size and structure of the data. Feel free to experiment. In our case, a vanilla BRIN index did just fine.

Instead of using an external scheduler for pruning, like the Python daemon thread in the stream_timed_cleanup.py example, other scheduling mechanisms can be of course used, e.g. pg_cron, or a scheduled Lambda on AWS, or similar.

Feel free to experiment and improve...

MQTT as transport for PostgreSQL events

MQTT has become a de-facto standard for the transport of messages between IoT devices. As a result, a plethora of libraries and MQTT message brokers have become available. Can we use this to transport messages originating from PostgreSQL?

Aa message broker we use Eclipse Mosquitto which is dead simple to set up if you don't have to change the default settings. Such a default installation is neither secure nor highly available, but for our demo it will do just fine. The event generators are written in Python3 with Eclipse paho mqtt for Python.

There are at least two ways to generate events from a PostgreSQL database, pg_recvlogical and NOTIFY / LISTEN. Both have their advantages and shortcomings.

pg_recvlogical:

• Configured on server and database level
• Generates comprehensive information about everything that happens in the database
• No additional programming neccessary
• Needs plugins to decode messages, e.g. into JSON
• Filtering has to be done later, e.g. by the decoder plugin

NOTIFY / LISTEN:

• Configured on DDL and table level
• Generates exactly the information and format you program into the triggers
• Filtering can be done before sending the message
• Needs trigger programming
• The message size is limited to 8000 bytes

Examples for both approaches can be found here. The NOTIFY / LISTEN example lacks a proper decoder but this makes be a good excercise to start with. The pg_recvlogical example needs the wal2json plugin, which can be found here and the proper setup, which is also explained in the Readme. Please note, that the slot used in the example is mqtt_slot, not test_slot:

pg_recvlogical -d postgres --slot mqtt_slot --create-slot -P wal2json

Otherwise, setup.sql should generate all objects to run both examples.

It looks like pgchem::tigress just got a major upgrade

With the Release of PostgreSQL 12.x and OpenBabel 3.x, I decided to see if pgchem::tigress would still compile. Well, it took some minor changes, but YES, it does!

And - it seems like OpenBabel now handles E/Z and enantiomer stereochemistry correctly, at least in SMILES notation. This is a major step forward, but I have to do some more checks before the next release...

Authenticate PostgreSQL users against the Amazon AWS Cognito service

I was asked recently if PostgreSQL could authenticate login users against AWS Cognito.  Since PostgreSQL allows PAM authentication, I was pretty sure it could.

But an (admittedly not exhaustive) search on the web did not produce any PAMs for Cognito.

So I wrote one, using pam-python, boto3, warrant and pyJWT:

cognito_PAM.py

It is designed primarily for PostgreSQL and pgbouncer, so it only supports pam_sm_authenticate and pam_sm_acct_mgmt, and all the work is done in pam_sm_authenticate. Because calling Cognito is comparatively slow, I didn't want to call it twice.

The necessary pam.d config is:

#%PAM-1.0
# Information for PostgreSQL process with the 'pam' option.
auth required  pam_python.so cognito_PAM.py aws_region user_pool_id client_id 
account required pam_python.so cognito_PAM.py

If you use PAM authentication, passwords are sent in cleartext, so transport layer encryption, e.g. SSL/TLS, between client and server becomes mandatory!

I think it does the correct dance of authentication with Cognito and supports USER_SRP_AUTH, but if you see any problem, please raise a paw.

Excel and ODF support for cloudfs_fdw

cloudfs_fdw now supports .xls (Excel 97-2003), .xlsx, and .ods (Open Document Format) Spreadsheets via pandas, xlrd, and odfpy. It requires pandas >= 1.0.1, so Multicorn must be compiled against Python 3.

Since pandas provides sorting and filtering capabilities, cloudfs_fdw tries to push down SQL qualifiers and sort keys when they can be translated into pandas notation.

Take a look and have fun.

cloudfs_fdw

Since I needed a Foreign Data Wrapper for files stored on S3, and the ones I found did things like loading the whole file in memory before sending the first rows, I wrote my own, using Multicorn.

Along the way, I discovered libraries like smart-open and ijson that allow to stream various file formats from various filesystems - and so this escalated a bit, into cloudfs_fdw.

It currently supports CSV and JSON files from S3, HTTP/HTTPS sources and local or network  filesystems but since smart-open supports more than that (e.g. HDFS, SSH), it certainly can be extended if needed.

For now, have fun.

Not all CASTs are created equal?

Can somebody explain this?

[Solved: See the comments section]

PostgreSQL 11.2.

The documentation says:

"A type cast specifies a conversion from one data type to another. PostgreSQL accepts two equivalent syntaxes for type casts:

CAST ( expression AS type )

expression::type

The CAST syntax conforms to SQL; the syntax with :: is historical PostgreSQL usage."

But when I test the lower limits of PostgreSQL's integer types, strange things happen.

select cast(-9223372036854775808 as bigint);
select cast(-2147483648 as integer);
select cast(-32768 as smallint);

All OK.

select -9223372036854775808::bigint;
select -2147483648::integer;
select -32768::smallint;

All fail with SQL Error [22003]: ERROR: out of range

But:

select -9223372036854775807::bigint;
select -2147483647::integer;
select -32767::smallint;

All OK.

???

The Hare and the Hedgehog. Muscle, brain - or both?

In the famous fairy tale the hedgehog wins the race against the hare because he uses his brain to outwit the much faster hare: Brain beats muscle. But is that always the case? And what if we combine the two virtues?

The case at hand: Screening large sets of molecules for chemical simliarity.

Since (sub)graph isomorphism searching faces some mathematical challenges because of nonpolynomial O - even if you can use a specialized index, like pgchem::tigress does - fast similarity searching based on binary fingerprints has gained popularity in recent years.

I was tasked with evaluating a solution to the problem of similarity screening large sets of molecules with PostgreSQL where the fingerprints are generated externally, e.g. with the CDK.

This is, what I came up with...

Preparing the Racetrack

CREATE TABLE cdk.externalfp (
id int4 NOT NULL,
smiles varchar NOT NULL,
pubchemfp varbit NULL,
"cardinality" int4 NULL,
CONSTRAINT externalfp_pk PRIMARY KEY (id)
);

Above is the table definition of the final table. The cardinality column will be not used now, but since it is calculated by the fingerprint generator anyway, keeping it will save some work later. If you want to copy my example code 1:1, please use a database named chemistry and a schema named cdk.

First we need to load some data into the table. I used the free NCISMA99 dataset  from the National Cancer Institute, containing 249081 chemical structures in SMILES notation.

COPY cdk.externalfp (id, smiles) FROM '/tmp/NCISMA99' 
WITH (DELIMITER ' ', HEADER false, FORMAT csv);

And a few seconds later you should have 249081 rows in the table. Now we need to generate the fingerprints. The generator code is here, additionally you need the CDK 2.2 and a PostgreSQL JDBC driver. After changing the code to reflect your JDBC URL you are good to go.

Running the FingerprintGenerator should show no errors and takes about 30 Minutes on my Core i5 Linux Notebook. The fingerprint used is the PubChem fingerprint as described here.
Now we can put an index on the cardinality column (also used later) and are all set.

CREATE INDEX externalfp_cardinality_idx ON cdk.externalfp USING btree (cardinality);

Almost...

The function to calculate the similarity measure is still missing. We use the Tanimoto coefficient, as it is widely used and fairly easy to understand. The Tanimoto coefficient over PostgreSQL BIT VARYING can thus be written in pure SQL as:

CREATE OR REPLACE FUNCTION cdk.tanimoto(bit varying, bit varying)
 RETURNS real
 LANGUAGE sql
 IMMUTABLE STRICT SECURITY INVOKER LEAKPROOF
AS $function$
select length(replace(($1 & $2)::text, '0', ''))::real / length(replace(($1 | $2)::text, '0', ''))::real;
$function$;

Please note that the required bitcount function on BIT VARYING is emulated by removing all 0s and measuring the length of the remaining string, containing all 1s.

The Baseline. No brain, no muscles

For the first naive test, we run FindBySimilarity with the following inputs:

SMILES: CC(=O)OC1=CC=CC=C1C(=O)O
Threshold: 0.9
top N: 10

which gives the following plan from EXPLAIN ANALYZE:

Limit  (cost=14515.22..14516.38 rows=10 width=77) (actual time=6436.022..6436.621 rows=10 loops=1)                                         
  ->  Gather Merge  (cost=14515.22..22587.95 rows=69190 width=77) (actual time=6436.021..6436.618 rows=10 loops=1)                         
        Workers Planned: 2                                                                                                                 
        Workers Launched: 2                                                                                                                
        ->  Sort  (cost=13515.19..13601.68 rows=34595 width=77) (actual time=6432.534..6432.535 rows=8 loops=3)                            
              Sort Key: (((length(replace((('1100000001110000001110000000000000000000000000000000000000000000000000000000000000000000000000
              Sort Method: top-N heapsort  Memory: 27kB                                                                                    
              Worker 0:  Sort Method: quicksort  Memory: 27kB                                                                              
              Worker 1:  Sort Method: top-N heapsort  Memory: 27kB                                                                         
              ->  Parallel Seq Scan on externalfp  (cost=0.00..12767.61 rows=34595 width=77) (actual time=41.329..6432.411 rows=30 loops=3)
                    Filter: (((length(replace((('110000000111000000111000000000000000000000000000000000000000000000000000000000000000000000
                    Rows Removed by Filter: 82997                                                                                          
Planning Time: 0.169 ms                                                                                                                    
Execution Time: 6436.648 ms                                                                                                                                                                                                                                                                                                                           
Including retrieval, this plan leads to an overall response time of about 14 seconds.

First race. Introducing the Hedgehog

An index could be helpful, but can we build one without major programming effort? Yes, due to the work of S. Joshua Swamidass and Pierre Baldi. In their 2007 paper "Bounds and Algorithms for Fast Exact Searches of Chemical Fingerprints in Linear and Sub-Linear Time", they found ways to calculate upper and lower bounds on the cardinality of fingerprints necessary to meet a given similarity once the cardinality of the search fingerprint is known.

The paper covers these calculations for various similarity measures. For Tanimoto it is:

min_cardinality_of_target = floor(cardinality_of_search_argument * similarity_threshold)

and 

max_cardinality_of_target = ceil(cardinality_of_search_argument / similarity_threshold)

The function swamidassBaldiLimitsForTanimoto() in FindBySimilarity calculates those bounds and if you change:

//int[] lohi = swamidassBaldiLimitsForTanimoto(fp.cardinality(), threshold);

int[] lohi = {0, Integer.MAX_VALUE};

to

int[] lohi = swamidassBaldiLimitsForTanimoto(fp.cardinality(), threshold);

//int[] lohi = {0, Integer.MAX_VALUE};

they will be used. Now the index we already put on the "cardinality" column makes sense, allowing the database to filter out impossible candidates before invoking the tanimoto function.

For CC(=O)OC1=CC=CC=C1C(=O)O, the fingerprint has a cardinality of 115, which gives an upper bound of 128 and a lower bound of 103 bits. All fingerprints with cardinalities outside that bounds can be safely ignored since they cannot yield a Tanimoto coefficient >= 0.9.

Now the plan becomes:

Limit  (cost=10445.68..10446.85 rows=10 width=77) (actual time=1492.430..1495.552 rows=10 loops=1)                                                           
  ->  Gather Merge  (cost=10445.68..12328.11 rows=16134 width=77) (actual time=1492.429..1495.548 rows=10 loops=1)                                           
        Workers Planned: 2                                                                                       
        Workers Launched: 2                                                                                                                                  
        ->  Sort  (cost=9445.66..9465.82 rows=8067 width=77) (actual time=1489.566..1489.567 rows=7 loops=3)                                                 
              Sort Key: (((length(replace((('1100000001110000001110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
              Sort Method: top-N heapsort  Memory: 27kB                                                                                                      
              Worker 0:  Sort Method: top-N heapsort  Memory: 27kB                                                                                           
              Worker 1:  Sort Method: top-N heapsort  Memory: 27kB                                                                                           
              ->  Parallel Bitmap Heap Scan on externalfp  (cost=826.09..9271.33 rows=8067 width=77) (actual time=22.032..1489.502 rows=30 loops=3)          
                    Recheck Cond: ((cardinality >= 103) AND (cardinality <= 128))                                                                            
                    Filter: (((length(replace((('110000000111000000111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                    Rows Removed by Filter: 19303                                                                                                            
                    Heap Blocks: exact=1928                                                                                                                  
                    ->  Bitmap Index Scan on externalfp_cardinality_idx  (cost=0.00..821.25 rows=58083 width=0) (actual time=5.238..5.238 rows=58000 loops=1)
                          Index Cond: ((cardinality >= 103) AND (cardinality <= 128))                                                                        
Planning Time: 0.166 ms                                                                                                                                      
Execution Time: 1495.587 ms                                                                                                                                                             

Including retrieval, this plan gives us now an overall response time of about 3 seconds, or 4.6 times faster.

Second race. Introducing the Hare

Time to pull out the big guns. The tanimoto calculation in SQL is apparently slow, primarily because PostgreSQL is lacking a native bit count function for BIT VARYING, so this must be emulated using binary string replace() and length().

However, we can build one in C. Since counting bits is a simple operation for a microprocessor (Actually, it is an art in itself. See Andrew Dalke's popcount benchmark for many different ways to count bits.), a C function should perform much better.

After you installed tanimoto.c, changed the tanimoto function calls in the SQL in FindBySimilarity to tanimoto_c, and disabled the Swamidass/Baldi indexing, we see the raw power of a native function.

The plan now becomes:

Limit  (cost=10363.85..10365.02 rows=10 width=77) (actual time=45.829..48.101 rows=10 loops=1)                                         
  ->  Gather Merge  (cost=10363.85..18436.58 rows=69190 width=77) (actual time=45.827..48.097 rows=10 loops=1)                         
        Workers Planned: 2                                                                                                             
        Workers Launched: 2                                                                                                            
        ->  Sort  (cost=9363.83..9450.32 rows=34595 width=77) (actual time=43.667..43.668 rows=8 loops=3)                              
              Sort Key: (tanimoto_c('11000000011100000011100000000000000000000000000000000000000000000000000000000000000000000000000000
              Sort Method: top-N heapsort  Memory: 27kB                                                                                
              Worker 0:  Sort Method: top-N heapsort  Memory: 27kB                                                                     
              Worker 1:  Sort Method: top-N heapsort  Memory: 27kB                                                                     
              ->  Parallel Seq Scan on externalfp  (cost=0.00..8616.24 rows=34595 width=77) (actual time=0.095..43.559 rows=30 loops=3)
                    Filter: (tanimoto_c('1100000001110000001110000000000000000000000000000000000000000000000000000000000000000000000000
                    Rows Removed by Filter: 82997                                                                                      
Planning Time: 0.062 ms                                                                                                                
Execution Time: 48.145 ms     


Overall response is 0.128 seconds, or 110 times faster.

Muscle beats brain. At least here.

Third race. Relay

But if we enable the Swamidass/Baldi index again and keep the native Tanimoto function, the real magic happens.

The final plan:

Limit  (cost=9427.54..9427.56 rows=10 width=77) (actual time=35.567..35.570 rows=10 loops=1)                                                           
  ->  Sort  (cost=9427.54..9475.94 rows=19361 width=77) (actual time=35.566..35.566 rows=10 loops=1)                                                   
        Sort Key: (tanimoto_c('110000000111000000111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
        Sort Method: top-N heapsort  Memory: 26kB                                                                                                      
        ->  Bitmap Heap Scan on externalfp  (cost=826.09..9009.15 rows=19361 width=77) (actual time=5.404..35.459 rows=90 loops=1)                     
              Recheck Cond: ((cardinality >= 103) AND (cardinality <= 128))                                                                            
              Filter: (tanimoto_c('11000000011100000011100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
              Rows Removed by Filter: 57910                                                                                                            
              Heap Blocks: exact=6801                                                                                                                  
              ->  Bitmap Index Scan on externalfp_cardinality_idx  (cost=0.00..821.25 rows=58083 width=0) (actual time=4.307..4.307 rows=58000 loops=1)
                    Index Cond: ((cardinality >= 103) AND (cardinality <= 128))                                                                        
Planning Time: 0.149 ms                                                                                                                                
Execution Time: 35.641 ms                                                                                                                                                                                                                                          
                                                                                                       
Final overall response now 0.04 seconds, or 350 times faster!

Muscle + brain: unmatched.

Conclusion

Sometimes the Hare wins, sometimes the Hedgehog does. Always attack nontrivial optimization problems from different angles and experiment, experiment, experiment.

While C largely outperforms the index in this case, it's still good to know both, because using native functions is not always possible, e.g. on an AWS RDS instance. Then, 4.6x faster is better than nothing.

PostgreSQL needs a native builtin function for counting bits in BIT VARYING. Since fingerprint screening can be used not only for chemical structures, but for virtually every complex data that can be broken down into binary features, this would be ever so useful.

Blockchain Soccer

A opinion piece - published on medium:

https://medium.com/@ernst.georg.schmid/blockchain-soccer-869a45a8077b