[Design] Accelerate json function with simdjson

[wanweiqiangintel]

JSON introduction

JSON (JavaScript Object Notation) is a lightweight data-interchange format. It is easy for humans to read and write. It is easy for machines to parse and generate. It is based on a subset of the JavaScript Programming Language Standard ECMA-262 3rd Edition - December 1999. JSON is a text format that is completely language independent but uses conventions that are familiar to programmers of the C-family of languages, including C, C++, C#, Java, JavaScript, Perl, Python, and many others. These properties make JSON an ideal data-interchange language.
JSON is built on two structures:

• A collection of name/value pairs. In various languages, this is realized as an object, record, struct, dictionary, hash table, keyed list, or associative array.
• An ordered list of values. In most languages, this is realized as an array, vector, list, or sequence.

JSON example:
'{"name":"John", "age":30, "books":[“A”,”B”,”C”]}'

---

JSON function in Velox

In the current Velox, 7 json related functions are supported as below. Functions 1~ 5 are implemented as simple functions. Functions 6~ 7 are implemented as vector functions. The input and output of those functions have been aligned with Presto json. But the behavior has some differences compared with Presto, details will be discussed in later chapters.

	Scalar Functions	function	Input	Output
1	is_json_scalar	IsJsonScalarFunction	json	boolean
2	json_array_contains	JsonArrayContainsFunction	json, value	boolean
3	json_array_length	JsonArrayLengthFunction	json	int64
4	json_extract_scalar	JsonExtractScalarFunction	json, json_path	varchar
5	json_size	JsonSizeFunction	json, json_path	int64
6	json_format	JsonFormatFunction	json	varchar
7	json_parse	JsonParseFunction	varchar	json

---

Simdjson introduction:

The simdjson library uses commonly available SIMD instructions and microparallel algorithms to parse JSON 4x faster than RapidJSON and 25x faster than JSON for Modern C++.

• Fast: Over 4x faster than commonly used production-grade JSON parsers.
• Record Breaking Features: Minify JSON at 6 GB/s, validate UTF-8 at 13 GB/s, NDJSON at 3.5 GB/s.
• Easy: First-class, easy to use and carefully documented APIs.
• Strict: Full JSON and UTF-8 validation, lossless parsing. Performance with no compromises.
• Automatic: Selects a CPU-tailored parser at runtime. No configuration needed.
• Reliable: From memory allocation to error handling, simdjson's design avoids surprises.
• Peer Reviewed: Our research appears in venues like VLDB Journal, Software: Practice and Experience.

---

Json function with simdjson in Velox

There are 7 JSON functions implemented with simdjson in Velox. The function json_extract is a new function that is very important in Presto. The input and output of the 7 functions have been aligned with Presto. While the output is json type, we use varchar to replace it temporarily because the built-in json type doesn’t support StringWriter method.

	Scalar Functions	function	Input	Output
1	is_json_scalar	SIMDIsJsonScalarFunction	json	boolean
2	json_array_contains	SIMDJsonArrayContainsFunction	json, value	boolean
3	json_array_length	SIMDJsonArrayLengthFunction	json	int64
4	json_extract_scalar	SIMDJsonExtractScalarFunction	json, json_path	varchar
5	json_parse	SIMDJsonParseFunction	varchar	json
6	json_size	SIMDJsonSizeFunction	json, json_path	int64
7	json_extract	SIMDJsonExtractFunction	json, json_path	json

---

Implementation Details

There are two methods of parsing json data in simdjson:

simdjson::dom::parser Parser;
simdjson::dom::element ele = Parser.parse(padded_json);

simdjson::ondemand::parser ondemandParser;
simdjson::ondemand::document doc = ondemandParser.iterate(padded_json);

The simdjson community refers to "On Demand" as a front-end component since it is an interface between the low-level parsing functions and the user. It hides much of the complexity of parsing JSON documents. "On Demand" parse the document and find all the structural indexes(i.e. stage 1), without including building json type. If we need to find different values in the json object many times, using the dom parse method is better.
According to the interface of simdjson, we create a struct ParserContext.

struct ParserContext {  
 public:   
  explicit ParserContext() noexcept;   
  explicit ParserContext(const char* data, size_t length) noexcept;   
  void parseElement();   
  void parseDocument();   
  simdjson::dom::element jsonEle;   
  simdjson::ondemand::document jsonDoc;   
 private:   
  simdjson::padded_string padded_json;   
  simdjson::dom::parser domParser;   
  simdjson::ondemand::parser ondemandParser;   
}; 

The interface of those functions are in the file SIMDJsonFunctions.h.

1. SIMDIsJsonScalarFunction:
   is_json_scalar(json) → boolean (Presto link)
   SELECT is_json_scalar('1'); -- true
   SELECT is_json_scalar('[1, 2, 3]'); -- false
   json element value includes 6 different types, array/object/number/string/boolean/null. If the input json type belongs to one of the 4 types number/string/Boolean/null, the is_json_scalar(json) returns true, otherwise returns false.

2. SIMDJsonArrayContainsFunction
   json_array_contains(json, value) → boolean (Presto link)
   SELECT json_array_contains('[1, 2, 3]', 2); -- true
   Determine if a value exists in json (a string containing a JSON array). The type of a json value can be one of four types: bool/int/double/varchar.

3. SIMDJsonArrayLengthFunction
   json_array_length(json) → int64 (Presto link)
   SELECT json_array_length('[1, 2, 3]'); -- 3
   Returns the array length of json (a string containing a JSON array).

4. SIMDJsonExtractScalarFunction
   json_extract_scalar(json, json_path) → varchar (Presto link)
   Like json_extract(), but returns the result value as a string (as opposed to being encoded as JSON). The value referenced by json_path must be a scalar (boolean, number or string).

5. SIMDJsonParseFunction
   json_parse(string) → varchar (original version is json in velox) (Presto link)
   SELECT json_parse('[1, 2, 3]'); -- JSON '[1,2,3]'
   SELECT json_parse('"abc"'); -- JSON '"abc"'
   Returns the JSON value deserialized from the input JSON text. This is the inverse function to json_format(). Note: the original version of the return type is json. But the built-in json type doesn’t support the StringWriter method, we return varchar temporarily. Another method is adding the template specialization struct resolver<CustomType<JSON>>

6. SIMDJsonExtractFunction
   json_extract(json, json_path) → varchar (original version is json in velox) (Presto link)

7. SIMDJsonSizeFunction
   json_size(json, json_path) → int64
   Like json_extract(), but returns the size of the value. For objects or arrays, the size is the number of members, and the size of a scalar value is zero:
   SELECT json_size('{"x": {"a": 1, "b": 2}}', '$.x'); -- 2
   SELECT json_size('{"x": [1, 2, 3]}', '$.x'); -- 3
   SELECT json_size('{"x": {"a": 1, "b": 2}}', '$.x.a'); -- 0

---

Benchmark

We have added two benchmarks about json_extract and json_parse to compare the performance between simdjson and folly implement.

The benchmark implementations are in JsonExprBenchmark.cpp(expression mode) and JsonFunctionBenchmark.cpp(function mode).
The performance result is as below:

json_extract performance(expression mode):

json_extract performance(function mode):

json_parse performance(expression smode):

---

Detect

We have added a parameter in the function registerJsonFunctions(bool useSimd), users can assign useSimd=1 to enable simdjson function.

Semantic differences

• In the overflow test of json_extract_scalar: TEST_F(JsonExtractScalarTest, overflow).
  jsonExtractScalar(R"(184467440737095516151844674407370955161518446744073709551615)","$")

  The JsonExtractScalarFunction return std::nullopt,
  SIMDJsonExtractScalarFunction return 184467440737095516151844674407370955161518446744073709551615,
  Presto return 184467440737095516151844674407370955161518446744073709551615.

• In the wildcard test of json_extract_scalar: TEST_F(JsonExtractScalarTest, wildcardSelect)
  jsonExtractScalar(R"({"tags":{"a":["b"],"c":["d"]}})", "$.tags.c[*]")

  The JsonExtractScalarFunction return d
  SIMDJsonExtractScalarFunction return std::null,
  The Presto return std::null.

• In the jsonParse test: TEST_F(JsonFunctionsTest, jsonParse).
  jsonParse(R"([1, 2, 3])")
  The JsonParseFunction return [1, 2, 3]
  SIMDJsonExtractScalarFunction return [1,2,3]
  The Presto return [1,2,3].

[mbasmanova]

CC: @Yuhta @laithsakka

[Yuhta]

I am wondering if we should have DOM element as the actual underlying value for JSON type in this case. Looks like we could lose a lot performance if we have to convert the DOM element back to string when there is a chain of these functions.

@wanweiqiangintel How fast is simdjson on parsing the string into DOM? Do you have some profiling on this and compare it to the actual Presto simdjson functions above? If it is a small fraction of the Presto function we can keep using string. Otherwise we may want to use a custom type with JSON.

[wanweiqiangintel]

For the unit test function EXPECT_EQ(jsonParse(R"([1, 2, 3])"), "[1,2,3]"); in SimdJsonFunctionsTest.cpp, ctx.parseElement() consumes about 10% time of the function jsonParse. There are two functions return the Json type: jsonExtract and jsonParse.

[Yuhta]

For functions that take JSON as parameter, we also need to parse the input, no?

[wanweiqiangintel]

Yes, the other 5 functions take JSON as parameter and we need to parse it. If we want to use DOM as input parameter, we should have the parsed DOM returned by other functions. According to the simdjson community, we should keep (1) the parser instance, (2) the input string and (3) the document instance alive throughout the parsing. I am wondering if we can meet these conditions between different UDF？

• TEST_F(SIMDJsonFunctionsTest, isJsonScalar) -> isJsonScalar(R"(1)"), true: ctx.parseDocument()/isJsonScalar = 10%
• TEST_F(SIMDJsonFunctionsTest, jsonArrayLength) -> jsonArrayLength(R"([1, 2, 3])"): ctx.parseDocument()/jsonArrayLength = 9%
• TEST_F(SIMDJsonFunctionsTest, jsonArrayContainsBool) -> jsonArrayContains(R"([1, 2, 3])", false): ctx.parseDocument()/jsonArrayContains = 8%
• TEST_F(SIMDJsonFunctionsTest, jsonSize) -> jsonSize(R"({"k1":{"k2": 999, "k3": [{"k4": [1, 2, 3]}]}})", "$.k1.k3[0].k4"): ctx.parseDocument()/jsonSize = 1%
• TEST_F(SIMDJsonExtractScalarTest, simple) -> jsonExtractScalar(R"(1)", "$") ctx.parseDocument()/jsonExtractScalar = 7%

[Yuhta]

The percentages look small enough and seems we don't need to keep the DOM between functions for now. If we have to keep it, we probably need to keep the parser in EvalCtx or ExecCtx and keep the string and DOM in the custom type instance data.

[wanweiqiangintel]

Yes, maybe we can keep the current code implementation for now. For the PR4053 , do you have any suggestions?

[mbasmanova]

But the function json_parse(string) → json and json_extract(json, json_path) → json can't be compiled and tested success because the built-in JSON type is Velox doesn’t support StringWriter method.

@wanweiqiangintel Would you clarify a bit what's not working?

[wanweiqiangintel]

If we define the SIMDJsonExtractFunction as:

struct SIMDJsonExtractFunction {
  VELOX_DEFINE_FUNCTION_TYPES(T);
  FOLLY_ALWAYS_INLINE bool call(
      out_type<Json>& result,
      const arg_type<Json>& json,
      const arg_type<Varchar>& jsonPath) {
...
}

and register json function as:

registerFunction<SIMDJsonExtractFunction, Json, Json, Varchar>({"json_extract"});

Then, compile will failure:

error: no matching function for call to 'facebook::velox::UDFOutputString::assign(facebook::velox::functions::SIMDJsonExtractFunction<facebook::velox::exec::VectorExec>::out_type<facebook::velox::CustomType<facebook::velox::JsonT> >&, std::__cxx11::basic_string<char>&)'
  187 |       UDFOutputString::assign(result, extractResult.value());
      |       ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

So we replace out_type<Json>& result with out_type<Varchar>& result and replace registerFunction<SIMDJsonExtractFunction, Json, Json, Varchar>({"json_extract"}); with registerFunction<SIMDJsonExtractFunction, Varchar, Json, Varchar>({"json_extract"});

[mbasmanova]

@wanweiqiangintel Thank you for clarifying. Would you create a separate GitHub issue for this? We should fix it. CC: @laithsakka

[wanweiqiangintel]

Thanks, issue has been created.

[mbasmanova]

@wanweiqiangintel Would it be possible to implement all JSON functions supported in Presto: https://prestodb.io/docs/current/functions/json.html ?

[wanweiqiangintel]

json_array_get(json_array, index) → json and json_format(json) → varchar can also be implemented with simdjson. Including the existing 7 functions, we can implement all JSON functions supported in Presto.

[mbasmanova]

Semantic differences

@wanweiqiangintel My reading of this section suggests that SIMD-based implementation is fully compatible with Presto, while current implementation is not. Is this the case? If so, let's clarify that SIMD-based implementation is fully compatible and file GitHub issues about current implementation not being compatible.

[Yuhta]

I vaguely remember the current one is used by XStream. We probably need XStream to take over the current implementation before fix them. cc: @kagamiori

[kagamiori]

@Yuhta The JsonExtractor class is used by XStream, but I don't think they're use other JSON functions right now. They're using their own JSON type (folly::dynamic) instead of Velox built-in JSON type.

[mbasmanova]

@wanweiqiangintel Would it be possible to add sections about benchmarking and testing. It would be nice to clarify how we are going to test the new implementation. Are we going to re-use existing tests and allow for running those twice: once using regular JSON functions and another time using SIMD-based functions? For benchmarks, it would be nice to explain which datasets we are planning to use and why these are representative.

[wanweiqiangintel]

Sure, benchmarking and testing are very important and we have added benchmarking about json_extract and json_parse in benchmarks/JsonExprBenchmark.cpp and benchmarks/JsonFunctionBenchmark.cpp in #4053. And testing is in tests/SimdJsonExtractScalarTest.cpp and tests/SimdJsonFunctionsTest.cpp. For benchmarks, I will refine them and explain the datasets. For unit tests, I will re-use existing tests while the semantic differences have been fixed.

[mbasmanova]

@wanweiqiangintel Overall, this design looks good to me. WRT the implementation, I suggest to first create a PR that adds simdjson dependency and implements one function using it. Then, submit more PRs adding more functions (1-2 functions per PR if possible).

[mbasmanova]

@wanweiqiangintel I'm also thinking that it would be good to have only one implementation in production code. I wonder if we could replace functions one by one and move existing implementations to the benchmark directory if it is needed for benchmarking.

[kagamiori]

FYI, in addition to the 7 functions listed above, there are also cast-to-JSON and cast-from-JSON functions in Velox. The implementation can be found in the JsonCastOperator class in JsonType.h/cpp.