Обсуждение: GiST opclass and varlena

Hi,

I'm trying to code a GiST opclass to index prefix searches (select ... from t
where t.prefix @> query), now using a prefix_range datatype. This datatype is
a varlena one, and storing it to disk and indexing it with BTrees work ok,
but I'm failing to have my GiST opclass working, here's the problem:

postgres=# create index idx_prefix on ranges using gist(prefix
gist_prefix_range_ops);
NOTICE:  gpr_picksplit(): entryvec->n= 234 maxoff= 232 l= 176 r=  56 l+r= 232
unionL='01[0-7]' unionR='01[4-7]'
NOTICE:  gpr_picksplit(): v->spl_ldatum='01[0-7]' v->spl_rdatum='01[4-7]'
ERROR:  invalid memory alloc request size 3049878020

The code is available at pgfoundry here: http://cvs.pgfoundry.org/cgi-bin/cvsweb.cgi/prefix/prefix/

The previous support for prefixes as text is still there (but will get
deprecated soon --- or so I hope), and the new datatype and its usage not
well commented nor documented currenlty. If this show up as a requirement to
get your attention, please state it and I'll work on documenting prefix_range
first.

I'm looking for some help on how to resolve the shown index creation problem,
which I think is related to how I give data to GiST in its spl_ldatum and
spl_rdatum from the user defined picksplit() method, lines 1101 and 1102 in
prefix.c (version 1.26).

Regards,
--
dim

Hello

Not so familiar with all this math :) ,but here's my solution,which I 
must admit keep things going at the moment:

db=> \d prefix                         Table "public.prefix" Column  |  Type   |                      Modifiers
           
 
----------+---------+-----------------------------------------------------id       | bigint  | not null default
nextval('prefix_id_seq'::regclass)prefix  | text    |operator | integer |
 
Indexes:   "prefix_pkey" PRIMARY KEY, btree (id)   "prefix_index" UNIQUE, btree (prefix)


and we're using a procedure to match prefices (longest prefix 
match),with simething like:

...

-- CHECK PREFIX START

while tmp_length <= char_length(d_number) loop

-- take the number and try to find it in prefix table
-- if not found,decrease it by removing last number
-- and try again
       tmp_dest_number := substring (d_number from 1 for tmp_length);
       select into operator_temp operator from prefix       where prefix=tmp_dest_number;                
       if not found then            tmp_length := tmp_length + 1;       else

-- if we have a match with some prefix
-- take the operator from that row
               operatorfound := true;               operator_out := operator_temp;               exit;
            end if;     
 

end loop;

-- CHECK PREFIX STOP

....

only 'semantic' problem You might have with this approach is that number 
is like 16511xxxxx,which belongs to some Hawaii island operator :),but 
the problem is that all You have in Your prefix table is 16xxxxxx,which 
You mark to belong to operator USA Something. In that case,Your system 
will think of 16511xxxxxx number as it belongs to USA Something operator 
and not Hawaii island operator :( Only solution to this is to always 
have up-to-date prefix table,and populate it even with the prefices Your 
system does not support,because Your system then reject that number and 
it will have a good/precise reason why he did it :)

Some poorly  measurement showed some 60-80 matching/sec with this 
algorithm of matching prefices and a couple of concurrent database 
connections.

Sincerely

Dragan

Dimitri Fontaine wrote:
> Hi,
>
> I'm trying to code a GiST opclass to index prefix searches (select ... from t 
> where t.prefix @> query), now using a prefix_range datatype. This datatype is 
> a varlena one, and storing it to disk and indexing it with BTrees work ok, 
> but I'm failing to have my GiST opclass working, here's the problem:
>
> postgres=# create index idx_prefix on ranges using gist(prefix 
> gist_prefix_range_ops);
> NOTICE:  gpr_picksplit(): entryvec->n= 234 maxoff= 232 l= 176 r=  56 l+r= 232 
> unionL='01[0-7]' unionR='01[4-7]'
> NOTICE:  gpr_picksplit(): v->spl_ldatum='01[0-7]' v->spl_rdatum='01[4-7]'
> ERROR:  invalid memory alloc request size 3049878020
>
> The code is available at pgfoundry here:
>   http://cvs.pgfoundry.org/cgi-bin/cvsweb.cgi/prefix/prefix/
>
> The previous support for prefixes as text is still there (but will get 
> deprecated soon --- or so I hope), and the new datatype and its usage not 
> well commented nor documented currenlty. If this show up as a requirement to 
> get your attention, please state it and I'll work on documenting prefix_range 
> first.
>
> I'm looking for some help on how to resolve the shown index creation problem, 
> which I think is related to how I give data to GiST in its spl_ldatum and 
> spl_rdatum from the user defined picksplit() method, lines 1101 and 1102 in 
> prefix.c (version 1.26).
>
> Regards,
>   

Le Tuesday 25 March 2008 17:57:11 Dragan Zubac, vous avez écrit :
> and we're using a procedure to match prefices (longest prefix
> match),with simething like:
>
> while tmp_length <= char_length(d_number) loop
>
> -- take the number and try to find it in prefix table
> -- if not found,decrease it by removing last number
> -- and try again
[...]
> Some poorly  measurement showed some 60-80 matching/sec with this
> algorithm of matching prefices and a couple of concurrent database
> connections.

With the GiST index support we're hoping to get millisecond response time
order (that mean something like 1000 matching per sec, best case), and with a
query that simple :   SELECT operator      FROM prefix     WHERE prefix @> '16511xxxxxx'  ORDER BY len(prefix) DESC
LIMIT1; 

For this you have to create a dedicated index, first version of the code has
this version: http://prefix.projects.postgresql.org/README.html CREATE INDEX idx_prefix ON prefix USING GIST(prefix
gist_prefix_ops);

New version I'm trying to make work looks like this: CREATE TABLE prefix(id serial, prefix prefix_range, operator
integer);CREATE INDEX idx_prefix ON prefix USING GIST(prefix gist_prefix_range_ops); 

Former usage shows performance of 2 to 5 ms answer time on lower setups
(meaning sth like 200 reqs/s already), latter one is aiming at 1000 req/s as
said before, but does not work at all at the moment... The goal is to be able
to use the search from an AFTER INSERT TRIGGER to materialize some calling
stats and prices, etc. So it has to be that fast.

Please consider trying the code if you're interrested, it's been tested with
PostgreSQL versions 8.2 and 8.3, and former version is working fine with text
type prefixes, and should offer you some speedups already.

Hope this helps clarifying the goals and context,
--
dim

Le mardi 25 mars 2008, Dimitri Fontaine a écrit :
> postgres=# create index idx_prefix on ranges using gist(prefix
> gist_prefix_range_ops);
> NOTICE:  gpr_picksplit(): entryvec->n= 234 maxoff= 232 l= 176 r=  56 l+r=
> 232 unionL='01[0-7]' unionR='01[4-7]'
> NOTICE:  gpr_picksplit(): v->spl_ldatum='01[0-7]' v->spl_rdatum='01[4-7]'
> ERROR:  invalid memory alloc request size 3049878020

My previous tests were only done with REL8_2_STABLE cvs branch, I just redone
some tests with REL8_3_STABLE and got no error. The index is still buggy, in
the sense some requests returns different results with or without it
(enable_seqscan).

I've received some help on testing it too, and it seems the behavior is also
dependent on the architecture used. I'm using 32 bits linux arch, tests in 64
bit arch showed no error.

> The code is available at pgfoundry here:
>   http://cvs.pgfoundry.org/cgi-bin/cvsweb.cgi/prefix/prefix/

It still is :)
The easy way to test it is:
 create table prefixes (        prefix    text primary key,        name      text not null,        shortname text,
 state     char default 'S', 
        check( state in ('S', 'R') ) ); comment on column prefixes.state is 'S:   - R: reserved';
 \copy prefixes from 'prefixes.fr.csv' with delimiter ; csv quote '"'
 create table ranges as    select prefix::prefix_range, name, shortname, state from prefixes ;
 create index idx_prefix on ranges using gist(prefix gist_prefix_range_ops);

Then enable_seqscan to on or off, and queries such as select * from ranges where prefix @> '0100101234'; select * from
rangeswhere prefix @> '0146640123'; 

On my 8.3 testing, the former query gives the same result with or without
using the GiST index, the latter doesn't.

Regards,
--
dim

I guess I'll keep talking to myself, but...

Le mercredi 02 avril 2008, Dimitri Fontaine a écrit :
> My previous tests were only done with REL8_2_STABLE cvs branch, I just
> redone some tests with REL8_3_STABLE and got no error. The index is still
> buggy, in the sense some requests returns different results with or without
> it (enable_seqscan).

It turned around the error was related to the definition of my gpr_penalty()
function, which I wanted to expose as the GiST "internal" and a SQL callable
one too (for debugging and tests purpose). I forgot to define the internal
one in the prefix.c side of things, got no complaint whatsover (nor at
compile time neither at prefix.sql installation time) but garbage as data in
__pr_penalty() function (not respecting GiST calling conventions).

I guess the 8.2 invalid memory alloc request size ERROR was related to the
same pilot error, as it's now gone too.

Now this problem is overcome and the codes allows me again to create index and
use them in queries both in 8.2 and 8.3, but there's still DEBUG ongoing.
I've augmented the README for interested people to have more information:
http://prefix.projects.postgresql.org/README.html

Regards,
--
dim

"Dimitri Fontaine" <dfontaine@hi-media.com> writes:

> It turned around the error was related to the definition of my gpr_penalty() 
> function, which I wanted to expose as the GiST "internal" and a SQL callable 
> one too (for debugging and tests purpose). I forgot to define the internal 
> one in the prefix.c side of things, got no complaint whatsover (nor at 
> compile time neither at prefix.sql installation time) but garbage as data in 
> __pr_penalty() function (not respecting GiST calling conventions).

I'm getting interested now. How was __pr_penalty defined? What was the
declaration you were missing in prefix.c?

Was it specifically related to a varlena or was it a char or something like
that?

And was it something gcc -Wall was warning about or somehow was it slipping
by?

--  Gregory Stark EnterpriseDB          http://www.enterprisedb.com Ask me about EnterpriseDB's PostGIS support!

Le jeudi 10 avril 2008, Gregory Stark a écrit :
> I'm getting interested now. How was __pr_penalty defined? What was the
> declaration you were missing in prefix.c?

In fact __pr_penalty is the internal code called from both the SQL callable
functions (and some other calling sites). The problem was that I missed some
SQL callable definitions and it got called with internal parameters instead
of the prefix_range * it expects.

Details:
http://cvs.pgfoundry.org/cgi-bin/cvsweb.cgi/prefix/prefix/prefix.c.diff?r1=1.33&r2=1.32
http://cvs.pgfoundry.org/cgi-bin/cvsweb.cgi/prefix/prefix/prefix.sql.in.diff?r1=1.15&r2=1.14

> Was it specifically related to a varlena or was it a char or something like
> that?

The datatype I'm playing with is prefix_range and is used as a varlena:
typedef struct { char first; char last; char prefix[1]; /* this is a varlena structure, data follows */
} prefix_range;

Then have a look at make_varlena() function and those macros:

#define DatumGetPrefixRange(X)            ((prefix_range *)
PREFIX_VARDATA(DatumGetPointer(X)) )
#define PrefixRangeGetDatum(X)            PointerGetDatum(make_varlena(X))
#define PG_GETARG_PREFIX_RANGE_P(n)
DatumGetPrefixRange(PG_DETOAST_DATUM(PG_GETARG_DATUM(n)))
#define PG_RETURN_PREFIX_RANGE_P(x)       return PrefixRangeGetDatum(x)

> And was it something gcc -Wall was warning about or somehow was it slipping
> by?

I didn't see any errors from gcc nor from PostgreSQL. I just was using the
following function definition for the two following SQL functions:

PG_FUNCTION_INFO_V1(pr_penalty);
Datum
pr_penalty(PG_FUNCTION_ARGS)
{ float penalty = __pr_penalty(PG_GETARG_PREFIX_RANGE_P(0),                              PG_GETARG_PREFIX_RANGE_P(1));
PG_RETURN_FLOAT4(penalty);
}

CREATE OR REPLACE FUNCTION gpr_penalty(internal, internal, internal)
RETURNS internal
AS 'MODULE_PATHNAME'
LANGUAGE 'C' STRICT;

CREATE OR REPLACE FUNCTION gpr_penalty(prefix_range, prefix_range)
RETURNS float4
AS 'MODULE_PATHNAME'
LANGUAGE 'C' STRICT;

This last one is now pr_penalty and as a matching function defined in the
prefix.c file, which was not the case when all was wrong. And of course the
gpr_penalty code has been rewrote to be correct WRT its arguments processing.

Sorry to be using CVS at pgfoundry, if it was something more elaborate a
revision id could get you easily to the buggy version, here you'll have to
play some cvs game to get the version before the commit with this message, if
you wanted to try the bug yourself: Respect GiST calling conventions for gpr_penalty()

Hope this helps, regards,
--
dim

Hi all,

The first version of prefix code is now released at pgfoundry, last bug
squashed by Jordan, who did his own prefix gist opclass implementation before
I did, but didn't publish at this time. The plan is to integrate is work into
the prefix solution, as his lookups are faster than mine, and the code base
simpler but limited to varchar(15).

You can get the prefix_range datatype and prefix search GiST opclass here:
http://cvs.pgfoundry.org/cgi-bin/cvsweb.cgi/prefix/prefix/http://prefix.projects.postgresql.org/README.html
http://pgfoundry.org/frs/?group_id=1000352

Le mardi 25 mars 2008, Dragan Zubac a écrit :
> Some poorly  measurement showed some 60-80 matching/sec with this
> algorithm of matching prefices and a couple of concurrent database
> connections.

On a workstation class hardware with a 11966 rows prefix table, 25000 random
10 digit numbers where matched in less than 5s, having an average lookup time
of about 0.2ms, or 5000 matches per second. http://prefix.projects.postgresql.org/TESTS.html

If you need some speedups on prefix matching but are not willing to install
any C-code additional module, please check this blog entry:
http://www.depesz.com/index.php/2008/03/04/searching-for-longest-prefix/

The cvs and tarball version of prefix have been tested on PostgreSQL versions
8.2 and 8.3, figures from tests were obtained with 8.3, and debian packages
are available for 8.3 only at the moment.

Regards,
--
dim