Skip to content

Commit 2ebe999

Browse files
authored
Expose list membership with SQL null semantics in Java and Python (#10053)
Expose the membership expressions from Java/JNI and Python, so callers can construct one set-membership expression with either Vortex or SQL null semantics. --------- Signed-off-by: Robert Kruszewski <[email protected]>
1 parent 9be4ef1 commit 2ebe999

16 files changed

Lines changed: 693 additions & 59 deletions

File tree

‎docs/api/python/expr.rst‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -52,6 +52,7 @@ Expressions are picklable, so a filter built in one process can be sent to anoth
5252
~vortex.expr.pack
5353
~vortex.expr.merge
5454
~vortex.expr.list_contains
55+
~vortex.expr.in_list
5556
~vortex.expr.list_length
5657
~vortex.expr.list_sum
5758
~vortex.expr.case_when
@@ -153,6 +154,8 @@ Lists
153154

154155
.. autofunction:: vortex.expr.list_contains
155156

157+
.. autofunction:: vortex.expr.in_list
158+
156159
.. autofunction:: vortex.expr.list_length
157160

158161
.. autofunction:: vortex.expr.list_sum

‎java/vortex-jni/src/main/java/dev/vortex/api/Expression.java‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -168,6 +168,54 @@ public static Expression between(
168168
value.nativePointer(), lower.nativePointer(), upper.nativePointer(), lowerStrict, upperStrict));
169169
}
170170

171+
/**
172+
* Whether the list {@code list} evaluates to contains {@code needle}, with Vortex's null rules: a null element
173+
* never matches anything, so a needle that matches no element is {@code false}. A null {@code needle} is null,
174+
* except against an empty list, where the result is {@code false}.
175+
*
176+
* <p>{@code list} must evaluate to a Vortex list whose element type matches {@code needle}'s type, ignoring
177+
* nullability. With a {@link #literalList(Expression, boolean, Expression...) list literal} on the left and a
178+
* column on the right this is a set-membership test that a constant-set kernel answers in one pass over the column,
179+
* however large the set.
180+
*
181+
* @see #listContains(Expression, Expression, boolean)
182+
* @see #in(Expression, Expression)
183+
*/
184+
public static Expression listContains(Expression list, Expression needle) {
185+
return listContains(list, needle, /* sqlNullSemantics= */ false);
186+
}
187+
188+
/**
189+
* {@link #listContains(Expression, Expression)} with a choice of null rules.
190+
*
191+
* @param sqlNullSemantics {@code false} for Vortex's rules, where a null element never matches; {@code true} for
192+
* SQL's three-valued {@code IN}, where a null element is an unknown value, so a needle that matches no element
193+
* is {@code null} rather than {@code false} whenever the list holds a null. A null needle is null, except
194+
* against an empty list with Vortex's default rules, where the result is {@code false}.
195+
*/
196+
public static Expression listContains(Expression list, Expression needle, boolean sqlNullSemantics) {
197+
return new Expression(
198+
NativeExpression.listContains(list.nativePointer(), needle.nativePointer(), sqlNullSemantics));
199+
}
200+
201+
/**
202+
* SQL {@code value IN (list)}: {@link #listContains(Expression, Expression, boolean)} with SQL null semantics and
203+
* the operands in SQL order. A null {@code value} is null, and so is a non-match against a list that holds a null;
204+
* both filter the row out of a scan.
205+
*/
206+
public static Expression in(Expression value, Expression list) {
207+
return listContains(list, value, /* sqlNullSemantics= */ true);
208+
}
209+
210+
/**
211+
* SQL {@code value NOT IN (list)}: the negation of {@link #in(Expression, Expression)}. Under SQL's rules a null
212+
* {@code value}, or a list that holds a null, makes a non-match null rather than true, so such a row is never
213+
* admitted.
214+
*/
215+
public static Expression notIn(Expression value, Expression list) {
216+
return not(in(value, list));
217+
}
218+
171219
public static Expression literal(boolean value) {
172220
return new Expression(NativeExpression.literalBool(value, false));
173221
}

‎java/vortex-jni/src/main/java/dev/vortex/jni/NativeExpression.java‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -42,6 +42,8 @@ private NativeExpression() {}
4242
public static native long between(
4343
long valuePointer, long lowerPointer, long upperPointer, boolean lowerStrict, boolean upperStrict);
4444

45+
public static native long listContains(long listPointer, long needlePointer, boolean sqlNullSemantics);
46+
4547
public static native long literalBool(boolean value, boolean isNull);
4648

4749
public static native long literalI8(byte value, boolean isNull);

‎java/vortex-jni/src/test/java/dev/vortex/api/ExpressionTest.java‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -47,6 +47,15 @@ public void packComposes() {
4747
true));
4848
}
4949

50+
@Test
51+
public void literalListComposesWithListContains() {
52+
Expression set = Expression.literalList(
53+
Expression.nullLiteral(Expression.DType.I64), false, Expression.literal(1L), Expression.literal(2L));
54+
assertNotNull(Expression.listContains(set, Expression.column("id")));
55+
assertNotNull(Expression.in(Expression.column("id"), set));
56+
assertNotNull(Expression.notIn(Expression.column("id"), set));
57+
}
58+
5059
@Test
5160
public void mergeComposes() {
5261
// Default duplicate handling (ERROR).
Lines changed: 223 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,223 @@
1+
// SPDX-License-Identifier: Apache-2.0
2+
// SPDX-FileCopyrightText: Copyright the Vortex contributors
3+
4+
package dev.vortex.api;
5+
6+
import static java.nio.charset.StandardCharsets.UTF_8;
7+
import static org.junit.jupiter.api.Assertions.assertEquals;
8+
import static org.junit.jupiter.api.Assertions.assertTrue;
9+
10+
import dev.vortex.arrow.ArrowAllocation;
11+
import dev.vortex.jni.NativeLoader;
12+
import java.io.IOException;
13+
import java.nio.file.Path;
14+
import java.util.ArrayList;
15+
import java.util.List;
16+
import org.apache.arrow.c.ArrowArray;
17+
import org.apache.arrow.c.ArrowSchema;
18+
import org.apache.arrow.c.Data;
19+
import org.apache.arrow.memory.BufferAllocator;
20+
import org.apache.arrow.vector.IntVector;
21+
import org.apache.arrow.vector.VarCharVector;
22+
import org.apache.arrow.vector.VectorSchemaRoot;
23+
import org.apache.arrow.vector.ipc.ArrowReader;
24+
import org.apache.arrow.vector.types.pojo.ArrowType;
25+
import org.apache.arrow.vector.types.pojo.Field;
26+
import org.apache.arrow.vector.types.pojo.Schema;
27+
import org.junit.jupiter.api.BeforeAll;
28+
import org.junit.jupiter.api.Test;
29+
import org.junit.jupiter.api.io.TempDir;
30+
31+
/**
32+
* End-to-end coverage for {@link Expression#listContains(Expression, Expression)} as a scan filter.
33+
*
34+
* <p>Constructing a list-contains expression proves nothing on its own: the element type is only checked when the
35+
* expression is bound to a schema, so a list literal built from the wrong element type builds fine and fails later,
36+
* inside a scan. These tests therefore write a small file and read it back through the filter, asserting on the rows
37+
* that survive.
38+
*
39+
* <p>The {@code maybe} column is nullable and null on every odd id, and the sets below hold a null element, to pin the
40+
* two null rules apart: under SQL's, which {@link Expression#in} and {@link Expression#notIn} use, a null element makes
41+
* every non-match null, so {@code NOT IN} keeps nothing; under Vortex's it is simply never a match.
42+
*
43+
* <p>The large-set case is the reason the binding exists. A caller without it has to expand {@code IN} into a chain of
44+
* equality comparisons, which is why callers cap the set size and fall back to a bounding range; a single
45+
* {@code list_contains} node carries the whole set, and the stats rewrite falsifies it for a zone only when every
46+
* element misses that zone's bounds.
47+
*/
48+
public final class ListContainsFilterTest {
49+
private static final int ROW_COUNT = 6;
50+
51+
@TempDir
52+
static Path tempDir;
53+
54+
private static Session session;
55+
private static String filePath;
56+
57+
@BeforeAll
58+
public static void loadLibrary() {
59+
NativeLoader.loadJni();
60+
}
61+
62+
@BeforeAll
63+
static void writeFile() throws IOException {
64+
session = Session.create();
65+
filePath =
66+
tempDir.resolve("list_contains.vortex").toAbsolutePath().toUri().toString();
67+
68+
BufferAllocator allocator = ArrowAllocation.rootAllocator();
69+
Schema schema = new Schema(List.of(
70+
Field.notNullable("id", new ArrowType.Int(32, true)),
71+
Field.notNullable("name", new ArrowType.Utf8()),
72+
Field.nullable("maybe", new ArrowType.Int(32, true))));
73+
74+
try (VortexWriter writer = VortexWriter.builder(session, filePath, schema, allocator)
75+
.build();
76+
VectorSchemaRoot root = VectorSchemaRoot.create(schema, allocator)) {
77+
IntVector id = (IntVector) root.getVector("id");
78+
VarCharVector name = (VarCharVector) root.getVector("name");
79+
IntVector maybe = (IntVector) root.getVector("maybe");
80+
id.allocateNew(ROW_COUNT);
81+
name.allocateNew(ROW_COUNT);
82+
maybe.allocateNew(ROW_COUNT);
83+
for (int i = 0; i < ROW_COUNT; i++) {
84+
id.setSafe(i, i + 1);
85+
name.setSafe(i, ("row-" + (i + 1)).getBytes(UTF_8));
86+
// Every other row is null; the rest carry their id.
87+
if (i % 2 == 0) {
88+
maybe.setNull(i);
89+
} else {
90+
maybe.setSafe(i, i + 1);
91+
}
92+
}
93+
root.setRowCount(ROW_COUNT);
94+
95+
try (ArrowArray array = ArrowArray.allocateNew(allocator);
96+
ArrowSchema arrowSchema = ArrowSchema.allocateNew(allocator)) {
97+
Data.exportVectorSchemaRoot(allocator, root, null, array, arrowSchema);
98+
writer.writeBatch(array.memoryAddress(), arrowSchema.memoryAddress());
99+
}
100+
writer.finish();
101+
}
102+
}
103+
104+
@Test
105+
public void inKeepsOnlyTheMatchingRows() {
106+
Expression set = Expression.literalList(
107+
i32(), false, Expression.literal(2), Expression.literal(4), Expression.literal(99));
108+
assertEquals(List.of(2, 4), scanIds(Expression.in(Expression.column("id"), set)));
109+
}
110+
111+
@Test
112+
public void notInKeepsTheComplement() {
113+
Expression set = Expression.literalList(
114+
i32(), false, Expression.literal(2), Expression.literal(4), Expression.literal(99));
115+
assertEquals(List.of(1, 3, 5, 6), scanIds(Expression.notIn(Expression.column("id"), set)));
116+
}
117+
118+
@Test
119+
public void listContainsTakesTheListFirst() {
120+
// in(value, list) is listContains(list, value) with the operands the other way round; both spellings have to
121+
// agree, and passing the column as the list would be a type error rather than a silently different filter.
122+
Expression set = Expression.literalList(i32(), false, Expression.literal(3));
123+
assertEquals(List.of(3), scanIds(Expression.listContains(set, Expression.column("id"))));
124+
}
125+
126+
@Test
127+
public void inWithANullElementKeepsOnlyMatches() {
128+
// maybe = [null, 2, null, 4, null, 6]; the set holds 2 and a null.
129+
Expression set = Expression.literalList(
130+
i32(), true, Expression.literal(2), Expression.nullLiteral(Expression.DType.I32));
131+
assertEquals(List.of(2), scanIds(Expression.in(Expression.column("maybe"), set)));
132+
}
133+
134+
@Test
135+
public void notInWithANullElementKeepsNothing() {
136+
// SQL: x NOT IN (2, NULL) is false for 2 and null for everything else, so no row survives.
137+
Expression set = Expression.literalList(
138+
i32(), true, Expression.literal(2), Expression.nullLiteral(Expression.DType.I32));
139+
assertEquals(List.of(), scanIds(Expression.notIn(Expression.column("maybe"), set)));
140+
// Without the null element NOT IN keeps the non-null non-matches.
141+
assertEquals(
142+
List.of(4, 6),
143+
scanIds(Expression.notIn(
144+
Expression.column("maybe"), Expression.literalList(i32(), false, Expression.literal(2)))));
145+
}
146+
147+
@Test
148+
public void vortexNullRulesTreatANullElementAsNoMatch() {
149+
// listContains without SQL semantics: the null element never matches, so a non-match stays false and its
150+
// negation keeps the non-null non-matches.
151+
Expression set = Expression.literalList(
152+
i32(), true, Expression.literal(2), Expression.nullLiteral(Expression.DType.I32));
153+
assertEquals(List.of(2), scanIds(Expression.listContains(set, Expression.column("maybe"))));
154+
assertEquals(List.of(4, 6), scanIds(Expression.not(Expression.listContains(set, Expression.column("maybe")))));
155+
}
156+
157+
@Test
158+
public void aStringSetFiltersOnUtf8() {
159+
Expression set =
160+
Expression.literalList(utf8(), false, Expression.literal("row-1"), Expression.literal("row-6"));
161+
assertEquals(List.of(1, 6), scanIds(Expression.in(Expression.column("name"), set)));
162+
}
163+
164+
@Test
165+
public void aSetLargerThanAnyOrChainCapStillPushesDown() {
166+
// The whole point of the binding: 1000 literals stay one expression node. Only 5 is present in the file.
167+
Expression[] elements = new Expression[1000];
168+
for (int i = 0; i < elements.length; i++) {
169+
elements[i] = Expression.literal(i == 0 ? 5 : ROW_COUNT + i);
170+
}
171+
assertEquals(
172+
List.of(5),
173+
scanIds(Expression.in(Expression.column("id"), Expression.literalList(i32(), false, elements))));
174+
}
175+
176+
@Test
177+
public void anEmptySetMatchesNothing() {
178+
Expression empty = Expression.literalList(i32(), true);
179+
assertTrue(scanIds(Expression.in(Expression.column("id"), empty)).isEmpty());
180+
}
181+
182+
@Test
183+
public void aNullSetMatchesNothing() {
184+
// A null list yields null rather than false, which filters the row out just the same.
185+
Expression nullList = Expression.nullLiteralList(i32(), true);
186+
assertTrue(scanIds(Expression.in(Expression.column("id"), nullList)).isEmpty());
187+
}
188+
189+
/** The element type prototype of an {@code i32} set. */
190+
private static Expression i32() {
191+
return Expression.nullLiteral(Expression.DType.I32);
192+
}
193+
194+
/** The element type prototype of a UTF-8 set. */
195+
private static Expression utf8() {
196+
return Expression.nullLiteral(Expression.DType.UTF8);
197+
}
198+
199+
/** Reads the {@code id} column of every row that survives {@code filter}, in file order. */
200+
private static List<Integer> scanIds(Expression filter) {
201+
BufferAllocator allocator = ArrowAllocation.rootAllocator();
202+
DataSource dataSource = DataSource.open(session, filePath);
203+
Scan scan = dataSource.scan(
204+
ScanOptions.builder().filter(filter).ordered(true).build());
205+
206+
List<Integer> ids = new ArrayList<>();
207+
while (scan.hasNext()) {
208+
Partition partition = scan.next();
209+
try (ArrowReader reader = partition.scanArrow(allocator)) {
210+
while (reader.loadNextBatch()) {
211+
VectorSchemaRoot root = reader.getVectorSchemaRoot();
212+
IntVector id = (IntVector) root.getVector("id");
213+
for (int i = 0; i < root.getRowCount(); i++) {
214+
ids.add(id.get(i));
215+
}
216+
}
217+
} catch (IOException e) {
218+
throw new AssertionError("failed reading partition", e);
219+
}
220+
}
221+
return ids;
222+
}
223+
}

‎vortex-jni/src/expression.rs‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -44,6 +44,7 @@ use vortex::expr::between;
4444
use vortex::expr::get_item;
4545
use vortex::expr::is_not_null;
4646
use vortex::expr::is_null;
47+
use vortex::expr::list_contains_opts;
4748
use vortex::expr::lit;
4849
use vortex::expr::merge_opts;
4950
use vortex::expr::not;
@@ -66,6 +67,7 @@ use vortex::scalar_fn::fns::between::StrictComparison;
6667
use vortex::scalar_fn::fns::binary::Binary;
6768
use vortex::scalar_fn::fns::like::Like;
6869
use vortex::scalar_fn::fns::like::LikeOptions;
70+
use vortex::scalar_fn::fns::list_contains::ListContainsOptions;
6971
use vortex::scalar_fn::fns::literal::Literal;
7072
use vortex::scalar_fn::fns::merge::DuplicateHandling;
7173
use vortex::scalar_fn::fns::operators::Operator;
@@ -410,6 +412,33 @@ fn strict_from_bool(value: jboolean) -> StrictComparison {
410412
}
411413
}
412414

415+
/// Build `list_contains(list, needle)`: whether the list-typed `list` expression contains
416+
/// `needle`.
417+
///
418+
/// `list` must evaluate to a Vortex `List`; the list's element dtype must match `needle`'s dtype
419+
/// ignoring nullability. With a list literal on the left and a column on the right this is a
420+
/// set-membership (`IN`) test that a constant-set kernel answers in one pass over the column.
421+
///
422+
/// `sql_null_semantics` selects how a null list element behaves: off, it never matches and a
423+
/// non-matching needle is `false`; on, it is SQL's unknown value and a non-matching needle is
424+
/// `null`, so `NOT IN` never admits it.
425+
#[unsafe(no_mangle)]
426+
pub extern "system" fn Java_dev_vortex_jni_NativeExpression_listContains(
427+
_env: EnvUnowned,
428+
_class: JClass,
429+
list: jlong,
430+
needle: jlong,
431+
sql_null_semantics: jboolean,
432+
) -> jlong {
433+
let list = unsafe { expr_ref(list) }.clone();
434+
let needle = unsafe { expr_ref(needle) }.clone();
435+
into_raw(list_contains_opts(
436+
list,
437+
needle,
438+
ListContainsOptions { sql_null_semantics },
439+
))
440+
}
441+
413442
#[unsafe(no_mangle)]
414443
pub extern "system" fn Java_dev_vortex_jni_NativeExpression_literalBool(
415444
_env: EnvUnowned,

0 commit comments

Comments
 (0)