# Large Table Parsing Strategy

## Overview

A comprehensive solution for parsing very large Excel tables (>1000 rows, >100 columns) that exceed Docling's processing limits. This strategy combines border detection, header normalization, and chunked data processing to extract massive tables efficiently.

## Problem Statement

**Challenge:** Docling-based extraction cannot handle Excel files with:
- Tables exceeding 1,000 rows
- Files with 600K+ cells
- Complex multi-level headers spanning 10+ rows
- Memory constraints during HTML conversion

**Example:** The JP1 configuration file has:
- 2 sheets with 619K and 622K cells respectively
- 3,995 rows × 155 columns (A to EY)
- 4-level hierarchical headers
- Would take hours or crash with standard Docling approach

## Solution Architecture

### High-Level Strategy

```
┌─────────────────────────────────────────────────────────────────┐
│ 1. Border Detection → Identify table boundaries and size       │
├─────────────────────────────────────────────────────────────────┤
│ 2. Header Extraction → Extract first N rows to temp file       │
├─────────────────────────────────────────────────────────────────┤
│ 3. Header Normalization → Parse multi-level headers            │
├─────────────────────────────────────────────────────────────────┤
│ 4. Chunked Processing → Process data rows with iter_rows()     │
├─────────────────────────────────────────────────────────────────┤
│ 5. Export → Generate JSON/Markdown with normalized headers     │
└─────────────────────────────────────────────────────────────────┘
```

### Step-by-Step Process

#### Step 1: Border Detection
**Purpose:** Detect table boundaries without loading full content

```python
from src.extraction_v2.detect_border import BorderTableDetector

detector = BorderTableDetector()
tables = detector.detect_tables_by_border(file_path)
# Returns: [{'sheet': '...', 'range': 'A4:EY3998', 'cell_count': 619057, ...}]
```

**Output:**
- Table location (sheet, range, start/end rows/columns)
- Cell count for size estimation
- Detection time: ~9 seconds for 619K cells

#### Step 2: Header Extraction
**Purpose:** Extract only header rows for normalization

```python
# Create temporary file with first 10 rows
workbook = load_excel_file(file_path)
sheet = workbook[sheet_name]

# Copy only header rows (preserving merged cells)
for row_num in range(start_row, start_row + 10):
    # Copy cells, formatting, and merged regions
    ...
workbook.save(temp_file)
```

**Output:**
- Small temp file (~14KB)
- Preserves merged cells and formatting
- Extraction time: ~4 seconds

#### Step 3: Header Normalization
**Purpose:** Convert multi-level headers to hierarchical names

```python
from src.extraction.header_extractor import HeaderExtractor

extractor = HeaderExtractor()
headers_info = extractor.extract_headers(sheet, boundary)

# Detect actual header depth (critical for avoiding data loss)
header_depth = extractor._detect_header_depth(sheet, boundary)

# Create column mapping with deduplication and table name removal
column_mapping = {}
for col_letter, header_info in headers_info.items():
    full_header = header_info.display
    levels = full_header.split(" > ")
    
    # Remove consecutive duplicates (from vertically merged cells)
    # e.g., ["保留", "保留", "保留"] -> ["保留"]
    deduplicated_levels = []
    for level in levels:
        if not deduplicated_levels or level != deduplicated_levels[-1]:
            deduplicated_levels.append(level)
    levels = deduplicated_levels
    
    # Remove first level (table/sheet name) if multiple levels exist
    if len(levels) > 1:
        levels = levels[1:]
    
    header_name = " > ".join(levels)
    column_mapping[col_letter] = header_name
```

**Output:**
- 155 normalized column names
- Multi-level hierarchy: `セクション > サブセクション > カラム`
- Example: `ユニット定義情報 > ユニット名`
- **Actual header depth detected** (e.g., 4 rows instead of assuming 10)
- **Duplicates removed** from merged cells
- **Table name prefix removed** for cleaner output

#### Step 4: Chunked Data Processing
**Purpose:** Process rows efficiently using openpyxl's iter_rows()

```python
# Load with read_only mode for memory efficiency
workbook = load_excel_file(file_path, read_only=True, data_only=True)
sheet = workbook[sheet_name]

# Use actual header depth (not HEADER_SAMPLE_ROWS) to avoid data loss
actual_header_depth = headers.get('header_depth', HEADER_SAMPLE_ROWS)
data_start_row = table['start_row'] + actual_header_depth

# Process in chunks (100 rows at a time)
for chunk_start in range(data_start_row, data_end_row, CHUNK_SIZE):
    for row in sheet.iter_rows(
        min_row=chunk_start,
        max_row=chunk_end,
        min_col=start_col_idx,
        max_col=end_col_idx,
        values_only=True  # Skip Cell object creation (FAST!)
    ):
        # Skip empty rows (all values are None or empty)
        if all(value is None or (isinstance(value, str) and not value.strip()) for value in row):
            continue
        
        row_data = {}
        for col_offset, value in enumerate(row):
            col_letter = get_column_letter(start_col_idx + col_offset)
            header_name = column_mapping[col_letter]
            row_data[header_name] = value
        data.append(row_data)
```

**Performance:**
- 100 rows processed in <1 second
- Memory efficient (read_only mode)
- `iter_rows()` is ~100x faster than cell-by-cell access
- **Uses actual header depth** to avoid skipping data rows
- **Automatically skips empty rows** to prevent null records

#### Step 5: Export Results
**Purpose:** Generate structured output formats

**JSON Output:**
```json
{
  "metadata": {
    "generated": "2025-12-01 15:09:45",
    "sheet": "1.2 JP1設定項目_東日本",
    "range": "A4:EY3998",
    "total_rows": 3995,
    "columns": {"start": "A", "end": "EY", "count": 155},
    "data_rows_processed": 200
  },
  "headers": {
    "A": "区分 > 区分 > 区分",
    "B": "ユニット定義情報 > ユニット名 > ユニット名",
    ...
  },
  "data": [
    {
      "ユニット定義情報 > ユニット名 > ユニット名": "DB抽出［光SO］_1",
      "ユニット共通定義情報 > コメント > コメント": "対象支店コード毎に...",
      ...
    }
  ]
}
```

## Performance Benchmarks

### Test Case: JP1 Configuration File
- **File size:** 4.82 MB
- **Tables:** 2 sheets
- **Largest table:** 3,995 rows × 155 columns (619,057 cells)
- **Header depth:** 4 levels

### Results

| Step | Duration | Details |
|------|----------|---------|
| Border Detection | 9.0s | Analyzed 619K cells, found boundaries |
| Header Extraction | 4.0s | Extracted 10 rows to 14KB temp file |
| HTML Conversion | 0.26s | Docling processed header-only file |
| Header Normalization | <1s | Extracted 155 headers with depth=4 |
| Data Processing | <1s | Processed 200 rows using iter_rows() |
| **Total Time** | **14.5s** | End-to-end for 200 rows |

### Scalability Estimates

| Rows | Estimated Time | Memory Usage |
|------|----------------|--------------|
| 200 | 14.5s | ~100 MB |
| 1,000 | ~20s | ~150 MB |
| 4,000 | ~45s | ~300 MB |
| 10,000 | ~90s | ~500 MB |

## Usage

### Basic Usage

```python
from tests.manual.test_large_table_strategy import test_large_table_strategy

# Test with default file
test_large_table_strategy("path/to/large_excel_file.xlsx")
```

### Command Line

```bash
# Run with default test file
python tests/manual/test_large_table_strategy.py

# Run with specific file
python tests/manual/test_large_table_strategy.py "CustomerDocument/file.xlsx"

# Use uv (recommended)
uv run python tests/manual/test_large_table_strategy.py "path/to/file.xlsx"
```

### Configuration

Edit constants in `test_large_table_strategy.py`:

```python
MAX_ROWS_FOR_DOCLING = 1000  # Threshold for using large table strategy
HEADER_SAMPLE_ROWS = 10      # Number of header rows to extract
CHUNK_SIZE = 100             # Rows per processing chunk
```

## Output Files

### JSON File
**Location:** `tmp/large_table_{sheet_name}_{timestamp}.json`

**Structure:**
- `metadata`: Table information and statistics
- `headers`: Column letter → normalized header name mapping
- `data`: Array of row objects with `{header: value}` format

**Size:** ~2.8 MB for 200 rows × 155 columns

### Markdown File
**Location:** `tmp/large_table_{sheet_name}_{timestamp}.md`

**Content:**
- Table information summary
- First 10 rows displayed as formatted JSON
- Statistics and metadata

**Size:** ~136 KB for 200 rows

## Key Features

### ✅ Border Detection
- Detects table boundaries by analyzing cell borders
- Handles tables with 600K+ cells
- No need to parse entire file
- Performance: O(cells) with early termination

### ✅ Header Normalization
- Extracts multi-level hierarchical headers (depth 1-4)
- **Detects actual header depth** to avoid data loss
- **Removes consecutive duplicates** from vertically merged cells
- **Removes table/sheet name prefix** for cleaner output
- Preserves merged cell structure and newlines
- Handles Japanese and multi-byte characters

### ✅ Efficient Data Processing
- Uses `iter_rows(values_only=True)` for speed
- Processes in configurable chunks
- Read-only mode for memory efficiency
- **Uses actual header depth** instead of assuming all sample rows are headers
- **Automatically skips empty rows** to prevent null records
- Progress tracking for long operations

### ✅ Structured Output
- JSON format for programmatic access
- Markdown format for human review
- Complete metadata tracking
- Easy integration with downstream systems

## Limitations

### Current Limitations

1. **Early Exit for Testing**
   - Currently limited to 200 rows (2 chunks)
   - Remove early exit in `process_data_rows()` for full processing

2. **Header Detection Depth**
   - Assumes headers are in first 10 rows
   - Increase `HEADER_SAMPLE_ROWS` if needed

3. **Table Name Detection**
   - Assumes table names contain "表" character
   - Modify detection logic in `extract_normalized_headers()` if needed

4. **Border Detection Performance**
   - Skips sheets with `max_row > 5000` for performance
   - These sheets fall back to standard processing

### Known Issues

1. **Deprecation Warnings**
   - openpyxl style `.copy()` method warnings
   - Harmless, can be suppressed or fixed with `from copy import copy`

2. **Sheet Name Encoding**
   - Non-ASCII sheet names work but may look garbled in some terminals
   - Output files correctly preserve UTF-8 encoding

## Best Practices

### When to Use This Strategy

✅ **Use when:**
- Table has >1,000 rows
- File has >100,000 cells per sheet
- Multi-level headers need preservation
- Memory is constrained
- Processing time is critical

❌ **Don't use when:**
- Tables are small (<1,000 rows)
- Headers are simple (1-2 levels)
- Standard Docling extraction works fine
- Need real-time processing

### Performance Optimization Tips

1. **Adjust Chunk Size**
   - Larger chunks (500-1000): Faster but more memory
   - Smaller chunks (50-100): Slower but less memory

2. **Reduce Header Sample Rows**
   - If headers are in first 5 rows, use `HEADER_SAMPLE_ROWS = 5`
   - Saves extraction time

3. **Filter Columns**
   - Modify `process_data_rows()` to skip unwanted columns
   - Reduces output file size

4. **Use read_only Mode**
   - Always use `load_excel_file(file_path, read_only=True)`
   - Significantly reduces memory usage

## Integration with V2 Pipeline

This strategy can be integrated into the main V2 extraction pipeline:

```python
# In batch_extract_v2.py or similar
from src.extraction_v2.detect_border import BorderTableDetector

def extract_large_table(file_path: str):
    detector = BorderTableDetector()
    tables = detector.detect_tables_by_border(file_path)

    for table in tables:
        num_rows = table['end_row'] - table['start_row'] + 1

        if num_rows > MAX_ROWS_FOR_DOCLING:
            # Use large table strategy
            result = extract_with_chunked_strategy(file_path, table)
        else:
            # Use standard Docling extraction
            result = extract_with_docling(file_path)

        yield result
```

## Troubleshooting

### Issue: "No bordered cells found"
**Cause:** Table doesn't use cell borders
**Solution:** Use standard Docling extraction or modify border detection criteria

### Issue: "Header extraction failed"
**Cause:** Headers not in expected format
**Solution:** Adjust `HEADER_SAMPLE_ROWS` or check header structure manually

### Issue: "Memory error during processing"
**Cause:** Large file + small chunk size
**Solution:** Reduce `CHUNK_SIZE` or increase available memory

### Issue: "Wrong headers extracted"
**Cause:** Table name detection failed
**Solution:** Modify table name detection logic in `extract_normalized_headers()`

### Issue: "File too slow to process"
**Cause:** `iter_rows()` not being used
**Solution:** Verify `values_only=True` parameter is set

## Testing

### Run Test Suite

```bash
# Run with default file
uv run python tests/manual/test_large_table_strategy.py

# Run with custom file
uv run python tests/manual/test_large_table_strategy.py "path/to/test.xlsx"
```

### Validate Output

```bash
# Check JSON structure
cat tmp/large_table_*.json | python3 -m json.tool | head

# View sample data
cat tmp/large_table_*.json | python3 -c "import json, sys; d=json.load(sys.stdin); print(json.dumps(d['data'][0], indent=2, ensure_ascii=False))"

# Check file sizes
ls -lh tmp/large_table_*
```

## References

### Source Files
- **Test Script:** `tests/manual/test_large_table_strategy.py`
- **Border Detection:** `src/extraction_v2/detect_border.py`
- **Header Extraction:** `src/extraction/header_extractor.py`
- **Excel Loader:** `src/extraction_v2/excel_loader.py`

### Related Documentation
- [V2 Pipeline Testing Epic](docs/feats/wrapup_pipeline_v2/)
- [Border Detection README](src/extraction_v2/detect_border.py)
- [Header Extractor](src/extraction/header_extractor.py)

## Future Enhancements

### Planned Improvements

1. **Parallel Processing**
   - Process multiple chunks in parallel
   - Use multiprocessing for CPU-bound operations

2. **Streaming Output**
   - Stream JSON output instead of building in memory
   - Support very large datasets (100K+ rows)

3. **Smart Header Detection**
   - Auto-detect header depth without sampling
   - Handle non-standard header formats

4. **Progress Bar**
   - Add tqdm progress bar for long operations
   - Better user feedback during processing

5. **Error Recovery**
   - Checkpoint progress for resumable processing
   - Handle corrupted cells gracefully

6. **Database Export**
   - Direct export to PostgreSQL/MySQL
   - Streaming inserts for large datasets

## License

Internal use only - DSOL Project

## Contact

For questions or issues with large table parsing, contact the development team.

## Recent Bug Fixes (2025-12-01)

Four critical bugs were identified and fixed:

### 1. Data Rows Being Skipped
- **Problem:** Used `HEADER_SAMPLE_ROWS` (10) to calculate data start, skipping all 10 rows even if only some were headers
- **Impact:** Lost 6 data rows when headers only occupied 4 rows
- **Fix:** Detect actual header depth using `HeaderExtractor._detect_header_depth()`

### 2. Empty Rows Creating Null Records
- **Problem:** Empty separator rows created records with all `null` values
- **Fix:** Skip rows where all values are `None` or empty

### 3. Duplicate Header Names from Merged Cells
- **Problem:** Vertically merged cells caused duplicates like `"保留 > 保留 > 保留"`
- **Fix:** Remove consecutive duplicate levels from header hierarchy

### 4. Redundant Table Name Prefix
- **Problem:** Headers included full table/sheet name prefix
- **Fix:** Remove first level if multiple levels exist

**Result:** Clean headers like `"ユニット定義情報 > ユニット名"` instead of `"表 １．２．１　JP1... > ユニット定義情報 > ユニット名 > ユニット名"`