You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@spark.apache.org by GitBox <gi...@apache.org> on 2021/11/18 02:27:42 UTC
[GitHub] [spark] c21 opened a new pull request #34640: [SPARK-31585][SQL] Introduce Z-order expression
c21 opened a new pull request #34640:
URL: https://github.com/apache/spark/pull/34640
<!--
Thanks for sending a pull request! Here are some tips for you:
1. If this is your first time, please read our contributor guidelines: https://spark.apache.org/contributing.html
2. Ensure you have added or run the appropriate tests for your PR: https://spark.apache.org/developer-tools.html
3. If the PR is unfinished, add '[WIP]' in your PR title, e.g., '[WIP][SPARK-XXXX] Your PR title ...'.
4. Be sure to keep the PR description updated to reflect all changes.
5. Please write your PR title to summarize what this PR proposes.
6. If possible, provide a concise example to reproduce the issue for a faster review.
7. If you want to add a new configuration, please read the guideline first for naming configurations in
'core/src/main/scala/org/apache/spark/internal/config/ConfigEntry.scala'.
8. If you want to add or modify an error type or message, please read the guideline first in
'core/src/main/resources/error/README.md'.
-->
### What changes were proposed in this pull request?
<!--
Please clarify what changes you are proposing. The purpose of this section is to outline the changes and how this PR fixes the issue.
If possible, please consider writing useful notes for better and faster reviews in your PR. See the examples below.
1. If you refactor some codes with changing classes, showing the class hierarchy will help reviewers.
2. If you fix some SQL features, you can provide some references of other DBMSes.
3. If there is design documentation, please add the link.
4. If there is a discussion in the mailing list, please add the link.
-->
This PR is to introduce a new expression in Spark - `ZOrder`. The motivation is Z-order enables to sort tuples in a way, to allow efficiently data skipping for columnar file format (Parquet and ORC).
For query with filter on combination of multiple columns, example:
```sql
SELECT *
FROM table
WHERE x = 0 OR y = 0
```
Parquet/ORC cannot skip file/row-groups efficiently when reading, even though the table is sorted (locally or globally) on any columns. However when table is Z-order sorted on multiple columns, Parquet/ORC can skip file/row-groups efficiently when reading. We should add the feature in Spark to allow OSS Spark users benefitted in running these queries.
With this PR, user can do Z-order sort when writing the table with followed syntax:
```sql
INSERT INTO t
SELECT ...
FROM ...
SORT BY ZORDER(x, y, ...)
```
or
```sql
INSERT INTO t
SELECT ...
FROM ...
ORDER BY ZORDER(x, y, ...)
```
Then when reading the table with filter on `x` and `y`, the performance can be improved by skipping more files and row-groups. More details below for micro benchmark.
This PR adds the support for Z-order on integer types (byte, short, int, and long). For other data types such as float and string will be added as followup. Code-gen support for expression will be also added later.
### Why are the changes needed?
<!--
Please clarify why the changes are needed. For instance,
1. If you propose a new API, clarify the use case for a new API.
2. If you fix a bug, you can clarify why it is a bug.
-->
To improve the query performance when filtering on multiple columns. Seeing 1x-6x run-time improvement in micro benchmark below.
```scala
override def runBenchmarkSuite(mainArgs: Array[String]): Unit = {
def prepareTable(dir: File, numRows: Int): Unit = {
import spark.implicits._
val df = spark.range(numRows).map(_ => (Random.nextLong, Random.nextLong))
.toDF("x", "y")
val zorderedDf = df.sort(Column(ZOrder(Seq($"x".expr, $"y".expr))))
saveAsTable(df, dir, "")
saveAsTable(zorderedDf, dir, "ZOrder")
}
def saveAsTable(df: DataFrame, dir: File, suffix: String): Unit = {
val blockSize = org.apache.parquet.hadoop.ParquetWriter.DEFAULT_PAGE_SIZE
val orcPath = dir.getCanonicalPath + "/orc" + suffix
val parquetPath = dir.getCanonicalPath + "/parquet" + suffix
df.write.mode("overwrite")
.option("orc.dictionary.key.threshold", 0.8)
.option("orc.compress.size", blockSize)
.option("orc.stripe.size", blockSize).orc(orcPath)
spark.read.orc(orcPath).createOrReplaceTempView("orcTable" + suffix)
df.write.mode("overwrite")
.option("parquet.block.size", blockSize).parquet(parquetPath)
spark.read.parquet(parquetPath).createOrReplaceTempView("parquetTable" + suffix)
}
def withTempTable(tableNames: String*)(f: => Unit): Unit = {
try f finally tableNames.foreach(spark.catalog.dropTempView)
}
runBenchmark(s"ZOrder") {
withTempPath { dir =>
withTempTable("orcTable", "parquetTable", "orcTableZOrder", "parquetTableZOrder") {
prepareTable(dir, 1024 * 1024 * 15)
val benchmark = new Benchmark("zorder", 1024 * 1024 * 15,
minNumIters = 5, output = output)
benchmark.addCase("Parquet no sort") { _ =>
spark.sql(s"SELECT * FROM parquetTable WHERE x = 0 OR y = 0").noop()
}
benchmark.addCase("Parquet z-order sort on (x, y)") { _ =>
spark.sql(s"SELECT * FROM parquetTableZOrder WHERE x = 0 OR y = 0").noop()
}
benchmark.addCase("ORC no sort") { _ =>
spark.sql(s"SELECT * FROM orcTable WHERE x = 0 OR y = 0").noop()
}
benchmark.addCase("ORC z-order sort on (x, y)") { _ =>
spark.sql(s"SELECT * FROM orcTableZOrder WHERE x = 0 OR y = 0").noop()
}
benchmark.run()
}
}
}
}
```
* Compare the performance between reading table having no sort, and table having local Z-order sort on `(x, y)`.
Seeing 6x run-time improvement for Parquet, and 1x for ORC:
```
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.16
Intel(R) Core(TM) i9-9980HK CPU @ 2.40GHz
zorder: Best Time(ms) Avg Time(ms) Stdev(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------------------------------
Parquet no sort 274 287 11 57.5 17.4 1.0X
Parquet z-order sort on (x, y) 37 41 2 420.2 2.4 7.3X
ORC no sort 674 754 47 23.3 42.8 0.4X
ORC z-order sort on (x, y) 262 282 11 59.9 16.7 1.0X
```
* Compare the performance between reading table having no sort, and table having local sort on `(x, y)`.
No performance improvement as expected.
```
Java HotSpot(TM) 64-Bit Server VM 1.8.0_181-b13 on Mac OS X 10.16
Intel(R) Core(TM) i9-9980HK CPU @ 2.40GHz
zorder: Best Time(ms) Avg Time(ms) Stdev(ms) Rate(M/s) Per Row(ns) Relative
------------------------------------------------------------------------------------------------------------------------
Parquet no sort 285 319 29 55.1 18.1 1.0X
Parquet sort on (x, y) 278 290 10 56.5 17.7 1.0X
ORC no sort 823 842 21 19.1 52.4 0.3X
ORC sort on (x, y) 748 760 16 21.0 47.6 0.4X
```
### Does this PR introduce _any_ user-facing change?
<!--
Note that it means *any* user-facing change including all aspects such as the documentation fix.
If yes, please clarify the previous behavior and the change this PR proposes - provide the console output, description and/or an example to show the behavior difference if possible.
If possible, please also clarify if this is a user-facing change compared to the released Spark versions or within the unreleased branches such as master.
If no, write 'No'.
-->
Yes. The added expression can be used by user - `zorder`.
### How was this patch tested?
<!--
If tests were added, say they were added here. Please make sure to add some test cases that check the changes thoroughly including negative and positive cases if possible.
If it was tested in a way different from regular unit tests, please clarify how you tested step by step, ideally copy and paste-able, so that other reviewers can test and check, and descendants can verify in the future.
If tests were not added, please describe why they were not added and/or why it was difficult to add.
If benchmark tests were added, please run the benchmarks in GitHub Actions for the consistent environment, and the instructions could accord to: https://spark.apache.org/developer-tools.html#github-workflow-benchmarks.
-->
Added unit test in `ZOrderExpressionSuite.scala`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] [spark] c21 commented on pull request #34640: [SPARK-31585][SQL] Introduce Z-order expression
Posted by GitBox <gi...@apache.org>.
c21 commented on pull request #34640:
URL: https://github.com/apache/spark/pull/34640#issuecomment-981978009
> Is there any query performance improvement report from your internal production usage? How about storage efficiency(any improvement on compression ratio)?
@advancedxy - we haven't rolled out this feature in our production yet, still testing so there should be quite some room for further optimization. For storage efficiency, I haven't checked, but assume it should help in some sense, as rows with same values are sorted to be adjacent to each other. So the Parquet & ORC output file should be encoded better and become smaller.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] [spark] sunchao commented on pull request #34640: [SPARK-31585][SQL] Introduce Z-order expression
Posted by GitBox <gi...@apache.org>.
sunchao commented on pull request #34640:
URL: https://github.com/apache/spark/pull/34640#issuecomment-972536327
cc @RussellSpitzer too who's working on Z-ordering from Apache Iceberg side
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] [spark] advancedxy commented on a change in pull request #34640: [SPARK-31585][SQL] Introduce Z-order expression
Posted by GitBox <gi...@apache.org>.
advancedxy commented on a change in pull request #34640:
URL: https://github.com/apache/spark/pull/34640#discussion_r752840061
##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/ZOrder.scala
##########
@@ -0,0 +1,222 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.sql.catalyst.expressions
+
+import org.apache.spark.sql.catalyst.InternalRow
+import org.apache.spark.sql.catalyst.expressions.codegen.CodegenFallback
+import org.apache.spark.sql.types.{AbstractDataType, BinaryType, ByteType, DataType, IntegerType, IntegralType, LongType, ShortType}
+
+/**
+ * An expression that calculates Z-order value (https://en.wikipedia.org/wiki/Z-order_curve)
+ * from `children` input data.
+ *
+ * At the high level, Z-order value is calculated by interleaving the binary representations of
+ * `children` input. So the Z-order value preserves locality of input data, while mapping the
+ * multi-dimensional input into one dimension output.
+ *
+ */
+@ExpressionDescription(
+ usage = """
+ _FUNC_(input1, input2, ...) - Returns Z-order value in binary type for inputs.
+ """,
+ examples = """
+ Examples:
+ > SELECT _FUNC_(1, 2);
+ [-64, 6]
+ """,
+ since = "3.3.0",
+ group = "misc_funcs")
+case class ZOrder(children: Seq[Expression])
+ extends Expression with ExpectsInputTypes with CodegenFallback {
+
+ override def nullable: Boolean = false
+
+ /**
+ * Supported input data types. Currently support [[IntegralType]].
+ *
+ * TODO(SPARK-37362): Support [[FractionalType]] for Z-order.
+ * TODO(SPARK-37363): Support [[StringType]] for Z-order.
+ */
+ override def inputTypes: Seq[AbstractDataType] = Seq.fill(children.size)(IntegralType)
+
+ override def dataType: DataType = BinaryType
+
+ override def prettyName: String = "zorder"
+
+ /**
+ * Number of bits per input in binary representation.
+ */
+ @transient private lazy val inputBitSizes = children.map(_.dataType.defaultSize * 8)
+
+ /**
+ * Maximal number of bits per input in binary representation.
+ */
+ @transient private lazy val inputBitMaxSize = inputBitSizes.max
+
+ /**
+ * Total number of bits per input in binary representation.
+ */
+ @transient private lazy val inputBitTotalSize = inputBitSizes.sum
+
+ /**
+ * The output for Z-order, represented in byte array format.
+ */
+ @transient private lazy val outputBytes = new Array[Byte](inputBitTotalSize / 8)
+
+ /**
+ * Handle input with null value. Convert null into minimal value per each data type.
+ * This mimics [[NullsFirst]] sort ordering.
+ */
+ @transient private lazy val handleNullFromInputs: Seq[Any => Any] = children.map {
+ child => child.dataType match {
+ case ByteType =>
+ value: Any => if (value == null) Byte.MinValue else value
+ case ShortType =>
+ value: Any => if (value == null) Short.MinValue else value
+ case IntegerType =>
+ value: Any => if (value == null) Int.MinValue else value
+ case LongType =>
+ value: Any => if (value == null) Long.MinValue else value
+ case x =>
+ throw new IllegalArgumentException(
+ s"ZOrder expression should not take $x as the data type")
+ }
+ }
+
+ /**
+ * Get the bit in `ordinal` position (0-based) of input `value`.
+ * The return value of corresponding bit is in [[Byte]] type.
+ */
+ @transient private lazy val getBitFromInputs: Seq[(Any, Int) => Byte] = children.map { child =>
+ child.dataType match {
+ case ByteType =>
+ (value: Any, ordinal: Int) =>
+ ((value.asInstanceOf[Byte] >> ordinal) & 1).toByte
+ case ShortType =>
+ (value: Any, ordinal: Int) =>
+ ((value.asInstanceOf[Short] >> ordinal) & 1).toByte
+ case IntegerType =>
+ (value: Any, ordinal: Int) =>
+ ((value.asInstanceOf[Int] >> ordinal) & 1).toByte
+ case LongType =>
+ (value: Any, ordinal: Int) =>
+ ((value.asInstanceOf[Long] >> ordinal) & 1).toByte
+ case x =>
+ throw new IllegalArgumentException(
+ s"ZOrder expression should not take $x as the data type")
+ }
+ }
+
+ /**
+ * Get the Z-order sign bit of input `value`.
+ *
+ * For [[IntegralType]], Z-order flips the original sign bit of input. Sign bit is 0 for negative
+ * value, and 1 for positive value. This is to maintain the same ordering between input and
+ * output in [[BinaryType]].
+ */
+ @transient private lazy val getZOrderSignBitFromInputs: Seq[Any => Byte] = children.map {
+ child => child.dataType match {
+ case ByteType =>
+ value: Any => if (value.asInstanceOf[Byte] < 0) 0.toByte else 1.toByte
+ case ShortType =>
+ value: Any => if (value.asInstanceOf[Short] < 0) 0.toByte else 1.toByte
+ case IntegerType =>
+ value: Any => if (value.asInstanceOf[Int] < 0) 0.toByte else 1.toByte
+ case LongType =>
+ value: Any => if (value.asInstanceOf[Long] < 0) 0.toByte else 1.toByte
+ case x =>
+ throw new IllegalArgumentException(
+ s"ZOrder expression should not take $x as the data type")
+ }
+ }
+
+ /**
+ * Update the bit at `ordinal` position (0-based) in `outputBytes`, with new value `bitAsByte`.
+ */
+ private def updateBitInOutput(bitAsByte: Byte, ordinal: Int): Unit = {
+ val currentByteIndex = ordinal >> 3
+ val currentByte = outputBytes(currentByteIndex)
+ val newByte = (currentByte | (bitAsByte << ((ordinal & 7) ^ 7))).toByte
+ outputBytes.update(currentByteIndex, newByte)
+ }
+
+ /**
+ * Calculate Z-order from `input` and store the result in `outputBytes`.
+ *
+ * The function has the following steps:
+ * - Step 1: Handle null value from `input`.
+ * - Step 2: Initialize `outputBytes` with all zeros.
+ * - Step 3: Interleave sign bits from `input` and write to `outputBytes`.
+ * - Step 4: Interleave data bits from `input` and write to `outputBytes`.
+ * Start from most significant bit to least. Skip the corresponding
+ * input if it finishes early.
+ *
+ * Example (all value in binary representation for illustration purpose):
+ * input1: 01111010
+ * input2: 10011011 11100001
+ *
+ * output: 10101011 11001101 11100001
+ * ||\ /
+ * || ---------------------
+ * (Z-order sign bits) |
+ * (Z-order data bits)
+ *
+ * TODO(SPARK-37364): Support code-gen evaluation for Z-order.
+ */
+ override def eval(input: InternalRow): Any = {
+ val evaluatedInput = children.map(_.eval(input))
+
+ // Handle null value from `input`.
+ val inputValues = handleNullFromInputs.zip(evaluatedInput).map {
+ case (nullHandler, value) => nullHandler(value)
+ }
+ var outputBitIndex = 0
+
+ // Initialize `outputBytes` with all zeros.
+ outputBytes.indices.foreach(outputBytes.update(_, 0))
Review comment:
How about create a new byte[] every time?
Otherwise, I think `Arrays.fill(outputBytes, 0.toByte)` should be more efficient
##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/ZOrder.scala
##########
@@ -0,0 +1,222 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.sql.catalyst.expressions
+
+import org.apache.spark.sql.catalyst.InternalRow
+import org.apache.spark.sql.catalyst.expressions.codegen.CodegenFallback
+import org.apache.spark.sql.types.{AbstractDataType, BinaryType, ByteType, DataType, IntegerType, IntegralType, LongType, ShortType}
+
+/**
+ * An expression that calculates Z-order value (https://en.wikipedia.org/wiki/Z-order_curve)
+ * from `children` input data.
+ *
+ * At the high level, Z-order value is calculated by interleaving the binary representations of
+ * `children` input. So the Z-order value preserves locality of input data, while mapping the
+ * multi-dimensional input into one dimension output.
+ *
+ */
+@ExpressionDescription(
+ usage = """
+ _FUNC_(input1, input2, ...) - Returns Z-order value in binary type for inputs.
+ """,
+ examples = """
+ Examples:
+ > SELECT _FUNC_(1, 2);
+ [-64, 6]
+ """,
+ since = "3.3.0",
+ group = "misc_funcs")
+case class ZOrder(children: Seq[Expression])
+ extends Expression with ExpectsInputTypes with CodegenFallback {
+
+ override def nullable: Boolean = false
+
+ /**
+ * Supported input data types. Currently support [[IntegralType]].
+ *
+ * TODO(SPARK-37362): Support [[FractionalType]] for Z-order.
+ * TODO(SPARK-37363): Support [[StringType]] for Z-order.
+ */
+ override def inputTypes: Seq[AbstractDataType] = Seq.fill(children.size)(IntegralType)
+
+ override def dataType: DataType = BinaryType
+
+ override def prettyName: String = "zorder"
+
+ /**
+ * Number of bits per input in binary representation.
+ */
+ @transient private lazy val inputBitSizes = children.map(_.dataType.defaultSize * 8)
+
+ /**
+ * Maximal number of bits per input in binary representation.
+ */
+ @transient private lazy val inputBitMaxSize = inputBitSizes.max
+
+ /**
+ * Total number of bits per input in binary representation.
+ */
+ @transient private lazy val inputBitTotalSize = inputBitSizes.sum
+
+ /**
+ * The output for Z-order, represented in byte array format.
+ */
+ @transient private lazy val outputBytes = new Array[Byte](inputBitTotalSize / 8)
+
+ /**
+ * Handle input with null value. Convert null into minimal value per each data type.
+ * This mimics [[NullsFirst]] sort ordering.
+ */
+ @transient private lazy val handleNullFromInputs: Seq[Any => Any] = children.map {
+ child => child.dataType match {
+ case ByteType =>
+ value: Any => if (value == null) Byte.MinValue else value
+ case ShortType =>
+ value: Any => if (value == null) Short.MinValue else value
+ case IntegerType =>
+ value: Any => if (value == null) Int.MinValue else value
+ case LongType =>
+ value: Any => if (value == null) Long.MinValue else value
+ case x =>
+ throw new IllegalArgumentException(
+ s"ZOrder expression should not take $x as the data type")
+ }
+ }
+
+ /**
+ * Get the bit in `ordinal` position (0-based) of input `value`.
+ * The return value of corresponding bit is in [[Byte]] type.
+ */
+ @transient private lazy val getBitFromInputs: Seq[(Any, Int) => Byte] = children.map { child =>
+ child.dataType match {
+ case ByteType =>
+ (value: Any, ordinal: Int) =>
+ ((value.asInstanceOf[Byte] >> ordinal) & 1).toByte
+ case ShortType =>
+ (value: Any, ordinal: Int) =>
+ ((value.asInstanceOf[Short] >> ordinal) & 1).toByte
+ case IntegerType =>
+ (value: Any, ordinal: Int) =>
+ ((value.asInstanceOf[Int] >> ordinal) & 1).toByte
+ case LongType =>
+ (value: Any, ordinal: Int) =>
+ ((value.asInstanceOf[Long] >> ordinal) & 1).toByte
+ case x =>
+ throw new IllegalArgumentException(
+ s"ZOrder expression should not take $x as the data type")
+ }
+ }
+
+ /**
+ * Get the Z-order sign bit of input `value`.
+ *
+ * For [[IntegralType]], Z-order flips the original sign bit of input. Sign bit is 0 for negative
+ * value, and 1 for positive value. This is to maintain the same ordering between input and
+ * output in [[BinaryType]].
+ */
+ @transient private lazy val getZOrderSignBitFromInputs: Seq[Any => Byte] = children.map {
Review comment:
this will involve a lot of object creation and gc-ed.
is it possible to put all the input bytes in one byte[] and do interleaving by accessing the input byte[] directly?
##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/ZOrder.scala
##########
@@ -0,0 +1,222 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.sql.catalyst.expressions
+
+import org.apache.spark.sql.catalyst.InternalRow
+import org.apache.spark.sql.catalyst.expressions.codegen.CodegenFallback
+import org.apache.spark.sql.types.{AbstractDataType, BinaryType, ByteType, DataType, IntegerType, IntegralType, LongType, ShortType}
+
+/**
+ * An expression that calculates Z-order value (https://en.wikipedia.org/wiki/Z-order_curve)
+ * from `children` input data.
+ *
+ * At the high level, Z-order value is calculated by interleaving the binary representations of
+ * `children` input. So the Z-order value preserves locality of input data, while mapping the
+ * multi-dimensional input into one dimension output.
+ *
+ */
+@ExpressionDescription(
+ usage = """
+ _FUNC_(input1, input2, ...) - Returns Z-order value in binary type for inputs.
+ """,
+ examples = """
+ Examples:
+ > SELECT _FUNC_(1, 2);
+ [-64, 6]
+ """,
+ since = "3.3.0",
+ group = "misc_funcs")
+case class ZOrder(children: Seq[Expression])
+ extends Expression with ExpectsInputTypes with CodegenFallback {
+
+ override def nullable: Boolean = false
+
+ /**
+ * Supported input data types. Currently support [[IntegralType]].
+ *
+ * TODO(SPARK-37362): Support [[FractionalType]] for Z-order.
+ * TODO(SPARK-37363): Support [[StringType]] for Z-order.
+ */
+ override def inputTypes: Seq[AbstractDataType] = Seq.fill(children.size)(IntegralType)
+
+ override def dataType: DataType = BinaryType
+
+ override def prettyName: String = "zorder"
+
+ /**
+ * Number of bits per input in binary representation.
+ */
+ @transient private lazy val inputBitSizes = children.map(_.dataType.defaultSize * 8)
+
+ /**
+ * Maximal number of bits per input in binary representation.
+ */
+ @transient private lazy val inputBitMaxSize = inputBitSizes.max
+
+ /**
+ * Total number of bits per input in binary representation.
+ */
+ @transient private lazy val inputBitTotalSize = inputBitSizes.sum
+
+ /**
+ * The output for Z-order, represented in byte array format.
+ */
+ @transient private lazy val outputBytes = new Array[Byte](inputBitTotalSize / 8)
+
+ /**
+ * Handle input with null value. Convert null into minimal value per each data type.
Review comment:
Since zorder is about bit interleaving, do you consider mapping null to zeros?
I am not saying that mapping null to minimal value is wrong.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] [spark] c21 commented on a change in pull request #34640: [SPARK-31585][SQL] Introduce Z-order expression
Posted by GitBox <gi...@apache.org>.
c21 commented on a change in pull request #34640:
URL: https://github.com/apache/spark/pull/34640#discussion_r758702199
##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/ZOrder.scala
##########
@@ -0,0 +1,222 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.sql.catalyst.expressions
+
+import org.apache.spark.sql.catalyst.InternalRow
+import org.apache.spark.sql.catalyst.expressions.codegen.CodegenFallback
+import org.apache.spark.sql.types.{AbstractDataType, BinaryType, ByteType, DataType, IntegerType, IntegralType, LongType, ShortType}
+
+/**
+ * An expression that calculates Z-order value (https://en.wikipedia.org/wiki/Z-order_curve)
+ * from `children` input data.
+ *
+ * At the high level, Z-order value is calculated by interleaving the binary representations of
+ * `children` input. So the Z-order value preserves locality of input data, while mapping the
+ * multi-dimensional input into one dimension output.
+ *
+ */
+@ExpressionDescription(
+ usage = """
+ _FUNC_(input1, input2, ...) - Returns Z-order value in binary type for inputs.
+ """,
+ examples = """
+ Examples:
+ > SELECT _FUNC_(1, 2);
+ [-64, 6]
+ """,
+ since = "3.3.0",
+ group = "misc_funcs")
+case class ZOrder(children: Seq[Expression])
+ extends Expression with ExpectsInputTypes with CodegenFallback {
+
+ override def nullable: Boolean = false
+
+ /**
+ * Supported input data types. Currently support [[IntegralType]].
+ *
+ * TODO(SPARK-37362): Support [[FractionalType]] for Z-order.
+ * TODO(SPARK-37363): Support [[StringType]] for Z-order.
+ */
+ override def inputTypes: Seq[AbstractDataType] = Seq.fill(children.size)(IntegralType)
+
+ override def dataType: DataType = BinaryType
+
+ override def prettyName: String = "zorder"
+
+ /**
+ * Number of bits per input in binary representation.
+ */
+ @transient private lazy val inputBitSizes = children.map(_.dataType.defaultSize * 8)
+
+ /**
+ * Maximal number of bits per input in binary representation.
+ */
+ @transient private lazy val inputBitMaxSize = inputBitSizes.max
+
+ /**
+ * Total number of bits per input in binary representation.
+ */
+ @transient private lazy val inputBitTotalSize = inputBitSizes.sum
+
+ /**
+ * The output for Z-order, represented in byte array format.
+ */
+ @transient private lazy val outputBytes = new Array[Byte](inputBitTotalSize / 8)
+
+ /**
+ * Handle input with null value. Convert null into minimal value per each data type.
+ * This mimics [[NullsFirst]] sort ordering.
+ */
+ @transient private lazy val handleNullFromInputs: Seq[Any => Any] = children.map {
+ child => child.dataType match {
+ case ByteType =>
+ value: Any => if (value == null) Byte.MinValue else value
+ case ShortType =>
+ value: Any => if (value == null) Short.MinValue else value
+ case IntegerType =>
+ value: Any => if (value == null) Int.MinValue else value
+ case LongType =>
+ value: Any => if (value == null) Long.MinValue else value
+ case x =>
+ throw new IllegalArgumentException(
+ s"ZOrder expression should not take $x as the data type")
+ }
+ }
+
+ /**
+ * Get the bit in `ordinal` position (0-based) of input `value`.
+ * The return value of corresponding bit is in [[Byte]] type.
+ */
+ @transient private lazy val getBitFromInputs: Seq[(Any, Int) => Byte] = children.map { child =>
+ child.dataType match {
+ case ByteType =>
+ (value: Any, ordinal: Int) =>
+ ((value.asInstanceOf[Byte] >> ordinal) & 1).toByte
+ case ShortType =>
+ (value: Any, ordinal: Int) =>
+ ((value.asInstanceOf[Short] >> ordinal) & 1).toByte
+ case IntegerType =>
+ (value: Any, ordinal: Int) =>
+ ((value.asInstanceOf[Int] >> ordinal) & 1).toByte
+ case LongType =>
+ (value: Any, ordinal: Int) =>
+ ((value.asInstanceOf[Long] >> ordinal) & 1).toByte
+ case x =>
+ throw new IllegalArgumentException(
+ s"ZOrder expression should not take $x as the data type")
+ }
+ }
+
+ /**
+ * Get the Z-order sign bit of input `value`.
+ *
+ * For [[IntegralType]], Z-order flips the original sign bit of input. Sign bit is 0 for negative
+ * value, and 1 for positive value. This is to maintain the same ordering between input and
+ * output in [[BinaryType]].
+ */
+ @transient private lazy val getZOrderSignBitFromInputs: Seq[Any => Byte] = children.map {
Review comment:
> this will involve a lot of object creation and gc-ed.
Please correct me if my understanding is wrong, but here with `lazy val`, `getZOrderSignBitFromInputs` is only created once and reused per row.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] [spark] SparkQA commented on pull request #34640: [SPARK-31585][SQL] Introduce Z-order expression
Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #34640:
URL: https://github.com/apache/spark/pull/34640#issuecomment-972485974
Kubernetes integration test starting
URL: https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder-K8s/49829/
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] [spark] c21 commented on pull request #34640: [SPARK-31585][SQL] Introduce Z-order expression
Posted by GitBox <gi...@apache.org>.
c21 commented on pull request #34640:
URL: https://github.com/apache/spark/pull/34640#issuecomment-981975058
> Just FYI some faster interleave bits approach from stanford
@ulysses-you - thanks for pointing it out. I think this is good to add later, once community agrees we should have a Z-order expression supported in Spark natively. This PR is just bare minimum, and would like to make sure we want to move forward with this direction first.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] [spark] ulysses-you commented on pull request #34640: [SPARK-31585][SQL] Introduce Z-order expression
Posted by GitBox <gi...@apache.org>.
ulysses-you commented on pull request #34640:
URL: https://github.com/apache/spark/pull/34640#issuecomment-972514840
Just FYI some faster interleave bits approach from [stanford](http://graphics.stanford.edu/~seander/bithacks.html#InterleaveTableObvious)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] [spark] SparkQA commented on pull request #34640: [SPARK-31585][SQL] Introduce Z-order expression
Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #34640:
URL: https://github.com/apache/spark/pull/34640#issuecomment-972534689
**[Test build #145358 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/145358/testReport)** for PR 34640 at commit [`783f0e6`](https://github.com/apache/spark/commit/783f0e60a88120614e54820f6ad3792e3b50cd84).
* This patch **fails Spark unit tests**.
* This patch merges cleanly.
* This patch adds the following public classes _(experimental)_:
* `case class ZOrder(children: Seq[Expression])`
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] [spark] AmplabJenkins removed a comment on pull request #34640: [SPARK-31585][SQL] Introduce Z-order expression
Posted by GitBox <gi...@apache.org>.
AmplabJenkins removed a comment on pull request #34640:
URL: https://github.com/apache/spark/pull/34640#issuecomment-972530341
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder-K8s/49829/
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] [spark] SparkQA commented on pull request #34640: [SPARK-31585][SQL] Introduce Z-order expression
Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #34640:
URL: https://github.com/apache/spark/pull/34640#issuecomment-972461584
**[Test build #145358 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/145358/testReport)** for PR 34640 at commit [`783f0e6`](https://github.com/apache/spark/commit/783f0e60a88120614e54820f6ad3792e3b50cd84).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] [spark] github-actions[bot] commented on pull request #34640: [SPARK-31585][SQL] Introduce Z-order expression
Posted by GitBox <gi...@apache.org>.
github-actions[bot] commented on pull request #34640:
URL: https://github.com/apache/spark/pull/34640#issuecomment-1065703076
We're closing this PR because it hasn't been updated in a while. This isn't a judgement on the merit of the PR in any way. It's just a way of keeping the PR queue manageable.
If you'd like to revive this PR, please reopen it and ask a committer to remove the Stale tag!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] [spark] advancedxy commented on pull request #34640: [SPARK-31585][SQL] Introduce Z-order expression
Posted by GitBox <gi...@apache.org>.
advancedxy commented on pull request #34640:
URL: https://github.com/apache/spark/pull/34640#issuecomment-983338047
> @advancedxy - we haven't rolled out this feature in our production yet, still testing so there should be quite some room for further optimization. For storage efficiency, I haven't checked, but assume it should help in some sense, as rows with same values are sorted to be adjacent to each other. So the Parquet & ORC output file should be encoded better and become smaller.
Looking forward to production usage report if that's possible. I also added zvalue support in our internal usage, it's quite useful for some query cases (1.5 ~ 2.x speedup for the corresponding scan stage)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] [spark] AmplabJenkins removed a comment on pull request #34640: [SPARK-31585][SQL] Introduce Z-order expression
Posted by GitBox <gi...@apache.org>.
AmplabJenkins removed a comment on pull request #34640:
URL: https://github.com/apache/spark/pull/34640#issuecomment-972534860
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/145358/
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] [spark] SparkQA removed a comment on pull request #34640: [SPARK-31585][SQL] Introduce Z-order expression
Posted by GitBox <gi...@apache.org>.
SparkQA removed a comment on pull request #34640:
URL: https://github.com/apache/spark/pull/34640#issuecomment-972461584
**[Test build #145358 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/145358/testReport)** for PR 34640 at commit [`783f0e6`](https://github.com/apache/spark/commit/783f0e60a88120614e54820f6ad3792e3b50cd84).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] [spark] AmplabJenkins commented on pull request #34640: [SPARK-31585][SQL] Introduce Z-order expression
Posted by GitBox <gi...@apache.org>.
AmplabJenkins commented on pull request #34640:
URL: https://github.com/apache/spark/pull/34640#issuecomment-972530341
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder-K8s/49829/
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] [spark] github-actions[bot] closed pull request #34640: [SPARK-31585][SQL] Introduce Z-order expression
Posted by GitBox <gi...@apache.org>.
github-actions[bot] closed pull request #34640:
URL: https://github.com/apache/spark/pull/34640
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] [spark] c21 commented on pull request #34640: [SPARK-31585][SQL] Introduce Z-order expression
Posted by GitBox <gi...@apache.org>.
c21 commented on pull request #34640:
URL: https://github.com/apache/spark/pull/34640#issuecomment-972459294
cc @cloud-fan and @wangyum could you help take a look when you have time? Thanks.
Looking forward to feedback.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] [spark] RussellSpitzer commented on a change in pull request #34640: [SPARK-31585][SQL] Introduce Z-order expression
Posted by GitBox <gi...@apache.org>.
RussellSpitzer commented on a change in pull request #34640:
URL: https://github.com/apache/spark/pull/34640#discussion_r759525098
##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/ZOrder.scala
##########
@@ -0,0 +1,222 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.sql.catalyst.expressions
+
+import org.apache.spark.sql.catalyst.InternalRow
+import org.apache.spark.sql.catalyst.expressions.codegen.CodegenFallback
+import org.apache.spark.sql.types.{AbstractDataType, BinaryType, ByteType, DataType, IntegerType, IntegralType, LongType, ShortType}
+
+/**
+ * An expression that calculates Z-order value (https://en.wikipedia.org/wiki/Z-order_curve)
+ * from `children` input data.
+ *
+ * At the high level, Z-order value is calculated by interleaving the binary representations of
+ * `children` input. So the Z-order value preserves locality of input data, while mapping the
+ * multi-dimensional input into one dimension output.
+ *
+ */
+@ExpressionDescription(
+ usage = """
+ _FUNC_(input1, input2, ...) - Returns Z-order value in binary type for inputs.
+ """,
+ examples = """
+ Examples:
+ > SELECT _FUNC_(1, 2);
+ [-64, 6]
+ """,
+ since = "3.3.0",
+ group = "misc_funcs")
+case class ZOrder(children: Seq[Expression])
+ extends Expression with ExpectsInputTypes with CodegenFallback {
+
+ override def nullable: Boolean = false
+
+ /**
+ * Supported input data types. Currently support [[IntegralType]].
+ *
+ * TODO(SPARK-37362): Support [[FractionalType]] for Z-order.
+ * TODO(SPARK-37363): Support [[StringType]] for Z-order.
+ */
+ override def inputTypes: Seq[AbstractDataType] = Seq.fill(children.size)(IntegralType)
+
+ override def dataType: DataType = BinaryType
+
+ override def prettyName: String = "zorder"
+
+ /**
+ * Number of bits per input in binary representation.
+ */
+ @transient private lazy val inputBitSizes = children.map(_.dataType.defaultSize * 8)
+
+ /**
+ * Maximal number of bits per input in binary representation.
+ */
+ @transient private lazy val inputBitMaxSize = inputBitSizes.max
+
+ /**
+ * Total number of bits per input in binary representation.
+ */
+ @transient private lazy val inputBitTotalSize = inputBitSizes.sum
+
+ /**
+ * The output for Z-order, represented in byte array format.
+ */
+ @transient private lazy val outputBytes = new Array[Byte](inputBitTotalSize / 8)
+
+ /**
+ * Handle input with null value. Convert null into minimal value per each data type.
Review comment:
I think null first semantics makes more sense here, but having the absolute minimum value would make interleaving difficult depending on the range of actual values. This is probably ok to leave for a later improvement which takes the range of values being zordered into account.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] [spark] advancedxy commented on a change in pull request #34640: [SPARK-31585][SQL] Introduce Z-order expression
Posted by GitBox <gi...@apache.org>.
advancedxy commented on a change in pull request #34640:
URL: https://github.com/apache/spark/pull/34640#discussion_r759890419
##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/ZOrder.scala
##########
@@ -0,0 +1,222 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.sql.catalyst.expressions
+
+import org.apache.spark.sql.catalyst.InternalRow
+import org.apache.spark.sql.catalyst.expressions.codegen.CodegenFallback
+import org.apache.spark.sql.types.{AbstractDataType, BinaryType, ByteType, DataType, IntegerType, IntegralType, LongType, ShortType}
+
+/**
+ * An expression that calculates Z-order value (https://en.wikipedia.org/wiki/Z-order_curve)
+ * from `children` input data.
+ *
+ * At the high level, Z-order value is calculated by interleaving the binary representations of
+ * `children` input. So the Z-order value preserves locality of input data, while mapping the
+ * multi-dimensional input into one dimension output.
+ *
+ */
+@ExpressionDescription(
+ usage = """
+ _FUNC_(input1, input2, ...) - Returns Z-order value in binary type for inputs.
+ """,
+ examples = """
+ Examples:
+ > SELECT _FUNC_(1, 2);
+ [-64, 6]
+ """,
+ since = "3.3.0",
+ group = "misc_funcs")
+case class ZOrder(children: Seq[Expression])
+ extends Expression with ExpectsInputTypes with CodegenFallback {
+
+ override def nullable: Boolean = false
+
+ /**
+ * Supported input data types. Currently support [[IntegralType]].
+ *
+ * TODO(SPARK-37362): Support [[FractionalType]] for Z-order.
+ * TODO(SPARK-37363): Support [[StringType]] for Z-order.
+ */
+ override def inputTypes: Seq[AbstractDataType] = Seq.fill(children.size)(IntegralType)
+
+ override def dataType: DataType = BinaryType
+
+ override def prettyName: String = "zorder"
+
+ /**
+ * Number of bits per input in binary representation.
+ */
+ @transient private lazy val inputBitSizes = children.map(_.dataType.defaultSize * 8)
+
+ /**
+ * Maximal number of bits per input in binary representation.
+ */
+ @transient private lazy val inputBitMaxSize = inputBitSizes.max
+
+ /**
+ * Total number of bits per input in binary representation.
+ */
+ @transient private lazy val inputBitTotalSize = inputBitSizes.sum
+
+ /**
+ * The output for Z-order, represented in byte array format.
+ */
+ @transient private lazy val outputBytes = new Array[Byte](inputBitTotalSize / 8)
+
+ /**
+ * Handle input with null value. Convert null into minimal value per each data type.
+ * This mimics [[NullsFirst]] sort ordering.
+ */
+ @transient private lazy val handleNullFromInputs: Seq[Any => Any] = children.map {
+ child => child.dataType match {
+ case ByteType =>
+ value: Any => if (value == null) Byte.MinValue else value
+ case ShortType =>
+ value: Any => if (value == null) Short.MinValue else value
+ case IntegerType =>
+ value: Any => if (value == null) Int.MinValue else value
+ case LongType =>
+ value: Any => if (value == null) Long.MinValue else value
+ case x =>
+ throw new IllegalArgumentException(
+ s"ZOrder expression should not take $x as the data type")
+ }
+ }
+
+ /**
+ * Get the bit in `ordinal` position (0-based) of input `value`.
+ * The return value of corresponding bit is in [[Byte]] type.
+ */
+ @transient private lazy val getBitFromInputs: Seq[(Any, Int) => Byte] = children.map { child =>
+ child.dataType match {
+ case ByteType =>
+ (value: Any, ordinal: Int) =>
+ ((value.asInstanceOf[Byte] >> ordinal) & 1).toByte
+ case ShortType =>
+ (value: Any, ordinal: Int) =>
+ ((value.asInstanceOf[Short] >> ordinal) & 1).toByte
+ case IntegerType =>
+ (value: Any, ordinal: Int) =>
+ ((value.asInstanceOf[Int] >> ordinal) & 1).toByte
+ case LongType =>
+ (value: Any, ordinal: Int) =>
+ ((value.asInstanceOf[Long] >> ordinal) & 1).toByte
+ case x =>
+ throw new IllegalArgumentException(
+ s"ZOrder expression should not take $x as the data type")
+ }
+ }
+
+ /**
+ * Get the Z-order sign bit of input `value`.
+ *
+ * For [[IntegralType]], Z-order flips the original sign bit of input. Sign bit is 0 for negative
+ * value, and 1 for positive value. This is to maintain the same ordering between input and
+ * output in [[BinaryType]].
+ */
+ @transient private lazy val getZOrderSignBitFromInputs: Seq[Any => Byte] = children.map {
Review comment:
```
case ByteType =>
value: Any => if (value.asInstanceOf[Byte] < 0) 0.toByte else 1.toByte
```
the value is an Any type, which will involves boxing and unboxing, which involves object creation. For code generation optimizations, we would avoid this type of methods.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] [spark] AmplabJenkins commented on pull request #34640: [SPARK-31585][SQL] Introduce Z-order expression
Posted by GitBox <gi...@apache.org>.
AmplabJenkins commented on pull request #34640:
URL: https://github.com/apache/spark/pull/34640#issuecomment-972534860
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/145358/
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] [spark] SparkQA commented on pull request #34640: [SPARK-31585][SQL] Introduce Z-order expression
Posted by GitBox <gi...@apache.org>.
SparkQA commented on pull request #34640:
URL: https://github.com/apache/spark/pull/34640#issuecomment-972521348
Kubernetes integration test status failure
URL: https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder-K8s/49829/
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] [spark] c21 commented on a change in pull request #34640: [SPARK-31585][SQL] Introduce Z-order expression
Posted by GitBox <gi...@apache.org>.
c21 commented on a change in pull request #34640:
URL: https://github.com/apache/spark/pull/34640#discussion_r758701226
##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/ZOrder.scala
##########
@@ -0,0 +1,222 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.sql.catalyst.expressions
+
+import org.apache.spark.sql.catalyst.InternalRow
+import org.apache.spark.sql.catalyst.expressions.codegen.CodegenFallback
+import org.apache.spark.sql.types.{AbstractDataType, BinaryType, ByteType, DataType, IntegerType, IntegralType, LongType, ShortType}
+
+/**
+ * An expression that calculates Z-order value (https://en.wikipedia.org/wiki/Z-order_curve)
+ * from `children` input data.
+ *
+ * At the high level, Z-order value is calculated by interleaving the binary representations of
+ * `children` input. So the Z-order value preserves locality of input data, while mapping the
+ * multi-dimensional input into one dimension output.
+ *
+ */
+@ExpressionDescription(
+ usage = """
+ _FUNC_(input1, input2, ...) - Returns Z-order value in binary type for inputs.
+ """,
+ examples = """
+ Examples:
+ > SELECT _FUNC_(1, 2);
+ [-64, 6]
+ """,
+ since = "3.3.0",
+ group = "misc_funcs")
+case class ZOrder(children: Seq[Expression])
+ extends Expression with ExpectsInputTypes with CodegenFallback {
+
+ override def nullable: Boolean = false
+
+ /**
+ * Supported input data types. Currently support [[IntegralType]].
+ *
+ * TODO(SPARK-37362): Support [[FractionalType]] for Z-order.
+ * TODO(SPARK-37363): Support [[StringType]] for Z-order.
+ */
+ override def inputTypes: Seq[AbstractDataType] = Seq.fill(children.size)(IntegralType)
+
+ override def dataType: DataType = BinaryType
+
+ override def prettyName: String = "zorder"
+
+ /**
+ * Number of bits per input in binary representation.
+ */
+ @transient private lazy val inputBitSizes = children.map(_.dataType.defaultSize * 8)
+
+ /**
+ * Maximal number of bits per input in binary representation.
+ */
+ @transient private lazy val inputBitMaxSize = inputBitSizes.max
+
+ /**
+ * Total number of bits per input in binary representation.
+ */
+ @transient private lazy val inputBitTotalSize = inputBitSizes.sum
+
+ /**
+ * The output for Z-order, represented in byte array format.
+ */
+ @transient private lazy val outputBytes = new Array[Byte](inputBitTotalSize / 8)
+
+ /**
+ * Handle input with null value. Convert null into minimal value per each data type.
+ * This mimics [[NullsFirst]] sort ordering.
+ */
+ @transient private lazy val handleNullFromInputs: Seq[Any => Any] = children.map {
+ child => child.dataType match {
+ case ByteType =>
+ value: Any => if (value == null) Byte.MinValue else value
+ case ShortType =>
+ value: Any => if (value == null) Short.MinValue else value
+ case IntegerType =>
+ value: Any => if (value == null) Int.MinValue else value
+ case LongType =>
+ value: Any => if (value == null) Long.MinValue else value
+ case x =>
+ throw new IllegalArgumentException(
+ s"ZOrder expression should not take $x as the data type")
+ }
+ }
+
+ /**
+ * Get the bit in `ordinal` position (0-based) of input `value`.
+ * The return value of corresponding bit is in [[Byte]] type.
+ */
+ @transient private lazy val getBitFromInputs: Seq[(Any, Int) => Byte] = children.map { child =>
+ child.dataType match {
+ case ByteType =>
+ (value: Any, ordinal: Int) =>
+ ((value.asInstanceOf[Byte] >> ordinal) & 1).toByte
+ case ShortType =>
+ (value: Any, ordinal: Int) =>
+ ((value.asInstanceOf[Short] >> ordinal) & 1).toByte
+ case IntegerType =>
+ (value: Any, ordinal: Int) =>
+ ((value.asInstanceOf[Int] >> ordinal) & 1).toByte
+ case LongType =>
+ (value: Any, ordinal: Int) =>
+ ((value.asInstanceOf[Long] >> ordinal) & 1).toByte
+ case x =>
+ throw new IllegalArgumentException(
+ s"ZOrder expression should not take $x as the data type")
+ }
+ }
+
+ /**
+ * Get the Z-order sign bit of input `value`.
+ *
+ * For [[IntegralType]], Z-order flips the original sign bit of input. Sign bit is 0 for negative
+ * value, and 1 for positive value. This is to maintain the same ordering between input and
+ * output in [[BinaryType]].
+ */
+ @transient private lazy val getZOrderSignBitFromInputs: Seq[Any => Byte] = children.map {
+ child => child.dataType match {
+ case ByteType =>
+ value: Any => if (value.asInstanceOf[Byte] < 0) 0.toByte else 1.toByte
+ case ShortType =>
+ value: Any => if (value.asInstanceOf[Short] < 0) 0.toByte else 1.toByte
+ case IntegerType =>
+ value: Any => if (value.asInstanceOf[Int] < 0) 0.toByte else 1.toByte
+ case LongType =>
+ value: Any => if (value.asInstanceOf[Long] < 0) 0.toByte else 1.toByte
+ case x =>
+ throw new IllegalArgumentException(
+ s"ZOrder expression should not take $x as the data type")
+ }
+ }
+
+ /**
+ * Update the bit at `ordinal` position (0-based) in `outputBytes`, with new value `bitAsByte`.
+ */
+ private def updateBitInOutput(bitAsByte: Byte, ordinal: Int): Unit = {
+ val currentByteIndex = ordinal >> 3
+ val currentByte = outputBytes(currentByteIndex)
+ val newByte = (currentByte | (bitAsByte << ((ordinal & 7) ^ 7))).toByte
+ outputBytes.update(currentByteIndex, newByte)
+ }
+
+ /**
+ * Calculate Z-order from `input` and store the result in `outputBytes`.
+ *
+ * The function has the following steps:
+ * - Step 1: Handle null value from `input`.
+ * - Step 2: Initialize `outputBytes` with all zeros.
+ * - Step 3: Interleave sign bits from `input` and write to `outputBytes`.
+ * - Step 4: Interleave data bits from `input` and write to `outputBytes`.
+ * Start from most significant bit to least. Skip the corresponding
+ * input if it finishes early.
+ *
+ * Example (all value in binary representation for illustration purpose):
+ * input1: 01111010
+ * input2: 10011011 11100001
+ *
+ * output: 10101011 11001101 11100001
+ * ||\ /
+ * || ---------------------
+ * (Z-order sign bits) |
+ * (Z-order data bits)
+ *
+ * TODO(SPARK-37364): Support code-gen evaluation for Z-order.
+ */
+ override def eval(input: InternalRow): Any = {
+ val evaluatedInput = children.map(_.eval(input))
+
+ // Handle null value from `input`.
+ val inputValues = handleNullFromInputs.zip(evaluatedInput).map {
+ case (nullHandler, value) => nullHandler(value)
+ }
+ var outputBitIndex = 0
+
+ // Initialize `outputBytes` with all zeros.
+ outputBytes.indices.foreach(outputBytes.update(_, 0))
Review comment:
hmm I think creating a new byte[] every time may generate too many short-living Java object and causes more GC. I can change it to `Arrays.fill(outputBytes, 0.toByte)`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] [spark] c21 commented on a change in pull request #34640: [SPARK-31585][SQL] Introduce Z-order expression
Posted by GitBox <gi...@apache.org>.
c21 commented on a change in pull request #34640:
URL: https://github.com/apache/spark/pull/34640#discussion_r758700614
##########
File path: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/ZOrder.scala
##########
@@ -0,0 +1,222 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.sql.catalyst.expressions
+
+import org.apache.spark.sql.catalyst.InternalRow
+import org.apache.spark.sql.catalyst.expressions.codegen.CodegenFallback
+import org.apache.spark.sql.types.{AbstractDataType, BinaryType, ByteType, DataType, IntegerType, IntegralType, LongType, ShortType}
+
+/**
+ * An expression that calculates Z-order value (https://en.wikipedia.org/wiki/Z-order_curve)
+ * from `children` input data.
+ *
+ * At the high level, Z-order value is calculated by interleaving the binary representations of
+ * `children` input. So the Z-order value preserves locality of input data, while mapping the
+ * multi-dimensional input into one dimension output.
+ *
+ */
+@ExpressionDescription(
+ usage = """
+ _FUNC_(input1, input2, ...) - Returns Z-order value in binary type for inputs.
+ """,
+ examples = """
+ Examples:
+ > SELECT _FUNC_(1, 2);
+ [-64, 6]
+ """,
+ since = "3.3.0",
+ group = "misc_funcs")
+case class ZOrder(children: Seq[Expression])
+ extends Expression with ExpectsInputTypes with CodegenFallback {
+
+ override def nullable: Boolean = false
+
+ /**
+ * Supported input data types. Currently support [[IntegralType]].
+ *
+ * TODO(SPARK-37362): Support [[FractionalType]] for Z-order.
+ * TODO(SPARK-37363): Support [[StringType]] for Z-order.
+ */
+ override def inputTypes: Seq[AbstractDataType] = Seq.fill(children.size)(IntegralType)
+
+ override def dataType: DataType = BinaryType
+
+ override def prettyName: String = "zorder"
+
+ /**
+ * Number of bits per input in binary representation.
+ */
+ @transient private lazy val inputBitSizes = children.map(_.dataType.defaultSize * 8)
+
+ /**
+ * Maximal number of bits per input in binary representation.
+ */
+ @transient private lazy val inputBitMaxSize = inputBitSizes.max
+
+ /**
+ * Total number of bits per input in binary representation.
+ */
+ @transient private lazy val inputBitTotalSize = inputBitSizes.sum
+
+ /**
+ * The output for Z-order, represented in byte array format.
+ */
+ @transient private lazy val outputBytes = new Array[Byte](inputBitTotalSize / 8)
+
+ /**
+ * Handle input with null value. Convert null into minimal value per each data type.
Review comment:
I think mapping null to zeros is probably also fine. I am mapping to minimal value to mimic NULL first ordering here.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org