like/ilike improvements
Starting from a review of a patch from Itagaki Takahiro to improve LIKE
performance for UTF8-encoded databases, I have been working on improving
both efficiency of the LIKE/ILIKE code and the code quality.
The main efficiency improvement comes from some fairly tricky analysis
and discussion on -patches. Essentially there are two calls that we make
to advance the text and pattern cursors: NextByte and NextChar. In the
case of single byte charsets these are in fact the same thing, but in
multi byte charsets they are obviously not, and in that case NextChar is
a lot more expensive. It turns out (according to the analysis) that the
only time we actually need to use NextChar is when we are matching an
"_" in a like/ilike pattern. It also turns out that there are some
comparison tests that we can hoist out of a loop and thus avoid
repeating over and over. Also, some calls can be marked "inline" to
improve efficiency. Finally, the special case of computing lower(x) on
the fly for ILIKE comparisons on single byte charset strings turns out
to have the potential to call lower() O(n^2) times, so it has been
removed and we now treat foo ILIKE bar as lower(foo) LIKE lower(bar) for
all charsets uniformly. There will be cases where this approach wins and
cases where it loses, but the wins are potentially dramatic, whereas the
losses should be mild.
The current state of this work is at
http://archives.postgresql.org/pgsql-patches/2007-05/msg00385.php
I've been testing it using a set of 5m rows of random Latin1 data - each
row is between 100 and 400 chars long, and 20% of them (roughly) have
the string "foo" randomly located within them. The test platform is
gcc/fc6/AMD64.
I have loaded the data into both Latin1 and UTF8 encoded databases. (I'm
not sure if there are other multibyte charsets that are compatible with
Latin1 client encoding). My test is essentially:
select count(*) from footable where t like '%_foo%';
select count(*) from footable where t ilike '%_foo%';
select count(*) from footable where t like '%foo%';
select count(*) from footable where t ilike '%foo%';
Note that the "%_" case is probably the worst for these changes, since
it involves lots of calls to NextChar() (see above).
The multibyte results show significant improvement. The results are
about flat or a slight improvement for the singlebyte cases. I'll post
some numbers on this shortly.
But before I commit this I'd appreciate seeing some more testing, both
for correctness and performance.
cheers
andrew
Andrew Dunstan <andrew@dunslane.net> writes:
... It turns out (according to the analysis) that the
only time we actually need to use NextChar is when we are matching an
"_" in a like/ilike pattern.
I thought we'd determined that advancing bytewise for "%" was also risky,
in two cases:
1. Multibyte character set that is not UTF8 (more specifically, does not
have a guarantee that first bytes and not-first bytes are distinct)
2. "_" immediately follows the "%".
regards, tom lane
Tom Lane wrote:
Andrew Dunstan <andrew@dunslane.net> writes:
... It turns out (according to the analysis) that the
only time we actually need to use NextChar is when we are matching an
"_" in a like/ilike pattern.I thought we'd determined that advancing bytewise for "%" was also risky,
in two cases:1. Multibyte character set that is not UTF8 (more specifically, does not
have a guarantee that first bytes and not-first bytes are distinct)
I will review - I thought we had ruled that out.
Which non-UTF8 multi-byte charset would be best to test with?
2. "_" immediately follows the "%".
The patch in fact calls NextChar in this case.
cheers
andrew
Andrew Dunstan wrote:
Tom Lane wrote:
Andrew Dunstan <andrew@dunslane.net> writes:
... It turns out (according to the analysis) that the only time we
actually need to use NextChar is when we are matching an "_" in a
like/ilike pattern.I thought we'd determined that advancing bytewise for "%" was also
risky,
in two cases:1. Multibyte character set that is not UTF8 (more specifically, does not
have a guarantee that first bytes and not-first bytes are distinct)
I thought we disposed of the idea that there was a problem with charsets
that didn't do first byte special.
And Dennis said:
Tom Lane skrev:
You could imagine trying to do
% a byte at a time (and indeed that's what I'd been thinking it did)
but that gets you out of sync which breaks the _ case.It is only when you have a pattern like '%_' when this is a problem
and we could detect this and do byte by byte when it's not. Now we
check (*p == '\\') || (*p == '_') in each iteration when we scan over
characters for '%', and we could do it once and have different loops
for the two cases.
That's pretty much what the patch does now - It never tries to match a
single byte when it sees "_", whether or not preceeded by "%".
cheers
andrew
Andrew Dunstan <andrew@dunslane.net> writes:
Tom Lane wrote:
I thought we'd determined that advancing bytewise for "%" was also
risky, in two cases:1. Multibyte character set that is not UTF8 (more specifically, does not
have a guarantee that first bytes and not-first bytes are distinct)
I thought we disposed of the idea that there was a problem with charsets
that didn't do first byte special.
We disposed of that in connection with a version of the patch that had
"%" advancing in NextChar units, so that comparison of ordinary
characters was always safely char-aligned. Consider 2-byte characters
represented as {AB} etc:
DATA x{AB}{CD}y
PATTERN %{BC}%
If "%" advances by bytes then this will find a spurious match. The
only thing that prevents it is if "B" can't be both a leading and a
trailing byte of validly-encoded MB characters.
regards, tom lane
On 5/22/07, Andrew Dunstan <andrew@dunslane.net> wrote:
But before I commit this I'd appreciate seeing some more testing, both
for correctness and performance.
Any chance the patch applies cleanly on a 8.2 code base? I can test it
on a real life 8.2 db but I won't have the time to load the data in a
CVS HEAD one.
If there is no obvious reason for it to fail on 8.2, I'll try to see
if I can apply it.
Thanks.
--
Guillaume
On 2007-05-22, Tom Lane <tgl@sss.pgh.pa.us> wrote:
If "%" advances by bytes then this will find a spurious match. The
only thing that prevents it is if "B" can't be both a leading and a
trailing byte of validly-encoded MB characters.
Which is (by design) true in UTF8, but is not true of most other
multibyte charsets.
The %_ case is also trivially handled in UTF8 by simply ensuring that
_ doesn't match a non-initial octet. This allows % to advance by bytes
without danger of losing sync.
--
Andrew, Supernews
http://www.supernews.com - individual and corporate NNTP services
On Tue, May 22, 2007 at 12:12:51PM -0400, Tom Lane wrote:
Andrew Dunstan <andrew@dunslane.net> writes:
... It turns out (according to the analysis) that the
only time we actually need to use NextChar is when we are matching an
"_" in a like/ilike pattern.I thought we'd determined that advancing bytewise for "%" was also risky,
in two cases:
1. Multibyte character set that is not UTF8 (more specifically, does not
have a guarantee that first bytes and not-first bytes are distinct)
2. "_" immediately follows the "%".
Have you considered a two pass approach? First pass - match on bytes.
Only if you find a match with the first pass, start a second pass to
do a 'safe' check?
Are there optimizations to recognize whether the index was created as
lower(field) or upper(field), and translate ILIKE to the appropriate
one?
Cheers,
mark
--
mark@mielke.cc / markm@ncf.ca / markm@nortel.com __________________________
. . _ ._ . . .__ . . ._. .__ . . . .__ | Neighbourhood Coder
|\/| |_| |_| |/ |_ |\/| | |_ | |/ |_ |
| | | | | \ | \ |__ . | | .|. |__ |__ | \ |__ | Ottawa, Ontario, Canada
One ring to rule them all, one ring to find them, one ring to bring them all
and in the darkness bind them...
Andrew - Supernews <andrew+nonews@supernews.com> writes:
On 2007-05-22, Tom Lane <tgl@sss.pgh.pa.us> wrote:
If "%" advances by bytes then this will find a spurious match. The
only thing that prevents it is if "B" can't be both a leading and a
trailing byte of validly-encoded MB characters.
Which is (by design) true in UTF8, but is not true of most other
multibyte charsets.
The %_ case is also trivially handled in UTF8 by simply ensuring that
_ doesn't match a non-initial octet. This allows % to advance by bytes
without danger of losing sync.
Yeah. It seems we need three comparison functions after all:
1. Single-byte character set: needs NextByte and ByteEq only.
2. Generic multi-byte character set: both % and _ must advance by
characters to ensure we never try an out-of-alignment character
comparison. But simple character comparison works bytewise given
that. So primitives are NextChar, NextByte, ByteEq.
3. UTF8: % can advance bytewise. _ must check it is on a first byte
(else return match failure) and if so do NextChar. So primitives
are NextChar, NextByte, ByteEq, IsFirstByte.
In no case do we need CharEq. I'd be inclined to drop ByteEq as a
macro and just use "==", too.
regards, tom lane
Tom Lane wrote:
Yeah. It seems we need three comparison functions after all:
Yeah, that was my confusion. I thought we had concluded that we didn't,
but clearly we do.
1. Single-byte character set: needs NextByte and ByteEq only.
2. Generic multi-byte character set: both % and _ must advance by
characters to ensure we never try an out-of-alignment character
comparison. But simple character comparison works bytewise given
that. So primitives are NextChar, NextByte, ByteEq.3. UTF8: % can advance bytewise. _ must check it is on a first byte
(else return match failure) and if so do NextChar. So primitives
are NextChar, NextByte, ByteEq, IsFirstByte.In no case do we need CharEq. I'd be inclined to drop ByteEq as a
macro and just use "==", too.
I'll work this up. I think it will be easier if I marry cases 1 and 2,
with NextChar being the same as NextByte in the single byte case.
cheers
andrew
And Dennis said:
It is only when you have a pattern like '%_' when this is a problem
and we could detect this and do byte by byte when it's not. Now we
check (*p == '\\') || (*p == '_') in each iteration when we scan over
characters for '%', and we could do it once and have different loops
for the two cases.That's pretty much what the patch does now - It never tries to match a
single byte when it sees "_", whether or not preceeded by "%".
My comment was about UTF-8 since I thought we were making a special
version for UTF-8. I don't know what properties other multibyte encodings
have.
/Dennis
Tom Lane wrote:
3. UTF8: % can advance bytewise. _ must check it is on a first byte
(else return match failure) and if so do NextChar. So primitives
are NextChar, NextByte, ByteEq, IsFirstByte.
We should only be able to get out of step from the "%_" case, I believe,
so we should only need to do the first-byte test in that case (which is
in a different code path from the normal "_" case. Does that seem right?
cheers
andrew
Andrew Dunstan <andrew@dunslane.net> writes:
We should only be able to get out of step from the "%_" case, I believe,
so we should only need to do the first-byte test in that case (which is
in a different code path from the normal "_" case. Does that seem right?
At least put Assert(IsFirstByte()) in the main path.
I'm a bit suspicious of the separate-path business anyway. Will it do
the right thing with say "%%%_" ?
regards, tom lane
Tom Lane wrote:
Andrew Dunstan <andrew@dunslane.net> writes:
We should only be able to get out of step from the "%_" case, I believe,
so we should only need to do the first-byte test in that case (which is
in a different code path from the normal "_" case. Does that seem right?At least put Assert(IsFirstByte()) in the main path.
I'm a bit suspicious of the separate-path business anyway. Will it do
the right thing with say "%%%_" ?
Yes:
/* %% is the same as % according to the SQL standard */
/* Advance past all %'s */
while ((plen > 0) && (*p == '%'))
NextByte(p, plen);
cheers
andrew
Andrew Dunstan wrote:
Tom Lane wrote:
Andrew Dunstan <andrew@dunslane.net> writes:
We should only be able to get out of step from the "%_" case, I
believe, so we should only need to do the first-byte test in that
case (which is in a different code path from the normal "_" case.
Does that seem right?At least put Assert(IsFirstByte()) in the main path.
I'm a bit suspicious of the separate-path business anyway. Will it do
the right thing with say "%%%_" ?Yes:
/* %% is the same as % according to the SQL standard */
/* Advance past all %'s */
while ((plen > 0) && (*p == '%'))
NextByte(p, plen);
I am also wondering if it might be sensible to make this choice once at
backend startup and store a function pointer, instead of doing it for
every string processed by like/ilike:
if (pg_database_encoding_max_length() == 1)
return SB_MatchText(s, slen, p, plen);
else if (GetDatabaseEncoding() == PG_UTF8)
return UTF8_MatchText(s, slen, p, plen);
else
return MB_MatchText(s, slen, p, plen);
I guess that might make matters harder if we ever got per-column encodings.
cheers
andrew
Andrew Dunstan <andrew@dunslane.net> writes:
I am also wondering if it might be sensible to make this choice once at
backend startup and store a function pointer, instead of doing it for
every string processed by like/ilike:
if (pg_database_encoding_max_length() == 1)
return SB_MatchText(s, slen, p, plen);
else if (GetDatabaseEncoding() == PG_UTF8)
return UTF8_MatchText(s, slen, p, plen);
else
return MB_MatchText(s, slen, p, plen);
I guess that might make matters harder if we ever got per-column encodings.
Yeah. It's not saving much anyway ... I wouldn't bother.
regards, tom lane
Tom Lane wrote:
Andrew Dunstan <andrew@dunslane.net> writes:
We should only be able to get out of step from the "%_" case, I believe,
so we should only need to do the first-byte test in that case (which is
in a different code path from the normal "_" case. Does that seem right?At least put Assert(IsFirstByte()) in the main path.
I'm a bit suspicious of the separate-path business anyway. Will it do
the right thing with say "%%%_" ?
OK, Here is a patch that I am fairly confident does what's been
discussed, as summarised by Tom.
To answer Guillaume's question - it probably won't apply cleanly to 8.2
sources.
cheers
andrew
Attachments:
like.patchtext/x-patch; name=like.patchDownload+491-526
Tom Lane wrote:
Andrew Dunstan <andrew@dunslane.net> writes:
We should only be able to get out of step from the "%_" case, I believe,
so we should only need to do the first-byte test in that case (which is
in a different code path from the normal "_" case. Does that seem right?At least put Assert(IsFirstByte()) in the main path.
I'm a bit suspicious of the separate-path business anyway. Will it do
the right thing with say "%%%_" ?
OK, Here is a patch that I am fairly confident does what's been
discussed, as summarised by Tom.
To answer Guillaume's question - it probably won't apply cleanly to 8.2
sources.
cheers
andrew
Attachments:
like.patchtext/x-patch; name=like.patchDownload+491-526
Andrew Dunstan <andrew@dunslane.net> writes:
OK, Here is a patch that I am fairly confident does what's been
discussed, as summarised by Tom.
! #define CHAREQ(p1, p2) (*p1 == *p2)
...
+ #define IsFirstByte(c) ((*c & 0xC0) != 0x80)
These macros are bugs waiting to happen. Please parenthesize the
arguments.
The header comment for like_match.c needs more love:
* This file is included by like.c *twice*, to provide an optimization
* for single-byte encodings.
I'm not sure I believe the new coding for %-matching at all, and I
certainly don't like the 100% lack of comments explaining why the
different cases are necessary and just how they differ. In particular,
once we've advanced more than one character, why does it still matter
what was immediately after the %?
There should somewhere be a block comment explaining all the reasoning
we've so painfully gone through about why the three cases (SB, MB, UTF8)
are needed and how they must differ.
regards, tom lane
Tom Lane wrote:
I'm not sure I believe the new coding for %-matching at all, and I
certainly don't like the 100% lack of comments explaining why the
different cases are necessary and just how they differ. In particular,
once we've advanced more than one character, why does it still matter
what was immediately after the %?
I don't understand the question. The % processing looks for a place that
matches what is immediately after the % and then tries to match the
remainder using a recursive call - so it never actually does matter. I
haven't actually changed the fundamental logic AFAIK, I have just
rearranged and optimised it some.
I admit that it takes some pondering to understand - I certainly intend
to adjust the comments once we are satisfied the code is right. It's
going to be next week now before I finish this up :-(
cheers
andrew
