PolarDB:Introduction to the In-Memory Column Index technical architecture

Achieving 100% MySQL compatibility

Not every query can run on IMCI. Two constraints limit coverage:

• Column coverage. A query that references columns not included in any columnar index cannot use IMCI for those columns.

• Operator coverage. The IMCI execution engine is a complete rewrite, not an extension of MySQL's row executor. Some column types, operators, and expression forms are not yet implemented in the IMCI engine.

The whitelist mechanism checks data types, operators, expressions, and unsupported scenarios (such as multi-statements) against a known-good list. If a query passes the whitelist, it is eligible for IMCI execution. If not, it falls back to MySQL's native row executor. This fallback guarantees 100% compatibility: IMCI accelerates what it can, and MySQL handles everything else.

Query plan conversion

Plan conversion transforms MySQL's abstract syntax tree (AST) representation into an IMCI logical plan. The process traverses the execution plan tree and rewrites AST nodes as relational operators, handling implicit type conversions to maintain compatibility with MySQL's flexible type system.

The logical plan is then optimized into a physical plan. Beyond standard optimizations (Hash Join vs. Nested Loop Join selection), the IMCI optimizer converts subqueries that the IMCI executor cannot handle directly into equivalent join operations.

Three-way cost-based selection

PolarDB's optimizer chooses among three execution paths:

The optimizer follows this process:

1. Parse the SQL statement and generate a logical plan. Pass the plan to both MySQL's native optimizer and IMCI's plan compiler.

2. Calculate the row-store execution cost. If it exceeds a threshold, attempt to push the query to IMCI.

3. If IMCI cannot execute the query, attempt to generate a parallel query plan.

4. If neither IMCI nor parallel query can handle the query, fall back to row-store serial execution.

This cost model assumes IMCI outperforms parallel query, which outperforms serial execution. In practice, a parallel index join on row-store indexes can sometimes be cheaper than a sort-merge join on a column store. The optimizer may select IMCI in cases where a row-store plan would be faster.

Column store as a secondary index

IMCI implements the column store as a secondary index of InnoDB, rather than as a separate storage engine. This design unlocks several advantages:

• Transaction reuse. InnoDB already applies INSERT, UPDATE, and DELETE operations to all secondary indexes atomically, within the same transaction. IMCI inherits this transaction framework without modification.

• Encoding reuse. Columnar indexes use the same data encoding as other row-store indexes. No character set or collation conversion is needed when moving data between formats.

• Flexible column selection. Create columnar indexes on any subset of columns. Add or drop columns using DDL. Index high-cardinality analytical columns (INT, FLOAT, DOUBLE) while keeping large columns used only for point queries (TEXT, BLOB) in the row store.

• Recovery reuse. Crash recovery reuses InnoDB's redo log module. Columnar indexes on RO nodes or standby nodes are rebuilt from redo log, integrating cleanly with PolarDB's physical replication process.

• Lifecycle management. A columnar index shares the lifecycle of the primary index, simplifying schema management.

In PolarDB, the primary index and all secondary indexes are B+ trees. A columnar index is logically an index — it captures all inserts, updates, and deletes on the indexed columns — but physically, it stores columns independently rather than encoding them together into a single row.

For the table shown above: the primary index stores all five columns (C1–C5); a secondary index stores two columns (C2, C1) encoded together in a B+ tree; the columnar index stores three columns (C2, C3, C4) in split, independent column format.

When all columns required by a query are covered by a columnar index, query execution uses only that index — never touching the primary index. This is the same covering index optimization MySQL already supports, applied to column-format data. Analytical queries on covered columns run dozens to hundreds of times faster than equivalent row-store queries.

Organization of column-oriented data

Each column in a columnar index is stored in append-write mode, unordered. Space reclamation uses deletion labels and background compaction rather than in-place updates. Key design points:

• Row groups. Records are organized in row groups of 64,000 rows each. Within a row group, each column is stored as a separate data pack.

• Active row group. One row group is active at any time, accepting new writes. When it fills up, it freezes. All its data packs are compressed and flushed to disk, and rough index statistics are computed for each pack.

• Row IDs. Each new row is assigned a row ID. The system uses the row ID to locate that row's data across all column data packs. A mapping index from primary keys to row IDs supports subsequent deletions and updates.

• Deletion labels. Delete operations set a bit in a delete bitmap rather than modifying column data in place. Update operations combine a deletion label on the old row with an append write of the new row data to the active row group.

• Background compaction. When invalid (deleted) records in a row group exceed a threshold, background compaction reclaims space and improves storage density for analytical scans.

This design keeps write operations lightweight: a write appends column data to memory; a delete sets a label; an update sets a label and appends. Column store maintenance adds minimal overhead to OLTP transactions, and transaction-level isolation is preserved throughout.

Rough index scheme

All data packs are unordered and append-written, so columnar indexes cannot support precise row-level filtering the way ordered B+ tree indexes can. Instead, IMCI uses a rough index scheme based on pre-computed statistics to skip irrelevant data packs before decompression.

When an active data pack finishes writing and freezes, the system computes and stores these statistics in the data pack's metadata:

• Minimum value

• Maximum value

• Sum of values

• Null value count

• Total record count

These statistics persist in memory. For frozen data packs with deletions, statistics are updated in the background.

At query time, the optimizer classifies each data pack as relevant, irrelevant, or possibly relevant based on query predicates and the pack's statistics. Irrelevant packs are skipped entirely. For aggregate operations such as COUNT and SUM, relevant packs can often be answered directly from pre-computed statistics, skipping decompression altogether.

Rough indexes work best for queries that scan large volumes of data — exactly the workload IMCI targets. For queries that locate a small number of specific rows, the cost-based optimizer routes to a row-store index instead.

TP/AP resource isolation

Running OLTP and OLAP on the same cluster creates resource contention risk: a large analytical query can consume enough CPU and I/O to spike OLTP latency. PolarDB supports three deployment modes to isolate these workloads, using its write-once-read-many architecture to add independent RO nodes.

In addition to deployment-level isolation, Auto DOP limits the resources any single analytical query can consume. The DOP calculation accounts for current system load, available CPU and memory, and the queue of scheduled queries — preventing a single large query from starving other requests.