Re: Adding a suffix array index

On Sun, 28 Nov 2004 17:53:38 -0500, Tom Lane wrote:
>> But is it cheaper, IO-wise to "jump" around in an index than to go back
>> and forth between index and tuple blocks?
>
> Perhaps not --- but why would you be "jumping around"? Wouldn't the
> needed info appear in consecutive locations in the index?

Searching for a match, using a suffix array entails a binary search in the
suffix array (can be optimized through the use of a longest-common-prefix
helper-array). So some amount of "jumping" is needed.

Anyhow: I've given up trying to create the suffix array as a "normal"
index type. As I'm running out of time, I'm inclined to hacks. I'm
considering storing the index of a sequence in a large object which I then
store a reference to in the data item: The large object interface seems
like something I could use.

Or I might store dnaseq values as
- some meta-information, perhaps (like a hash value)
- a reference to a large object containing the sequence
- a reference to a large object containing the suffix array
- a reference to a large object containing a helper-array
(longest common prefix-information)

One problem with this approach is that the related, large objects will not
automatically be removed when a value is removed from a table (but that
could probably be somewhat fixes using a trigger). Beyond being somewhat
ugly: Is it possible?

How much of[1] is still the case today? Are today's large objects somewhat
corresponding to the article's description of "v-segments"?
The article mentions that POSTGRES supported a CREATE LARGE TYPE
construct. Am I right in assuming that today's corresponding construct is
as exemplified in the manual:
CREATE TYPE bigobj (INPUT = lo_filein, OUTPUT = lo_fileout,...)

Reference 1:
Stonebraker & Olson: Large Object Support in POSTGRES (1993)
http://epoch.cs.berkeley.edu:8000/postgres/papers/S2K-93-30.pdf

--
Greetings from Troels Arvin, Copenhagen, Denmark