high-dimensional knn-GIST tests (was Re: Cube extension kNN support)

On 9/22/13 4:38 PM, Stas Kelvich wrote:
> Hello, hackers.
>
> Here is the patch that introduces kNN search for cubes with
> euclidean, taxicab and chebyshev distances.

Thanks for this! I decided to give the patch a try at the bleeding edge
with some high-dimensional vectors, specifically the 1.4 million
1000-dimensional Freebase entity vectors from the Google 'word2vec' project:

https://code.google.com/p/word2vec/#Pre-trained_entity_vectors_with_Freebase_naming

Unfortunately, here's what I found:

* with 1000-dimensional vectors, the index size on disk grows to many
times (1000x or more) the size of the indexed data, making other tests
of the index's helpfulness impractical. (Perhaps, other parameter-tuning
can help?)

* with 500-dimensional or 100-dimensional vectors, the index size is
more manageable -- 2x to 6x the data size -- but using the index
significantly hurts performance on top-10 nearest-neighbor searches,
making it much slower than a full table scan. (The planner still tries
to use the index, even though it's hurting.)

Much more detail for the curious is below...

Regarding the dataset & hoped-for results:

The word2vec project's example scripts do their synonym/analogy
demonstrations by loading the entire 5GB+ dataset into main memory
(~3min), do a full scan of all vectors (~40sec) to find those nearest a
target vector.

My motivating question was: could the data be loaded to Postgresql using
the cube type, and kNN-GIST indexed using this patch, then do speedy
index-assisted ranked-nearest-neighbor queries from the database?

(While the patch's distance_euclid is not the same cosine-distance the
word2vec examples use, the freebase entity vectors are all unit vectors,
and even additions of vectors can be scaled to unit length. My intuition
is that euclidean-distances on the unit sphere will be in the same rank
order as cosine-distance, so the cube distance_euclid/<-> should enable
the same sort of synonym/analogy demos.)

Regarding the 1000-dimensional case:

It was necessary to change three compiled-in implementation limits. In
the four steps that the need for change became evident:

(1) in contrib/cube/cubedata.h, increase CUBE_MAX_DIM (to accept vectors
with more than 100 dimensions)

(2) in src/include/pg_config.h, increase BLCKSZ to 16384 (otherwise 1000
64-bit floats in a single column gave an <ERROR: row is too big>,
mentioning the 8160 limit - large cube values not TOASTable?)

(3) in src/include/access/itup.h, increase INDEX_SIZE_MASK to 0x3fff
(otherwise encountering an <ERROR: index row requires 16016 bytes,
maximum size is 8191> when attempting to create the index>

(4) in src/include/pg_config.h, again increase BLCKSZ now to 32768
(otherwise encountering an <ERROR: index row size 16416 exceeds maximum
5440 for index "pg_class_relname_nsp_index"> when attempting to create
the index>

With the cube-kNN patch applied and these other changes, I was able to
import the 1.4M freebase vectors and do a full-scan nearest-neighbors
query. (My starting postgresql codebase was the github mirror of 9.4dev
as of about a week ago.)

The psql transcript:

word2vec=# \timing
Timing is on.
word2vec=# CREATE EXTENSION cube;
CREATE EXTENSION
Time: 42.141 ms
word2vec=# CREATE TABLE word2vec ( word varchar(200), vec cube );
CREATE TABLE
Time: 8.532 ms
word2vec=# COPY word2vec FROM PROGRAM 'zcat
/tmp/pgvectors/freebase-vectors-skipgram1000.pgtxt.gz';
COPY 1422903
Time: 12399065.498 ms
word2vec=# SELECT word, dist FROM (SELECT word,
distance_euclid(vec,(SELECT vec FROM word2vec WHERE word='geoffrey
hinton')) AS dist FROM word2vec) AS subquery ORDER BY dist LIMIT 11;
word | dist
-------------------------+------------------
geoffrey hinton | 0
marvin minsky | 1.03892498287268
paul corkum | 1.05221701690288
william richard peltier | 1.06244397334495
brenda milner | 1.06387762685894
john charles polanyi | 1.07444446452295
leslie valiant | 1.07735786596934
hava siegelmann | 1.08148623006629
hans moravec | 1.0862034591185
david rumelhart | 1.08748431130477
godel prize | 1.08774264379264
(11 rows)

Time: 310753.976 ms

That's 3.5 hours to do the import and 5 minutes to do the query; this is
on a 2009 MacBook Pro with 8GB RAM and SSD.

Confirming the intuition above, these 10-nearest are the same entities
in the same order as on the word2vec project page's example output,
though the euclidean distances are of course different than the cosine
distances.

The DATA directory is 23GB after the import of 1.4 million rows. In the
word2vec uncompressed binary format, this dataset is about 5.4GB, so
this word2vec-table cube-column representation involves about 4X expansion.

So, to the main question: can that query be sped up by building a
kNN-GIST index? Here the problems start.

word2vec=# CREATE INDEX word2vec_index ON word2vec USING gist (vec);

This attempt ran for hours, consuming another 80GB+ before failing due
to disk full.

In fact, the largest table with 1000-dimensional vectors for which I was
able to build a gist index was a mere 100 rows. That index-build took
about 14 minutes and grew the DATA directory like so:

73MB pgdata # empty word2vec table
75MB pgdata # after COPY FROM of 100 vectors
8.4GB pgdata # after CREATE INDEX

Of course with just 100 rows the index isn't practically needed or
helpful for query speed-up.

Even trying just 500 rows, the CREATE INDEX command ran for hours before
failing by consuming all available disk space (about 90GB more). It
seems the knn-GIST index overhead for 1000-dimensional cubes grows
faster than linearly in the number of rows.

I was able to complete index builds with fewer dimensions.

100-dimensions, most-frequent 850K entities:

The dataset was trimmed to the first (most-frequent) 850K entities and
each vector truncated to its first 100-dimensions. (Even though this
would fit in the usual CUBE_MAX_DIM/BLCKSZ/INDEX_SIZE_MASK limits, I
still used the customized build with limits expanded for the 1000d-case.)

Observed data sizes and operation times were:

73MB pgdata # empty word2vec table
2.6GB pgdata # after COPY FROM of 850K vectors, taking 216s

before indexing:
nearest-11 by distance_euclid(): ~2s
nearest-11 by <-> operator: ~2s

5.0GB pgdata # after CREATE INDEX, taking 1344s

after indexing:
nearest-11 by distance_euclid(): ~2s
nearest-11 by <-> operator: ~57s # "Index Scan using word2vec_index…"

So the availability of the index causes a significant slowdown... and
the planner does not learn to choose the faster full sequential-scan.

500-dimensions, most-frequent 100K entities:

The dataset was trimmed to the first (most-frequent) 100K entities and
each vector truncated to its first 500-dimensions. (Again, still using
the custom build with upped CUBE_MAX_DIM/BLCKSZ/INDEX_SIZE_MASK.)

Observed data sizes and operation times were:

73MB pgdata # empty word2vec table
1.6GB pgdata # after COPY FROM of 100K vectors, taking 266s

before indexing:
nearest-11 by distance_euclid(): ~2s
nearest-11 by <-> operator: ~2s

4.8GB pgdata # after CREATE INDEX, taking 977s

after indexing:
nearest-11 by distance_euclid(): ~2s
nearest-11 by <-> operator: ~46s # "Index Scan using word2vec_index…"

Dropping the index makes the <-> query fast again.

Open questions and tentative conclusions:

The massive knn-GIST index overhead for 1000-dimensional vectors makes
it hard to evaluate whether a fully-built index could be useful on large
datasets.

Perhaps, some aspects of the knn-GIST support implicitly assume a
low-dimensionality (2-4) in the data, and large numbers of dimensions
cause pathological index sizes?

Or, something specific about this dataset (all vectors on the unit
sphere) is a challenging case?

In the truncated 100d or 500d cases, the index can be built, but slows
rather than speeds nearest-neighbor queries that use the index.

The evaluated patch's definitions of distance_euclid and other support
function seem straightforward, and give proper results on simple test
cases... so the problem, if any, would appear to be in the general
distance-driven knn-GIST indexing and query-planning.

If there is a type of cube-type represented dimensional data where this
indexing helps, it may only be with far fewer dimensions than 100,
and/or far more rows than 100K/850K.

If a knn-GIST implementor/expert has suggestions for tuning the index
overhead and behavior -- perhaps a different penalty or picksplit
function? -- I'd be happy to try those out and report back.

Otherwise, I hope this write-up will help evaluate the patch or save
time for others tempted to try similar knn-GIST indexing of
higher-dimensional data.

- Gordon Mohr