DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma;
	h=from:content-type:content-transfer-encoding:subject:date:message-id
	:to:mime-version:x-mailer;
	b=fstSoOfD9OnOhbN1JXXDynt6lh29HOwcmi4ghkyDLnFHOQksF0+r/GxdFC/RhOPgOc
	27QS+BxNiwRFZYkGktbC80OgUueD0aGOOJBGWFYvy72JuO8rfj8bGrWK2dT65ndPjonN
	gw7zhHY/V4X4FrThvdWWE3NHrX7triBDyIoQ0=
From: Joel Reymont <joelr1@gmail.com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: quoted-printable
Subject: optimizing a cpu-heavy query
Date: Tue, 26 Apr 2011 16:16:19 +0100
Message-Id: <FE56AC3F-6398-41FC-B9D0-B5BEF295A745@gmail.com>
To: pgsql-performance@postgresql.org
Mime-Version: 1.0 (Apple Message framework v1084)

Folks,

I'm trying to optimize the following query that performs KL Divergence =
[1]. As you can see the distance function operates on vectors of 150 =
floats.=20

The query takes 12 minutes to run on an idle (apart from pgsql) EC2 m1 =
large instance with 2 million documents in the docs table. The CPU is =
pegged at 100% during this time. I need to be able to both process =
concurrent distance queries and otherwise use the database.

I have the option of moving this distance calculation off of PG but are =
there other options?

Is there anything clearly wrong that I'm doing here?

Would it speed things up to make the float array a custom data type =
backed by C code?

	Thanks in advance, Joel

[1] http://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence

---

CREATE DOMAIN topics AS float[150];
CREATE DOMAIN doc_id AS varchar(64);

CREATE TABLE docs
(
 id      serial,
 doc_id  doc_id NOT NULL PRIMARY KEY,
 topics  topics NOT NULL
);

CREATE OR REPLACE FUNCTION docs_within_distance(vec topics, threshold =
float)=20
RETURNS TABLE(id doc_id, distance float) AS $$
BEGIN
	RETURN QUERY
   SELECT *=20
   FROM (SELECT doc_id, (SELECT sum(vec[i] * ln(vec[i] / topics[i]))=20
                     FROM generate_subscripts(topics, 1) AS i
                     WHERE topics[i] > 0) AS distance
         FROM docs) AS tab
   WHERE tab.distance <=3D threshold;
END;
$$ LANGUAGE plpgsql;


=
--------------------------------------------------------------------------=

- for hire: mac osx device driver ninja, kernel extensions and usb =
drivers
=
---------------------+------------+---------------------------------------=

http://wagerlabs.com | @wagerlabs | =
http://www.linkedin.com/in/joelreymont
=
---------------------+------------+---------------------------------------=