Hi Ng,

maybe this question is not closely relatd to postgres but maybe someone
can proide a better way than my approach.

I'm trying to implement a blacklist lookup.
The blacklist table contains strings (or beginning-parts of strings)
which are considered "black". Lenght of this test patterns may be up to
25 char. And there may be *a lot* of them.
A pattern 'ABC' in the table allways means 'ABC.*' as a regexp.

Now i need a fast way to test a single string varchar(25) if it matches
against one (ore more) candidates in the table.

---------
A naive way may be having a table
blacklist
(
syskey integer NOT NULL
, haystack varchar(25) NOT NULL
);

containing
1, AB
2, EFG

Testing the string needle = 'ABC' would then lead to the dynamic
creation (because of the variable number of characters in 'needle') of a
select like

select count(*)
from blacklist
where
(substr(haystack,1,1) = '0' or substr(haystack,1,1) ='')
and (substr(haystack,2,1) = '9' or substr(haystack,2,1) ='')
and (substr(haystack,3,1) = '6' or substr(haystack,3,1) ='')

This is very expensive.

---------
Maybe with a table layout like
blacklist
(
syskey integer NOT NULL
, haystack_1 char NOT NULL
...
, haystack_25 char NOT NULL
);

or the postgres-specific array type i could save the substr and use
preapred statements.

The table-access is 99% read-only, so creating extensive indexes would
be ok.
---------

I also could rearrange the table to have haystack-entries
1, AB%
2, EFG%
and use the LIKE operator like

select count(*)
from blacklist
where 'ABC' like haystack

EXPLAIN think's this is quicker.


I think we can do better.

Any ideas?

Regards,
Michael

reppisch <spam (AT) reppisch (DOT) de> wrote:
Maybe I get something wrong here, but

SELECT count(*) FROM blacklist WHERE 'ABC' || '%' LIKE haystack;

should work nicely with your original query and use an index on the
column "haystack".

If it does not use the index, try again with more rows in the table
or issue "SET enable_seqscan=off;" for test purposes.

Yours,
Laurenz Albe

reppisch <spam (AT) reppisch (DOT) de> wrote:
Maybe I get something wrong here, but

SELECT count(*) FROM blacklist WHERE 'ABC' || '%' LIKE haystack;

should work nicely with your original query and use an index on the
column "haystack".

If it does not use the index, try again with more rows in the table
or issue "SET enable_seqscan=off;" for test purposes.

Yours,
Laurenz Albe

reppisch <spam (AT) reppisch (DOT) de> wrote:
Maybe I get something wrong here, but

SELECT count(*) FROM blacklist WHERE 'ABC' || '%' LIKE haystack;

should work nicely with your original query and use an index on the
column "haystack".

If it does not use the index, try again with more rows in the table
or issue "SET enable_seqscan=off;" for test purposes.

Yours,
Laurenz Albe

reppisch <spam (AT) reppisch (DOT) de> wrote:
Maybe I get something wrong here, but

SELECT count(*) FROM blacklist WHERE 'ABC' || '%' LIKE haystack;

should work nicely with your original query and use an index on the
column "haystack".

If it does not use the index, try again with more rows in the table
or issue "SET enable_seqscan=off;" for test purposes.

Yours,
Laurenz Albe

reppisch <spam (AT) reppisch (DOT) de> wrote:
Maybe I get something wrong here, but

SELECT count(*) FROM blacklist WHERE 'ABC' || '%' LIKE haystack;

should work nicely with your original query and use an index on the
column "haystack".

If it does not use the index, try again with more rows in the table
or issue "SET enable_seqscan=off;" for test purposes.

Yours,
Laurenz Albe

reppisch <spam (AT) reppisch (DOT) de> wrote:
Maybe I get something wrong here, but

SELECT count(*) FROM blacklist WHERE 'ABC' || '%' LIKE haystack;

should work nicely with your original query and use an index on the
column "haystack".

If it does not use the index, try again with more rows in the table
or issue "SET enable_seqscan=off;" for test purposes.

Yours,
Laurenz Albe

reppisch <spam (AT) reppisch (DOT) de> wrote:
Maybe I get something wrong here, but

SELECT count(*) FROM blacklist WHERE 'ABC' || '%' LIKE haystack;

should work nicely with your original query and use an index on the
column "haystack".

If it does not use the index, try again with more rows in the table
or issue "SET enable_seqscan=off;" for test purposes.

Yours,
Laurenz Albe

reppisch <spam (AT) reppisch (DOT) de> wrote:
Maybe I get something wrong here, but

SELECT count(*) FROM blacklist WHERE 'ABC' || '%' LIKE haystack;

should work nicely with your original query and use an index on the
column "haystack".

If it does not use the index, try again with more rows in the table
or issue "SET enable_seqscan=off;" for test purposes.

Yours,
Laurenz Albe

Hi,

thanks for responding
The concept is:
the blacklist table contains a set of 'rules'
like
'AB%'
'EFG%'
....

Now i like to test some strings
a) 'ABC' or
b) 'QRZY' against all entries of the blacklist 'rules' and check if any
'rule' matches the sample.
So ABC is a varchar(25) typed argument to the query.

In sample a) 'ABC' matches rule 1 ('AB%') causing count(*) to be >0
In sample b) 'QRZY' is matched by no rule matches and count(*) will be 0

Nomally we do the inverse thing with 'LIKE' Eg. looking for names in a
table as in
'John'
'Jonny'
'Joe'
'Will'
and look for all Datasets matching 'Jo%'

The question was, if we know something faster then a inverse LIKE search.