GK One-Line Question & Answer

An index using a hash function to map key values to bucket positions - supports only equality lookups (O(1) average) but NOT range queries or ordering; superior for equality-only workloads with no range/ordering requirements

A table where the entire row data is stored within the index structure (B-tree leaf nodes) rather than in a separate heap file - eliminates the double storage of data (heap + index) provides fast primary key access but slower for full table scans and secondary index lookups

Each INSERT/UPDATE/DELETE on a table must also update ALL indexes on that table multiplying the write I/O: a table with 5 indexes requires writing to 6 places (heap + 5 indexes) per row change - significantly reduces write throughput in insert-heavy OLTP systems

A query execution method where all required data is found directly in the index pages without accessing the table heap - requires that all columns referenced in the query (SELECT WHERE GROUP BY ORDER BY) are included in the index (covering index)

The percentage of each index page that is filled with data at index creation time; setting below 100% (e.g. 80%) leaves free space in each page for future insertions reducing page splits - beneficial for frequently updated indexes at the cost of larger initial index size

An index built on the RESULT of an expression/function applied to one or more columns allowing efficient queries that filter/sort on computed values - e.g. CREATE INDEX ON users(LOWER(email)) enables case-insensitive email lookups to use the index

When a B-tree leaf page is full and a new key must be inserted the page splits into two pages (50/50 distribution) requiring: allocating new page redistributing keys updating parent pointer possibly cascading parent splits - causes write I/O overhead and index fragmentation

An index that the optimizer ignores (as if it does not exist) but is still maintained by DML operations - used to safely test the impact of dropping an index without actually removing it or to prepare a new index for testing before making it active

An index where the bytes of the key are reversed before storage in the B-tree distributing sequential key inserts (like auto-increment IDs) across all index leaf blocks instead of always inserting into the rightmost block - reduces right-hand-side contention in OLTP systems

Statistical information about index column value distribution (cardinality histograms null count average row size) that the query optimizer uses to estimate result sizes and costs for different execution plan choices - stale or inaccurate statistics lead to poor plan choices

Index seek: uses the B-tree to navigate directly to the matching key value(s) - O(log n) + matching rows only. Index scan: reads all (or most) leaf pages of the index sequentially - O(index_size). Seek is much faster for selective queries; scan used when large fraction of data is returned or index cannot be used for point lookup

Building an index without holding a table lock (allows concurrent reads AND writes during index build) - trade-offs: takes longer than normal index creation (multiple table scans needed) uses more CPU/I/O cannot be done in a transaction and may fail requiring manual REINDEX

An extensible index framework that supports a wide variety of data types and query operators beyond equality/comparison: geometric objects text search IP ranges JSON paths custom types - by allowing user-defined key types and split/union/penalty functions

A directive added to a SQL query that forces or suggests the query optimizer to use a specific index instead of choosing one automatically - should be used sparingly when the optimizer consistently makes poor choices due to inaccurate statistics or atypical query patterns

An automatically built in-memory hash index that InnoDB creates on top of frequently accessed B-tree index pages - when InnoDB detects that the same index lookups are performed repeatedly it builds a hash index for those values enabling O(1) lookup vs O(log n) B-tree traversal

A technique that reduces the storage size of index entries by: prefix compression (storing only the suffix that differs from the previous key for sorted keys) dictionary compression (replacing repeated values with integer codes) or key compression - smaller index means more pages fit in buffer pool improving cache efficiency and reducing I/O

A primary index is built on the primary key and determines the physical order of data (clustered); secondary indexes are built on non-primary key columns and do not determine physical data order (non-clustered in most DBMS) - secondary indexes reference the primary key to locate actual rows

A special index type that stores data by column rather than by row enabling high compression and vectorized batch processing - primarily used for OLAP/analytical workloads where queries aggregate over large datasets and touch only a few columns

The cost of updating indexes on every INSERT/UPDATE/DELETE which includes: additional I/O for each index page write, page splits causing fragmentation, and potential index bloat - managed by: choosing indexes carefully (only create indexes that pay off) rebuilding fragmented indexes (ALTER INDEX REBUILD) and reorganizing (ALTER INDEX REORGANIZE) on a scheduled basis

All operations in a transaction either ALL complete successfully (COMMIT) or ALL are undone (ROLLBACK) - implemented via the undo log: before each change the original value is written to the undo log enabling complete rollback if the transaction fails or is explicitly rolled back

Consistency means the transaction takes the database from one valid state to another - the DBMS enforces defined constraints (PK FK CHECK NOT NULL) but the APPLICATION is responsible for ensuring business-level constraints are upheld (the DB only enforces what it knows about)

Isolation ensures concurrent transactions execute as if they were serial; stronger isolation (SERIALIZABLE) prevents more anomalies but requires more locking/MVCC overhead reducing concurrency and throughput. Weaker isolation (READ COMMITTED) allows more anomalies but permits higher concurrency

Once a transaction is committed its changes persist even through system crashes; WAL implements this by writing log records to disk BEFORE applying changes to the database ensuring that committed changes can be replayed during recovery even if the data pages were not yet flushed

Reading uncommitted changes of another concurrent transaction - if that other transaction later rolls back the read data never existed. Only READ UNCOMMITTED isolation level allows dirty reads; all higher levels prevent them

Within one transaction reading the same row twice returns different values because another committed transaction modified that row between the two reads; prevented by REPEATABLE READ and SERIALIZABLE isolation levels

Within one transaction executing the same range query twice returns different sets of rows because another committed transaction inserted/deleted rows in the query range; SERIALIZABLE adds range locking (predicate locks) or snapshot validation beyond REPEATABLE READ which only locks existing rows

A named point within a transaction to which a partial rollback can be made - ROLLBACK TO SAVEPOINT name undoes work done after the savepoint but keeps work done before it allowing partial recovery without rolling back the entire transaction

2PL: a transaction must acquire ALL needed locks before releasing ANY lock - Phase 1 (growing phase): acquire locks only no releases. Phase 2 (shrinking phase): release locks only no acquisitions. This guarantees serializability because the lock acquisition order is consistent and creates a serial order

When one transaction rolls back all other transactions that read its uncommitted data must also rollback (cascade) because those reads are now dirty reads - prevented by Strict 2PL (holds write locks until commit so other transactions cannot read uncommitted changes)

PCC: locks data when accessed to prevent concurrent modifications (assume conflicts will occur); OCC: no locks during execution validates at commit time for conflicts (assume conflicts are rare) aborts if conflict detected - OCC better for low-contention workloads PCC better for high-contention

Each transaction receives a timestamp at start; data items track the timestamps of the last read (max_R_TS) and write (max_W_TS); conflicts are resolved using these timestamps: if a younger transaction tries to read data written by an older committed transaction it is allowed; otherwise abort and restart

An optimization that allows a write operation to be silently ignored (rather than aborting the transaction) when a newer transaction has already written the same data item - since the outdated write would be overwritten by the newer write anyway it is safe to skip

A transaction that remains open for an extended period causing: accumulated locks blocking other transactions MVCC undo/version storage growth (old versions cannot be purged) replication lag in logical replication and increased probability of conflict/deadlock

The technique of dividing a long transaction into smaller sub-transactions to improve concurrency; safe only when: the sub-transactions maintain the same semantic consistency there are no dependencies between the pieces that require atomic execution and the application can handle partial failures

READ COMMITTED prevents dirty reads (only sees committed data at the time of each statement) but allows non-repeatable reads (re-reading same row can return different committed values) and phantom reads

A local transaction operates within a single DBMS; a distributed transaction spans multiple separate database instances and requires coordination protocols (typically Two-Phase Commit - 2PC) to ensure atomicity across all participating databases

Snapshot isolation: each transaction reads from a consistent snapshot taken at transaction start preventing dirty reads non-repeatable reads and phantoms but does NOT prevent write skew anomaly. REPEATABLE READ in standard SQL prevents non-repeatable reads; SNAPSHOT adds phantom prevention via MVCC

Two transactions each read overlapping data make decisions based on it and write to non-overlapping parts collectively violating an integrity constraint that neither individual write would violate - e.g. both doctors check at least one doctor on call both see the other is on call both decide to go off call

COMMIT WORK makes all transaction changes permanent and releases locks; ROLLBACK WORK undoes all changes and releases locks; implicit COMMIT occurs in most DBMS when: a DDL statement is executed (CREATE ALTER DROP) when a session normally ends or when autocommit is enabled (each statement auto-commits)

MVCC maintains multiple timestamped versions of each row; readers see the latest committed version as of their transaction start time (snapshot) without needing to acquire locks on data; writers create new versions without affecting readers current snapshots - reads and writes proceed concurrently