Kernel Technology Revealed: Query Tree Node Reentrant Read Technology

The Query tree is a very important data structure in PostgreSQL. One of its characteristics is that it can be serialized/deserialized. A very important application of this feature is the Rule System. For example, Views are built on top of the rule system.

When we define a view:

CREATE VIEW v_test AS SELECT * FROM test WHERE grade = 9;

Essentially, it serializes the Query tree of the statement after AS and stores it in the system:

SELECT ev_action FROM pg_rewrite WHERE ev_class = (SELECT oid FROM pg_class WHERE relname='v_test');

ev_action
--------------------------------------------------------------------------------------------------------------------------------
 ({QUERY :commandType 1 :querySource 0 :canSetTag true :utilityStmt <> :resultRelation 0 ...})

Through this serialized Query tree, we can know the type of this Query (commandType), target table, target columns, and other detailed information needed for the query. After deserialization, it can be restored to a complete Query tree, which can then be directly planned, generating an execution plan, and then executed. In fact, when we query the view definition, we also find that the definition in the system is significantly different from our original definition:

 SELECT definition FROM pg_views WHERE viewname='v_test';
       definition
---------------------------
 SELECT test.empno,      +
    test.grade,          +
    test.depno,          +
    test.name,           +
    test.sal             +
   FROM test             +
  WHERE (test.grade = 9);
(1 row)

This is because the definition in the system is actually based on the serialized Query tree (as above), obtained through deserialization and then recompilation, not the original definition statement.

It should be said that PostgreSQL's mechanism is very well designed. However, there are still some deficiencies in the actual code implementation. The most fatal flaw is that if for some reason (such as bug fixes) the structural definition of the Query tree changes (for example, adding a node), then system upgrade becomes a very troublesome matter. You will have to reinitialize the entire database cluster! If you just upgrade the program, it will lead to very serious problems, and may even cause the system to be unable to connect!

Let's look at how the definition in pg_views comes about. This definition is actually obtained through the _readQuery method provided in backend/nodes/readfuncs.c, and then transformed. This _readQuery is actually the process of deserializing the Query tree.

static Query *
_readQuery(void)
{
  READ_LOCALS(Query);
  READ_ENUM_FIELD(commandType, CmdType);
  READ_ENUM_FIELD(querySource, QuerySource);
  local_node->queryId = UINT64CONST(0);  /* not saved in output format */
  READ_BOOL_FIELD(canSetTag);
  ...
    READ_DONE();
}

These READ_XXX methods continuously advance the pointer of the string (serialized Query tree) until the end, thereby reconstructing a Query tree. Therefore, if the definition of the Query tree changes, such as adding a node, and these existing Query trees in the system do not have information about the new node, and the pointer of the READ_XXX method keeps advancing, it will eventually lead to a null pointer error, causing system crash.

To address this issue, we developed Query tree node reentrant read technology in the Halo product. Simply put, the pointer of the READ_XXX method will readjust its position as needed, thus avoiding null pointer errors. One of the key technical implementations is token reentrant read, with partial code as follows:

/* reenterable pg_strtok */
const char *
pg_strtok_reentrant(char token_name, int length)
{
    ...
  /* Reenterable token read support */
  token_len = strlen(token_name) + 1;
  token1 = malloc(sizeof(char) * (token_len + 1));
  token1[0] = ':';
  token1[1] = '\0';
  strcat(token1, token_name);
  token1[token_len] = '\0';
  token2 = malloc(sizeof(char) * (token_len + 1));
  token2[0] = '\0';
  strncpy(token2, ret_str, token_len);
  token2[token_len] = '\0';
  if (strcasecmp(token1, token2) != 0)
  {
    *length = -1;
    pg_strtok_ptr = prev_strtok_ptr;
    free(token1);
    free(token2);
    return ret_str;
  }
    ...
}

By comparing whether the read token and the passed token are equal, if they are not equal, the working pointer will fall back to the position before working, thus achieving reentrant read.