Thread: 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