Thread

Commits

Fix query jumbling to account for NULL nodes
- f31aad9b07b7 18.0 landed
RE: Query ID Calculation Fix for DISTINCT / ORDER BY and LIMIT / OFFSET

Ivan Bykov <i.bykov@modernsys.ru> — 2025-03-06T14:39:48Z
Here is bug description from
https://www.postgresql.org/message-id/flat/ca447b72d15745b9a877fad7e258407a%40localhost.localdomain

Problem
=======
In some cases, we could have same IDs for not identical query trees.
For two structurally similar query subnodes, we may have query
trees that look like this:
----
QueryA->subNodeOne = Value X;
QueryA->subNodeTwo = NULL;
QueryB->subNodeOne = NULL;
QueryB->subNodeTwo = Value X;
----
When the query jumble walker calculates the query ID, it traverses the
Query members from top to bottom and generates the same IDs for these
two queries because it does not change the hash value when visiting
an empty node (= NULL).
Here is an example (the collection of jstate->jumble is omitted):
----
/* QueryA_ID = AAAA */
QueryA->subNodeOne = &(Value X);
/* QueryA_ID = hash_any_extended(&(Value X), sizeof(Value X), QueryA_ID) = BBBB */
QueryA->subNodeTwo = NULL;
/* QueryA_ID = BBBB; */
/* QueryB_ID = AAAA */
QueryB->subNodeOne = NULL;
/* QueryB_ID = AAAA; */
QueryB->subNodeTwo = &(Value X);
/* QueryB_ID = hash_any_extended(&(Value X), sizeof(Value X), QueryB_ID) = BBBB */
----
There are two pairs of subnodes that can trigger this error:
- distinctClause and sortClause (both contain a list of SortGroupClauses);
- limitOffset and limitCount (both contain an int8 expression).
Here is an example of such errors (all queries run on REL_17_0):
----
SET compute_query_id = on;
/* DISTINCT / ORDER BY *************************************/
EXPLAIN (VERBOSE) SELECT DISTINCT "oid" FROM pg_class;
/* Query Identifier: 751948508603549510 */
EXPLAIN (VERBOSE) SELECT "oid" FROM pg_class ORDER BY "oid";
/* Query Identifier: 751948508603549510 */
/* LIMIT / OFFSET ******************************************/
EXPLAIN (VERBOSE) SELECT "oid" FROM pg_class LIMIT 1;
/* Query Identifier: 5185884322440896420 */
EXPLAIN (VERBOSE) SELECT "oid" FROM pg_class OFFSET 1;
/* Query Identifier: 5185884322440896420 */
----
Solution One
============
The simplest way to fix the problem is to place the scalar field used in
the query ID calculation between similar subnodes. A patch for this
solution is attached below (0001-Query-ID-Calculation-Fix-Variant-A.patch).
Here is an example:
----
/* QueryA_ID = AAAA */
QueryA->subNodeOne = &(Value X);
/* QueryA_ID = hash_any_extended(&(Value X), sizeof(Value X), QueryA_ID) = BBBB */
QueryA->scalar = Value Y;
/* QueryA_ID = hash_any_extended(&(Value Y), sizeof(Value Y), QueryA_ID) = CCCC */
QueryA->subNodeTwo = NULL;
/* QueryA_ID = CCCC; */
/* QueryB_ID = AAAA */
QueryB->subNodeOne = NULL;
/* QueryB_ID = AAAA; */
QueryB->scalar = Value Y;
/* QueryB_ID = hash_any_extended(&(Value Y), sizeof(Value Y), QueryB_ID) = DDDD */
QueryB->subNodeOne = &(Value X);
/* QueryB_ID = hash_any_extended(&(Value X), sizeof(Value X), QueryB_ID) = EEEE */
----
Solution Two
============
Alternatively, we can change the hash sum when we encounter an empty node.
This approach may impact performance but will protect us from such errors
in the future. A patch for this solution is attached below
(0001-Query-ID-Calculation-Fix-Variant-B.patch).
Here is an example:
----
/* QueryA_ID = AAAA */
QueryA->subNodeOne = &(Value X);
/* QueryA_ID = hash_any_extended(&(Value Y), sizeof(Value Y), QueryA_ID) = BBBB */
QueryA->subNodeTwo = NULL;
/* QueryA_ID = hash_any_extended(&('\0'), sizeof(char), QueryA_ID) = CCCC */
/* QueryB_ID = AAAA */
QueryB->subNodeOne = NULL;
/* QueryB_ID = hash_any_extended(&('\0'), sizeof(char), QueryB_ID) = DDDD */
QueryB->subNodeOne = &(Value X);
/* QueryB_ID = hash_any_extended(&(Value X), sizeof(Value X), QueryB_ID) = EEEE */
----


From: Быков Иван Александрович
Sent: Thursday, March 6, 2025 7:32 PM
To: 'pgsql-hackers@postgresql.org' <pgsql-hackers@postgresql.org>
Subject: RE: Query ID Calculation Fix for DISTINCT / ORDER BY and LIMIT / OFFSET

Hello!
Last time, I forgot to attach the patches.
The problem still persists in the 17.3 release.
Solution One
============
The simplest way to fix the problem is to place the scalar field used in the query ID calculation
between similar subnodes.
A patch for this solution is attached below (0001-Query-ID-Calculation-Fix-Variant-A.patch).
Solution Two
============
Alternatively, we can change the hash sum when we encounter an empty node.
This approach may impact performance but will protect us from such errors in the future.
A patch for this solution is attached below (0001-Query-ID-Calculation-Fix-Variant-B.patch).

======
SELECT version();
                                             version
-------------------------------------------------------------------------------------------------
PostgreSQL 17.3 on x86_64-pc-linux-gnu, compiled by gcc (Debian 12.2.0-14) 12.2.0, 64-bit

SET compute_query_id = on;

/* LIMIT / OFFSET */
EXPLAIN (VERBOSE) SELECT "oid" FROM pg_class LIMIT 1;

                                 QUERY PLAN
----------------------------------------------------------------------------
Limit  (cost=0.00..0.04 rows=1 width=4)
   Output: oid
   ->  Seq Scan on pg_catalog.pg_class  (cost=0.00..18.15 rows=415 width=4)
         Output: oid
Query Identifier: 5185884322440896420

EXPLAIN (VERBOSE) SELECT "oid" FROM pg_class OFFSET 1;
                                 QUERY PLAN
----------------------------------------------------------------------------
Limit  (cost=0.04..18.15 rows=414 width=4)
   Output: oid
   ->  Seq Scan on pg_catalog.pg_class  (cost=0.00..18.15 rows=415 width=4)
         Output: oid
Query Identifier: 5185884322440896420

/* DISTINCT / ORDER BY */
EXPLAIN (VERBOSE) SELECT DISTINCT "oid" FROM pg_class;

                                                 QUERY PLAN
------------------------------------------------------------------------------------------------------------
Unique  (cost=0.27..23.54 rows=415 width=4)
   Output: oid
   ->  Index Only Scan using pg_class_oid_index on pg_catalog.pg_class  (cost=0.27..22.50 rows=415 width=4)
         Output: oid
Query Identifier: 751948508603549510

EXPLAIN (VERBOSE) SELECT "oid" FROM pg_class ORDER BY "oid";

                                              QUERY PLAN
------------------------------------------------------------------------------------------------------
Index Only Scan using pg_class_oid_index on pg_catalog.pg_class  (cost=0.27..22.50 rows=415 width=4)
   Output: oid
Query Identifier: 751948508603549510
RE: Query ID Calculation Fix for DISTINCT / ORDER BY and LIMIT / OFFSET

Ivan Bykov <i.bykov@modernsys.ru> — 2025-03-06T14:51:23Z
```
Here is
0001-Query-ID-Calculation-Fix-Variant-A.patch
and
0001-Query-ID-Calculation-Fix-Variant-B.patch
```