On 24.06.2011 11:40, Heikki Linnakangas wrote:
On 21.06.2011 13:08, Alexander Korotkov wrote:
I believe it's due to relatively expensive penalty
method in that opclass.
Hmm, I wonder if it could be optimized. I did a quick test, creating a
gist_trgm_ops index on a list of English words from
/usr/share/dict/words. oprofile shows that with the patch, 60% of the
CPU time is spent in the makesign() function.
I couldn't resist looking into this, and came up with the attached
patch. I tested this with:
CREATE TABLE words (word text);
COPY words FROM '/usr/share/dict/words';
CREATE INDEX i_words ON words USING gist (word gist_trgm_ops);
And then ran "REINDEX INDEX i_words" a few times with and without the
patch. Without the patch, reindex takes about 4.7 seconds. With the
patch, 3.7 seconds. That's a worthwhile gain on its own, but becomes
even more important with Alexander's fast GiST build patch, which calls
the penalty function more.
I used the attached showsign-debug.patch to verify that the patched
makesign function produces the same results as the existing code. I
haven't tested the big-endian code, however.
--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com
diff --git a/contrib/pg_trgm/trgm_gist.c b/contrib/pg_trgm/trgm_gist.c
index b328a09..1f3d3e3 100644
--- a/contrib/pg_trgm/trgm_gist.c
+++ b/contrib/pg_trgm/trgm_gist.c
@@ -84,17 +84,88 @@ gtrgm_out(PG_FUNCTION_ARGS)
static void
makesign(BITVECP sign, TRGM *a)
{
- int4 k,
- len = ARRNELEM(a);
+ int4 len = ARRNELEM(a);
trgm *ptr = GETARR(a);
- int4 tmp = 0;
+ char *p;
+ char *endptr;
+ uint32 w1,
+ w2,
+ w3;
+ uint32 trg1,
+ trg2,
+ trg3,
+ trg4;
+ uint32 *p32;
MemSet((void *) sign, 0, sizeof(BITVEC));
SETBIT(sign, SIGLENBIT); /* set last unused bit */
- for (k = 0; k < len; k++)
+
+ if (len == 0)
+ return;
+
+ endptr = (char *) (ptr + len);
+ /*------------------------------------------------------------------------
+ * We have to extract each trigram into a uint32, and calculate the HASH.
+ * This would be a lot easier if each trigram was aligned at 4-byte
+ * boundary, but they're not. The simple way would be to copy each
+ * trigram byte-per-byte, but that is quite slow, and this function is a
+ * hotspot in penalty calculation.
+ *
+ * The first trigram in the array doesn't begin at a 4-byte boundary, the
+ * flags byte comes first, but the next one does. So we fetch the first
+ * trigram as a special case, and after that the following four trigrams
+ * fall onto 4-byte words like this:
+ *
+ * w1 w2 w3
+ * AAAB BBCC CDDD
+ *
+ * As long as there's at least four trigrams left to process, we fetch
+ * the next three words and extract the trigrams from them with bit
+ * operations.
+ *------------------------------------------------------------------------
+ */
+ p32 = (uint32 *) (((char *) ptr) - 1);
+
+ /* Fetch and extract the initial word */
+ w1 = *(p32++);
+#ifdef WORDS_BIGENDIAN
+ trg1 = w1 << 8;
+#else
+ trg1 = w1 >> 8;
+#endif
+ HASH(sign, trg1);
+
+ while((char *) p32 < endptr - 12)
{
- CPTRGM(((char *) &tmp), ptr + k);
- HASH(sign, tmp);
+ w1 = *(p32++);
+ w2 = *(p32++);
+ w3 = *(p32++);
+
+#ifdef WORDS_BIGENDIAN
+ trg1 = w1 & 0xFFFFFF00;
+ trg2 = (w1 << 24) | ((w2 & 0xFFFF0000) >> 8);
+ trg3 = ((w2 & 0x0000FFFF) << 16) | ((w3 & 0xFF000000) >> 16);
+ trg4 = w3 << 8;
+#else
+ trg1 = w1 & 0x00FFFFFF;
+ trg2 = (w1 >> 24) | ((w2 & 0x0000FFFF) << 8);
+ trg3 = ((w2 & 0xFFFF0000) >> 16) | ((w3 & 0x000000FF) << 16);
+ trg4 = w3 >> 8;
+#endif
+
+ HASH(sign, trg1);
+ HASH(sign, trg2);
+ HASH(sign, trg3);
+ HASH(sign, trg4);
+ }
+
+ /* Handle remaining 1-3 trigrams the slow way */
+ p = (char *) p32;
+ while (p < endptr)
+ {
+ CPTRGM(((char *) &trg1), p);
+ HASH(sign, trg1);
+ p += 3;
}
}
diff --git a/contrib/pg_trgm/trgm_gist.c b/contrib/pg_trgm/trgm_gist.c
index b328a09..b5be800 100644
--- a/contrib/pg_trgm/trgm_gist.c
+++ b/contrib/pg_trgm/trgm_gist.c
@@ -44,6 +44,9 @@ Datum gtrgm_penalty(PG_FUNCTION_ARGS);
PG_FUNCTION_INFO_V1(gtrgm_picksplit);
Datum gtrgm_picksplit(PG_FUNCTION_ARGS);
+PG_FUNCTION_INFO_V1(gtrgm_showsign);
+Datum gtrgm_showsign(PG_FUNCTION_ARGS);
+
#define GETENTRY(vec,pos) ((TRGM *) DatumGetPointer((vec)->vector[(pos)].key))
/* Number of one-bits in an unsigned byte */
@@ -98,6 +101,32 @@ makesign(BITVECP sign, TRGM *a)
}
}
+static char *
+printsign(BITVECP sign)
+{
+ static char c[200];
+ char *p = c;
+ int i;
+ for(i=0; i < SIGLEN;i++)
+ {
+ p += snprintf(p, 3, "%02x", (unsigned int) (((unsigned char *) sign)[i]));
+ }
+ return c;
+}
+
+Datum
+gtrgm_showsign(PG_FUNCTION_ARGS)
+{
+ text *in = PG_GETARG_TEXT_P(0);
+ BITVEC sign;
+ TRGM *trg;
+
+ trg = generate_trgm(VARDATA(in), VARSIZE(in) - VARHDRSZ);
+ makesign(sign, trg);
+
+ PG_RETURN_TEXT_P(cstring_to_text(printsign(sign)));
+}
+
Datum
gtrgm_compress(PG_FUNCTION_ARGS)
{
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
