*** a/contrib/pg_trgm/Makefile --- b/contrib/pg_trgm/Makefile *************** *** 4,10 **** MODULE_big = pg_trgm OBJS = trgm_op.o trgm_gist.o trgm_gin.o trgm_regexp.o $(WIN32RES) EXTENSION = pg_trgm ! DATA = pg_trgm--1.2.sql pg_trgm--1.0--1.1.sql pg_trgm--1.1--1.2.sql pg_trgm--unpackaged--1.0.sql PGFILEDESC = "pg_trgm - trigram matching" REGRESS = pg_trgm --- 4,10 ---- OBJS = trgm_op.o trgm_gist.o trgm_gin.o trgm_regexp.o $(WIN32RES) EXTENSION = pg_trgm ! DATA = pg_trgm--1.3.sql pg_trgm--1.0--1.1.sql pg_trgm--1.1--1.2.sql pg_trgm--1.2--1.3.sql pg_trgm--unpackaged--1.0.sql PGFILEDESC = "pg_trgm - trigram matching" REGRESS = pg_trgm *** /dev/null --- b/contrib/pg_trgm/pg_trgm--1.2--1.3.sql *************** *** 0 **** --- 1,53 ---- + /* contrib/pg_trgm/pg_trgm--1.2--1.3.sql */ + + -- complain if script is sourced in psql, rather than via ALTER EXTENSION + \echo Use "ALTER EXTENSION pg_trgm UPDATE TO '1.3'" to load this file. \quit + + CREATE FUNCTION set_substring_limit(float4) + RETURNS float4 + AS 'MODULE_PATHNAME' + LANGUAGE C STRICT VOLATILE; + + CREATE FUNCTION show_substring_limit() + RETURNS float4 + AS 'MODULE_PATHNAME' + LANGUAGE C STRICT STABLE; + + CREATE FUNCTION substring_similarity(text,text) + RETURNS float4 + AS 'MODULE_PATHNAME' + LANGUAGE C STRICT IMMUTABLE; + + CREATE FUNCTION substring_similarity_op(text,text) + RETURNS bool + AS 'MODULE_PATHNAME' + LANGUAGE C STRICT STABLE; -- stable because depends on trgm_substring_limit + + CREATE FUNCTION substring_similarity_commutator_op(text,text) + RETURNS bool + AS 'MODULE_PATHNAME' + LANGUAGE C STRICT STABLE; -- stable because depends on trgm_substring_limit + + CREATE OPERATOR <% ( + LEFTARG = text, + RIGHTARG = text, + PROCEDURE = substring_similarity_op, + COMMUTATOR = '%>', + RESTRICT = contsel, + JOIN = contjoinsel + ); + + CREATE OPERATOR %> ( + LEFTARG = text, + RIGHTARG = text, + PROCEDURE = substring_similarity_commutator_op, + COMMUTATOR = '<%', + RESTRICT = contsel, + JOIN = contjoinsel + ); + + ALTER OPERATOR FAMILY gist_trgm_ops USING gist ADD + OPERATOR 7 %> (text, text); + + ALTER OPERATOR FAMILY gin_trgm_ops USING gin ADD + OPERATOR 7 %> (text, text); *** a/contrib/pg_trgm/pg_trgm--1.2.sql --- /dev/null *************** *** 1,188 **** - /* contrib/pg_trgm/pg_trgm--1.2.sql */ - - -- complain if script is sourced in psql, rather than via CREATE EXTENSION - \echo Use "CREATE EXTENSION pg_trgm" to load this file. \quit - - CREATE FUNCTION set_limit(float4) - RETURNS float4 - AS 'MODULE_PATHNAME' - LANGUAGE C STRICT VOLATILE; - - CREATE FUNCTION show_limit() - RETURNS float4 - AS 'MODULE_PATHNAME' - LANGUAGE C STRICT STABLE; - - CREATE FUNCTION show_trgm(text) - RETURNS _text - AS 'MODULE_PATHNAME' - LANGUAGE C STRICT IMMUTABLE; - - CREATE FUNCTION similarity(text,text) - RETURNS float4 - AS 'MODULE_PATHNAME' - LANGUAGE C STRICT IMMUTABLE; - - CREATE FUNCTION similarity_op(text,text) - RETURNS bool - AS 'MODULE_PATHNAME' - LANGUAGE C STRICT STABLE; -- stable because depends on trgm_limit - - CREATE OPERATOR % ( - LEFTARG = text, - RIGHTARG = text, - PROCEDURE = similarity_op, - COMMUTATOR = '%', - RESTRICT = contsel, - JOIN = contjoinsel - ); - - CREATE FUNCTION similarity_dist(text,text) - RETURNS float4 - AS 'MODULE_PATHNAME' - LANGUAGE C STRICT IMMUTABLE; - - CREATE OPERATOR <-> ( - LEFTARG = text, - RIGHTARG = text, - PROCEDURE = similarity_dist, - COMMUTATOR = '<->' - ); - - -- gist key - CREATE FUNCTION gtrgm_in(cstring) - RETURNS gtrgm - AS 'MODULE_PATHNAME' - LANGUAGE C STRICT IMMUTABLE; - - CREATE FUNCTION gtrgm_out(gtrgm) - RETURNS cstring - AS 'MODULE_PATHNAME' - LANGUAGE C STRICT IMMUTABLE; - - CREATE TYPE gtrgm ( - INTERNALLENGTH = -1, - INPUT = gtrgm_in, - OUTPUT = gtrgm_out - ); - - -- support functions for gist - CREATE FUNCTION gtrgm_consistent(internal,text,int,oid,internal) - RETURNS bool - AS 'MODULE_PATHNAME' - LANGUAGE C IMMUTABLE STRICT; - - CREATE FUNCTION gtrgm_distance(internal,text,int,oid) - RETURNS float8 - AS 'MODULE_PATHNAME' - LANGUAGE C IMMUTABLE STRICT; - - CREATE FUNCTION gtrgm_compress(internal) - RETURNS internal - AS 'MODULE_PATHNAME' - LANGUAGE C IMMUTABLE STRICT; - - CREATE FUNCTION gtrgm_decompress(internal) - RETURNS internal - AS 'MODULE_PATHNAME' - LANGUAGE C IMMUTABLE STRICT; - - CREATE FUNCTION gtrgm_penalty(internal,internal,internal) - RETURNS internal - AS 'MODULE_PATHNAME' - LANGUAGE C IMMUTABLE STRICT; - - CREATE FUNCTION gtrgm_picksplit(internal, internal) - RETURNS internal - AS 'MODULE_PATHNAME' - LANGUAGE C IMMUTABLE STRICT; - - CREATE FUNCTION gtrgm_union(bytea, internal) - RETURNS _int4 - AS 'MODULE_PATHNAME' - LANGUAGE C IMMUTABLE STRICT; - - CREATE FUNCTION gtrgm_same(gtrgm, gtrgm, internal) - RETURNS internal - AS 'MODULE_PATHNAME' - LANGUAGE C IMMUTABLE STRICT; - - -- create the operator class for gist - CREATE OPERATOR CLASS gist_trgm_ops - FOR TYPE text USING gist - AS - OPERATOR 1 % (text, text), - FUNCTION 1 gtrgm_consistent (internal, text, int, oid, internal), - FUNCTION 2 gtrgm_union (bytea, internal), - FUNCTION 3 gtrgm_compress (internal), - FUNCTION 4 gtrgm_decompress (internal), - FUNCTION 5 gtrgm_penalty (internal, internal, internal), - FUNCTION 6 gtrgm_picksplit (internal, internal), - FUNCTION 7 gtrgm_same (gtrgm, gtrgm, internal), - STORAGE gtrgm; - - -- Add operators and support functions that are new in 9.1. We do it like - -- this, leaving them "loose" in the operator family rather than bound into - -- the gist_trgm_ops opclass, because that's the only state that can be - -- reproduced during an upgrade from 9.0 (see pg_trgm--unpackaged--1.0.sql). - - ALTER OPERATOR FAMILY gist_trgm_ops USING gist ADD - OPERATOR 2 <-> (text, text) FOR ORDER BY pg_catalog.float_ops, - OPERATOR 3 pg_catalog.~~ (text, text), - OPERATOR 4 pg_catalog.~~* (text, text), - FUNCTION 8 (text, text) gtrgm_distance (internal, text, int, oid); - - -- Add operators that are new in 9.3. - - ALTER OPERATOR FAMILY gist_trgm_ops USING gist ADD - OPERATOR 5 pg_catalog.~ (text, text), - OPERATOR 6 pg_catalog.~* (text, text); - - -- support functions for gin - CREATE FUNCTION gin_extract_value_trgm(text, internal) - RETURNS internal - AS 'MODULE_PATHNAME' - LANGUAGE C IMMUTABLE STRICT; - - CREATE FUNCTION gin_extract_query_trgm(text, internal, int2, internal, internal, internal, internal) - RETURNS internal - AS 'MODULE_PATHNAME' - LANGUAGE C IMMUTABLE STRICT; - - CREATE FUNCTION gin_trgm_consistent(internal, int2, text, int4, internal, internal, internal, internal) - RETURNS bool - AS 'MODULE_PATHNAME' - LANGUAGE C IMMUTABLE STRICT; - - -- create the operator class for gin - CREATE OPERATOR CLASS gin_trgm_ops - FOR TYPE text USING gin - AS - OPERATOR 1 % (text, text), - FUNCTION 1 btint4cmp (int4, int4), - FUNCTION 2 gin_extract_value_trgm (text, internal), - FUNCTION 3 gin_extract_query_trgm (text, internal, int2, internal, internal, internal, internal), - FUNCTION 4 gin_trgm_consistent (internal, int2, text, int4, internal, internal, internal, internal), - STORAGE int4; - - -- Add operators that are new in 9.1. - - ALTER OPERATOR FAMILY gin_trgm_ops USING gin ADD - OPERATOR 3 pg_catalog.~~ (text, text), - OPERATOR 4 pg_catalog.~~* (text, text); - - -- Add operators that are new in 9.3. - - ALTER OPERATOR FAMILY gin_trgm_ops USING gin ADD - OPERATOR 5 pg_catalog.~ (text, text), - OPERATOR 6 pg_catalog.~* (text, text); - - -- Add functions that are new in 9.6 (pg_trgm 1.2). - - CREATE FUNCTION gin_trgm_triconsistent(internal, int2, text, int4, internal, internal, internal) - RETURNS "char" - AS 'MODULE_PATHNAME' - LANGUAGE C IMMUTABLE STRICT; - - ALTER OPERATOR FAMILY gin_trgm_ops USING gin ADD - FUNCTION 6 (text,text) gin_trgm_triconsistent (internal, int2, text, int4, internal, internal, internal); --- 0 ---- *** /dev/null --- b/contrib/pg_trgm/pg_trgm--1.3.sql *************** *** 0 **** --- 1,241 ---- + /* contrib/pg_trgm/pg_trgm--1.3.sql */ + + -- complain if script is sourced in psql, rather than via CREATE EXTENSION + \echo Use "CREATE EXTENSION pg_trgm" to load this file. \quit + + CREATE FUNCTION set_limit(float4) + RETURNS float4 + AS 'MODULE_PATHNAME' + LANGUAGE C STRICT VOLATILE; + + CREATE FUNCTION show_limit() + RETURNS float4 + AS 'MODULE_PATHNAME' + LANGUAGE C STRICT STABLE; + + CREATE FUNCTION show_trgm(text) + RETURNS _text + AS 'MODULE_PATHNAME' + LANGUAGE C STRICT IMMUTABLE; + + CREATE FUNCTION similarity(text,text) + RETURNS float4 + AS 'MODULE_PATHNAME' + LANGUAGE C STRICT IMMUTABLE; + + CREATE FUNCTION similarity_op(text,text) + RETURNS bool + AS 'MODULE_PATHNAME' + LANGUAGE C STRICT STABLE; -- stable because depends on trgm_limit + + CREATE OPERATOR % ( + LEFTARG = text, + RIGHTARG = text, + PROCEDURE = similarity_op, + COMMUTATOR = '%', + RESTRICT = contsel, + JOIN = contjoinsel + ); + + CREATE FUNCTION set_substring_limit(float4) + RETURNS float4 + AS 'MODULE_PATHNAME' + LANGUAGE C STRICT VOLATILE; + + CREATE FUNCTION show_substring_limit() + RETURNS float4 + AS 'MODULE_PATHNAME' + LANGUAGE C STRICT STABLE; + + CREATE FUNCTION substring_similarity(text,text) + RETURNS float4 + AS 'MODULE_PATHNAME' + LANGUAGE C STRICT IMMUTABLE; + + CREATE FUNCTION substring_similarity_op(text,text) + RETURNS bool + AS 'MODULE_PATHNAME' + LANGUAGE C STRICT STABLE; -- stable because depends on trgm_substring_limit + + CREATE FUNCTION substring_similarity_commutator_op(text,text) + RETURNS bool + AS 'MODULE_PATHNAME' + LANGUAGE C STRICT STABLE; -- stable because depends on trgm_substring_limit + + CREATE OPERATOR <% ( + LEFTARG = text, + RIGHTARG = text, + PROCEDURE = substring_similarity_op, + COMMUTATOR = '%>', + RESTRICT = contsel, + JOIN = contjoinsel + ); + + CREATE OPERATOR %> ( + LEFTARG = text, + RIGHTARG = text, + PROCEDURE = substring_similarity_commutator_op, + COMMUTATOR = '<%', + RESTRICT = contsel, + JOIN = contjoinsel + ); + + CREATE FUNCTION similarity_dist(text,text) + RETURNS float4 + AS 'MODULE_PATHNAME' + LANGUAGE C STRICT IMMUTABLE; + + CREATE OPERATOR <-> ( + LEFTARG = text, + RIGHTARG = text, + PROCEDURE = similarity_dist, + COMMUTATOR = '<->' + ); + + -- gist key + CREATE FUNCTION gtrgm_in(cstring) + RETURNS gtrgm + AS 'MODULE_PATHNAME' + LANGUAGE C STRICT IMMUTABLE; + + CREATE FUNCTION gtrgm_out(gtrgm) + RETURNS cstring + AS 'MODULE_PATHNAME' + LANGUAGE C STRICT IMMUTABLE; + + CREATE TYPE gtrgm ( + INTERNALLENGTH = -1, + INPUT = gtrgm_in, + OUTPUT = gtrgm_out + ); + + -- support functions for gist + CREATE FUNCTION gtrgm_consistent(internal,text,int,oid,internal) + RETURNS bool + AS 'MODULE_PATHNAME' + LANGUAGE C IMMUTABLE STRICT; + + CREATE FUNCTION gtrgm_distance(internal,text,int,oid) + RETURNS float8 + AS 'MODULE_PATHNAME' + LANGUAGE C IMMUTABLE STRICT; + + CREATE FUNCTION gtrgm_compress(internal) + RETURNS internal + AS 'MODULE_PATHNAME' + LANGUAGE C IMMUTABLE STRICT; + + CREATE FUNCTION gtrgm_decompress(internal) + RETURNS internal + AS 'MODULE_PATHNAME' + LANGUAGE C IMMUTABLE STRICT; + + CREATE FUNCTION gtrgm_penalty(internal,internal,internal) + RETURNS internal + AS 'MODULE_PATHNAME' + LANGUAGE C IMMUTABLE STRICT; + + CREATE FUNCTION gtrgm_picksplit(internal, internal) + RETURNS internal + AS 'MODULE_PATHNAME' + LANGUAGE C IMMUTABLE STRICT; + + CREATE FUNCTION gtrgm_union(bytea, internal) + RETURNS _int4 + AS 'MODULE_PATHNAME' + LANGUAGE C IMMUTABLE STRICT; + + CREATE FUNCTION gtrgm_same(gtrgm, gtrgm, internal) + RETURNS internal + AS 'MODULE_PATHNAME' + LANGUAGE C IMMUTABLE STRICT; + + -- create the operator class for gist + CREATE OPERATOR CLASS gist_trgm_ops + FOR TYPE text USING gist + AS + OPERATOR 1 % (text, text), + FUNCTION 1 gtrgm_consistent (internal, text, int, oid, internal), + FUNCTION 2 gtrgm_union (bytea, internal), + FUNCTION 3 gtrgm_compress (internal), + FUNCTION 4 gtrgm_decompress (internal), + FUNCTION 5 gtrgm_penalty (internal, internal, internal), + FUNCTION 6 gtrgm_picksplit (internal, internal), + FUNCTION 7 gtrgm_same (gtrgm, gtrgm, internal), + STORAGE gtrgm; + + -- Add operators and support functions that are new in 9.1. We do it like + -- this, leaving them "loose" in the operator family rather than bound into + -- the gist_trgm_ops opclass, because that's the only state that can be + -- reproduced during an upgrade from 9.0 (see pg_trgm--unpackaged--1.0.sql). + + ALTER OPERATOR FAMILY gist_trgm_ops USING gist ADD + OPERATOR 2 <-> (text, text) FOR ORDER BY pg_catalog.float_ops, + OPERATOR 3 pg_catalog.~~ (text, text), + OPERATOR 4 pg_catalog.~~* (text, text), + FUNCTION 8 (text, text) gtrgm_distance (internal, text, int, oid); + + -- Add operators that are new in 9.3. + + ALTER OPERATOR FAMILY gist_trgm_ops USING gist ADD + OPERATOR 5 pg_catalog.~ (text, text), + OPERATOR 6 pg_catalog.~* (text, text); + + -- Add operators that are new in 9.6 (pg_trgm 1.3). + + ALTER OPERATOR FAMILY gist_trgm_ops USING gist ADD + OPERATOR 7 %> (text, text); + + -- support functions for gin + CREATE FUNCTION gin_extract_value_trgm(text, internal) + RETURNS internal + AS 'MODULE_PATHNAME' + LANGUAGE C IMMUTABLE STRICT; + + CREATE FUNCTION gin_extract_query_trgm(text, internal, int2, internal, internal, internal, internal) + RETURNS internal + AS 'MODULE_PATHNAME' + LANGUAGE C IMMUTABLE STRICT; + + CREATE FUNCTION gin_trgm_consistent(internal, int2, text, int4, internal, internal, internal, internal) + RETURNS bool + AS 'MODULE_PATHNAME' + LANGUAGE C IMMUTABLE STRICT; + + -- create the operator class for gin + CREATE OPERATOR CLASS gin_trgm_ops + FOR TYPE text USING gin + AS + OPERATOR 1 % (text, text), + FUNCTION 1 btint4cmp (int4, int4), + FUNCTION 2 gin_extract_value_trgm (text, internal), + FUNCTION 3 gin_extract_query_trgm (text, internal, int2, internal, internal, internal, internal), + FUNCTION 4 gin_trgm_consistent (internal, int2, text, int4, internal, internal, internal, internal), + STORAGE int4; + + -- Add operators that are new in 9.1. + + ALTER OPERATOR FAMILY gin_trgm_ops USING gin ADD + OPERATOR 3 pg_catalog.~~ (text, text), + OPERATOR 4 pg_catalog.~~* (text, text); + + -- Add operators that are new in 9.3. + + ALTER OPERATOR FAMILY gin_trgm_ops USING gin ADD + OPERATOR 5 pg_catalog.~ (text, text), + OPERATOR 6 pg_catalog.~* (text, text); + + -- Add functions that are new in 9.6 (pg_trgm 1.2). + + CREATE FUNCTION gin_trgm_triconsistent(internal, int2, text, int4, internal, internal, internal) + RETURNS "char" + AS 'MODULE_PATHNAME' + LANGUAGE C IMMUTABLE STRICT; + + ALTER OPERATOR FAMILY gin_trgm_ops USING gin ADD + FUNCTION 6 (text,text) gin_trgm_triconsistent (internal, int2, text, int4, internal, internal, internal); + + -- Add operators that are new in 9.6 (pg_trgm 1.3). + + ALTER OPERATOR FAMILY gin_trgm_ops USING gin ADD + OPERATOR 7 %> (text, text); *** a/contrib/pg_trgm/pg_trgm.control --- b/contrib/pg_trgm/pg_trgm.control *************** *** 1,5 **** # pg_trgm extension comment = 'text similarity measurement and index searching based on trigrams' ! default_version = '1.2' module_pathname = '$libdir/pg_trgm' relocatable = true --- 1,5 ---- # pg_trgm extension comment = 'text similarity measurement and index searching based on trigrams' ! default_version = '1.3' module_pathname = '$libdir/pg_trgm' relocatable = true *** a/contrib/pg_trgm/trgm.h --- b/contrib/pg_trgm/trgm.h *************** *** 26,37 **** #define DIVUNION /* operator strategy numbers */ ! #define SimilarityStrategyNumber 1 ! #define DistanceStrategyNumber 2 ! #define LikeStrategyNumber 3 ! #define ILikeStrategyNumber 4 ! #define RegExpStrategyNumber 5 ! #define RegExpICaseStrategyNumber 6 typedef char trgm[3]; --- 26,38 ---- #define DIVUNION /* operator strategy numbers */ ! #define SimilarityStrategyNumber 1 ! #define DistanceStrategyNumber 2 ! #define LikeStrategyNumber 3 ! #define ILikeStrategyNumber 4 ! #define RegExpStrategyNumber 5 ! #define RegExpICaseStrategyNumber 6 ! #define SubstringSimilarityStrategyNumber 7 typedef char trgm[3]; *************** *** 103,117 **** typedef char *BITVECP; #define GETARR(x) ( (trgm*)( (char*)x+TRGMHDRSIZE ) ) #define ARRNELEM(x) ( ( VARSIZE(x) - TRGMHDRSIZE )/sizeof(trgm) ) typedef struct TrgmPackedGraph TrgmPackedGraph; extern float4 trgm_limit; extern uint32 trgm2int(trgm *ptr); extern void compact_trigram(trgm *tptr, char *str, int bytelen); extern TRGM *generate_trgm(char *str, int slen); extern TRGM *generate_wildcard_trgm(const char *str, int slen); ! extern float4 cnt_sml(TRGM *trg1, TRGM *trg2); extern bool trgm_contained_by(TRGM *trg1, TRGM *trg2); extern bool *trgm_presence_map(TRGM *query, TRGM *key); extern TRGM *createTrgmNFA(text *text_re, Oid collation, --- 104,125 ---- #define GETARR(x) ( (trgm*)( (char*)x+TRGMHDRSIZE ) ) #define ARRNELEM(x) ( ( VARSIZE(x) - TRGMHDRSIZE )/sizeof(trgm) ) + #ifdef DIVUNION + #define CALCSML(count, len1, len2) ((float4) (count)) / ((float4) ((len1) + (len2) - (count))) + #else + #define CALCSML(count, len1, len2) ((float4) (count)) / ((float4) (((len1) > (len2)) ? (len1) : (len2))) + #endif + typedef struct TrgmPackedGraph TrgmPackedGraph; extern float4 trgm_limit; + extern float4 trgm_substring_limit; extern uint32 trgm2int(trgm *ptr); extern void compact_trigram(trgm *tptr, char *str, int bytelen); extern TRGM *generate_trgm(char *str, int slen); extern TRGM *generate_wildcard_trgm(const char *str, int slen); ! extern float4 cnt_sml(TRGM *trg1, TRGM *trg2, bool inexact); extern bool trgm_contained_by(TRGM *trg1, TRGM *trg2); extern bool *trgm_presence_map(TRGM *query, TRGM *key); extern TRGM *createTrgmNFA(text *text_re, Oid collation, *** a/contrib/pg_trgm/trgm_gin.c --- b/contrib/pg_trgm/trgm_gin.c *************** *** 89,94 **** gin_extract_query_trgm(PG_FUNCTION_ARGS) --- 89,95 ---- switch (strategy) { case SimilarityStrategyNumber: + case SubstringSimilarityStrategyNumber: trg = generate_trgm(VARDATA(val), VARSIZE(val) - VARHDRSZ); break; case ILikeStrategyNumber: *************** *** 176,181 **** gin_trgm_consistent(PG_FUNCTION_ARGS) --- 177,183 ---- bool res; int32 i, ntrue; + float4 nlimit; /* All cases served by this function are inexact */ *recheck = true; *************** *** 183,188 **** gin_trgm_consistent(PG_FUNCTION_ARGS) --- 185,191 ---- switch (strategy) { case SimilarityStrategyNumber: + case SubstringSimilarityStrategyNumber: /* Count the matches */ ntrue = 0; for (i = 0; i < nkeys; i++) *************** *** 190,199 **** gin_trgm_consistent(PG_FUNCTION_ARGS) if (check[i]) ntrue++; } #ifdef DIVUNION ! res = (nkeys == ntrue) ? true : ((((((float4) ntrue) / ((float4) (nkeys - ntrue)))) >= trgm_limit) ? true : false); #else ! res = (nkeys == 0) ? false : ((((((float4) ntrue) / ((float4) nkeys))) >= trgm_limit) ? true : false); #endif break; case ILikeStrategyNumber: --- 193,203 ---- if (check[i]) ntrue++; } + nlimit = (strategy == SimilarityStrategyNumber) ? trgm_limit : trgm_substring_limit; #ifdef DIVUNION ! res = (nkeys == ntrue) ? true : ((((((float4) ntrue) / ((float4) (nkeys - ntrue)))) >= nlimit) ? true : false); #else ! res = (nkeys == 0) ? false : ((((((float4) ntrue) / ((float4) nkeys))) >= nlimit) ? true : false); #endif break; case ILikeStrategyNumber: *************** *** 256,265 **** gin_trgm_triconsistent(PG_FUNCTION_ARGS) --- 260,271 ---- int32 i, ntrue; bool *boolcheck; + float4 nlimit; switch (strategy) { case SimilarityStrategyNumber: + case SubstringSimilarityStrategyNumber: /* Count the matches */ ntrue = 0; for (i = 0; i < nkeys; i++) *************** *** 267,276 **** gin_trgm_triconsistent(PG_FUNCTION_ARGS) if (check[i] != GIN_FALSE) ntrue++; } #ifdef DIVUNION ! res = (nkeys == ntrue) ? GIN_MAYBE : (((((float4) ntrue) / ((float4) (nkeys - ntrue))) >= trgm_limit) ? GIN_MAYBE : GIN_FALSE); #else ! res = (nkeys == 0) ? GIN_FALSE : (((((float4) ntrue) / ((float4) nkeys)) >= trgm_limit) ? GIN_MAYBE : GIN_FALSE); #endif break; case ILikeStrategyNumber: --- 273,283 ---- if (check[i] != GIN_FALSE) ntrue++; } + nlimit = (strategy == SimilarityStrategyNumber) ? trgm_limit : trgm_substring_limit; #ifdef DIVUNION ! res = (nkeys == ntrue) ? GIN_MAYBE : (((((float4) ntrue) / ((float4) (nkeys - ntrue))) >= nlimit) ? GIN_MAYBE : GIN_FALSE); #else ! res = (nkeys == 0) ? GIN_FALSE : (((((float4) ntrue) / ((float4) nkeys)) >= nlimit) ? GIN_MAYBE : GIN_FALSE); #endif break; case ILikeStrategyNumber: *** a/contrib/pg_trgm/trgm_gist.c --- b/contrib/pg_trgm/trgm_gist.c *************** *** 191,196 **** gtrgm_consistent(PG_FUNCTION_ARGS) --- 191,197 ---- bool res; Size querysize = VARSIZE(query); gtrgm_consistent_cache *cache; + float4 nlimit; /* * We keep the extracted trigrams in cache, because trigram extraction is *************** *** 218,223 **** gtrgm_consistent(PG_FUNCTION_ARGS) --- 219,225 ---- switch (strategy) { case SimilarityStrategyNumber: + case SubstringSimilarityStrategyNumber: qtrg = generate_trgm(VARDATA(query), querysize - VARHDRSZ); break; *************** *** 286,300 **** gtrgm_consistent(PG_FUNCTION_ARGS) switch (strategy) { case SimilarityStrategyNumber: ! /* Similarity search is exact */ ! *recheck = false; if (GIST_LEAF(entry)) { /* all leafs contains orig trgm */ ! float4 tmpsml = cnt_sml(key, qtrg); /* strange bug at freebsd 5.2.1 and gcc 3.3.3 */ ! res = (*(int *) &tmpsml == *(int *) &trgm_limit || tmpsml > trgm_limit) ? true : false; } else if (ISALLTRUE(key)) { /* non-leaf contains signature */ --- 288,304 ---- switch (strategy) { case SimilarityStrategyNumber: ! case SubstringSimilarityStrategyNumber: ! /* Similarity search is exact. Substring similarity search is inexact */ ! *recheck = (strategy == SubstringSimilarityStrategyNumber) ? true : false; ! nlimit = (strategy == SimilarityStrategyNumber) ? trgm_limit : trgm_substring_limit; if (GIST_LEAF(entry)) { /* all leafs contains orig trgm */ ! float4 tmpsml = cnt_sml(qtrg, key, *recheck); /* strange bug at freebsd 5.2.1 and gcc 3.3.3 */ ! res = (*(int *) &tmpsml == *(int *) &nlimit || tmpsml > nlimit) ? true : false; } else if (ISALLTRUE(key)) { /* non-leaf contains signature */ *************** *** 308,314 **** gtrgm_consistent(PG_FUNCTION_ARGS) if (len == 0) res = false; else ! res = (((((float8) count) / ((float8) len))) >= trgm_limit) ? true : false; } break; case ILikeStrategyNumber: --- 312,318 ---- if (len == 0) res = false; else ! res = (((((float8) count) / ((float8) len))) >= nlimit) ? true : false; } break; case ILikeStrategyNumber: *************** *** 463,469 **** gtrgm_distance(PG_FUNCTION_ARGS) case DistanceStrategyNumber: if (GIST_LEAF(entry)) { /* all leafs contains orig trgm */ ! res = 1.0 - cnt_sml(key, qtrg); } else if (ISALLTRUE(key)) { /* all leafs contains orig trgm */ --- 467,473 ---- case DistanceStrategyNumber: if (GIST_LEAF(entry)) { /* all leafs contains orig trgm */ ! res = 1.0 - cnt_sml(key, qtrg, false); } else if (ISALLTRUE(key)) { /* all leafs contains orig trgm */ *** a/contrib/pg_trgm/trgm_op.c --- b/contrib/pg_trgm/trgm_op.c *************** *** 15,27 **** --- 15,33 ---- PG_MODULE_MAGIC; float4 trgm_limit = 0.3f; + float4 trgm_substring_limit = 0.6f; PG_FUNCTION_INFO_V1(set_limit); PG_FUNCTION_INFO_V1(show_limit); PG_FUNCTION_INFO_V1(show_trgm); PG_FUNCTION_INFO_V1(similarity); + PG_FUNCTION_INFO_V1(substring_similarity); PG_FUNCTION_INFO_V1(similarity_dist); PG_FUNCTION_INFO_V1(similarity_op); + PG_FUNCTION_INFO_V1(set_substring_limit); + PG_FUNCTION_INFO_V1(show_substring_limit); + PG_FUNCTION_INFO_V1(substring_similarity_op); + PG_FUNCTION_INFO_V1(substring_similarity_commutator_op); Datum *************** *** 41,46 **** show_limit(PG_FUNCTION_ARGS) --- 47,69 ---- PG_RETURN_FLOAT4(trgm_limit); } + Datum + set_substring_limit(PG_FUNCTION_ARGS) + { + float4 nlimit = PG_GETARG_FLOAT4(0); + + if (nlimit < 0 || nlimit > 1.0) + elog(ERROR, "wrong limit, should be between 0 and 1"); + trgm_substring_limit = nlimit; + PG_RETURN_FLOAT4(trgm_substring_limit); + } + + Datum + show_substring_limit(PG_FUNCTION_ARGS) + { + PG_RETURN_FLOAT4(trgm_substring_limit); + } + static int comp_trgm(const void *a, const void *b) { *************** *** 166,203 **** make_trigrams(trgm *tptr, char *str, int bytelen, int charlen) return tptr; } ! TRGM * ! generate_trgm(char *str, int slen) { ! TRGM *trg; char *buf; ! trgm *tptr; ! int len, ! charlen, bytelen; char *bword, *eword; - /* - * Guard against possible overflow in the palloc requests below. (We - * don't worry about the additive constants, since palloc can detect - * requests that are a little above MaxAllocSize --- we just need to - * prevent integer overflow in the multiplications.) - */ - if ((Size) (slen / 2) >= (MaxAllocSize / (sizeof(trgm) * 3)) || - (Size) slen >= (MaxAllocSize / pg_database_encoding_max_length())) - ereport(ERROR, - (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED), - errmsg("out of memory"))); - - trg = (TRGM *) palloc(TRGMHDRSIZE + sizeof(trgm) * (slen / 2 + 1) *3); - trg->flag = ARRKEY; - SET_VARSIZE(trg, TRGMHDRSIZE); - if (slen + LPADDING + RPADDING < 3 || slen == 0) ! return trg; ! tptr = GETARR(trg); /* Allocate a buffer for case-folded, blank-padded words */ buf = (char *) palloc(slen * pg_database_encoding_max_length() + 4); --- 189,208 ---- return tptr; } ! static int ! generate_trgm_only(trgm *trg, char *str, int slen) { ! trgm *tptr; char *buf; ! int charlen, bytelen; char *bword, *eword; if (slen + LPADDING + RPADDING < 3 || slen == 0) ! return 0; ! tptr = trg; /* Allocate a buffer for case-folded, blank-padded words */ buf = (char *) palloc(slen * pg_database_encoding_max_length() + 4); *************** *** 237,243 **** generate_trgm(char *str, int slen) pfree(buf); ! if ((len = tptr - GETARR(trg)) == 0) return trg; /* --- 242,281 ---- pfree(buf); ! return tptr - trg; ! } ! ! static void ! protect_out_of_mem(int slen) ! { ! /* ! * Guard against possible overflow in the palloc requests below. (We ! * don't worry about the additive constants, since palloc can detect ! * requests that are a little above MaxAllocSize --- we just need to ! * prevent integer overflow in the multiplications.) ! */ ! if ((Size) (slen / 2) >= (MaxAllocSize / (sizeof(trgm) * 3)) || ! (Size) slen >= (MaxAllocSize / pg_database_encoding_max_length())) ! ereport(ERROR, ! (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED), ! errmsg("out of memory"))); ! } ! ! TRGM * ! generate_trgm(char *str, int slen) ! { ! TRGM *trg; ! int len; ! ! protect_out_of_mem(slen); ! ! trg = (TRGM *) palloc(TRGMHDRSIZE + sizeof(trgm) * (slen / 2 + 1) *3); ! trg->flag = ARRKEY; ! ! len = generate_trgm_only(GETARR(trg), str, slen); ! SET_VARSIZE(trg, CALCGTSIZE(ARRKEY, len)); ! ! if (len == 0) return trg; /* *************** *** 254,259 **** generate_trgm(char *str, int slen) --- 292,534 ---- return trg; } + /* Trigram with position */ + typedef struct + { + trgm t; + int i; + } ptrgm; + + /* + * Make array of positional trigrams from two trigram arrays. The first array + * is required substing which positions don't matter and replaced with -1. + * The second array is haystack where we search and have to store its + * positions. + */ + static ptrgm * + make_positional_trgm(trgm *trg1, int len1, trgm *trg2, int len2) + { + ptrgm *result; + int i, len = len1 + len2; + + result = (ptrgm *) palloc(sizeof(ptrgm) * len); + + for (i = 0; i < len1; i++) + { + memcpy(&result[i].t, &trg1[i], sizeof(trgm)); + result[i].i = -1; + } + + for (i = 0; i < len2; i++) + { + memcpy(&result[i + len1].t, &trg2[i], sizeof(trgm)); + result[i + len1].i = i; + } + + return result; + } + + /* + * Compare position trigrams: compare trigrams first and position second. + */ + static int + comp_ptrgm(const void *v1, const void *v2) + { + const ptrgm *p1 = (const ptrgm *)v1; + const ptrgm *p2 = (const ptrgm *)v2; + int cmp; + + cmp = CMPTRGM(p1->t, p2->t); + if (cmp != 0) + return cmp; + + if (p1->i < p2->i) + return -1; + else if (p1->i == p2->i) + return 0; + else + return 1; + } + + /* + * Iterative procedure if finding maximum similarity with substring. + */ + static float4 + iterate_substring_similarity(int *trg2indexes, + bool *found, + int ulen1, + int len2, + int len) + { + int *lastpos, + i, + ulen2 = 0, + count = 0, + upper = -1, + lower = -1; + float4 smlr_cur, + smlr_max = 0.0f; + + /* Memorise last position of each trigram */ + lastpos = (int *) palloc(sizeof(int) * len); + memset(lastpos, -1, sizeof(int) * len); + + for (i = 0; i < len2; i++) + { + /* Get index of next trigram */ + int trgindex = trg2indexes[i]; + + /* Update last position of this trigram */ + if (lower >= 0 || found[trgindex]) + { + if (lastpos[trgindex] < 0) + { + ulen2++; + if (found[trgindex]) + count++; + } + lastpos[trgindex] = i; + } + + /* Adjust lower bound if this trigram is present in required substing */ + if (found[trgindex]) + { + int prev_lower, + tmp_ulen2, + tmp_lower, + tmp_count; + + upper = i; + if (lower == -1) + { + lower = i; + ulen2 = 1; + } + + smlr_cur = CALCSML(count, ulen1, ulen2); + + /* Also try to adjust upper bound for greater similarity */ + tmp_count = count; + tmp_ulen2 = ulen2; + prev_lower = lower; + for (tmp_lower = lower; tmp_lower <= upper; tmp_lower++) + { + float smlr_tmp = CALCSML(tmp_count, ulen1, tmp_ulen2); + int tmp_trgindex; + + if (smlr_tmp > smlr_cur) + { + smlr_cur = smlr_tmp; + ulen2 = tmp_ulen2; + lower = tmp_lower; + count = tmp_count; + } + tmp_trgindex = trg2indexes[tmp_lower]; + if (lastpos[tmp_trgindex] == tmp_lower) + { + tmp_ulen2--; + if (found[tmp_trgindex]) + tmp_count--; + } + } + + for (tmp_lower = prev_lower; tmp_lower < lower; tmp_lower++) + { + int tmp_trgindex; + tmp_trgindex = trg2indexes[tmp_lower]; + if (lastpos[tmp_trgindex] == tmp_lower) + lastpos[tmp_trgindex] = -1; + } + + smlr_max = Max(smlr_max, smlr_cur); + } + } + + pfree(lastpos); + + return smlr_max; + } + + /* + * Calculate substring similarity. + */ + static float4 + calc_substring_similarity(char *str1, int slen1, char *str2, int slen2) + { + bool *found; + ptrgm *ptrg; + trgm *trg1; + trgm *trg2; + int len1, + len2, + len, + i, + j, + ulen1; + int *trg2indexes; + float4 result; + + protect_out_of_mem(slen1 + slen2); + + /* Make positional trigrams */ + trg1 = (trgm *) palloc(sizeof(trgm) * (slen1 / 2 + 1) * 3); + trg2 = (trgm *) palloc(sizeof(trgm) * (slen2 / 2 + 1) * 3); + + len1 = generate_trgm_only(trg1, str1, slen1); + len2 = generate_trgm_only(trg2, str2, slen2); + + ptrg = make_positional_trgm(trg1, len1, trg2, len2); + len = len1 + len2; + qsort(ptrg, len, sizeof(ptrgm), comp_ptrgm); + + pfree(trg1); + pfree(trg2); + + /* + * Merge positional trigrams array: enumerate each trigram and find its + * presence in required substring. + */ + trg2indexes = (int *) palloc(sizeof(int) * len2); + found = (bool *) palloc0(sizeof(bool) * len); + + ulen1 = 0; + j = 0; + for (i = 0; i < len; i++) + { + if (i > 0) + { + int cmp = CMPTRGM(ptrg[i - 1].t, ptrg[i].t); + if (cmp != 0) + { + if (found[j]) + ulen1++; + j++; + } + } + + if (ptrg[i].i >= 0) + { + trg2indexes[ptrg[i].i] = j; + } + else + { + found[j] = true; + } + } + if (found[j]) + ulen1++; + + /* Run iterative procedure to find maximum similarity with substring */ + result = iterate_substring_similarity(trg2indexes, found, ulen1, len2, len); + + pfree(trg2indexes); + pfree(found); + pfree(ptrg); + + return result; + } + + /* * Extract the next non-wildcard part of a search string, ie, a word bounded * by '_' or '%' meta-characters, non-word characters or string end. *************** *** 426,442 **** generate_wildcard_trgm(const char *str, int slen) bytelen; const char *eword; ! /* ! * Guard against possible overflow in the palloc requests below. (We ! * don't worry about the additive constants, since palloc can detect ! * requests that are a little above MaxAllocSize --- we just need to ! * prevent integer overflow in the multiplications.) ! */ ! if ((Size) (slen / 2) >= (MaxAllocSize / (sizeof(trgm) * 3)) || ! (Size) slen >= (MaxAllocSize / pg_database_encoding_max_length())) ! ereport(ERROR, ! (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED), ! errmsg("out of memory"))); trg = (TRGM *) palloc(TRGMHDRSIZE + sizeof(trgm) * (slen / 2 + 1) *3); trg->flag = ARRKEY; --- 701,707 ---- bytelen; const char *eword; ! protect_out_of_mem(slen); trg = (TRGM *) palloc(TRGMHDRSIZE + sizeof(trgm) * (slen / 2 + 1) *3); trg->flag = ARRKEY; *************** *** 557,563 **** show_trgm(PG_FUNCTION_ARGS) } float4 ! cnt_sml(TRGM *trg1, TRGM *trg2) { trgm *ptr1, *ptr2; --- 822,828 ---- } float4 ! cnt_sml(TRGM *trg1, TRGM *trg2, bool inexact) { trgm *ptr1, *ptr2; *************** *** 591,604 **** cnt_sml(TRGM *trg1, TRGM *trg2) } } ! #ifdef DIVUNION ! return ((float4) count) / ((float4) (len1 + len2 - count)); ! #else ! return ((float4) count) / ((float4) ((len1 > len2) ? len1 : len2)); ! #endif ! } /* * Returns whether trg2 contains all trigrams in trg1. * This relies on the trigram arrays being sorted. --- 856,869 ---- } } ! /* if inexact then len2 is equal to count */ ! if (inexact) ! return CALCSML(count, len1, count); ! else ! return CALCSML(count, len1, len2); } + /* * Returns whether trg2 contains all trigrams in trg1. * This relies on the trigram arrays being sorted. *************** *** 693,699 **** similarity(PG_FUNCTION_ARGS) trg1 = generate_trgm(VARDATA(in1), VARSIZE(in1) - VARHDRSZ); trg2 = generate_trgm(VARDATA(in2), VARSIZE(in2) - VARHDRSZ); ! res = cnt_sml(trg1, trg2); pfree(trg1); pfree(trg2); --- 958,964 ---- trg1 = generate_trgm(VARDATA(in1), VARSIZE(in1) - VARHDRSZ); trg2 = generate_trgm(VARDATA(in2), VARSIZE(in2) - VARHDRSZ); ! res = cnt_sml(trg1, trg2, false); pfree(trg1); pfree(trg2); *************** *** 704,709 **** similarity(PG_FUNCTION_ARGS) --- 969,990 ---- } Datum + substring_similarity(PG_FUNCTION_ARGS) + { + text *in1 = PG_GETARG_TEXT_PP(0); + text *in2 = PG_GETARG_TEXT_PP(1); + float4 res; + + res = calc_substring_similarity(VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1), + VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2)); + + PG_FREE_IF_COPY(in1, 0); + PG_FREE_IF_COPY(in2, 1); + + PG_RETURN_FLOAT4(res); + } + + Datum similarity_dist(PG_FUNCTION_ARGS) { float4 res = DatumGetFloat4(DirectFunctionCall2(similarity, *************** *** 722,724 **** similarity_op(PG_FUNCTION_ARGS) --- 1003,1025 ---- PG_RETURN_BOOL(res >= trgm_limit); } + + Datum + substring_similarity_op(PG_FUNCTION_ARGS) + { + float4 res = DatumGetFloat4(DirectFunctionCall2(substring_similarity, + PG_GETARG_DATUM(0), + PG_GETARG_DATUM(1))); + + PG_RETURN_BOOL(res >= trgm_substring_limit); + } + + Datum + substring_similarity_commutator_op(PG_FUNCTION_ARGS) + { + float4 res = DatumGetFloat4(DirectFunctionCall2(substring_similarity, + PG_GETARG_DATUM(1), + PG_GETARG_DATUM(0))); + + PG_RETURN_BOOL(res >= trgm_substring_limit); + } *** a/doc/src/sgml/pgtrgm.sgml --- b/doc/src/sgml/pgtrgm.sgml *************** *** 85,90 **** --- 85,101 ---- + substring_similarity(text, text)substring_similarity + real + + Returns a number that indicates how similar the first string + to the most similar substring of the second string. The range of + the result is zero (indicating that the two strings are completely + dissimilar) to one (indicating that the first string is identical + to substring of the second substring). + + + show_trgm(text)show_trgm text[] *************** *** 111,116 **** --- 122,145 ---- Returns the same value passed in. + + show_substring_limit()show_substring_limit + real + + Returns the current similarity threshold used by the <% + operator. This sets the minimum substring similarity between + two phrases. + + + + set_substring_limit(real)set_substring_limit + real + + Sets the current substring similarity threshold that is used by + the <% operator. The threshold must be between + 0 and 1 (default is 0.6). Returns the same value passed in. + + *************** *** 137,142 **** --- 166,180 ---- + text <% text + boolean + + Returns true if its arguments have a substring similarity + that is greater than the current substring similarity threshold set by + set_substring_limit. + + + text <-> text real *************** *** 204,209 **** SELECT t, t <-> 'word' AS dist --- 242,262 ---- + Also you can use an index on the t column for substring + similarity. For example: + + SELECT t, substring_similarity('word', t) AS sml + FROM test_trgm + WHERE 'word' <% t + ORDER BY sml DESC, t; + + This will return all values in the text column that have a substring + which sufficiently similar to word, sorted from best + match to worst. The index will be used to make this a fast operation + even over very large data sets. + + + Beginning in PostgreSQL 9.1, these index types also support index searches for LIKE and ILIKE, for example