Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1lhPPL-0000ag-58 for pgsql-hackers@arkaria.postgresql.org; Fri, 14 May 2021 04:26:39 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.92) (envelope-from ) id 1lhPPJ-0006nz-Or for pgsql-hackers@arkaria.postgresql.org; Fri, 14 May 2021 04:26:37 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1lhPPJ-0006nr-8C for pgsql-hackers@lists.postgresql.org; Fri, 14 May 2021 04:26:37 +0000 Received: from sss.pgh.pa.us ([66.207.139.130]) by makus.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1lhPPG-0007Dx-9b for pgsql-hackers@lists.postgresql.org; Fri, 14 May 2021 04:26:36 +0000 Received: from sss1.sss.pgh.pa.us (localhost [127.0.0.1]) by sss.pgh.pa.us (8.15.2/8.15.2) with ESMTP id 14E4QNmE1850357; Fri, 14 May 2021 00:26:23 -0400 From: Tom Lane To: Julien Rouhaud cc: Stephen Frost , Bruce Momjian , Christoph Berg , Pavel Stehule , Kyotaro Horiguchi , Magnus Hagander , Fujii Masao , Michael Paquier , Andres Freund , Alvaro Herrera , Peter Eisentraut , PostgreSQL Hackers Subject: Re: compute_query_id and pg_stat_statements In-reply-to: <1579535.1620930549@sss.pgh.pa.us> References: <20210513005236.aj7n6b76yjsxythc@nol> <20210513011325.GA11075@momjian.us> <20210513015700.fp33q5rfvwl2ahfx@nol> <20210513030652.GB11075@momjian.us> <20210513031613.j47baglf6xl3mgbs@nol> <20210513033332.GF11075@momjian.us> <20210513040342.fouh7ryglrfgxglu@nol> <20210513144143.GG11075@momjian.us> <20210513175947.GP11075@momjian.us> <20210513180706.GG20766@tamriel.snowman.net> <1579535.1620930549@sss.pgh.pa.us> Comments: In-reply-to Tom Lane message dated "Thu, 13 May 2021 14:29:09 -0400" MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----- =_aaaaaaaaaa0" Content-ID: <1850352.1620966375.0@sss.pgh.pa.us> Date: Fri, 14 May 2021 00:26:23 -0400 Message-ID: <1850356.1620966383@sss.pgh.pa.us> List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk ------- =_aaaaaaaaaa0 Content-Type: text/plain; charset="us-ascii" Content-ID: <1850352.1620966375.1@sss.pgh.pa.us> I wrote: > Maybe we should revert this thing pending somebody doing the work to > make a version of queryid labeling that actually is negligibly cheap. > It certainly seems like that could be done; one more traversal of the > parse tree can't be that expensive in itself. I suspect that the > performance problem is with the particular hashing mechanism that > was used, which looks mighty ad-hoc anyway. To put a little bit of meat on that idea, I experimented with jacking up the "jumble" calculation and driving some other implementations underneath. I thought that Julien's "worst case" scenario was pretty far from worst case, since it involved a join which a lot of simple queries don't. I tested this scenario instead: $ cat naive.sql SELECT * FROM pg_class c ORDER BY oid DESC LIMIT 1; $ pgbench -n -f naive.sql -T 60 postgres which is still complicated enough that there's work for the query fingerprinter to do, but not so much for planning and execution. I confirm that on HEAD, there's a noticeable TPS penalty from turning on compute_query_id: about 3.2% on my machine. The first patch attached replaces the "jumble" calculation with two CRC32s (two so that we still get 64 bits out at the end). I see 2.7% penalty with this version. Now, I'm using an Intel machine with #define USE_SSE42_CRC32C_WITH_RUNTIME_CHECK 1 so on machines without any hardware CRC support, this'd likely be a loss. But it still proves the point that the existing implementation is just not very speedy. I then tried a really dumb xor'ing implementation, and that gives me a slowdown of 2.2%. This could undoubtedly be improved on further, say by unrolling the loop or processing multiple bytes at once. One problem with it is that I suspect it will tend to concentrate the entropy into the third/fourth and seventh/eighth bytes of the accumulator, since so many of the fields being jumbled are 4-byte or 8-byte fields with most of the entropy in their low-order bits. Probably that could be improved with a bit more thought -- say, an extra bump of the nextbyte pointer after each field. Anyway, I think that what we have here is quite an inferior implementation, and we can do better with some more thought. regards, tom lane ------- =_aaaaaaaaaa0 Content-Type: text/x-diff; name="query-id-with-crc.patch"; charset="us-ascii" Content-ID: <1850352.1620966375.2@sss.pgh.pa.us> Content-Description: query-id-with-crc.patch Content-Transfer-Encoding: quoted-printable diff --git a/src/backend/utils/misc/queryjumble.c b/src/backend/utils/misc= /queryjumble.c index f004a9ce8c..74ed555ed7 100644 --- a/src/backend/utils/misc/queryjumble.c +++ b/src/backend/utils/misc/queryjumble.c @@ -41,7 +41,7 @@ = static uint64 compute_utility_query_id(const char *str, int query_locatio= n, int query_len); static void AppendJumble(JumbleState *jstate, - const unsigned char *item, Size size); + const void *item, Size size); static void JumbleQueryInternal(JumbleState *jstate, Query *query); static void JumbleRangeTable(JumbleState *jstate, List *rtable); static void JumbleRowMarks(JumbleState *jstate, List *rowMarks); @@ -106,9 +106,11 @@ JumbleQuery(Query *query, const char *querytext) { jstate =3D (JumbleState *) palloc(sizeof(JumbleState)); = - /* Set up workspace for query jumbling */ - jstate->jumble =3D (unsigned char *) palloc(JUMBLE_SIZE); - jstate->jumble_len =3D 0; + /* Initialize CRCs for query jumbling */ + INIT_CRC32C(jstate->crc0); + INIT_CRC32C(jstate->crc1); + jstate->whichcrc =3D 0; + /* Initialize state for tracking where constants are */ jstate->clocations_buf_size =3D 32; jstate->clocations =3D (LocationLen *) palloc(jstate->clocations_buf_size * sizeof(LocationLen)); @@ -117,9 +119,11 @@ JumbleQuery(Query *query, const char *querytext) = /* Compute query ID and mark the Query node with it */ JumbleQueryInternal(jstate, query); - query->queryId =3D DatumGetUInt64(hash_any_extended(jstate->jumble, - jstate->jumble_len, - 0)); + + FIN_CRC32C(jstate->crc0); + FIN_CRC32C(jstate->crc1); + query->queryId =3D (((uint64) jstate->crc0) << 32) | + ((uint64) jstate->crc1); = /* * If we are unlucky enough to get a hash of zero, use 1 instead, to @@ -165,36 +169,18 @@ compute_utility_query_id(const char *query_text, int= query_location, int query_l * the current jumble. */ static void -AppendJumble(JumbleState *jstate, const unsigned char *item, Size size) +AppendJumble(JumbleState *jstate, const void *item, Size size) { - unsigned char *jumble =3D jstate->jumble; - Size jumble_len =3D jstate->jumble_len; - - /* - * Whenever the jumble buffer is full, we hash the current contents and - * reset the buffer to contain just that hash value, thus relying on the - * hash to summarize everything so far. - */ - while (size > 0) + if (jstate->whichcrc) { - Size part_size; - - if (jumble_len >=3D JUMBLE_SIZE) - { - uint64 start_hash; - - start_hash =3D DatumGetUInt64(hash_any_extended(jumble, - JUMBLE_SIZE, 0)); - memcpy(jumble, &start_hash, sizeof(start_hash)); - jumble_len =3D sizeof(start_hash); - } - part_size =3D Min(size, JUMBLE_SIZE - jumble_len); - memcpy(jumble + jumble_len, item, part_size); - jumble_len +=3D part_size; - item +=3D part_size; - size -=3D part_size; + COMP_CRC32C(jstate->crc1, item, size); + jstate->whichcrc =3D 0; + } + else + { + COMP_CRC32C(jstate->crc0, item, size); + jstate->whichcrc =3D 1; } - jstate->jumble_len =3D jumble_len; } = /* @@ -202,9 +188,9 @@ AppendJumble(JumbleState *jstate, const unsigned char = *item, Size size) * of individual local variable elements. */ #define APP_JUMB(item) \ - AppendJumble(jstate, (const unsigned char *) &(item), sizeof(item)) + AppendJumble(jstate, (const void *) &(item), sizeof(item)) #define APP_JUMB_STRING(str) \ - AppendJumble(jstate, (const unsigned char *) (str), strlen(str) + 1) + AppendJumble(jstate, (const void *) (str), strlen(str) + 1) = /* * JumbleQueryInternal: Selectively serialize the query tree, appending diff --git a/src/include/utils/queryjumble.h b/src/include/utils/queryjumb= le.h index 83ba7339fa..3a09c555fa 100644 --- a/src/include/utils/queryjumble.h +++ b/src/include/utils/queryjumble.h @@ -15,8 +15,7 @@ #define QUERYJUBLE_H = #include "nodes/parsenodes.h" - -#define JUMBLE_SIZE 1024 /* query serialization buffer size */ +#include "port/pg_crc32c.h" = /* * Struct for tracking locations/lengths of constants during normalizatio= n @@ -33,11 +32,13 @@ typedef struct LocationLen */ typedef struct JumbleState { - /* Jumble of current query tree */ - unsigned char *jumble; - - /* Number of bytes used in jumble[] */ - Size jumble_len; + /* + * Since we'd like a 64-bit-wide query ID, but we're using 32-bit CRC + * technology, we combine two 32-bit CRCs. + */ + pg_crc32c crc0; /* some fields go into here ... */ + pg_crc32c crc1; /* ... and others into here */ + int whichcrc; /* 0 or 1, says which CRC accum to use next */ = /* Array of locations of constants that should be removed */ LocationLen *clocations; ------- =_aaaaaaaaaa0 Content-Type: text/x-diff; name="query-id-with-xor.patch"; charset="us-ascii" Content-ID: <1850352.1620966375.3@sss.pgh.pa.us> Content-Description: query-id-with-xor.patch Content-Transfer-Encoding: quoted-printable diff --git a/src/backend/utils/misc/queryjumble.c b/src/backend/utils/misc= /queryjumble.c index f004a9ce8c..225940d40c 100644 --- a/src/backend/utils/misc/queryjumble.c +++ b/src/backend/utils/misc/queryjumble.c @@ -106,9 +106,10 @@ JumbleQuery(Query *query, const char *querytext) { jstate =3D (JumbleState *) palloc(sizeof(JumbleState)); = - /* Set up workspace for query jumbling */ - jstate->jumble =3D (unsigned char *) palloc(JUMBLE_SIZE); - jstate->jumble_len =3D 0; + /* Initialize state for query jumbling */ + jstate->j.id =3D 0; + jstate->nextbyte =3D 0; + /* Initialize state for tracking where constants are */ jstate->clocations_buf_size =3D 32; jstate->clocations =3D (LocationLen *) palloc(jstate->clocations_buf_size * sizeof(LocationLen)); @@ -117,9 +118,7 @@ JumbleQuery(Query *query, const char *querytext) = /* Compute query ID and mark the Query node with it */ JumbleQueryInternal(jstate, query); - query->queryId =3D DatumGetUInt64(hash_any_extended(jstate->jumble, - jstate->jumble_len, - 0)); + query->queryId =3D jstate->j.id; = /* * If we are unlucky enough to get a hash of zero, use 1 instead, to @@ -167,34 +166,17 @@ compute_utility_query_id(const char *query_text, int= query_location, int query_l static void AppendJumble(JumbleState *jstate, const unsigned char *item, Size size) { - unsigned char *jumble =3D jstate->jumble; - Size jumble_len =3D jstate->jumble_len; + int nextbyte =3D jstate->nextbyte; = - /* - * Whenever the jumble buffer is full, we hash the current contents and - * reset the buffer to contain just that hash value, thus relying on the - * hash to summarize everything so far. - */ while (size > 0) { - Size part_size; - - if (jumble_len >=3D JUMBLE_SIZE) - { - uint64 start_hash; - - start_hash =3D DatumGetUInt64(hash_any_extended(jumble, - JUMBLE_SIZE, 0)); - memcpy(jumble, &start_hash, sizeof(start_hash)); - jumble_len =3D sizeof(start_hash); - } - part_size =3D Min(size, JUMBLE_SIZE - jumble_len); - memcpy(jumble + jumble_len, item, part_size); - jumble_len +=3D part_size; - item +=3D part_size; - size -=3D part_size; + jstate->j.bytes[nextbyte] ^=3D *item++; + nextbyte++; + if (nextbyte >=3D sizeof(uint64)) + nextbyte =3D 0; + size--; } - jstate->jumble_len =3D jumble_len; + jstate->nextbyte =3D nextbyte; } = /* diff --git a/src/include/utils/queryjumble.h b/src/include/utils/queryjumb= le.h index 83ba7339fa..d01712af4d 100644 --- a/src/include/utils/queryjumble.h +++ b/src/include/utils/queryjumble.h @@ -16,8 +16,6 @@ = #include "nodes/parsenodes.h" = -#define JUMBLE_SIZE 1024 /* query serialization buffer size */ - /* * Struct for tracking locations/lengths of constants during normalizatio= n */ @@ -33,11 +31,13 @@ typedef struct LocationLen */ typedef struct JumbleState { - /* Jumble of current query tree */ - unsigned char *jumble; - - /* Number of bytes used in jumble[] */ - Size jumble_len; + /* Working state for accumulating a 64-bit query ID */ + union + { + unsigned char bytes[sizeof(uint64)]; + uint64 id; + } j; + int nextbyte; /* index of next byte to update in j.bytes[] */ = /* Array of locations of constants that should be removed */ LocationLen *clocations; ------- =_aaaaaaaaaa0--