Re: WIP: index support for regexp search

For depth-first it's not. 

On 02.12.2012 20:19, Tom Lane wrote:

Alexander Korotkov<aekorotkov@gmail.com>  writes:

Nice idea to delay expanding colors to characters! Obviously, we should
delay expanding inly alphanumerical characters. Because non-alphanumberical
characters influence graph structure. Trying to implement...

Uh, why would that be?  Colors are colors.  The regexp machinery doesn't
care whether they represent alphanumerics or not.  (Or to be more
precise, if there is a situation where it makes a difference, separate
colors will have been created for each set of characters that need to be
distinguished.)

The regexp machinery doesn't care, but the trigrams that pg_trgm extracts only contain alphanumeric characters. So if by looking at the CNFA graph produced by the regexp machinery you conclude that any matching strings must contain three-letter sequences "%oo" and "#oo", you can just club them together into " oo" trigram.

I think you can run a pre-processing step to the colors, and merge colors that are equivalent as far as trigrams are considered. For example, if you have a color that contains only character '%', and another that contains character '#', you can treat them as the same hcolor. You might then be able to simplify the CNFA. Actually, it would be even better if you could apply the pre-processing to the regexp before the regexp machinery turns it into a CNFA. Not sure how easy it would be to do such pre-processing.

BTW, why create the path matrix? You could check the "check" array of trigrams in the consistent function directly against the graph. Consistent should return true, iff there is a path through the graph following only arcs that contain trigrams present in the check array. Finding a path through a complex graph could be expensive, O(|E|), but if the path is complex, the path matrix would be large as well, and checking against a large matrix isn't exactly free either. It would allow you to avoid "overflows" caused by having too many paths through the graph.

On Mon, Dec 3, 2012 at 4:31 PM, Alexander Korotkov <aekorotkov@gmail.com> wrote:

Actually, I generally dislike path matrix for same reasons. But:

1) Output graphs could contain trigrams which are completely useless for search. For example, for regex /(abcdefgh)*ijk/ we need only "ijk" trigram while graph would contain much more.Path matrix is a method to get rid of all of them.

2) If we use color trigrams then we need some criteria for which color trigrams to expand into trigrams. Simultaneously, we shouldn't allow path from initial state to the final by unexpanded trigrams. It seems much harder to do with graph than with matrix.

Now, I have an idea about doing some not comprehensive but simple and fast simplification of graph. I'm doing experiments now. In case of success we could get rid of path matrix.

On Tue, December 18, 2012 08:04, Alexander Korotkov wrote:
I ran the same test again: HEAD versus trgm_regex v6, 7 and 9.  In v9 there is some gain but also
some regression.

It remains a difficult problem...

If I get some time in the holidays I'll try to diversify the test program; it is now too simple.

On Sun, December 16, 2012 22:25, Alexander Korotkov wrote:

> trgm-regexp-0.8.patch.gz   22 k

Hi Alexander,

I gave this a quick try; the patch works when compiled for DEBUG, but crashes as a
'speed'-compiled binary:

Compile for speed:

$ pg_config --configure
'--prefix=/home/aardvark/pg_stuff/pg_installations/pgsql.trgm_regex8' '--with-pgport=6556'
'--enable-depend' '--with-openssl' '--with-perl' '--with-libxml'

$ psql
psql (9.3devel-trgm_regex8-20121216_2336-c299477229559d4ee7db68720d86d3fb391db761)
Type "help" for help.

testdb=# explain analyze select txt from azjunk5 where txt ~ 'x[aeiouy]{2,5}q';
The connection to the server was lost. Attempting reset: Failed.
!> \q

Alexander Korotkov <aekorotkov@gmail.com> writes:
> Now I have working implemetation of this API. Comments still need rework.
> Could you give me any feedback?

I looked at this a little bit, but it's not very far along at all
towards resolving my API worries.  The basic point that I'm concerned
about is that we would like to split off the regex library (ie,
backend/regex/) as a standalone project someday.  There are already
some problems to be resolved to make that possible, and I don't want
this patch to introduce new ones.  From that standpoint, the proposed
regextract.c file is a disaster, because it depends on a boatload of
Postgres-specific stuff (at least StringInfo, List, HTAB, and pg_wchar;
to say nothing of palloc).  We can't consider that to be on the regex
side of the fence.

Similarly, pushing PG-specific declarations like RE_compile_and_cache()
into regex/regex.h is completely not the right thing for preserving a
clear library boundary (even positing that we want to expose that
function outside adt/regexp.c, which I'd rather we didn't).

Given that you've already got a notion of callbacks provided by
contrib/pg_trgm, perhaps this can be fixed by pushing more of the work
into those callbacks, so that the heavy-duty data structures like the
hash table live over there and the API exposed by backend/regex/ is at
a much simpler level than what you have here.  But right now I don't
see any usable library API here.

Perhaps we could avoid these issues by defining a library API that
provides accessors like these for the opaque regex_t struct:

* get the number of states in the CNFA

* get the numbers of the initial and final states

* get the number of out-arcs for the N'th state

* get the out-arcs for the N'th state into a caller-provided array
(sized using the previous function), where each out-arc is represented
by a color and an end-state

* get the number of character codes represented by color C

* get the wchar codes for color C into a caller-provided array

(The reason for letting the caller allocate the result arrays is so we
can use palloc for that; if we allocate it in backend/regex/ we must
use malloc, which will greatly increase the risk of leakages.  Also,
as far as the color API goes, the above lets the caller decide how
many characters is "too many" to bother with.)

Glad to see this patch hasn't been totally forgotten. Being able to use indexes for regular expressions would be really cool!

Back in January, I asked for some high-level description of how the algorithm works (http://archives.postgresql.org/message-id/4F187D5C.30701@enterprisedb.com). That's still sorely needed. Googling around, I found the slides for your presentation on this from PGConf.EU - it would be great to have the information from that presentation included in the patch.

On 30.11.2012 13:20, Alexander Korotkov wrote:

On Thu, Nov 29, 2012 at 5:25 PM, Heikki Linnakangas<hlinnakangas@vmware.com

wrote:

Would it be safe to simply stop short the depth-first search on overflow,
and proceed with the graph that was constructed up to that point?

For depth-first it's not. But your proposal naturally makes sense. I've
changed it to breadth-first search. And then it's safe to mark all
unprocessed states as final when overflow. It means that we assume every
unprocessed branch to immediately finish with matching (this can give us
more false positives but no false negatives).
For overflow of matrix collection, it's safe to do just OR between all the
trigrams.
New version of patch is attached.

Thanks, sounds good.

I've spent quite a long time trying to understand the transformation the getState/addKeys/addAcrs functions do to the original CNFA graph. I think that still needs more comments to explain the steps involved in it.

One thing that occurs to me is that it might be better to delay expanding colors to characters. You could build and transform the graph, and even create the paths, all while operating on colors. You would end up with lists of "color trigrams", consisting of sequences of three colors that must appear in the source string. Only at the last step you would expand the color trigrams to real character trigrams. I think that would save a lot of processing while building the graph, if you have colors that contain many characters. It would allow us to do better than the fixed small MAX_COLOR_CHARS limit. For example with MAX_COLOR_CHARS = 4 in the current patch, it's a shame that we can't do anything with a fairly simple regexp like "^a[b-g]h$"

Please add this patch here so it does not get lost in the shuffle:

https://commitfest.postgresql.org/action/commitfest_view/open

Heikki Linnakangas <hlinnakangas@vmware.com> writes:
> On 23.01.2013 09:36, Alexander Korotkov wrote:

>> On Wed, Jan 23, 2013 at 6:08 AM, Tom Lane<tgl@sss.pgh.pa.us>  wrote:
>>> The biggest problem is that I really don't care for the idea of
>>> contrib/pg_trgm being this cozy with the innards of regex_t.

>> The only option I see now is to provide a method like "export_cnfa" which
>> would export corresponding CNFA in fixed format.

> Yeah, I think that makes sense. The transformation code in trgm_regexp.c
> would probably be more readable too, if it didn't have to deal with the
> regex guts representation of the CNFA. Also, once you have intermediate
> representation of the original CNFA, you could do some of the
> transformation work on that representation, before building the
> "tranformed graph" containing trigrams. You could eliminate any
> non-alphanumeric characters, joining states connected by arcs with
> non-alphanumeric characters, for example.

It's not just the CNFA though; the other big API problem is with mapping
colors back to characters.  Right now, that not only knows way too much
about a part of the regex internals we have ambitions to change soon,
but it also requires pg_wchar2mb_with_len() and lowerstr(), neither of
which should be known to the regex library IMO.  So I'm not sure how we
divvy that up sanely.  To be clear: I'm not going to insist that we have
to have a clean API factorization before we commit this at all.  But it
worries me if we don't even know how we could get to that, because we
are going to need it eventually.

On Fri, Jan 20, 2012 at 01:33, Erik Rijkers <er@xs4all.nl> wrote:
> Btw, it seems impossible to Ctrl-C out of a search once it is submitted; I suppose this is
> normally necessary for perfomance reasons, but it would be useful te be able to compile a test
> version that allows it.

I believe being interruptible is a requirement for the patch to be accepted.

CHECK_FOR_INTERRUPTS(); should be added to the indeterminate loops.

On Tue, December 18, 2012 09:45, Alexander Korotkov wrote:
>
> You should use {0,n} to express from 0 to n occurences.
>

Thanks, but I know that of course.  It's a testing program; and in the end robustness with
unexpected or even wrong input is as important as performance.  (to put it bluntly, I am also
trying to get your patch to fall over ;-))

What does last 7 zeros in the first column means? No conversion to pg_wchar is possible from these encodings?

The biggest problem is that I really don't care for the idea of

contrib/pg_trgm being this cozy with the innards of regex_t.  Sooner
or later we are going to want to split the regex code off again as a
standalone library, and we *must* have a cleaner division of labor if
that is ever to happen.  Not sure what a suitable API would look like
though.

I think the assumption that all MB characters fit in 4 bytes is
unacceptable; someday we'll want to support wider Unicode characters
than we do now, and this code seems utterly unable to handle it.  It's
especially bad that the code isn't even bothering to defend itself
against the possibility of wider characters.

Can't just modify pg_trgm--1.0.sql in place, must create a "1.1" version
and an upgrade script.

Comments and documentation still need a lot of copy-editing, also I
think a lot of the comment blocks will not survive pg_indent.  It'd be
a good idea to run trgm_regexp.c through pg_indent as soon as you have
that fixed.

New file trgm_regexp.c lacks a copyright notice

Calling RE_compile_and_cache with DEFAULT_COLLATION_OID is not good
enough; need to pass through the actual collation for the regex
operator.

Not too happy with convertPgWchar: aside from hard-wired, unchecked
assumption about maximum length of pg_wchar2mb_with_len result, why is
it that this is doing a lowercase conversion?  Surely the regex stuff
dealt with that already?

2) It's common to use upper-case names for macros, but trgm.h defines

   macro "iswordchr" - I see it's moved from trgm_op.c but maybe we
   could make it a bit more correct?

3) I see there are two '#ifdef KEEPONLYALNUM" blocks right next to each
   other in trgm.h - maybe it'd be a good idea to join them?

4) The two new method prototypes at the end of trgm.h use different
   indendation than the rest (spaces only instead of tabs).

Heikki Linnakangas <hlinnakangas@vmware.com> writes:
> On 23.01.2013 09:36, Alexander Korotkov wrote:

>> On Wed, Jan 23, 2013 at 6:08 AM, Tom Lane<tgl@sss.pgh.pa.us>  wrote:
>>> The biggest problem is that I really don't care for the idea of
>>> contrib/pg_trgm being this cozy with the innards of regex_t.

>> The only option I see now is to provide a method like "export_cnfa" which
>> would export corresponding CNFA in fixed format.

> Yeah, I think that makes sense. The transformation code in trgm_regexp.c
> would probably be more readable too, if it didn't have to deal with the
> regex guts representation of the CNFA. Also, once you have intermediate
> representation of the original CNFA, you could do some of the
> transformation work on that representation, before building the
> "tranformed graph" containing trigrams. You could eliminate any
> non-alphanumeric characters, joining states connected by arcs with
> non-alphanumeric characters, for example.

It's not just the CNFA though; the other big API problem is with mapping
colors back to characters.  Right now, that not only knows way too much
about a part of the regex internals we have ambitions to change soon,
but it also requires pg_wchar2mb_with_len() and lowerstr(), neither of
which should be known to the regex library IMO.  So I'm not sure how we
divvy that up sanely.  To be clear: I'm not going to insist that we have
to have a clean API factorization before we commit this at all.  But it
worries me if we don't even know how we could get to that, because we
are going to need it eventually.

One thing that bothers me with this algoritm is that the overflow mechanism is all-or-nothing. In many cases, even when there is a huge number of states in the diagram, you could still extract at least a few trigrams that must be present in any matching string, with little effort. At least, it seems like that to a human :-).

For example, consider this:

explain analyze select count(*) from azjunk4 where txt ~ ('^aabaacaadaaeaafaagaahaaiaajaakaalaamaanaaoaapaaqaaraasaataauaavaawaaxaayaazabaabbabcabdabeabfabgabhabiabjabkablabmabnaboabpabqabrabsabtabuabvabwabxabyabzacaacbaccacdaceacfacgachaciacjackaclacmacnacoacpacqacracsactacuacvacwacxacyaczadaadbadcaddadeadfadgadhadiadjadkadladmadnadoadpadqadradsadtaduadvadwadxadyadzaeaaebaecaedaeeaefaegaehaeiaejaekaelaemaenaeoaepaeqaeraesaetaeuaevaewaexaeyaezafaafbafcafdafeaffafgafhafiafjafkaflafmafnafoafpafqafrafsaftafuafvafwafxafyafzagaagbagcagdageagfaggaghagiagjagkaglagmagnagoagpagqagragsagtaguagvagwagxagyagzahaahbahcahdaheahfahgahhahiahjahkahlahmahnahoahpahqahrahs$');

you get a query plan like this (the long regexp string edited out):

 Aggregate  (cost=228148.02..228148.03 rows=1 width=0) (actual time=131.100..131
.101 rows=1 loops=1)
   ->  Bitmap Heap Scan on azjunk4  (cost=228144.01..228148.02 rows=1 width=0) (
actual time=131.096..131.096 rows=0 loops=1)
         Recheck Cond: (txt ~ <ridiculously long regexp>)
         Rows Removed by Index Recheck: 10000
         ->  Bitmap Index Scan on azjunk4_trgmrgx_txt_01_idx (cost=0.00..228144
.01 rows=1 width=0) (actual time=82.914..82.914 rows=10000 loops=1)
               Index Cond: (txt ~ <ridiculously long regexp>)
 Total runtime: 131.230 ms
(7 rows)

That ridiculously long string exceeds the number of states (I think, could be number of paths or arcs too), and the algorithm gives up, resorting to scanning the whole index as can be seen by the "Rows Removed by Index Recheck" line. However, it's easy to see that any matching string must contain *any* of the possible trigrams the algorithm extracts. If it could safely return just a few of them, say "aab" and "abz", and discard the rest, that would already be much better than a full index scan.

Would it be safe to simply stop short the depth-first search on overflow, and proceed with the graph that was constructed up to that point?

On Wed, Jan 23, 2013 at 7:29 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Heikki Linnakangas <hlinnakangas@vmware.com> writes:
> On 23.01.2013 09:36, Alexander Korotkov wrote:

>> On Wed, Jan 23, 2013 at 6:08 AM, Tom Lane<tgl@sss.pgh.pa.us>  wrote:
>>> The biggest problem is that I really don't care for the idea of
>>> contrib/pg_trgm being this cozy with the innards of regex_t.

>> The only option I see now is to provide a method like "export_cnfa" which
>> would export corresponding CNFA in fixed format.

> Yeah, I think that makes sense. The transformation code in trgm_regexp.c
> would probably be more readable too, if it didn't have to deal with the
> regex guts representation of the CNFA. Also, once you have intermediate
> representation of the original CNFA, you could do some of the
> transformation work on that representation, before building the
> "tranformed graph" containing trigrams. You could eliminate any
> non-alphanumeric characters, joining states connected by arcs with
> non-alphanumeric characters, for example.

It's not just the CNFA though; the other big API problem is with mapping
colors back to characters.  Right now, that not only knows way too much
about a part of the regex internals we have ambitions to change soon,
but it also requires pg_wchar2mb_with_len() and lowerstr(), neither of
which should be known to the regex library IMO.  So I'm not sure how we
divvy that up sanely.  To be clear: I'm not going to insist that we have
to have a clean API factorization before we commit this at all.  But it
worries me if we don't even know how we could get to that, because we
are going to need it eventually.

Now I have following idea about API.

Put code of stage 2 (transform the original CNFA into an automaton-like graph) into regex engine. It would use API which describes what exactly are we going to extract from CNFA. This API could look like this.

typedef char *Prefix;

typedef char *ArcLabel;

typedef struct

{

Prefix newPrefix;

ArcLabel label;

} ArcInfo;

typedef struct

{

Prefix (*getInitialPrefix) ();

bool (*prefixContains) (Prefix prefix1, Prefix prefix2);

Prefix * (*getPrefixes) (Prefix prefix, color c, int *n);

ArcInfo * (*getArcs) (Prefix prefix, color c, int *n);

void (*freePrefix) (Prefix prefix);

void (*freeArcLabel) (ArcLabel arcLabel);

} CFNATransformAPI;

getInitialPrefix returns initial prefix value like now this code does:

> initkey.prefix.colors[0] = UNKNOWN_COLOR;

> initkey.prefix.colors[1] = UNKNOWN_COLOR;

prefixContains are exactly same as function with this name.

getPrefixes and getArcs cycle step work of addKeys an addArcs.

freePrefix and freeArcLabel frees used memory of Prefix and ArcLabel strutures.

Additionally regex engine should provide correct way to examine colormap.

int getColorCharsCount(colormap *cm, color c);

pg_wchar *getColorChars(colormap *cm, color c);

getColorCharsCount would return -1 if this color should be considered as unexpandable.

Now I'm working on additional comments.

On Fri, November 30, 2012 12:22, Alexander Korotkov wrote:
> Hi!
>
> On Thu, Nov 29, 2012 at 12:58 PM, er <er@xs4all.nl> wrote:
>
>> On Mon, November 26, 2012 20:49, Alexander Korotkov wrote:
>>
>>

>> I ran the simple-minded tests against generated data (similar to the ones
>> I did in January 2012).
>> The problems of that older version seem pretty much all removed. (although
>> I didn't do much work
>> on it -- just reran these tests).
>>
>
> Thanks a lot for testing! Could you repeat for 0.7 version of patch which
> has new overflow handling?
>

I've attached a similar test re-run that compares HEAD with patch versions 0.6, and 0.7.

Actually, I generally dislike path matrix for same reasons. But:

1) Output graphs could contain trigrams which are completely useless for search. For example, for regex /(abcdefgh)*ijk/ we need only "ijk" trigram while graph would contain much more.Path matrix is a method to get rid of all of them.

2) If we use color trigrams then we need some criteria for which color trigrams to expand into trigrams. Simultaneously, we shouldn't allow path from initial state to the final by unexpanded trigrams. It seems much harder to do with graph than with matrix.

On Wed, January 23, 2013 08:36, Alexander Korotkov wrote:
> Hi!
>
> Some quick answers to the part of notes/issues. I will provide rest of
> answers soon.
>

[...]
> trgm-regexp-0.10.patch.gz    27 k

Trying to build this I get, after 'make install' in contrib/ :

/usr/bin/install: cannot stat `./pg_trgm--1.1.sql': No such file or directory
/usr/bin/install: cannot stat `./pg_trgm--1.0--1.1.sql': No such file or directory
make[1]: *** [install] Error 1

make: *** [install-pg_trgm-recurse] Error 2

On Fri, Jan 20, 2012 at 12:30 AM, Heikki Linnakangas <heikki.linnakangas@enterprisedb.com> wrote:

Apart from that, the multibyte issue seems like the big one. Any way around that?

Conversion of pg_wchar to multibyte character is the only way I found to avoid serious hacking of existing regexp code. Do you think additional function in pg_wchar_tbl which converts pg_wchar back to multibyte character is possible solution?

The patch yields spectacular speedups with small, simple-enough regexen.  But it does not do a

good enough job when guessing where to use the index and where fall back to Seq Scan.  This can
lead to (also spectacular) slow-downs, compared to Seq Scan.

I guessed that MAX_COLOR_CHARS limits the character class size (to 4, in your patch), is that
true?   I can understand you want that value to be low to limit the above risk, but now it reduces
the usability of the feature a bit: one has to split up larger char-classes into several smaller
ones to make a statement use the index: i.e.:

Btw, it seems impossible to Ctrl-C out of a search once it is submitted; I suppose this is
normally necessary for perfomance reasons, but it would be useful te be able to compile a test
version that allows it.  I don't know how hard that would be.

There is also a minor bug, I think, when running with  'set enable_seqscan=off'  in combination
with a too-large regex:

On Mon, November 26, 2012 20:49, Alexander Korotkov wrote:

> trgm-regexp-0.6.patch.gz

I ran the simple-minded tests against generated data (similar to the ones I did in January 2012).
The problems of that older version seem pretty much all removed. (although I didn't do much work
on it -- just reran these tests).

Didn't reproduce it yet. Can you retry it with this line uncommented:

#define TRGM_REGEXP_DEBUG

Then we can see which stage it fails.

6) It does not compile - I do get a bunch of errors like this

7) Once fixed, it seems to work

CREATE EXTENSION pg_trgm ;
CREATE TABLE TEST (val TEXT);
INSERT INTO test
       SELECT md5(i::text) FROM generate_series(1,1000000) s(i);
CREATE INDEX trgm_idx ON test USING gin (val gin_trgm_ops);
ANALYZE test;

EXPLAIN SELECT * FROM test WHERE val ~ '.*qqq.*';


                           QUERY PLAN
---------------------------------------------------------------------
 Bitmap Heap Scan on test  (cost=16.77..385.16 rows=100 width=33)
   Recheck Cond: (val ~ '.*qqq.*'::text)
   ->  Bitmap Index Scan on trgm_idx  (cost=0.00..16.75 rows=100
                                       width=0)
         Index Cond: (val ~ '.*qqq.*'::text)
(4 rows)

but I do get a bunch of NOTICE messages with debugging info (no matter
if the GIN index is used or not, so it's somewhere in the common regexp
code). But I guess that's due to WIP status.

The code badly needs comments. There is no explanation of how the trigram extraction code in trgm_regexp.c works.

Guessing from the variable names, it seems to be some sort of a coloring algorithm that works on a graph, but that all needs to be explained. Can this algorithm be found somewhere in literature, perhaps? A link to a paper would be nice.

Apart from that, the multibyte issue seems like the big one. Any way around that?

Great, that top-level comment helped tremendously! I feel enlightened.

I fixed some spelling, formatting etc. trivial stuff while reading through the patch, see attached. Below is some feedback on the details:

* I don't like the PG_TRY/CATCH trick. It's not generally safe to catch an error, without propagating it further or rolling back the whole (sub)transation. It might work in this case, as you're only suppressing errors with the special sqlcode that are used in the same file, but it nevertheless feels naughty. I believe none of the limits that are being checked are strict; it's OK to exceed the limits somewhat, as long as you terminate the processing in a reasonable time, in case of pathological input. I'd suggest putting an explicit check for the limits somewhere, and not rely on ereport(). Something like this, in the code that recurses:

if (trgmCNFA->arcsCount > MAX_RESULT_ARCS ||
    hash_get_num_entries(trgmCNFA->states) > MAX_RESULT_STATES)
{
        trgmCNFA->overflowed = true;
        return;
}

And then check for the overflowed flag at the top level.

* This part of the high-level comment was not clear to me:

 * States of the graph produced in the first stage are marked with "keys". Key is a pair
 * of a "prefix" and a state of the original automaton. "Prefix" is a last
 * characters. So, knowing the prefix is enough to know what is a trigram when we read some new
 * character. However, we can know single character of prefix or don't know any
 * characters of it. Each state of resulting graph have an "enter key" (with that
 * key we've entered this state) and a set of keys which are reachable without
 * reading any predictable trigram. The algorithm of processing each state
 * of resulting graph are so:
 * 1) Add all keys which achievable without reading of any predictable trigram.
 * 2) Add outgoing arcs labeled with trigrams.
 * Step 2 leads to creation of new states and recursively processing them. So,
 * we use depth-first algorithm.

I didn't understand that. Can you elaborate? It might help to work through an example, with some ascii art depicting the graph.

* It would be nice to add some comments to TrgmCNFA struct, explaining which fields are valid at which stages. For example, it seems that 'trgms' array is calculated only after building the CNFA, by getTrgmVector() function, while arcsCount is updated on the fly, while recursing in the getState() function.

* What is the representation used for the path matrix? Needs a comment.

* What do the getColorinfo()

and scanColorMap() functions do?

What exactly does a color represent?

What's the tradeoff in choosing MAX_COLOR_CHARS?

do you plan to support GiST?