Date: Fri, 20 Apr 2007 12:07:29 -0700
From: Andrew Lazarus <andrew@pillette.com>
Organization: Pillette Investment Management
Message-ID: <1217328326.20070420120729@pillette.com>
To: pgsql-performance@postgresql.org
Subject: index structure for 114-dimension vector
In-Reply-To: <b42b73150704181716wb1600aey8761b6793d3fd702@mail.gmail.com>
References: <b42b73150704170917n33ebcdc8wc852a3fa02fd8bb5@mail.gmail.com>
	<01db01c781e4$c700bf30$2e00a8c0@tridecap.com>
	<b42b73150704181716wb1600aey8761b6793d3fd702@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

I have a table with 2.5 million real[] arrays. (They are points in a
time series.) Given a new array X, I'd like to find, say, the 25
closest to X in some sense--for simplification, let's just say in the
usual vector norm. Speed is critical here, and everything I have tried
has been too slow.

I imported the cube contrib package, and I tried creating an index on
a cube of the last 6 elements, which are the most important. Then I
tested the 2.5MM rows for being contained within a tolerance of the
last 6 elements of X, +/- 0.1 in each coordinate, figuring that would
be an indexed search (which I CLUSTERED on). I then ran the sort on
this smaller set. The index was used, but it was still too slow. I
also tried creating new columns with rounded int2 values of the last 6
coordinates and made a multicolumn index.

For each X the search is taking about 4-15 seconds which is above my
target at least one order of magnitude. Absolute numbers are dependent
on my hardware and settings, and some of this can be addressed with
configuration tweaks, etc., but first I think I need to know the
optimum data structure/indexing strategy.

Is anyone on the list experienced with this sort of issue?

Thanks.
Andrew Lazarus  andrew@pillette.com