perf: simplify redundant same-column IN conjunctions before Bitmap index queries

The reproduction is in repro_core.py and fixture.py; run repro_core.py and compare the PLAN output for the full_after_narrow and narrow_warm cases. The issue asks for the planner to drop a redundant same-column IN before Bitmap index execution, while keeping SQL three-valued logic correct and leaving OR/NOT regions alone. The author is asking maintainers to settle scope and approach before any patch, so confirm that first. Done means the redundant plan matches the narrow plan's index work and the results still match with indexes off.

We would like to take ownership

Our team is very happy to take ownership of this issue and contribute the implementation, regression tests, and validation. We would appreciate maintainer feedback on scope and the preferred approach before starting a non-trivial change. If this needs a design discussion first, we are happy to follow that process.

Type

Predicate simplification / scalar-index performance optimization. No result correctness failure observed.

Environment

Reproduced independently with official pylance==12.0.0 and pylance==13.0.0. Also reproduced in official lance-spark 0.8.0 / Spark 3.5.8 task metrics. No custom JNI.

Fixture: 58 fragments, one per month 202201–202610, 2,048 rows each. clip_id BTree and month Bitmap each cover 100% of fragments. Three target rows are in 202608; NULL clip IDs and zero-hit queries are included.

Reproduction

The runnable synthetic files below generate all literals, indexes, native plans and scan statistics. Scan one fixed fragment using the same Dataset/Session:

1. Execute and repeat clip equality + three-month IN to prewarm the required index parts.
2. Add a redundant 58-month IN on the same column, whose set is a superset of those three months.
3. Repeat the redundant query after all parts are cached.
4. Verify identical results with indexes disabled.

Equivalent WHERE expressions:

clip_id = 'synthetic-target'
AND month IN ('202607', '202608', '202609')

clip_id IS NOT NULL
AND month IN ('202201', '202202', '202203', '202204', '202205', '202206', '202207', '202208', '202209', '202210', '202211', '202212', '202301', '202302', '202303', '202304', '202305', '202306', '202307', '202308', '202309', '202310', '202311', '202312', '202401', '202402', '202403', '202404', '202405', '202406', '202407', '202408', '202409', '202410', '202411', '202412', '202501', '202502', '202503', '202504', '202505', '202506', '202507', '202508', '202509', '202510', '202511', '202512', '202601', '202602', '202603', '202604', '202605', '202606', '202607', '202608', '202609', '202610')
AND clip_id = 'synthetic-target'
AND month IN ('202607', '202608', '202609')

Actual native plan

The narrow plan has one BTree query and one three-value Bitmap query. The redundant plan still contains both the 58-value Bitmap query and the three-value Bitmap query under AND. The reproduction below prints the complete native EXPLAIN strings and scalar-index statistics.

Actual statistics on both official versions

Metric	Narrow warm	Redundant after narrow	Redundant hot
index_comparisons	4099	4157	4157
index_cache_hits	4	7	62
index_cache_misses	0	55	0
parts_loaded	0	55	0

The extra 58 comparisons and 55 cold parts correspond to the redundant wide membership set. This also occurs when the clip equality yields zero matches. Positive-hit outputs are identical (three rows); negative-hit outputs are empty with or without indexes.

Spark independently records an extra 58 comparisons per task for the redundant filter, both with ordinary indexes only and with additional ZoneMap task pruning.

Related work

Related Spark candidate-fragment planning request: https://github.com/lance-format/lance-spark/issues/882. It is separate from this Core predicate-simplification issue.

#5418 discusses coalescing many Bitmap/BTree part loads. This report is complementary: the wide part loads in this example are semantically unnecessary and could be avoided by simplifying the predicate before index execution, rather than only making those loads cheaper.

Expected / proposal

Where SQL three-valued logic permits it, intersect same-column IN sets within one AND region, or eliminate a membership superset that is redundant with a narrower membership predicate. In this example only the three-month query is needed. Do not apply the rewrite across OR/NOT boundaries or incompatible expressions.

Limits

This small fixture reproduces unnecessary index work, not a large latency regression. Millisecond timings are noisy and are not asserted. We have not established which individual native function dominates cold-part processing at large scale.

Six local validation tests check rows, plans/task counts and native counters. No production data or internal identifiers are included.

Runnable synthetic reproduction

Save these two files in an otherwise empty directory. No external dataset is needed; all data is generated locally, and the script creates its own temporary fixture directory.

python -m pip install pylance==13.0.0 pyarrow==26.0.0
python repro_core.py
# The same script also reproduces with pylance==12.0.0.

fixture.py

"""Synthetic, fully indexed fixture; no external data or services."""
from pathlib import Path
import tempfile

import lance
import pyarrow as pa

MONTHS = [f'{year}{month:02d}' for year in range(2022, 2027)
          for month in range(1, 13) if f'{year}{month:02d}' <= '202610']
ROWS_PER_MONTH = 2048
NARROW_IN = "month IN ('202607','202608','202609')"
WIDE_IN = 'month IN (' + ','.join(repr(month) for month in MONTHS) + ')'


def make_fixture():
    batches = []
    for month in MONTHS:
        clips = [f'synthetic-{month}-{i}' for i in range(ROWS_PER_MONTH)]
        clips[0] = None
        if month == '202608':
            clips[1:4] = ['synthetic-target'] * 3
        batches.append(pa.table({'clip_id': pa.array(clips, type=pa.string()),
                                 'month': [month] * ROWS_PER_MONTH,
                                 'row_key': list(range(ROWS_PER_MONTH))}))
    uri = Path(tempfile.mkdtemp(prefix='lance-public-repro-')) / 'fixture.lance'
    ds = lance.write_dataset(pa.concat_tables(batches), uri,
                             max_rows_per_file=ROWS_PER_MONTH,
                             max_rows_per_group=ROWS_PER_MONTH,
                             data_storage_version='2.1')
    ds.create_scalar_index('clip_id', 'BTREE', name='clip_id_idx')
    ds.create_scalar_index('month', 'BITMAP', name='month_idx')
    ds = lance.dataset(uri)
    assert len(ds.get_fragments()) == 58
    for name in ['clip_id_idx', 'month_idx']:
        stats = ds.index_statistics(name)
        assert stats['num_indexed_fragments'] == 58
        assert stats['num_unindexed_fragments'] == 0
    return uri, ds.version

repro_core.py

"""Run with official pylance 12.0.0 or 13.0.0."""
import json
import time

import lance
from fixture import MONTHS, NARROW_IN, WIDE_IN, make_fixture

uri, version = make_fixture()
print('Lance version:', lance.__version__)
for mode, clip, expected in [('hit', 'synthetic-target', 3),
                             ('miss', 'synthetic-does-not-exist', 0)]:
    ds = lance.dataset(uri, version=version)
    fragment = ds.get_fragments()[MONTHS.index('202608')]
    equality = f'clip_id = {clip!r}'
    narrow = f'({equality}) AND ({NARROW_IN})'
    full = f'(clip_id IS NOT NULL) AND ({WIDE_IN}) AND ({equality}) AND ({NARROW_IN})'
    baseline = None
    for label, condition, use_index in [
        ('clip_only', equality, True),
        ('narrow_cold', narrow, True),
        ('narrow_warm', narrow, True),
        ('full_after_narrow', full, True),
        ('full_hot', full, True),
        ('narrow_after_full', narrow, True),
        ('full_index_off', full, False),
    ]:
        statistics = []
        scan = ds.scanner(columns=['clip_id', 'month', 'row_key'],
                          filter=condition, fragments=[fragment], batch_size=8192,
                          use_scalar_index=use_index,
                          scan_stats_callback=statistics.append)
        print('PLAN', mode, label, scan.explain_plan(verbose=True))
        start = time.perf_counter()
        table = scan.to_table()
        elapsed_ms = 1000 * (time.perf_counter() - start)
        assert len(table) == expected
        keys = table['row_key'].to_pylist()
        if baseline is None:
            baseline = keys
        assert keys == baseline
        stats = statistics[-1]
        print(json.dumps({'case': f'{mode}_{label}', 'rows': len(table),
                          'elapsed_ms': elapsed_ms,
                          'index_comparisons': stats.index_comparisons,
                          'index_cache_hits': stats.index_cache_hits,
                          'index_cache_misses': stats.index_cache_misses,
                          'parts_loaded': stats.parts_loaded}))