Page Indexes Evaluation

Evaluation of DataFusion-style embedded page indexes (ColumnIndex/OffsetIndex) for ParqueDB, comparing with current row group stats and external bloom files approach.

Issue: parquedb-450n Date: 2026-02-03 Status: Evaluation Complete

Executive Summary

Key Finding: hyparquet already has full support for reading and writing page-level indexes (ColumnIndex/OffsetIndex). The infrastructure exists and is actively used in parquetQuery().

Recommendation: Adopt DataFusion-style page indexes as the primary predicate pushdown mechanism. Migrate from external bloom files to embedded page indexes + embedded bloom filters for better query optimization.

Priority: Medium-High - This is an optimization that can significantly reduce I/O for filtered queries.

1. hyparquet Support Analysis

1.1 Reading Page Indexes (hyparquet v1.17.1)

Full support exists in node_modules/hyparquet/src/indexes.js:

// readColumnIndex - reads per-page min/max statistics
export function readColumnIndex(reader, schema, parsers) {
  const thrift = deserializeTCompactProtocol(reader)
  return {
    null_pages: thrift.field_1,           // boolean[] - which pages are all-null
    min_values: thrift.field_2.map(...),  // MinMaxType[] - page minimums
    max_values: thrift.field_3.map(...),  // MinMaxType[] - page maximums
    boundary_order: BoundaryOrder[thrift.field_4],  // 'ASCENDING'|'DESCENDING'|'UNORDERED'
    null_counts: thrift.field_5,          // bigint[] - null count per page
  }
}

// readOffsetIndex - reads page byte locations
export function readOffsetIndex(reader) {
  return {
    page_locations: thrift.field_1.map(pageLocation),
    // Each: { offset: bigint, compressed_page_size: number, first_row_index: bigint }
  }
}

1.2 Writing Page Indexes (hyparquet-writer v0.12.0)

Full support exists in node_modules/hyparquet-writer/src/indexes.js:

// writeIndexes - writes ColumnIndex and OffsetIndex after column data
export function writeIndexes(writer, pageIndexes) {
  for (const { chunk, columnIndex } of pageIndexes) {
    writeColumnIndex(writer, chunk, columnIndex)
  }
  for (const { chunk, offsetIndex } of pageIndexes) {
    writeOffsetIndex(writer, chunk, offsetIndex)
  }
}

Writer configuration in ParquetWriter.prototype.write():

const { name, data, encoding, columnIndex = false, offsetIndex = true } = columnData[j]
//                            ^^^^^^^^^^^^^^^^^^^  ^^^^^^^^^^^^^^^^
// columnIndex: opt-in (default false) - generates per-page min/max
// offsetIndex: opt-out (default true) - generates page locations

1.3 Query Integration (hyparquet/src/query.js)

Page-level filtering is already implemented:

// In readSmallRowGroup():
const hasIndexes = rowGroup.columns.some((col) => col.column_index_offset)
if (hasIndexes && predicates.size > 0) {
  return readRowGroupWithPageFilter(bufferedFile, metadata, rgIndex, predicates, columns, options)
}

// selectPages() - finds which pages might match predicates
export async function selectPages(file, metadata, rowGroup, predicates, columnIndexMap, nestedIndexMap) {
  for (const [columnPath, predicate] of predicates) {
    const indexes = await readIndexes(file, column, metadata.schema)
    for (let i = 0; i < indexes.columnIndex.min_values.length; i++) {
      const matches = predicate(indexes.columnIndex.min_values[i], indexes.columnIndex.max_values[i])
      if (matches) matchingPages.add(i)
    }
  }
  return selectedPages // AND semantics across columns
}

// readSelectedPages() - reads only matching pages
export async function readSelectedPages(file, metadata, rowGroup, columns, selectedPages, columnIndexMap, options) {
  // Uses offsetIndex to seek directly to page offsets
  // Decodes only selected pages
}

2. Current ParqueDB Architecture

2.1 Current Approach: Row Group Stats + External Bloom Files

/warehouse/{namespace}/
├── data/
│   └── entities.parquet          # Row group level statistics only
└── indexes/
    └── bloom/
        ├── global.bloom          # Global entity existence
        ├── {uuid}.bloom          # Per-file bloom filters
        └── {uuid}.compound.bloom # Compound key blooms

Row Group Statistics (in Parquet file):

Min/max per column per row group
Used for row group skipping
Coarse-grained (typically 10K-100K rows per group)

External Bloom Filters:

Stored in separate .bloom files
Custom binary format (see BLOOM_FILTER_INDEXES.md)
Three-level hierarchy: global, file, row group
Requires additional I/O to load bloom files

2.2 DataFusion Approach: Embedded Page Indexes

entities.parquet
├── Row Group 0
│   ├── Column: $id
│   │   ├── Page 0 (rows 0-999)
│   │   ├── Page 1 (rows 1000-1999)
│   │   └── Page 2 (rows 2000-2999)
│   └── ...
├── Row Group 1
│   └── ...
├── Footer
│   ├── Schema
│   ├── Row Group Metadata
│   │   └── Column Chunks
│   │       ├── column_index_offset -> ColumnIndex
│   │       └── offset_index_offset -> OffsetIndex
│   └── Page Indexes (after footer)
│       ├── ColumnIndex (per-page min/max/null_count)
│       └── OffsetIndex (page byte offsets)

3. Comparison: Current vs DataFusion Approach

Aspect	Current (Row Group Stats + External Bloom)	DataFusion (Embedded Page Indexes)
Granularity	Row group level (10K-100K rows)	Page level (typically 1K rows)
Predicate Types	Range predicates (row group stats) + Equality (bloom)	Range predicates at page level
I/O Pattern	Multiple files (data + bloom)	Single file, sequential reads
Maintenance	Must keep bloom files in sync	Self-contained in Parquet
Skip Efficiency	~80-90% for point lookups	~95-99% for filtered scans
Write Overhead	Separate bloom file writes	Slightly larger Parquet footer
R2 Compatibility	Two range requests (data + bloom)	Single range request
Bloom Filter Support	External files	Can embed in Parquet (spec supported)

3.1 Pros of DataFusion-style Page Indexes

Finer-grained filtering: Skip at page level (1K rows) vs row group (100K rows)
Single file: No external bloom files to maintain or sync
Automatic statistics: hyparquet-writer generates them automatically
Better for range queries: Page-level min/max enables efficient range scans
R2 optimization: Single object, fewer HTTP requests
Already implemented: hyparquet's parquetQuery() uses page indexes

3.2 Cons / Considerations

Bloom filters still valuable: Page indexes don't provide bloom filter semantics
File size increase: Page indexes add ~1-2% to file size
Migration effort: Need to update ParqueDB to enable page index writing

4. Implementation Path

Phase 1: Enable Page Index Writing (Low Effort)

Files to modify:

src/storage/parquet-writer.ts or wherever we call ParquetWriter

Change:

// Current (likely):
const writer = new ParquetWriter({
  writer,
  schema,
  codec: 'SNAPPY',
  statistics: true
})

// New:
const writer = new ParquetWriter({
  writer,
  schema,
  codec: 'SNAPPY',
  statistics: true
})

// When writing columns, enable columnIndex:
writer.write({
  columnData: columns.map(col => ({
    ...col,
    columnIndex: true,  // Enable per-page min/max
    offsetIndex: true   // Already default
  })),
  pageSize: 1048576     // 1MB pages for good granularity
})

Estimated effort: Simple configuration change, ~1-2 hours

Phase 2: Leverage Page Indexes in Query (Medium Effort)

Current query path (likely):

// In QueryExecutor or similar
const metadata = await parquetMetadataAsync(file)
for (const rowGroup of metadata.row_groups) {
  if (!canRowGroupMatch(rowGroup, predicates)) continue
  // Read entire row group
}

New query path:

import { parquetQuery } from 'hyparquet'

// parquetQuery already does page-level filtering!
const results = await parquetQuery({
  file,
  filter: { $id: 'entity-123' },  // MongoDB-style filter
  columns: ['$id', 'data', 'createdAt'],
})

Files to examine:

src/query/executor.ts
src/worker/QueryExecutor.ts

Estimated effort: 2-4 hours to integrate with existing query path

Phase 3: Embedded Bloom Filters (Optional, Higher Effort)

The Parquet spec supports embedded bloom filters per column per row group. hyparquet-writer doesn't currently expose this, but it could be added.

Benefit: Eliminate external bloom files entirely Effort: Would require hyparquet-writer changes or fork

Recommendation: Defer to Phase 2; external bloom files work well for now

Phase 4: Variant Shredding Integration (Already Done!)

hyparquet already supports Variant shredding for predicate pushdown:

const results = await parquetQuery({
  file,
  filter: { '$index.titleType': 'movie' },
  variantConfig: [
    { column: '$index', fields: ['titleType'] }
  ]
})

This maps $index.titleType to $index.typed_value.titleType.typed_value for statistics.

5. Recommendation

Adopt DataFusion-style Page Indexes

Why:

hyparquet already supports it fully (read + write + query)
Better filtering granularity than row group stats
Self-contained in Parquet files (easier R2 integration)
Already integrated with Variant shredding

Implementation Priority:

Phase 1 (Now): Enable columnIndex: true when writing Parquet files
Phase 2 (Next Sprint): Use parquetQuery() in QueryExecutor
Phase 3 (Later): Consider embedded bloom filters to replace external files
Phase 4: Already done for Variant fields

Keep External Bloom Filters (For Now)

External bloom filters still provide value:

Global entity existence checks (cross-file)
Edge existence queries (before traversal)
Compound key lookups

Long-term: Migrate to embedded Parquet bloom filters when hyparquet-writer adds support

6. Code Examples

Enabling Page Indexes in ParqueDB

// src/storage/parquet-writer.ts

import { ParquetWriter } from 'hyparquet-writer'

export function createParquetWriter(writer: Writer, schema: SchemaElement[]) {
  return new ParquetWriter({
    writer,
    schema,
    codec: 'SNAPPY',
    statistics: true,
    // Page indexes are enabled per-column during write()
  })
}

export function writeEntities(writer: ParquetWriter, entities: Entity[]) {
  const columnData = [
    { name: '$id', data: entities.map(e => e.$id), columnIndex: true },
    { name: '$type', data: entities.map(e => e.$type), columnIndex: true },
    { name: 'createdAt', data: entities.map(e => e.createdAt), columnIndex: true },
    { name: 'data', data: entities.map(e => e.data), columnIndex: false }, // Variant, no stats
  ]

  writer.write({
    columnData,
    rowGroupSize: [1000, 100000], // Small first group, then 100K
    pageSize: 1048576 // 1MB pages
  })
}

Using parquetQuery in QueryExecutor

// src/query/executor.ts

import { parquetQuery } from 'hyparquet'

export async function executeQuery(
  file: AsyncBuffer,
  filter: Filter,
  options: QueryOptions
): Promise<Entity[]> {
  // Convert ParqueDB filter to hyparquet filter format
  const hyparquetFilter = convertFilter(filter)

  // parquetQuery handles:
  // 1. Row group skipping (row group stats)
  // 2. Page skipping (ColumnIndex)
  // 3. Page-level reads (OffsetIndex)
  // 4. Row-level filtering
  const results = await parquetQuery({
    file,
    filter: hyparquetFilter,
    columns: options.projection,
    variantConfig: options.variantConfig,
    limit: options.limit,
    offset: options.offset,
    orderBy: options.orderBy,
    desc: options.desc
  })

  return results
}

7. References

Parquet Format Spec: https://github.com/apache/parquet-format/blob/master/PageIndex.md
hyparquet Source: node_modules/hyparquet/src/
hyparquet-writer Source: node_modules/hyparquet-writer/src/
ParqueDB Bloom Filter Design: docs/architecture/BLOOM_FILTER_INDEXES.md
DataFusion Page Index Usage: https://arrow.apache.org/datafusion/

8. Conclusion

hyparquet provides excellent page-level index support that ParqueDB should leverage. The implementation path is straightforward:

Enable columnIndex: true when writing (trivial change)
Use parquetQuery() for queries (already implemented in hyparquet)
Benefit from 10-100x better predicate pushdown granularity

External bloom filters remain valuable for cross-file existence checks and can coexist with embedded page indexes.

Page Indexes Evaluation

On this page