wildcards as both ends

[Sam Z J <sa...@gmail.com>]

Hi all

I'm wondering how or if it's possible to implement efficient wildcards at
both ends, e.g. *string*

I can think of a few options... please comment, thanks =D

- if I can get another equality constraint which narrows down potential
result set significantly, I can do a scan. I'm not sure how feasible this
is without benchmarks. Does any one know if I can scan couple hundreds
/ thousands in a 3 node replication factory=2 cluster quickly?

- for each string I have, index all the prefixes in a column family, e.g.
for string 'string', I'd have rows string, strin, stri, str, st, s, with
column values somehow pointing back as row keys. This almost blows up the
storage needed =/ (also, what do I do if I hit the 2billion row width
limit? is there a way to say 'insert into another row if the current one is
full'?)

thanks

-- 
Zhongshi (Sam) Jiang
sammyjiang721@gmail.com

Re: wildcards as both ends

[Sam Overton <sa...@acunu.com>]

Hi Sam,

On 20 June 2012 15:20, Sam Z J <sa...@gmail.com> wrote:
>
> - for each string I have, index all the prefixes in a column family, e.g.
> for string 'string', I'd have rows string, strin, stri, str, st, s, with
> column values somehow pointing back as row keys. This almost blows up the
> storage needed =/ (also, what do I do if I hit the 2billion row width limit?
> is there a way to say 'insert into another row if the current one is full'?)

It's actually not the prefixes that you want to store, it's the suffixes.

Searching for prefixes is naturally possible in Cassandra with normal
range queries, eg. if you want to search for "str*" then a range query
from "str" to "sts" would find all values starting with "str". Range
queries are inclusive at both ends so you would need to strip off any
exact match for "sts" at the end of the results.

To implement the wildcard at the other end you could store all
suffixes for a word. Suppose you stored these as a composite column in
the format "suffix:prefix", eg. "string" would map to columns with the
names "string:", "tring:s", "ring:st", "ing:str" ... etc.

To search for "*tri*" you perform a range query from "tri:" to "trj:"
which would match "tring:s". It would also match "trium:a",
"trict:dis", "tric:me". Since the prefix is stored as the second part
of the column name it's easy to map back to the original word.

Your data blow up will be of the order of the average word length.
Increased storage and write load is a standard trade-off when
denormalising to gain some advantage/flexibility at query time.

Regards,


--
Sam Overton
Acunu | http://www.acunu.com | @acunu

Re: wildcards as both ends

[aaron morton <aa...@thelastpickle.com>]

> I'm wondering how or if it's possible to implement efficient wildcards at both ends, e.g. *string*
No. 

> - if I can get another equality constraint which narrows down potential result set significantly, I can do a scan. I'm not sure how feasible this is without benchmarks. Does any one know if I can scan couple hundreds / thousands in a 3 node replication factory=2 cluster quickly?

Not efficiently. 

If you need full text capabilities look at Solr, Solandra (the solr to cassandra port) or Data Stax Enterprise. 

Cheers


-----------------
Aaron Morton
Freelance Developer
@aaronmorton
http://www.thelastpickle.com

On 21/06/2012, at 2:20 AM, Sam Z J wrote:

> Hi all
> 
> I'm wondering how or if it's possible to implement efficient wildcards at both ends, e.g. *string*
> 
> I can think of a few options... please comment, thanks =D
> 
> - if I can get another equality constraint which narrows down potential result set significantly, I can do a scan. I'm not sure how feasible this is without benchmarks. Does any one know if I can scan couple hundreds / thousands in a 3 node replication factory=2 cluster quickly?
> 
> - for each string I have, index all the prefixes in a column family, e.g. for string 'string', I'd have rows string, strin, stri, str, st, s, with column values somehow pointing back as row keys. This almost blows up the storage needed =/ (also, what do I do if I hit the 2billion row width limit? is there a way to say 'insert into another row if the current one is full'?)
> 
> thanks
> 
> -- 
> Zhongshi (Sam) Jiang
> sammyjiang721@gmail.com