gsoc, oprrest function for text search take 2

Jan Urbański wrote:

Another thing are cstring_to_text_with_len calls. I'm doing them so I
can use bttextcmp in bsearch(). I think I could come up with a dedicated
function to return text Datums and WordEntries (read: non-NULL
terminated strings with a given length).

Just keep them as cstrings and use strcmp. We're only keeping the array
sorted so that we can binary search it, so we don't need proper
locale-dependent collation. Note that we already assume that two strings
('text's) are equal if and only if their binary representations are
equal (texteq() uses strcmp).

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

Heikki Linnakangas wrote:

Jan Urbański wrote:

Another thing are cstring_to_text_with_len calls. I'm doing them so I
can use bttextcmp in bsearch(). I think I could come up with a
dedicated function to return text Datums and WordEntries (read:
non-NULL terminated strings with a given length).

Just keep them as cstrings and use strcmp. We're only keeping the array
sorted so that we can binary search it, so we don't need proper
locale-dependent collation. Note that we already assume that two strings
('text's) are equal if and only if their binary representations are
equal (texteq() uses strcmp).

OK, I got rid of cstring->text calls and memory contexts as I went
through it. The only tiny ugliness is that there's one function used for
qsort() and another for bsearch(), because I'm sorting an array of texts
(from pg_statistic) and I'm binary searching for a lexeme (non-NULL
terminated string with length).
My medicore gprof skills got me:
0.00 0.22 5/5 OidFunctionCall4 [37]
[38]: 28.4 0.00 0.22 5 tssel [38] 0.00 0.17 5/5 get_restriction_variable [40] 0.03 0.01 5/10 pg_qsort [60] 0.00 0.00 5/5 get_attstatsslot [139]
0.00 0.17 5/5
get_restriction_variable [40]
0.03 0.01 5/10 pg_qsort [60]
0.00 0.00 5/5 get_attstatsslot [139]

Hopefully that says that the qsort() overhead is small compared to
munging through the planner Node.
Revised version of the patch attached.

Cheers,
Jan

--
Jan Urbanski
GPG key ID: E583D7D2

ouden estin

Jan Urbański wrote:

Heikki Linnakangas wrote:

Jan Urbański wrote:

Another thing are cstring_to_text_with_len calls. I'm doing them so I
can use bttextcmp in bsearch(). I think I could come up with a
dedicated function to return text Datums and WordEntries (read:
non-NULL terminated strings with a given length).

Just keep them as cstrings and use strcmp. We're only keeping the
array sorted so that we can binary search it, so we don't need proper
locale-dependent collation. Note that we already assume that two
strings ('text's) are equal if and only if their binary
representations are equal (texteq() uses strcmp).

OK, I got rid of cstring->text calls and memory contexts as I went
through it. The only tiny ugliness is that there's one function used for
qsort() and another for bsearch(), because I'm sorting an array of texts
(from pg_statistic) and I'm binary searching for a lexeme (non-NULL
terminated string with length).

It would be nice to clean that up a bit. I think you could convert the
lexeme to a TextFreq, or make the TextFreq.element a "text *" instead of
Datum (ie., detoast it with PG_DETOAST_DATUM while you build the array
for qsort).

My medicore gprof skills got me:
0.00 0.22 5/5 OidFunctionCall4 [37]
[38] 28.4 0.00 0.22 5 tssel [38]
0.00 0.17 5/5 get_restriction_variable [40]
0.03 0.01 5/10 pg_qsort [60]
0.00 0.00 5/5 get_attstatsslot [139]

Hopefully that says that the qsort() overhead is small compared to
munging through the planner Node.

I'd like to see a little bit more testing of that. I can't read gprof
myself, so the above doesn't give me much confidence. I use oprofile,
which I find is much simpler to use.

I think the worst case scenario is with statistics_target set to
maximum, with a simplest possible query and simplest possible tsquery.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

Heikki Linnakangas wrote:

Jan Urbański wrote:

through it. The only tiny ugliness is that there's one function used
for qsort() and another for bsearch(), because I'm sorting an array of
texts (from pg_statistic) and I'm binary searching for a lexeme
(non-NULL terminated string with length).

It would be nice to clean that up a bit. I think you could convert the
lexeme to a TextFreq, or make the TextFreq.element a "text *" instead of
Datum (ie., detoast it with PG_DETOAST_DATUM while you build the array
for qsort).

Hm, making it a text * won't help, I think, because the problem is:
- pg_statistics holds an array of text datums and an array of float
datums, ordered by the latter
- a tsquery is a tree of WordEntries (lexemes), ie. non-NULL
terminated strings

The approach was to:
(1) create an array of (text, float) pairs by zipping the two
pg_statistics arrays into one
(2) sort that array on text values
(3) every time a frequency of a WordEntry needs to be determined, look
it up using binary search in the sorted array

So for (2) I needed a function that compares text with text (I reused
bttext_pattern_cmp for that). And to do (3) I needed a function that
compares text with WordEntries. I didn't want to convert WordEntries
into "text *" values, because that would require a palloc().
Hmm, maybe I could build an array of (lexeme, float) in (1) instead,
turning "text *" into a lexeme is very straightforward. Then I'd use the
same function in (2) and (3) - cleaner.

However, maybe I should just skip all that qsort() nonsense and use a
hashtable?
Another bold thought is: keep the pg_statistics arrays for tsvectors
ordered by text datums, and not frequencies. Would've been awkward,
'cause people expect the most common frequencies array to be sorted and
not the most common values/elements one, but it'd help a lot and
simplify the code quite a bit. It would induce one extra qsort() in
ts_typanalyze(), but would allow only bsearch()es in tssel().

My medicore gprof skills got me:
[... nonsense ...]

I'd like to see a little bit more testing of that. I can't read gprof
myself, so the above doesn't give me much confidence. I use oprofile,
which I find is much simpler to use.
I think the worst case scenario is with statistics_target set to
maximum, with a simplest possible query and simplest possible tsquery.

One kernel recompile later...
I got oprofile running, here's the setup:
$ pgbench -n -f tssel-bench.sql -c 10 -t 1000 postgres
And here's tssel-bench.sql:
explain select * from manuals where tsvector @@ to_tsquery('foo');

The "manuals" table was rather small (but that's irrelevant I think) and
statistic_target for the "tsvector" column were set to 100.

Obviously foo() isn't a most common element in my test data, so the
bsearch()es always miss. The results are:
samples % symbol name
101507 13.4461 internal_text_pattern_compare
91398 12.1070 bttext_pattern_cmp
82753 10.9618 pg_detoast_datum_packed
66434 8.8001 pg_qsort
54005 7.1537 DirectFunctionCall2
48925 6.4808 pglz_decompress
44931 5.9518 compare_two_textfreqs
40178 5.3222 AllocSetAlloc
26763 3.5451 AllocSetCheck
20839 2.7604 AtEOXact_CatCache
16057 2.1270 AllocSetFree
13772 1.8243 swapfunc
10001 1.3248 .plt
7859 1.0410 text_to_cstring
7556 1.0009 datumCopy

So, maybe qsorting() every time you plan a query is not that cheap after
all. I think hashing would also be an overkill. How do peole feel about
storing the statistics sorted on values and not on frequencies?

Cheers,
Jan

PS:
I used a simple
$ opreport --symbols /path/to/postgres
are there any magic switches I need to add?

J

--
Jan Urbanski
GPG key ID: E583D7D2

ouden estin

Jan Urbański wrote:

26763 3.5451 AllocSetCheck

Make sure you disable assertions before profiling. Although I'm actually
a bit surprised the overhead isn't more than 3.5%, I've seen much higher
overheads on other tests, but it's still skewing the results.

- Heikki

Heikki Linnakangas wrote:

Jan Urbański wrote:

26763 3.5451 AllocSetCheck

Make sure you disable assertions before profiling.

Awww, darn. OK, here goes another set of results, without casserts this
time.

=== CVS HEAD ===

number of clients: 10
number of transactions per client: 100000
number of transactions actually processed: 1000000/1000000
tps = 6437.286494 (including connections establishing)
tps = 6438.168927 (excluding connections establishing)

samples % symbol name
220443 11.6613 AllocSetAlloc
79355 4.1978 base_yyparse
77230 4.0854 SearchCatCache
56011 2.9629 hash_search_with_hash_value
45946 2.4305 MemoryContextAllocZeroAligned
38577 2.0407 hash_any
36414 1.9263 MemoryContextAlloc
33060 1.7489 AllocSetFree
27218 1.4398 ScanKeywordLookup
25793 1.3644 base_yylex
20579 1.0886 hash_uint32
18867 0.9981 hash_seq_search
18293 0.9677 expression_tree_walker
17696 0.9361 copyObject
16979 0.8982 LockAcquire
14292 0.7560 MemoryContextAllocZero
13117 0.6939 SearchSysCache

=== ts_sel ====

number of clients: 10
number of transactions per client: 100000
number of transactions actually processed: 1000000/1000000
tps = 3216.753677 (including connections establishing)
tps = 3216.996592 (excluding connections establishing)

942096 10.9130 internal_text_pattern_compare
809195 9.3735 bttext_pattern_cmp
659545 7.6400 pg_detoast_datum_packed
628114 7.2759 pg_qsort
603998 6.9966 AllocSetAlloc
581880 6.7403 pglz_decompress
467708 5.4178 DirectFunctionCall2
385854 4.4696 compare_two_textfreqs
160578 1.8601 AllocSetFree
128642 1.4902 swapfunc
112885 1.3076 MemoryContextAlloc
103388 1.1976 SearchCatCache
100387 1.1629 text_to_cstring
99004 1.1468 hash_search_with_hash_value
98444 1.1403 .plt
92664 1.0734 base_yyparse
88511 1.0253 errstart

Not good... Shall I try sorting pg_statistics arrays on text values
instead of frequencies?
BTW: I just noticed some text_to_cstring calls, they came from
elog(DEBUG1)s that I have in my code. But they couldn't have skewn the
results much, could they?

Cheers,
Jan

--
Jan Urbanski
GPG key ID: E583D7D2

ouden estin

Jan Urbański wrote:

Not good... Shall I try sorting pg_statistics arrays on text values
instead of frequencies?

Yeah, I'd go with that. If you only do it for the new
STATISTIC_KIND_MCV_ELEMENT statistics, you shouldn't need to change any
other code.

Hmm. There has been discussion on raising default_statistic_target, and
one reason why we've been afraid to do so has been that it increases the
cost of planning (there's some O(n^2) algorithms in there). Pre-sorting
the STATISTIC_KIND_MCV array as well, and replacing the linear searches
with binary searches would alleviate that, which would be nice.

BTW: I just noticed some text_to_cstring calls, they came from
elog(DEBUG1)s that I have in my code. But they couldn't have skewn the
results much, could they?

Well, text_to_cstring was consuming 1.1% of the CPU time on its own, and
presumably some of the AllocSetAlloc overhead is attributable to that as
well. And perhaps some of the detoasting as well.

Speaking of which, a lot of time seems to be spent on detoasting. I'd
like to understand that a better. Where is the detoasting coming from?

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

Heikki Linnakangas wrote:

Jan Urbański wrote:

Not good... Shall I try sorting pg_statistics arrays on text values
instead of frequencies?

Yeah, I'd go with that. If you only do it for the new
STATISTIC_KIND_MCV_ELEMENT statistics, you shouldn't need to change any
other code.

OK, will do.

BTW: I just noticed some text_to_cstring calls, they came from
elog(DEBUG1)s that I have in my code. But they couldn't have skewn the
results much, could they?

Well, text_to_cstring was consuming 1.1% of the CPU time on its own, and
presumably some of the AllocSetAlloc overhead is attributable to that as
well. And perhaps some of the detoasting as well.

Speaking of which, a lot of time seems to be spent on detoasting. I'd
like to understand that a better. Where is the detoasting coming from?

Hmm, maybe bttext_pattern_cmp does some detoasting? It calls
PG_GETARG_TEXT_PP(), which in turn calls pg_detoast_datum_packed(). Oh,
and also I think that compare_lexeme_textfreq() uses DatumGetTextP() and
that also does detoasting. The root of all evil could by keeping a Datum
in the TextFreq array, and not a "text *", which is something you
pointed out earlier and I apparently didn't understand.

So right now the idea is to:
(1) pre-sort STATISTIC_KIND_MCELEM values
(2) build an array of pointers to detoasted values in tssel()
(3) use binary search when looking for MCELEMs during tsquery analysis

Jan

--
Jan Urbanski
GPG key ID: E583D7D2

ouden estin

Jan Urbański wrote:

So right now the idea is to:
(1) pre-sort STATISTIC_KIND_MCELEM values
(2) build an array of pointers to detoasted values in tssel()
(3) use binary search when looking for MCELEMs during tsquery analysis

Sounds like a plan. In (2), it's even better to detoast the values
lazily. For a typical one-word tsquery, the binary search will only look
at a small portion of the elements.

Another thing is, how significant is the time spent in tssel() anyway,
compared to actually running the query? You ran pgbench on EXPLAIN,
which is good to see where in tssel() the time is spent, but if the time
spent in tssel() is say 1% of the total execution time, there's no point
optimizing it further.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

Jan Urbański <j.urbanski@students.mimuw.edu.pl> writes:

Heikki Linnakangas wrote:

Speaking of which, a lot of time seems to be spent on detoasting. I'd like to
understand that a better. Where is the detoasting coming from?

Hmm, maybe bttext_pattern_cmp does some detoasting? It calls
PG_GETARG_TEXT_PP(), which in turn calls pg_detoast_datum_packed(). Oh, and
also I think that compare_lexeme_textfreq() uses DatumGetTextP() and that also
does detoasting.

DatumGetTextP() will detoast packed data (ie, 1-byte length headers) whereas
DatumGetTextPP will only detoast compressed or externally stored data. I
suspect you're seeing the former.

The root of all evil could by keeping a Datum in the TextFreq array, and not
a "text *", which is something you pointed out earlier and I apparently
didn't understand.

Well it doesn't really matter which type. If you store Datums which are
already detoasted then the DatumGetTextP and DatumGetTextPP will just be noops
anyways. If you store packed data (from DatumGetTextPP) then it's probably
safer to store it as Datums so if you need to pass it to any functions which
don't expect packed data they'll untoast it.

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com
Ask me about EnterpriseDB's Slony Replication support!

Heikki Linnakangas wrote:

Jan Urbański wrote:

So right now the idea is to:
(1) pre-sort STATISTIC_KIND_MCELEM values
(2) build an array of pointers to detoasted values in tssel()
(3) use binary search when looking for MCELEMs during tsquery analysis

Sounds like a plan. In (2), it's even better to detoast the values
lazily. For a typical one-word tsquery, the binary search will only look
at a small portion of the elements.

Hm, how can I do that? Toast is still a bit black magic to me... Do you
mean I should stick to having Datums in TextFreq? And use DatumGetTextP
in bsearch() (assuming I'll get rid of qsort())? I wanted to avoid that,
so I won't detoast the same value multiple times, but it's true: a
binary search won't touch most elements.

Another thing is, how significant is the time spent in tssel() anyway,
compared to actually running the query? You ran pgbench on EXPLAIN,
which is good to see where in tssel() the time is spent, but if the time
spent in tssel() is say 1% of the total execution time, there's no point
optimizing it further.

Changed to the pgbench script to
select * from manual where tsvector @@ to_tsquery('foo');
and the parameters to
pgbench -n -f tssel-bench.sql -t 1000 postgres

and got

number of clients: 1
number of transactions per client: 1000
number of transactions actually processed: 1000/1000
tps = 12.238282 (including connections establishing)
tps = 12.238606 (excluding connections establishing)

samples % symbol name
174731 31.6200 pglz_decompress
88105 15.9438 tsvectorout
17280 3.1271 pg_mblen
13623 2.4653 AllocSetAlloc
13059 2.3632 hash_search_with_hash_value
10845 1.9626 pg_utf_mblen
10335 1.8703 internal_text_pattern_compare
9196 1.6641 index_getnext
9102 1.6471 bttext_pattern_cmp
8075 1.4613 pg_detoast_datum_packed
7437 1.3458 LWLockAcquire
7066 1.2787 hash_any
6811 1.2325 AllocSetFree
6623 1.1985 pg_qsort
6439 1.1652 LWLockRelease
5793 1.0483 DirectFunctionCall2
5322 0.9631 _bt_compare
4664 0.8440 tsCompareString
4636 0.8389 .plt
4539 0.8214 compare_two_textfreqs

But I think I'll go with pre-sorting anyway, it feels cleaner and neater.
--
Jan Urbanski
GPG key ID: E583D7D2

ouden estin

Heikki Linnakangas wrote:

Jan Urbański wrote:

So right now the idea is to:
(1) pre-sort STATISTIC_KIND_MCELEM values
(2) build an array of pointers to detoasted values in tssel()
(3) use binary search when looking for MCELEMs during tsquery analysis

Sounds like a plan. In (2), it's even better to detoast the values
lazily. For a typical one-word tsquery, the binary search will only look
at a small portion of the elements.

Here's another version.

Most common lexemes get sorted before storing in pg_statistic. The
ordering is on length first and value second. That way we can avoid
strncmp() calls when the lexemes have different lengths (and lexemes
know their lengths, so the data is readily available). Also, in the
binary search routine during selectivity estimation we can sometimes
avoid detoasting (I think) Datums from the pg_statistic MCELEM array.
See comments in code.

Pre-sorting introduced one problem (see XXX in code): it's not easy
anymore to get the minimal frequency of MCELEM values. I was using it to
assert that the selectivity of a tsquery node containing a lexeme not in
MCELEM is no more that min(MCELEM freqs) / 2. That's only significant
when the minimum frequency is less than DEFAULT_TS_SEL * 2, so I'm kind
of inclined to ignore it and maybe drop a comment in the code that this
may be a potential problem.

If nothing is fundamentally broken with this, I'll repeat my profiling
tests to see if anything has been gained.

Cheers,
Jan

--
Jan Urbanski
GPG key ID: E583D7D2

ouden estin

Jan Urbański wrote:

Heikki Linnakangas wrote:

Jan Urbański wrote:

So right now the idea is to:
(1) pre-sort STATISTIC_KIND_MCELEM values
(2) build an array of pointers to detoasted values in tssel()
(3) use binary search when looking for MCELEMs during tsquery analysis

Sounds like a plan. In (2), it's even better to detoast the values
lazily. For a typical one-word tsquery, the binary search will only
look at a small portion of the elements.

Here's another version.

Context diff this time, always forget to convert them...

--
Jan Urbanski
GPG key ID: E583D7D2

ouden estin

Jan Urbański wrote:

Heikki Linnakangas wrote:

Sounds like a plan. In (2), it's even better to detoast the values
lazily. For a typical one-word tsquery, the binary search will only
look at a small portion of the elements.

Hm, how can I do that? Toast is still a bit black magic to me... Do you
mean I should stick to having Datums in TextFreq?

Store both the Datum and the text *. If the latter is NULL, then grab
the datum, detoast and store the result in the text *. Next time you
need to look at it, it's already detoasted.

I don't know the code so I have no idea if this is applicable.

--
Alvaro Herrera http://www.CommandPrompt.com/
The PostgreSQL Company - Command Prompt, Inc.

Alvaro Herrera wrote:

Jan Urbański wrote:

Heikki Linnakangas wrote:

Sounds like a plan. In (2), it's even better to detoast the values
lazily. For a typical one-word tsquery, the binary search will only
look at a small portion of the elements.

Hm, how can I do that? Toast is still a bit black magic to me... Do you
mean I should stick to having Datums in TextFreq?

Store both the Datum and the text *. If the latter is NULL, then grab
the datum, detoast and store the result in the text *. Next time you
need to look at it, it's already detoasted.

Yeah, I got that idea, but then I thought the chances of touching the
same element during binary search twice were very small. Especially now
when the detoasting occurs only when we hit a text Datum that has the
same length as the sought lexeme.
Still, I can do it if people feel like it.

Cheers,
Jan

--
Jan Urbanski
GPG key ID: E583D7D2

ouden estin

Jan Urbański wrote:

Yeah, I got that idea, but then I thought the chances of touching the
same element during binary search twice were very small. Especially now
when the detoasting occurs only when we hit a text Datum that has the
same length as the sought lexeme.
Still, I can do it if people feel like it.

Actually, in that light it sounds pretty useless.

--
Alvaro Herrera http://www.CommandPrompt.com/
PostgreSQL Replication, Consulting, Custom Development, 24x7 support

Simon Riggs wrote:

On Thu, 2008-08-14 at 22:27 +0200, Jan Urbański wrote:

Jan Urbański wrote:

+ * ts_selfuncs.c

Not sure why this is in its own file

I couldn't decide where to put it, so I came up with this.

put it in a file called selfuncs_ts.c so it is similar to the existing
filename?

I followed the pattern of ts_parse.c, ts_utils.c and so on.
Also, I see geo_selfuncs.c. No big deal, though, I can move it.

Cheers,
Jan

--
Jan Urbanski
GPG key ID: E583D7D2

ouden estin

On Thu, 2008-08-14 at 22:27 +0200, Jan Urbański wrote:

Jan Urbański wrote:

+ * ts_selfuncs.c

Not sure why this is in its own file, but if it must be could we please
put it in a file called selfuncs_ts.c so it is similar to the existing
filename?

--
Simon Riggs www.2ndQuadrant.com
PostgreSQL Training, Services and Support

On Tue, 2008-08-26 at 12:45 +0200, Jan Urbański wrote:

put it in a file called selfuncs_ts.c so it is similar to the existing
filename?

I followed the pattern of ts_parse.c, ts_utils.c and so on.
Also, I see geo_selfuncs.c. No big deal, though, I can move it.

No don't worry. You're right, the horse has already bolted.

--
Simon Riggs www.2ndQuadrant.com
PostgreSQL Training, Services and Support