Stack overflow with lots of OR in a query

[wjones127]

Possible source:

lance/rust/lance-index/src/scalar/expression.rs

Line 654 in eb6f2c9

(Self::Or(l0, l1), Self::Or(r0, r1)) => l0 == r0 && l1 == r1,

Reproduction

import lance
import pyarrow as pa

ds = lance.write_dataset(pa.table({'id': [1, 2]}), "memory://")
# ds.create_scalar_index("id", "BTREE")

filter = ' OR '.join([f"id = {i}" for i in range(100)])

ds.to_table(filter=filter)

[BubbleCal]

i doubt it's caused by this comparison, no any line try to compare 2 expression except tests

[BubbleCal]

potential cause:

lance/rust/lance-index/src/scalar/expression.rs

Lines 1170 to 1184 in a371357

	fn visit_node(expr: &Expr, index_info: &dyn IndexInformationProvider) -> Option<IndexedExpression> {
	match expr {
	Expr::Between(between) => visit_between(between, index_info),
	Expr::Column(_) => visit_column(expr, index_info),
	Expr::InList(in_list) => visit_in_list(in_list, index_info),
	Expr::IsFalse(expr) => visit_is_bool(expr.as_ref(), index_info, false),
	Expr::IsTrue(expr) => visit_is_bool(expr.as_ref(), index_info, true),
	Expr::IsNull(expr) => visit_is_null(expr.as_ref(), index_info, false),
	Expr::IsNotNull(expr) => visit_is_null(expr.as_ref(), index_info, true),
	Expr::Not(expr) => visit_not(expr.as_ref(), index_info),
	Expr::BinaryExpr(binary_expr) => visit_binary_expr(binary_expr, index_info),
	Expr::ScalarFunction(scalar_fn) => visit_scalar_fn(scalar_fn, index_info),
	_ => None,
	}
	}

[Xuanwo]

Is it a good idea to we convert those OR into an IN list?

[BubbleCal]

Is it a good idea to we convert those OR into an IN list?

yeah it's a good idea, prob that will improve the query perf.
but AND would cause the same problem as well

[BubbleCal]

we may need to limit the filter length / depth, it's just hard to tell what the limitation number exactly is so that we won't get stack overflow.

so additionally, we may need to resolve this by implementing a non-recursive visit_node

[Xuanwo]

so additionally, we may need to resolve this by implementing a non-recursive visit_node

Yes, I've been thinking about this and have tried a bit, but it's quite complex and difficult to maintain 😢

[vortex-hue]

hi, please can I get assigned to this task, and I'd get to work on it as soon as possible.

[vortex-hue]

Hi @yanghua , my pr is available for review: [https://github.com//pull/4376](PR issue 4373)