<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Mohamed Shaaban on Medium]]></title>
        <description><![CDATA[Stories by Mohamed Shaaban on Medium]]></description>
        <link>https://medium.com/@mohamed.shaaban.elbay?source=rss-163154ddb199------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*CpDwF4Noe-KXGOPy</url>
            <title>Stories by Mohamed Shaaban on Medium</title>
            <link>https://medium.com/@mohamed.shaaban.elbay?source=rss-163154ddb199------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 04:59:31 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@mohamed.shaaban.elbay/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Sharding — System Design Series]]></title>
            <link>https://medium.com/@mohamed.shaaban.elbay/sharding-system-design-series-b0760c3ef9af?source=rss-163154ddb199------2</link>
            <guid isPermaLink="false">https://medium.com/p/b0760c3ef9af</guid>
            <dc:creator><![CDATA[Mohamed Shaaban]]></dc:creator>
            <pubDate>Mon, 10 Aug 2026 13:04:00 GMT</pubDate>
            <atom:updated>2026-08-11T09:32:00.870Z</atom:updated>
            <content:encoded><![CDATA[<h4>not an ai content</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*zuJ8ZadRwiRyI5gV4EPfkg.png" /></figure><h3>Content</h3><ul><li><strong>What is Sharding</strong></li><li><strong>Sharding vs. Replication</strong></li><li><strong>The Complexity of Sharding</strong></li><li><strong>The Sharding Key</strong></li><li><strong>Sharding Strategies</strong><br> — Directory-based Sharding<br> — Range-based Sharding<br> — Hash-based Sharding<br> — Consistent Hashing</li><li><strong>Query Router</strong></li><li><strong>Global and Local Indexes</strong></li></ul><h3>What is Sharding</h3><p>When a database becomes too large, or the write throughput becomes too high for a single node to handle, the data can be split into smaller units called <strong>shards</strong> or <strong>partitions</strong>. These shards are then distributed across multiple nodes.</p><p>Each piece of data — such as a record, row, or document — belongs to exactly one shard. Each shard effectively operates as a smaller database of its own, although some database systems support operations that access multiple shards at the same time.</p><blockquote>Some database systems distinguish <strong>partitioning</strong> from <strong>sharding</strong>, while others use the terms interchangeably.</blockquote><blockquote>For example, in PostgreSQL, partitioning splits a large table into smaller parts, typically stored on the same machine. This can provide benefits such as making it faster to delete an entire partition.</blockquote><blockquote><strong>Sharding</strong>, by contrast, usually means splitting a dataset across multiple machines.</blockquote><h3>Choosing Between Sharding &amp; Replication</h3><p>The choice between <strong>sharding</strong> and <strong>replication</strong> depends mainly on <strong>what is limiting your database</strong>: read throughput, write throughput, storage capacity, or fault tolerance.</p><h4>Sharding for Write and Storage Scalability</h4><p>The primary reason for sharding a database is <strong>scalability</strong>. Sharding becomes useful when the <strong>amount of data</strong> or <strong>write throughput</strong> has grown beyond what a <strong>single node can handle</strong>.</p><p>Instead of keeping the entire dataset and all writes on one machine, sharding <strong>splits the dataset into multiple shards</strong> and distributes them across multiple nodes. Each node is responsible for only a portion of the data, allowing the system to process data and writes <strong>in parallel</strong>.</p><p>This makes sharding one of the main techniques for achieving <strong>horizontal scaling (scale-out)</strong>. Rather than upgrading a single machine to a more powerful one, we can increase the system’s capacity by <strong>adding more machines</strong>.</p><h4>Replication for Read Scaling &amp; fault tolerance</h4><p>If the main bottleneck is <strong>read throughput</strong>, we don’t necessarily need sharding. <strong>Replication</strong> can often solve the problem more simply.</p><p>By maintaining multiple replicas of the same data, read requests can be distributed across multiple nodes. This allows the system to increase its <strong>read capacity</strong> without splitting the dataset.</p><p>Replication is also useful because it provides <strong>fault tolerance</strong> and allows the system to continue operating when a node becomes unavailable.</p><p>However, replication becomes more complicated when we try to use it to scale <strong>writes</strong>.</p><p>for more about replication revisit the article about it in the series<strong> </strong><a href="https://medium.com/@mohamed.shaaban.elbay/replication-system-design-series-ii-fd490e706b40?sharedUserId=mohamed.shaaban.elbay"><strong>replication</strong></a></p><blockquote>In real systems, since <strong>replication and sharding solve two different problems</strong>, they are often used together. The database is sharded into smaller pieces, while each shard can have one or more <strong>read replicas</strong>, since each shard now acts as an isolated database on its own.</blockquote><blockquote>This allows the system to keep the benefits of replication, such as <strong>higher read throughput</strong> and <strong>fault tolerance</strong>, while using sharding across the whole system to handle the <strong>high write throughput</strong> of the overall database.</blockquote><h3>The Complexity with Sharding</h3><p>Sharding is a <strong>heavyweight solution</strong> that is mostly relevant at large scale. If your data volume and write throughput are such that a single machine can handle them (and a single machine can do a lot nowadays!), it’s often better to avoid sharding and stick with a <strong>single-shard database</strong>.</p><p>The reason for this recommendation is that sharding adds complexity. You typically have to decide which records to put in which shard by choosing a <strong>partition key</strong>; all records with the same partition key are placed in the same shard. This choice matters because accessing a record is fast if you know which shard it’s in, but if you don’t, you have to do an inefficient search across all shards. The sharding scheme is also difficult to change. and choosing the right sharding key is a core concept we will cover below.</p><p>Another problem with sharding is that a write may need to update related records in <strong>several shards</strong>. While transactions on a single node are quite common, ensuring consistency across multiple shards requires a <strong>distributed transaction</strong>. Distributed transactions are available in some databases, but they are usually much slower than single-node transactions and may become a bottleneck for the system as a whole.</p><h3>The Sharding Key</h3><p>To split a dataset into shards, we need an algorithm that takes the <strong>sharding key</strong> of a record as input and determines which shard contains that record. In a key-value store, the partition key is usually the key or the first part of the key. In a relational model, the partition key might be a column of a table, not necessarily its primary key.</p><p>When choosing a sharding key, there are two important goals. The first is to <strong>keep related data together within the same shard</strong>. For example, keeping all data belonging to a specific user in one shard eliminates the need to scan multiple shards when fetching that user’s data.</p><p>The second goal is to <strong>spread the data and query load evenly across nodes</strong>. If every node takes a fair share, then — in theory — 10 nodes should be able to handle 10 times as much data and 10 times the read and write throughput of a single node.</p><p>These two goals need to be balanced. A sharding key that keeps related data together may not always distribute the workload evenly. If some shards contain significantly more data or receive more queries than others, the sharding becomes <strong>skewed</strong>. The presence of <em>skew</em> makes sharding much less effective.</p><p>In an extreme case, all the load could end up on one shard, leaving 9 out of 10 nodes idle while the single busy node becomes the bottleneck. A shard with disproportionately high load is called a <strong>hot shard</strong> or <strong>hotspot</strong>. If one key has a particularly high load, such as a celebrity in a social network, we call it a <strong>hot key</strong>.</p><p>To deal with skew and hotspots, the sharding scheme should support <strong>rebalancing</strong>. If we add or remove a node, we need to redistribute the load so that it remains evenly distributed across the new number of nodes. Therefore, the algorithm used to determine the shard for each record needs to be amenable to rebalancing in order to relieve hotspots.</p><p>Choosing such a sharding key is often easier for <strong>key-value data</strong>, where you can easily shard by key. It is harder with <strong>relational data</strong>, where you may want to search by a secondary index or join records that might be distributed across different shards.</p><h3>Sharding Strategies</h3><h4>1. Directory-based Sharding</h4><ul><li>Uses a lookup table or “map” to track which shard stores specific data.</li><li>Example: A system with a <em>Company</em> table could map specific countries, such as <strong>Brazil → Shard 0</strong>, directly to their corresponding shard. In an e-commerce system, you could also assign different types of data to different shards, such as <strong>customers on one shard and orders on another</strong>.</li><li><strong>Pros:</strong> Highly flexible, as you can easily add new shards by updating the map.</li><li><strong>Cons:</strong> The lookup table can become a single point of failure or a performance bottleneck. If a shard becomes a hot shard, the data may need to be redistributed and the mapping updated.</li></ul><h4>2. Range-based Sharding</h4><ul><li>Distributes data based on ranges of a shard key, such as dates or numerical values.</li><li>Example: An <em>Orders</em> table might store orders from <strong>2025 on Shard 0</strong> and orders from <strong>2026 on Shard 1</strong>.</li><li><strong>Pros:</strong> Excellent for range-based queries, as the system can quickly route requests to the correct shard.</li><li><strong>Cons:</strong> Prone to <strong>hotspots</strong>, where one shard receives significantly more traffic because it contains the most active data range. This may require rebalancing or choosing a better sharding key, such as adding the order ID or the customer ID to the prefix of the key. This can provide a more uniform distribution, but with the trade-off of losing the benefits of range queries.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Q3lcAI6fQ0vq5d-uhcZhZQ.png" /><figcaption>distribute data based on the date range</figcaption></figure><h4>3. Hash-based Sharding</h4><ul><li>Applies a hash function to the shard key, followed by a modulo operation, to determine the target shard.</li><li>Example: Using a <em>Customer ID</em>, the system calculates Hash(ID) % N, where N is the number of shards, to distribute data evenly across the available nodes.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ragAxyKd0AZjGFCiAOKrrg.png" /><figcaption>hash based sharding</figcaption></figure><ul><li><strong>Pros:</strong> Provides a more uniform data distribution, reducing the chance of a single shard becoming overloaded.</li><li><strong>Cons:</strong> Lacks data locality and business meaning, often requiring broadcasts to all shards for complex queries. Re-balancing is also expensive because, with the mod N approach, changing the number of shards causes most keys to map to a different shard, requiring significant data movement and network traffic like the following example:</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/816/1*uJEOzp39BP8yyga_C09tQA.png" /><figcaption>rebalancing a hash based sharding, most of the key have to move</figcaption></figure><h4>4. Consistent Hashing</h4><p>Consistent hashing is an approach used to address the <strong>rebalancing problem</strong> of traditional hash-based sharding. With Hash(key) % N, changing the number of shards causes most keys to map to different shards, requiring a large amount of data to be moved.</p><p>With consistent hashing, both <strong>keys and shards are mapped onto a hash ring</strong>. Each key is assigned to the next shard on the ring according to its hash value.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*GuFFy0MhXsF2LdK3oxCZ3w.png" /><figcaption>Consistent hashing ring</figcaption></figure><p>As shown above, each shard is represented by <strong>S</strong> followed by the shard number, and each key is represented by <strong>K</strong> followed by its key number. Each key is mapped to the <strong>next shard in the ring</strong>.</p><p>The main advantage is that when a shard is <strong>added or removed</strong>, only a relatively small portion of the keys need to be remapped and moved, instead of most of the data. This makes consistent hashing more suitable for systems where the number of shards can change frequently.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*syNFTQh7SxSowFOOB6LtLg.png" /><figcaption>Consistent hashing ring after adding a new shard</figcaption></figure><p>For example, adding <strong>Shard 4</strong> to the ring means that it is hashed between <strong>Shard 3 and Shard 0</strong>. As a result, only <strong>K5</strong> needs to be moved from Shard 0 to Shard 4. This means that only a small portion of the keys needs to be moved.</p><p>However, because the shards are hashed to random positions on the ring, the distance between shards may not be equal. This means one shard may own a much larger range than another, which can lead to uneven data and workload distribution.</p><p>To solve this problem, <strong>virtual nodes</strong> can be used.</p><p>Instead of placing each physical shard only once on the ring, each shard is represented by multiple virtual nodes distributed across different positions as in the following figure:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*GjI6jMkirrXltdoaJzKyBw.png" /></figure><p>Now each physical shard handles multiple smaller ranges instead of one large continuous range. This makes the overall distribution of data and traffic more balanced.</p><p>It also improves what happens when a shard is added or removed. Instead of taking one large range from a single shard, the new shard can take several small ranges from different shards.</p><p>This provides:</p><ul><li>More even distribution of data and workload across shards.</li><li>When adding or removing a shard only s mall potion of data we be moved from each shard in the previous virtual shards and moved to the next shard in the ring.</li><li>These guarantees moving small portion from each shard in rebalancing, instead of moving bigger portions from one shard to another one as it was before the virtual nodes</li></ul><p>A virtual node is not another physical server. It is simply another logical position on the hash ring that belongs to the same physical shard.</p><h3>Query Router</h3><p>After sharding, your application needs to know <strong>which shard it should talk to</strong> for each read or write operation. There are multiple ways to do this, depending on the system’s needs and complexity.</p><p>One of the simplest approaches is to keep the <strong>sharding information in the application layer itself</strong>. For example, if the system operates with multiple tenants or countries and each tenant or country has a separate database, the application can identify the tenant or country from the request and use it to determine which database to connect to.</p><p>Another approach is to put this responsibility on the <strong>database side</strong>. Some databases provide built-in components that act as routers, knowing which shard contains the requested data and, when needed, how to combine data from multiple shards. For example, in MongoDB, the router component is called <strong>mongos</strong>.</p><p>For more complex systems, a <strong>dedicated routing layer</strong> can be placed between the application and database layers. This provides more separation and allows the routing logic to be handled independently from the application. These components can also be responsible for identifying the <strong>sharding strategy</strong>, maintaining shard metadata, and handling <strong>rebalancing</strong> when the distribution of data changes.</p><p>In general, the routing layer needs to know <strong>which shard contains which data</strong> and use this information to route requests to the appropriate shard. Tools such as <strong>ZooKeeper</strong> can be used as a coordination and metadata management system to help manage this information and coordinate changes across the cluster.</p><p>The following are the most common types of query routers:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/998/1*LopH6BQwJWKLoh2XnbcwMA.png" /><figcaption>sharding query router types</figcaption></figure><ul><li>The client connects to any node. Each node holds the sharding metadata and identifies which shard contains the required data.</li><li>The client connects to a query router component, such as <strong>mongos</strong> in MongoDB or <strong>ZooKeeper</strong>, which routes the request to the appropriate shard.</li><li>The client holds the sharding metadata itself and connects directly to the required node.</li></ul><h3>Global and Local Indexes</h3><p>When querying data that is <strong>not the shard key</strong>, there is no information that tells the query router which shard contains the required data. As a result, the query router may need to access <strong>all shards</strong> to look for the requested data.</p><p>For example, if the <strong>shard key is the customer ID</strong> but the query is based on the customer’s email:</p><p>Find the customer where email = customer123@example.com</p><p>The query router would need to access all shards to check whether each shard contains the required email, which can be very expensive.</p><p>To mitigate this problem, one approach is to use a <strong>Global Index</strong> instead of relying only on the normal local indexes within each shard. A global index is maintained across <strong>all shards</strong> and allows the query router to determine which shard contains the required data. Instead of querying every shard, the router first queries the <strong>global index</strong> to identify the relevant shard and then sends the query only to that shard.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3Mee05WBOlWHwhp-z_uVkg.png" /><figcaption>global index to know the shards contain the required data</figcaption></figure><h3>Scaling Reads vs Scaling Writes Mind Map</h3><p>The following mind map is based on my understanding and experience. It is <strong>not a standard strategy that fits all types of systems</strong>. Choosing the right strategy always depends on the system’s requirements, available budget, team skills, priorities, and many other factors. In the end, it is a <strong>subjective decision</strong> based on the specific context.</p><p>However, I hope this mind map can help new learners understand thePokecut_1786267405774 different options available and provide a starting point when thinking about how to scale a system.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*mP0rynDrIQ1iG854Yp-c8A.jpeg" /></figure><p>references:</p><ul><li><strong>Design Data Intensive Applications </strong>Book by Martin Kleppmann and Chris Riccomin</li><li>HelloInterview</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b0760c3ef9af" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Replication — System Design Series]]></title>
            <link>https://medium.com/@mohamed.shaaban.elbay/replication-system-design-series-ii-fd490e706b40?source=rss-163154ddb199------2</link>
            <guid isPermaLink="false">https://medium.com/p/fd490e706b40</guid>
            <category><![CDATA[data-replication]]></category>
            <category><![CDATA[system-design-interview]]></category>
            <category><![CDATA[database]]></category>
            <category><![CDATA[distributed-systems]]></category>
            <category><![CDATA[system-design-concepts]]></category>
            <dc:creator><![CDATA[Mohamed Shaaban]]></dc:creator>
            <pubDate>Tue, 09 Jun 2026 19:01:21 GMT</pubDate>
            <atom:updated>2026-06-09T19:06:13.716Z</atom:updated>
            <content:encoded><![CDATA[<h4><em>painstaking work &amp; not ai content</em></h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ixqnAS99jYYS8KJXKCeOQQ.png" /></figure><h3>Content</h3><p><strong>→ Intro</strong></p><p><strong>→ CAP Theorem</strong></p><p><strong>→</strong> <strong>Implementation of Replication Logs</strong></p><p><strong>→</strong> <strong>Single-Leader Replication</strong></p><ul><li>Synchronous vs Asynchronous Replication</li><li>Problem: Synchronization Between Leader and Followers</li><li>Problem of Asynchronous Replication Lag</li><li>Replication Lag: Common Problems &amp; Solutions</li><li>Setting Up New Followers</li><li>Leader Failure: Failover</li><li>Follower Failure: Catch-up Recovery</li></ul><p><strong>→</strong> <strong>Multi-Leader Replication</strong></p><ul><li>Synchronous vs Asynchronous Replication</li><li>Multi-Leader Across Regions</li><li>Replication Lag: Common Problems &amp; Solutions</li><li>Conflict Detection</li><li>Conflict Resolution Strategies</li></ul><p><strong>→ Leaderless Replication</strong></p><ul><li>Inconsistent Data Problems</li><li>Quorum Reads and Writes</li><li>Using Quorums for Reading and Writing</li><li>Tuning Quorum Configurations</li></ul><p><strong>→ References</strong></p><h3>Intro</h3><p>Replication means keeping copies of the same data on multiple machines connected through a network.</p><p>There are several reasons why systems replicate data, including:</p><ul><li>Keeping data geographically close to users, which reduces access latency.</li><li>Allowing the system to continue working even if some parts fail, which increases availability and durability.</li><li>Scaling the number of machines that can serve read queries, which increases read throughput.</li></ul><p>Most of the time, when we talk about replication, we are referring to database replication rather than the automatic scale-out mechanisms that happen when infrastructure scales.</p><p>Replication is also not an alternative to backups. If data is accidentally deleted or corrupted, that deletion or corruption will also be propagated to the replicas. Backups are still required if you want the ability to restore deleted or old data.</p><p>In many cases, it is cheaper to store backups in an object storage system optimized for infrequently accessed data.</p><p>Although examples in this article will mostly focus on databases, the same replication concepts can be applied to many other types of distributed data stores. For example, similar replication mechanisms can also be designed in systems like a Redis cluster.</p><p>In this article, we will discuss the three main families of replication algorithms used to replicate changes between nodes:</p><ul><li>Single-leader replication</li><li>Multi-leader replication</li><li>Leaderless replication</li></ul><p>Almost all modern databases support one or more of these three replication approaches. Each model comes with its own advantages, disadvantages, and trade-offs, which we will examine in detail.</p><p>Each copy of the database is called a replica, and the main challenge in replication is determining how changes written to one replica are propagated and applied to the other replicas while keeping the data as consistent as possible.</p><p>The replica databases do not necessarily have to use the same database technology. For example, the leader may use a relational database, while the replicas could use either another relational database or even a different type of database such as a document database. However, this setup is usually more complex and often requires customized configuration like for the replication log like the logical replication type or even additional handling at the application level.</p><h3>CAP Theorem</h3><p>Before discussing replication and distributed consistency challenges, it is important to understand a fundamental concept in distributed systems known as the <strong>CAP Theorem</strong>.</p><p>The CAP Theorem describes the trade-offs distributed systems face between:</p><ul><li><strong>Consistency (C):</strong> all nodes see the same data at the same time.</li><li><strong>Availability (A):</strong> every request receives a response, even if some nodes are unavailable.</li><li><strong>Partition Tolerance (P):</strong> the system continues operating despite network failures or communication loss between nodes.</li></ul><p>The theorem states that during a network partition, a distributed system can guarantee either consistency or availability, but not both simultaneously. This trade-off directly influences the design of replication strategies, conflict resolution, and fault tolerance mechanisms in distributed databases.</p><p>For more detailed explanation about this concept, I highly recommend this article <a href="https://medium.com/r?url=https%3A%2F%2Fwww.hellointerview.com%2Flearn%2Fsystem-design%2Fcore-concepts%2Fcap-theorem">CAP Theorem on helloInterview</a></p><h3>Implementation of Replication Logs</h3><p>There are multiple approaches for implementing replication logs, including:</p><ul><li>Statement-Based Replication</li><li>Write-Ahead Log (WAL) Replication</li><li>Logical Replication</li></ul><p>Each approach has its own advantages and disadvantages, which are outside the scope of this article.</p><p>In general, replication can be viewed as a sequence of logs representing the changes applied to the database. Each log entry is associated with a Log Sequence Number (LSN), which represents the offset or position of that change in the replication log and determines the order in which changes are applied to the database.</p><h3>Single-Leader Replication</h3><p>Single-leader replication is the most commonly used replication model in most systems. It is also known as:</p><ul><li>Leader-Based Replication</li><li>Primary-Backup Replication</li><li>Active-Passive Replication</li></ul><p>In this model, all write operations are directed to a single leader replica. The leader then propagates the replication logs (data changes) to the follower replicas.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/698/1*rsOtLVgv4CzFj5NPaGr8jA.png" /><figcaption>Single-leader replication directs all writes to leader, which sends a stream of changes to the follower replicas.</figcaption></figure><p>As shown in the previous diagram, data is written only to the leader replica, while follower replicas receive and apply the changes asynchronously or synchronously depending on the replication configuration.</p><p>Read queries can be served either from the leader replica itself or from the follower replicas, depending on the system’s consistency requirements and configuration.</p><h4><strong>Problem: Synchronization Between Leader and Followers</strong></h4><p>One of the main challenges in single-leader replication is synchronizing follower replicas after a write operation.</p><p>In synchronous replication, the leader waits for one or more replicas to acknowledge the write before responding successfully to the client. While this improves consistency and durability, it can significantly increase write latency, especially when:</p><ul><li>there are many replicas,</li><li>replicas are geographically distributed,</li><li>or network latency is high.</li></ul><h4>Synchronous vs Asynchronous Replication</h4><p>The main advantage of synchronous replication is that follower replicas are guaranteed to have an up-to-date copy of the data consistent with the leader. If the leader suddenly fails, the data remains safely available on the synchronous follower replicas.</p><p>However, synchronous replication has an important drawback: if a synchronous follower stops responding due to a crash, network issue, or any other failure, the leader cannot continue processing new write operations. The leader must wait until the follower becomes available again or acknowledges the write.</p><p>Because of this limitation, making all replicas synchronous is usually impractical. A failure in a single replica could block the entire system from accepting writes, effectively turning that replica into a single point of failure.</p><h4>Solution</h4><p>To reduce write latency and improve availability, many systems use asynchronous replication for some or all follower replicas.</p><p>In asynchronous replication, the leader does not wait for followers to confirm the write before responding to the client. Instead, changes are propagated to replicas in the background, allowing the system to continue processing writes with lower latency and higher availability.</p><p>One common solution is to keep one follower replica synchronous while configuring the remaining replicas to replicate asynchronously. This approach ensures that at least two nodes — the leader and one synchronous follower — always contain the latest committed data, while still maintaining reasonable write performance.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/699/1*Q2W3qPu1l3i-0s5QvtHc4A.png" /><figcaption>Leader-based replication with one synchronous and one asynchronous follower</figcaption></figure><p>Some systems also use a majority-based replication approach. For example, in a cluster of five replicas, the leader may wait synchronously for acknowledgments from three replicas, while the remaining two replicas are updated asynchronously. This provides stronger consistency guarantees without the overhead of waiting for every replica to acknowledge the write.</p><blockquote>Some systems configure all follower replicas to replicate asynchronously. this could be very dangerous, especially when the written but lost data has already been used in other systems or caches, which may be regenerated in the new replica, such as primary keys (PK), causing confusion and incorrect data between users.</blockquote><blockquote>This gives the intuition that it is better to keep at least one synchronous replica.</blockquote><h4>Problem of Asynchronous Replication Lag</h4><p>The trade-off of asynchronous replication is that follower replicas may temporarily lag behind the leader, resulting in stale reads. In addition, if the leader fails before pending changes are replicated, some recently acknowledged writes may be lost.</p><p>When all replicas use asynchronous replication, a leader failure may cause permanent data loss if a new leader is promoted before receiving the latest replication logs from the old leader.</p><p>Before discussing the common problems caused by replication lag and stale data, it is important to understand several concepts commonly used to mitigate these issues.</p><h4>Vector Versions</h4><p>Vector clocks are a distributed versioning mechanism used to track causal relationships between updates across replicas by maintaining a counter for each replica or node.</p><p>For example, a vector clock such as [A:2, B:1] means that replica A performed two updates while replica B performed one update.</p><p>When replicas synchronize, they compare vector clocks to determine whether an update is newer, older, or concurrently modified.</p><p>This helps detect stale data and identify write conflicts between replicas.</p><h4>Session Consistency</h4><p>Session consistency is commonly implemented by routing a user’s requests to the same replica during a session to ensure the user continues seeing their most recent writes.</p><p>The session is typically identified using a session ID, authentication token, cookie, sticky load balancer mapping, or a hash of the user ID.</p><p>Some systems also apply a time threshold after a write operation, during which reads are routed to the leader before switching back to follower replicas.</p><p>This approach helps reduce stale reads caused by replication lag and supports read-your-writes consistency within a user session.</p><h4>Log Sequence Number (LSN)</h4><p>LSN (Log Sequence Number) is a unique monotonically increasing identifier assigned to operations written to the database transaction log.</p><p>In replication systems, replicas compare LSNs to determine:</p><ul><li>which changes have already been replicated,</li><li>the order of operations,</li><li>and whether a replica is behind the leader.</li></ul><h3>Replication Lag: Common Problems &amp; Solutions</h3><p>In this section, we will discuss three common problems caused by replication lag and explore practical solutions using the previously introduced concepts.</p><h4>1. Stale Reads</h4><p>As shown in the following scenario, a user writes data to the leader, and the leader asynchronously propagates updates to follower replicas. However, when the user performs a read operation, the request may be routed to a replica that has not yet received the latest update, resulting in stale data being returned.</p><p>This creates an inconsistency where a user reads outdated information immediately after performing a write.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/761/1*txxjH8ZvX0bdUP0ntLEpCw.png" /><figcaption>Inconsistencies can arise when a user makes a write, followed by a read from a stale replica.</figcaption></figure><h4>Solutions to Stale Reads</h4><p>Several approaches can be used to mitigate stale read issues:</p><p><strong>Read from Leader</strong><br> Route all critical or consistency-sensitive read operations directly to the leader to ensure the most up-to-date data is always returned.</p><p><strong>Read-Your-Writes Consistency</strong><br> Ensure that after a write operation, the user continues reading from the leader for a short period or until replication is expected to complete. This guarantees that the user always sees their own latest updates. And this can be achieved by maintaining the time threshold using sessions.</p><p><strong>Session Consistency</strong><br> Bind the user to a specific replica (or the leader) for the duration of a session so that all reads within that session are served from the same node. This can be implemented using session identifiers, authentication tokens, cookies, sticky load balancers, or user ID hashing.</p><p><strong>LSN-Based Consistency</strong><br> This is a hybrid approach where the system tracks the Log Sequence Number (LSN) of the latest write observed by the user. During subsequent reads, the system ensures that the replica’s LSN is greater than or equal to the stored session LSN before serving the data. If not, the request can be redirected to a more up-to-date replica or the leader.</p><blockquote>note: these 4 solutions are also used in the following problems like monotonic reads &amp; consistent prefix reads</blockquote><h4>2. Monotonic reads Violation</h4><p>When the user reads from a synced replica at the first time and then reads again from a not synced replica, the user may think that the data has disappeared, which causes a confusing experience.</p><p>For example, when a user first reads from a fresh replica and then reads from a stale replica, time appears to go backward.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/772/1*-72B-wxzZ0MtXFs6bObvZA.png" /><figcaption>When a user first reads from a fresh replica, then from a stale replica, time appears to go backward</figcaption></figure><p>The same 4 solutions are fit here as well, to keep the user reads consistent to a specific replica if it is a different user. And we can use the read-your-writes approach or the LSN approach if it is the user writer itself reading.</p><h4>3. Consistent prefix reads</h4><p>If some shards are replicated slower than others, an observer may see the answer before they see the question.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/768/1*DSaepHPH6mFt3DbRoEqDfg.png" /><figcaption>If some shards are replicated slower than others, an observer may see the answer before they see the question</figcaption></figure><p>This can be solved using session consistency to stick the user to read from the same replica each time to see the data in order. It can also be solved by writing related data together on the same shard, so the question and its replies are stored together instead of being distributed across different shards.</p><p>We also use the previously mentioned approaches like vector clocks, or LSN to keep writes ordered and avoid incorrectly concurrent ordering issues.</p><blockquote>As discussed earlier, there are ways for an application to provide a stronger guarantee than the underlying database — for example, by performing certain kinds of reads on the leader or a synchronously updated follower. However, handling these issues in application code is complex and easy to get wrong.</blockquote><h4>Setting Up New Followers</h4><p>The practical steps for setting up a follower vary significantly by database. In some systems, the process is fully automated, while in others it may be a complicated process that needs to be investigated for each system individually.</p><p>For example, in PostgreSQL, a new replica starts from a snapshot backup taken from the leader. The replica then connects to the leader and requests all WAL records starting from the latest LSN. The leader streams those changes, and the replica replays them until it catches up. After that, it continues streaming new updates in real time.</p><h4>Leader failure: Failover</h4><p>When a leader fails, the system detects the failure using timeouts, elects the most up-to-date follower replica as the new leader, and redirects clients to it.</p><p>At the same time, the old leader must step down to avoid conflicts, and when it becomes available again, it joins the system as a follower replica.</p><p>This failover process can happen either automatically or manually.</p><h4>Follower failure: Catch-up recovery</h4><p>Followers store a local log of changes, allowing them to resume from the last processed point and catch up by requesting missing updates from the leader after a crash or disconnection using the LSN.</p><p>However, if a follower lags for too long, the leader must choose between keeping old logs, which may risk disk space usage, or deleting them, which forces the follower to rebuild from a fresh backup.</p><p>So far, we have discussed systems where a single node accepts writes while multiple nodes handle reads. This creates a bottleneck in the system because if the leader node fails for any reason, the system may become unavailable until another follower catches up and is promoted to become the new leader.</p><p>Another limitation is geographical latency. If the leader is located close to a specific region, write operations in that region may be fast, while users in other regions experience higher write latency. In such cases, it may be better to set up a writable node closer to those regions.</p><p>One way to reduce these limitations is to allow writes through multiple nodes, which is known as multi-leader replication, discussed in the following section.</p><h3>Multi-Leader Replication</h3><p>Replication in a multi-leader setup follows the same fundamental principle: each node that processes a write propagates that change to all other nodes. This configuration is known as multi-leader replication or active-active replication. It can also be implicitly described as multi-leader write replication, since writes can originate from any leader.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*TCayBlGMkYawt-2DZhjb1Q.png" /><figcaption>Multi-Leader Replication</figcaption></figure><p>In this model:</p><ul><li>each leader can accept write operations independently.</li><li>each leader simultaneously acts as a follower to the other leaders.</li><li>every processed write must eventually be replicated to the remaining leaders.</li><li>multiple nodes can serve write traffic at the same time.</li></ul><h4>Synchronous vs Asynchronous Replication</h4><p>In synchronous multi-leader replication, a leader cannot complete a write operation until all other replicas acknowledge and synchronize the change.</p><p>This means that:</p><ul><li>every write requires coordination between all leaders,</li><li>network interruptions between nodes can completely block writes,</li><li>a leader cannot commit a write until all replicas are synchronized,</li><li>and write latency increases as the number of leaders increases.</li></ul><p>The situation becomes even more complex when concurrent writes occur on the same data across different leaders.</p><p>However, this design removes the primary advantage of multi-leader replication. At high throughput, enforcing synchronous coordination between multiple leaders becomes impractical because write operations frequently block while waiting for cross-node agreement, which degrades system performance. As a result, this architecture starts behaving similarly to single-leader replication for each write operation.</p><p>For this reason, synchronous multi-leader replication is generally considered equivalent to single-leader replication and is rarely used in real-world systems.</p><p>In contrast, asynchronous multi-leader replication allows each leader to process writes independently without waiting for acknowledgments from other replicas. Replication occurs asynchronously in the background, allowing the system to continue accepting writes even when connectivity between leaders is temporarily disrupted.</p><h4>Multi-Leader across Regions</h4><p>Multi-leader replication can be implemented within the same region or across multiple regions, which is the most common approach, as shown in the following diagram.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/827/1*AH6DoLR7zD7dWlBuWFYA7A.png" /><figcaption>Multi-Leader Replication across multiple regions</figcaption></figure><p>Each region contains one leader replica and one or more read replicas, which may also be distributed across different time zones within the same region.</p><p>The synchronization between the leader and follower replicas inside each region can be considered similar to single-leader replication and follows the same replication rules.</p><h3>Replication Lag: Common Problems &amp; Solutions</h3><p>There is no single perfect fix — systems usually combine several strategies depending on consistency needs.</p><h4>1. Write to Stale Data</h4><p>With multi-leader replication, writes may arrive in the wrong order at some replicas, as shown in the following example.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/852/1*qdYqSXGChPJJADY6zZNykg.png" /><figcaption>With multi-leader replication, writes may arrive in the wrong order at some replicas</figcaption></figure><p>Client B tries to update the same row that Client A has already updated, but Client A’s update has not yet reached the replica, while Client B’s update has already arrived. This leads to Client B updating stale data.</p><h4>2. Write Conflicts</h4><p>When two different users write to two different leaders at the same time while updating the same data, this may cause write conflicts when the two leaders synchronize with each other, as shown in the following example.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/850/1*7utuzqFFxcKE0u3fr6SlCg.png" /><figcaption>A write conflict caused by two leaders concurrently updating the same record</figcaption></figure><p><strong>For example:</strong></p><ul><li>User1 tries to update a title value from A to B on leader 1.</li><li>At the same time, User2 tries to update the same value from A to C on leader 2.</li></ul><h3>Solutions to These Problems</h3><p>The system first needs to detect the conflicts, then apply a resolution strategy.</p><h4><strong>Conflict Detection (First Step in All Solutions)</strong></h4><p>before solving the conflict, replicas must detect that a conflict has occurred using techniques such as version numbers or timestamps.</p><p>After detection, the system can apply a merge algorithm such as CRDTs (Conflict-free Replicated Data Types), or handle the conflict in application code, or use one of the following approaches:</p><h4>1. Conflict Avoidance</h4><p>This can be done by routing each user to a specific leader that is closer to the user’s region. In this way, the same user always writes to the same leader. However, this approach may break if the user changes location.</p><h4>2. Last Write Wins (Discarding Concurrent Writes)</h4><p>In this approach, the latest write based on the timestamp overrides the previous concurrent writes.</p><p>In this approach, the latest write based on the timestamp or vector versions overrides the previous concurrent writes.</p><p>However, this may cause data loss, which may not be acceptable in all cases.</p><blockquote>One example where limited data loss may be acceptable is social media likes, especially on celebrity posts where millions of users react to the same post from different countries and regions. Each follower can write to a leader replica in their region, and later the system can apply LWW or another merging algorithm to merge the data.</blockquote><h4>comparison between single leader and multi leader replicas</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3beKtFoVhRAAg7TR91ozKg.png" /></figure><blockquote>multi-leader replication is often considered dangerous technique that should be avoided if possible since its unexpected problems are a lot.</blockquote><h3>Leaderless Replication</h3><p>In the leaderless replication model, there are no leaders or followers. All replicas can serve both read and write requests. Client requests are distributed among replicas, typically through a load balancer, allowing any replica to receive and process reads and writes.</p><h3>Inconsistent Data Problems</h3><p>When a replica receives a write request, it propagates the update to the other replicas asynchronously. If replication were synchronous, the system would behave similarly to a single-leader architecture, where writes must wait for all replicas before completing. This asynchronous replication model is commonly used in databases such as DynamoDB.</p><p>However, if a replica is unavailable when an update occurs, it will miss that update and become stale. As a result, a client reading from that replica may receive outdated data, as shown in the following diagram.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/796/1*ZQ1CbIoFUu7Ioe1VIGn35Q.png" /><figcaption><em>Writing to a majority of replicas, reading from a majority, and forwarding the latest value to a replica that was unavailable during the write</em></figcaption></figure><h4>How can we solve this problem?</h4><p>Since there is no designated leader, as in multi-leader replication, a common solution is to use <strong><em>quorums</em></strong>. The idea is to perform reads and writes on a majority of replicas. By writing to multiple replicas and reading from multiple replicas, the system guarantees that the read operation will overlap with at least one replica that contains the most recent version of the data. This greatly reduces the chance of returning stale data and helps maintain consistency across replicas.</p><h4>Using Quorums for Reading and Writing</h4><p>Assume there are <strong>n</strong> replicas. A write operation is considered successful only after it has been acknowledged by <strong>w</strong> replicas, and a read operation queries <strong>r</strong> replicas. For example, if <strong>n = 3</strong>, <strong>w = 2</strong>, and <strong>r = 2</strong>, a write must be stored on at least two replicas before it succeeds, and a read must retrieve data from at least two replicas.</p><p>As long as <strong>w + r &gt; n</strong>, every read is guaranteed to overlap with at least one replica that contains the latest version of the data. This overlap greatly reduces the chance of returning stale data. Reads and writes that satisfy these conditions are known as <strong>quorum reads</strong> and <strong>quorum writes</strong>.</p><p>In Dynamo-style databases, the values of <strong>n</strong>, <strong>w</strong>, and <strong>r</strong> are configurable. A common configuration is to use an odd number of replicas, such as <strong>3</strong> or <strong>5</strong>, and set <strong>w = r = (n + 1) / 2</strong>. These balances read and write performance while maintaining good consistency guarantees.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/777/1*6tocA9cdxm7jOZaPCOUlbw.png" /><figcaption><em>If w + r &gt; n, at least one of the r replicas you read from must have seen the most recent successful write</em></figcaption></figure><p>Different workloads may require different configurations. For example, applications with many reads and few writes may choose <strong>w = n</strong> and <strong>r = 1</strong>. This makes read operations very fast because only one replica needs to be queried. However, it also means that a single replica failure can prevent write operations from succeeding.</p><p><em>The quorum condition, w + r &gt; n, allows the system to tolerate unavailable nodes as follows:</em></p><ul><li>if <em>w &lt; n</em>, we can still process writes if a node is unavailable.</li><li>If <em>r &lt; n</em>, we can still process reads if a node is unavailable.</li><li>With <em>n = 3, w = 2, r = 2</em>, we can tolerate one unavailable node.</li><li>With <em>n = 5, w = 3, r = 3</em>, we can tolerate two unavailable nodes</li></ul><p>the sets of nodes used by the read and write operations overlap in at least one node</p><p>The parameters w and r allow you to adjust the probability of stale values being read but it’s wise to not take them as absolute guarantees. Even with the <em>quorum </em>approach<em>, </em>some problems may still happen such as concurrent reads missed data, and the data rebalancing when node is down.</p><h4><strong>Tuning Quorum Configurations</strong></h4><ul><li><strong>Higher <em>w</em></strong> → stronger consistency &amp; durability, but slower writes.</li><li><strong>Lower <em>w</em></strong> → faster writes, but higher risk of stale/lost data.</li><li><strong>Higher <em>r</em> </strong>→ fresher reads, but slower reads.</li><li><strong>Lower <em>r</em></strong> → faster reads, but higher chance of stale reads.</li><li><strong>Majority quorum </strong>→ (e.g., n=5, w=3, r=3) provides a good balance of consistency, availability, and performance.</li></ul><p>references:</p><ul><li><strong>Design Data Intensive Applications </strong>Book by Martin Kleppmann and Chris Riccomin</li></ul><p>Please feel free to share your constructive feedback with me at <a href="https://www.linkedin.com/in/mohamed-shaaban-4b8019178/">LinkedIn</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=fd490e706b40" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Data Modeling — System Design Series]]></title>
            <link>https://medium.com/@mohamed.shaaban.elbay/data-modeling-system-design-series-e889b3c1fa9f?source=rss-163154ddb199------2</link>
            <guid isPermaLink="false">https://medium.com/p/e889b3c1fa9f</guid>
            <category><![CDATA[database]]></category>
            <category><![CDATA[distributed-systems]]></category>
            <category><![CDATA[system-design-concepts]]></category>
            <category><![CDATA[data-modeling]]></category>
            <dc:creator><![CDATA[Mohamed Shaaban]]></dc:creator>
            <pubDate>Tue, 28 Apr 2026 09:40:23 GMT</pubDate>
            <atom:updated>2026-04-29T14:10:08.326Z</atom:updated>
            <content:encoded><![CDATA[<h4>Painstaking work — not an ai content</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/0*T3LyYdS1fbi5Iceg" /></figure><p><strong>Table of Content:</strong></p><ul><li>Quick Intro</li><li>Relational Data Model Representation</li><li>Document Data Model Representation</li><li>The One-to-Many relationship</li><li>The One-to-Many relationship</li><li>Schema Flexibility in Document Data Model</li><li>When to Use Each Model</li><li>Graph data model</li><li>Graph Representation (Cypher Example)</li><li>Equivalent Representation in SQL</li><li>Storage and retrievals</li><li>Log Structured Merge tree — LSM tree</li><li>Challenges in LSM tree Design</li><li>The LSM tree structure and data flow</li><li>Bloom Filter</li><li>LSM tree vs B-tree</li><li>Columnar Databases</li><li>Star Model</li></ul><h4>Quick Intro</h4><p>Relational databases like SQL come from an earlier era. As software systems evolved, new bottlenecks appeared. Like any invention, every solution introduces its own limitations — there is no final solution, only tradeoffs that must be considered when designing or improving systems.</p><p>Each topic in this article could be explored in much more detail — covering document, relational, graph, and columnar databases, as well as their internals. However, the goal here is to highlight the most common tradeoffs to consider when choosing a database model.</p><p>This article is mainly a summary of Chapters 3 and 4 of the book Designing Data-Intensive Applications, with additional insights from other resources.</p><p>We will start by designing a LinkedIn profile using both the relational data model and the document data model.</p><h4>Relational Data Model Representation</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*lUI4TDas-k1pvd9nyDbL3A.png" /><figcaption>Using a relational schema to represent a LinkedIn profile</figcaption></figure><pre>SELECT * FROM users<br>LEFT JOIN experience ON users.id = experience.user_id<br>LEFT JOIN education ON users.id = education.user_id<br>LEFT JOIN user_skills ON users.id = user_skills.user_id<br>LEFT JOIN skills ON user_skills.skill_id = skills.id<br>WHERE users.id = 1234;</pre><p>As we can see, in the relational schema used to represent LinkedIn profiles, we need to perform multiple joins across five tables to fetch a single profile’s data. This can become more complex and slower over time as the system grows which requires to maintain our query plan looking at the used indexes and the join types.</p><h4>Document Data Model Representation</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*6zjC3cfuYo_ByLpj_Nz27w.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rWnImNvz3lA6MclvQXz-Vg.png" /><figcaption>Representing a LinkedIn profile as a JSON document</figcaption></figure><ul><li>In the document data model, we can fetch a single document to retrieve one profile’s data using a simple, direct query.</li><li>We can notice that the document is denormalized and contains all the required data. This is better for read operations, but it introduces challenges when updating data. For example, if organizations are referenced across multiple documents and an organization’s name changes, we would need to update every document that contains that data.<br> <strong>Deduction:</strong> we need to carefully consider the impact of denormalization when choosing it.</li><li>In relational databases, normalization helps reduce duplication but requires joins. In document data models, some systems do not support joins in their query language, so joins are handled at the application level, often leading to the N+1 query problem.</li></ul><h4>The One-to-Many relationship</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*834bcCL6PpxYl-F3HnDh-w.png" /><figcaption>one-to-few tree structured data model fits the best with document databases</figcaption></figure><p>If we represent a LinkedIn profile document as a shape, it can be modeled as a tree. A user has jobs, educations, and basic information such as first name and last name. Since a user typically has a limited number of jobs and educations, this structure fits well.</p><p>Document data models work best when the entire document is fetched at once, especially if it is small and contains few references. This aligns naturally with one-to-few relationships, like a tree structure.</p><p>However, one-to-many relationships can become problematic, as they may increase document size or require more joins. If the document grows too large (for example, comments on a celebrity post), fetching it becomes inefficient. Multiple layers of referenced data can also add complexity.</p><p><strong>Deduction:</strong> documents should remain small, with limited references to other documents.</p><h4>The Many to Many relationship</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-MPXcoKqXhAmQY4iBpfZpQ.png" /><figcaption>many-to-many relationship with relational model</figcaption></figure><p><strong>In relational databases</strong>, many-to-many relationships are typically handled using a pivot (junction) table that stores the relationship between entities, such as users and organizations. Joins are highly optimized in relational models, which makes many-to-many relationships efficient in practice.</p><p><strong>In the document data model</strong>, the same relationship can be represented using arrays. For example, a user document can contain multiple jobs, where each job is an object inside an array and may reference another document (such as an organization). Similarly, other documents can also contain arrays referencing related entities. This approach is similar to representing data in code or JSON format.</p><p>However, if we try to normalize the data (similar to relational models), querying from both sides in document databases becomes challenging. We may end up reintroducing joins, which some document databases do not support efficiently.</p><p>Using a denormalized structure like the following:</p><pre>{<br>  &quot;user_id&quot;: 251,<br>  &quot;first_name&quot;: &quot;Barack&quot;,<br>  &quot;last_name&quot;: &quot;Obama&quot;,<br>  &quot;positions&quot;: [<br>    { &quot;start&quot;: 2009, &quot;end&quot;: 2017, &quot;job_title&quot;: &quot;President&quot;, &quot;org_id&quot;: 513 },<br>    { &quot;start&quot;: 2005, &quot;end&quot;: 2008, &quot;job_title&quot;: &quot;US Senator&quot;, &quot;org_id&quot;: 514 }<br>  ]<br>}</pre><p>makes reads simpler and more efficient. However, as mentioned before it introduces challenges for writes — for example, if an organization’s data changes, multiple documents may need to be updated.</p><h4>Schema Flexibility in Document Data Model</h4><p>Another perspective we should consider in <strong>document database</strong>s is <strong>schema flexibility</strong>. Since data is stored in a JSON-like format, it provides a well-known advantage: flexible schema design. However, this flexibility also comes with tradeoffs and limitations.</p><p>The structure between documents is not strict. For example, we might initially store a single name field for a user and later decide to split it into first_name and last_name.</p><p>We can compare this behavior in relational and document models:</p><p><strong>In relational databases</strong>, schema changes are straightforward and efficient, even if they require updating existing rows:</p><pre>ALTER TABLE users ADD COLUMN first_name text DEFAULT NULL;<br>UPDATE users SET first_name = split_part(name, &#39; &#39;, 1);</pre><p><strong>In document databases</strong>, this change is more complex. The application must handle both the old and new schemas on reads, which increases code complexity. To manage this, we often migrate data gradually — either on read or in the background:</p><pre>if (user &amp;&amp; user.name &amp;&amp; !user.first_name) {<br>  // Documents written before Dec 8, 2023 don&#39;t have first_name<br>  user.first_name = user.name.split(&quot; &quot;)[0];<br>}</pre><p>This approach ensures compatibility but adds additional logic to the application layer.</p><blockquote>Schema flexibility in NoSQL does not always require switching away from relational databases. for simpler use cases, SQL systems like PostgreSQL with JSONB can be sufficient, offering both flexibility and strong indexing optimizations such as inverted indexes — so it’s important to think carefully before deciding.</blockquote><h3>When to Use Each Model</h3><p><strong>Use the Document Model when:</strong></p><ul><li>Your schema is flexible or frequently changing</li><li>Data follows one-to-few tree-like structure</li><li>You usually load everything from a single document</li><li>There are few or no deeply nested references</li><li>Constraints and validations can be handled in application code</li></ul><p><strong>Use the Relational Model when:</strong></p><ul><li>Data has complex relationships (closer to a graph than a tree)</li><li>You need joins between entities</li><li>Entities must be referenced and managed independently</li><li>You care about consistency and data integrity</li></ul><blockquote>One of the most significant features of NoSQL databases is <strong>sharding</strong>, which distributes data across multiple nodes. While this improves scalability, it also makes atomic operations across shards difficult, often pushing systems toward <strong>eventual consistency</strong>.</blockquote><blockquote>From the perspective of the CAP theorem, sharding forces a trade-off. Systems must choose between <strong>CP (Consistency and Partition tolerance)</strong> — sacrificing availability to maintain accurate data — or <strong>AP (Availability and Partition tolerance)</strong> — accepting stale or inconsistent data to ensure uptime.</blockquote><blockquote>It’s also important to note that even without sharding, consistency can still be weakened if <strong>asynchronous replication</strong> is used to sync data between replicas.</blockquote><h3>Graph Data model</h3><p>As we saw earlier, the type of relationships in your data is a key factor in choosing the right model. If your application mostly has <strong>one-to-many</strong> relationships (tree-structured data), the <strong>document model</strong> works well. And for <strong>many-to-many </strong>relationship it may be better in <strong>relational model</strong>, but when <strong>many-to-many</strong> relationships become common and <strong>complex with multilevel queries</strong>, modeling the data as a <strong>graph</strong> becomes more natural.</p><p>In graph models, data is represented as <strong>vertices (nodes)</strong> and <strong>edges (relationships)</strong>. This makes it easier to express and query complex connections.</p><p>Graph data models excel at representing and analyzing complex, interconnected data. They are especially useful when relationships are as important as the data itself.</p><p>Typical use cases include:</p><ol><li><strong>Social networks:</strong> modeling people and their relationships (e.g., friendships, follows)</li></ol><p>For example, Facebook uses a large graph to connect users, posts, events, and locations through relationships like friendships, comments, and interactions like the following:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_DyMeee4CbNYheMwswf6Kw.png" /><figcaption>Graph-structured data (boxes represent vertices, arrows represent edges)</figcaption></figure><p><strong>2. Web graphs:</strong> linking web pages to support ranking, navigation and identify important pages to improve search relevance.</p><p>For example, Search engines also rely on knowledge graphs to understand entities such as people, places, and organizations to get insights about data like:</p><ul><li>Targeted advertising (e.g., identifying users in Cairo interested in specific topics)</li><li>Trend detection and demand analysis</li><li>Recommendation systems based on user behavior and connections</li></ul><p>3. <strong>Transportation networks:</strong> modeling routes for shortest path and optimization problems</p><p>This ability to model and query relationships directly makes graph databases a strong choice for <strong>insight-driven </strong>applications to represent <strong>relation</strong> between <strong>totally different entities</strong>.</p><h4>Graph Representation (Cypher Example)</h4><pre>CREATE<br>  (america:Location {name: &#39;North America&#39;, type: &#39;continent&#39;}),<br>  (usa:Location {name: &#39;United States&#39;, type: &#39;country&#39;}),<br>  (idaho:Location {name: &#39;Idaho&#39;, type: &#39;state&#39;}),<br>  (lucy:Person {name: &#39;Lucy&#39;}),<br><br>  (idaho)-[:WITHIN]-&gt;(usa),<br>  (usa)-[:WITHIN]-&gt;(america),<br>  (lucy)-[:BORN_IN]-&gt;(idaho);</pre><p>This query creates nodes (vertices) for locations and a person, then defines relationships (edges) between them:</p><ul><li>WITHIN represents a hierarchical relationship between locations</li><li>BORN_IN connects a person to a location</li></ul><p>This forms a graph structure where different entities are directly connected through relationships, such as location-to-location and person-to-location, and so on.</p><pre>MATCH<br>  (person:Person)-[:BORN_IN]-&gt;()-[:WITHIN*0..]-&gt;(:Location {name: &#39;United States&#39;}),<br>  (person)-[:LIVES_IN]-&gt;()-[:WITHIN*0..]-&gt;(:Location {name: &#39;Europe&#39;})<br>RETURN person.name</pre><p>This query searches for people who:</p><ul><li>Were born in the United States (or any location within it)</li><li>Currently live in Europe (or any location within it)</li></ul><p>The *0.. means traversing multiple levels in the hierarchy (e.g., state → country → continent).</p><h4>Equivalent Representation in SQL</h4><pre>CREATE TABLE vertices (<br>    vertex_id INTEGER PRIMARY KEY,<br>    label TEXT,<br>    properties JSONB<br>);<br><br>CREATE TABLE edges (<br>    edge_id INTEGER PRIMARY KEY,<br>    tail_vertex INTEGER REFERENCES vertices(vertex_id),<br>    head_vertex INTEGER REFERENCES vertices(vertex_id),<br>    label TEXT,<br>    properties JSONB<br>);<br><br>CREATE INDEX edges_tails ON edges (tail_vertex);<br>CREATE INDEX edges_heads ON edges (head_vertex);</pre><p>This schema represents a graph using relational tables:</p><ul><li>vertices table stores nodes (e.g., people, locations)</li><li>edges table stores relationships between nodes</li></ul><pre>WITH RECURSIVE<br><br>-- in_usa: set of vertex IDs of all locations within the United States<br>in_usa(vertex_id) AS (<br>    SELECT vertex_id<br>    FROM vertices<br>    WHERE label = &#39;Location&#39; AND properties-&gt;&gt;&#39;name&#39; = &#39;United States&#39;<br><br>UNION<br><br>SELECT edges.tail_vertex<br>    FROM edges<br>    JOIN in_usa ON edges.head_vertex = in_usa.vertex_id<br>    WHERE edges.label = &#39;within&#39;<br>),<br><br>-- in_europe: set of vertex IDs of all locations within Europe<br>in_europe(vertex_id) AS (<br>    SELECT vertex_id<br>    FROM vertices<br>    WHERE label = &#39;Location&#39; AND properties-&gt;&gt;&#39;name&#39; = &#39;Europe&#39;<br><br>UNION<br><br>SELECT edges.tail_vertex<br>    FROM edges<br>    JOIN in_europe ON edges.head_vertex = in_europe.vertex_id<br>    WHERE edges.label = &#39;within&#39;<br>),<br><br>-- born_in_usa: people born in the US<br>born_in_usa(vertex_id) AS (<br>    SELECT edges.tail_vertex<br>    FROM edges<br>    JOIN in_usa ON edges.head_vertex = in_usa.vertex_id<br>    WHERE edges.label = &#39;born_in&#39;<br>),<br><br>-- lives_in_europe: people living in Europe<br>lives_in_europe(vertex_id) AS (<br>    SELECT edges.tail_vertex<br>    FROM edges<br>    JOIN in_europe ON edges.head_vertex = in_europe.vertex_id<br>    WHERE edges.label = &#39;lives_in&#39;<br>)<br><br>-- final result: people born in US AND living in Europe<br>SELECT vertices.properties-&gt;&gt;&#39;name&#39;<br>FROM vertices<br>JOIN born_in_usa ON vertices.vertex_id = born_in_usa.vertex_id<br>JOIN lives_in_europe ON vertices.vertex_id = lives_in_europe.vertex_id;</pre><p>This SQL query simulates graph traversal using recursive queries:</p><ul><li>WITH RECURSIVE is used to traverse hierarchical relationships (like WITHIN*0..)</li><li>It builds sets of locations within the US and Europe</li><li>Then finds people born in the US and living in Europe</li><li>Finally, it returns the matching people</li></ul><p>As shown, representing the same graph structure in SQL is much more complex. The queries require multiple CTEs and recursive logic, whereas in graph databases, the same result can be achieved with just two lines using Cypher.</p><h3>Storage and retrievals</h3><p>We will walk through two common types of trees used in databases to understand how data is written and retrieved from disk into memory, and how this impacts read and write performance, helping us choose the right one based on system workload.</p><h4>1. Log Structured Merge tree — LSM tree</h4><p>The basic idea of an LSM tree can be understood from a simple file-based approach to storing data.</p><p>We can think of storing user input by appending data into files sequentially. When we need to read a specific item, we scan through the file until we find the required data. However, this becomes inefficient as the file grows.</p><p>To improve this, we can use an in-memory data structure such as a HashMap to quickly check whether a value exists without scanning the entire file. This structure (or any sorted in-memory structure that allows fast lookup) is called a “<strong>MemTable”</strong>.</p><p>To further optimize performance, the MemTable does not only store the keys — it can also store the offset (location) of each key inside the log files on disk. In some designs, it may even store the values themselves, allowing faster reads without always accessing disk.</p><p>This way, when a read request comes in, the system first checks the MemTable in memory. If the key exists, it can directly locate the data in the log file using the stored offset, significantly reducing disk reads.</p><p>The following diagram shows a MemTable storing the offset in log files for each key.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*CAUycAVyTFfyoRl2X3yVUA.png" /><figcaption>Storing a log of key-value pairs in a CSV-like format, indexed with an in-memory hash map</figcaption></figure><h4>Challenges in This Design</h4><p>Although the LSM-based approach improves write performance, it introduces several challenges as the system scales:</p><h4>1. Memtable Growth and Memory Limitations</h4><p>As data continues to grow, the MemTable may eventually become too large to fit entirely in memory.</p><p><strong>Suggested solution:</strong><br> To handle this, the MemTable is periodically flushed to disk once it reaches a predefined size threshold. This prevents uncontrolled memory usage and ensures the system remains stable under continuous writes.</p><h4>2. Large Log Files and Disk Usage</h4><p>Over time, append-only log files can grow significantly, leading to excessive disk usage. Additionally, these files may contain redundant or outdated data.</p><p><strong>Suggested solution:</strong><br> A background process can periodically merge log files and remove redundant entries. This process reduces disk space usage and improves storage efficiency. This mechanism is generally known as <strong>compaction</strong>, and it will be discussed in more detail later.</p><h4>3. Lack of Efficient Segment Search</h4><p>Because the data is not inherently sorted, queries are inefficient. The absence of ordering requires scanning large portions of the dataset to locate specific keys, resulting in poor performance for point lookups and range queries.</p><p><strong>Suggested solution:</strong><br>To solve this, data should be stored in a sorted structure to enable efficient key access and support range queries. This is achieved by introducing an indexing mechanism that maintains sorted data.</p><p>This leads to the concept of <strong>Sorted Strings Tables (SSTables)</strong>, where data is stored in sorted order on disk. SSTables form the foundation for efficient reads and range queries in LSM-based systems.</p><p>The following diagram illustrates the transition toward SSTables.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ci3jEQR5RaL8dJcS1FA6uQ.png" /><figcaption>An SSTable with a sparse index, allowing queries to jump to the right block</figcaption></figure><p>An <strong>SSTable (Sorted Strings Table)</strong> is like organizing keys into ranges. For each key, the value can be either a list of sorted values or offsets that point to the location in the page containing the data.</p><p>To support efficient access, a data structure such as a B-tree (or any similar structure) can be used to store and organize the data in front of each key, making it easy to reach and overwrite when needed.</p><h4>The LSM tree structure and data flow</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*WRPEMeSrvCUuX8XVvTUwdw.png" /></figure><ol><li>When a write comes in, add it to an in-memory ordered map data structure, such as a red–black tree, skip list, or trie. With these data structures, you can insert keys in any order, look them up efficiently, and read them back in sorted order. This in-memory data structure is called the MemTable.</li><li>When the MemTable gets bigger than a certain threshold — typically a few megabytes — write it out to disk in sorted order as an SSTable file. We call this new SSTable file the most recent segment of the database, and it is stored as a separate file alongside the older segments. Each segment has a separate index of its contents. While the new segment is being written out to disk, the database can continue writing to a new memtable instance, and the old memtable’s memory is freed when the writing of the SSTable is complete.</li><li>To read the value for a key, first try to find the key in the MemTable and the most recent on-disk segment. If it’s not there, keep looking in the next-older segment until you either find the key or reach the oldest segment. If the key does not appear in any of the segments, it does not exist in the database.</li><li>From time to time, run a merging and compaction process in the background</li><li>Merging segments works similarly to the merge sort algorithm. start reading the input files side by side, look at the first key in each file, copy the lowest key (according to the sort order) to the output file, and repeat. If the same key appears in more than one input file, keep only the more recent value.</li><li>This produces a new merged segment file, also sorted by key, with one value per key, and it uses minimal memory because we can iterate over the SSTables one key at a time.</li><li>To ensure that the data in the Memtable is not lost if the database crashes, the storage engine keeps a separate log on disk to which every write is immediately appended to the WAL(Write-Ahead-Log). This log is not sorted by key, but that doesn’t matter, because its only purpose is to restore the MemTable after a crash. Every time the MemTable gets written out to an SSTable, the corresponding part of the log can be discarded.</li></ol><h4>Problem: Slow Reads in LSM Storage</h4><p>With LSM storage, reading a key can be slow in certain cases. If a key was last updated a long time ago, it may exist in an older segment file. This requires checking multiple segments, starting from the most recent and moving toward the oldest.</p><p>Similarly, attempting to read a key that does not exist can also be inefficient, since the storage engine must still check several segment files before confirming its absence.</p><p>To mitigate this issue, a <strong>Bloom Filter</strong> is introduced.</p><h3>Bloom Filter</h3><p>A <strong>Bloom Filter</strong> is a fast but approximate way of checking whether a particular key appears in a specific SSTable.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*8iRMvrfpFg8e922Vkembnw.png" /><figcaption>bloom filter</figcaption></figure><p>In this example, the Bloom filter is used to quickly check whether a key might exist in an SSTable.</p><p>First, existing keys such as <strong>“handbag”</strong> and <strong>“handoff”</strong> are passed through multiple hash functions.</p><ul><li><strong>“handbag”</strong> generates the indexes <strong>2, 9, and 4</strong>, so the bits at these positions are set to 1.</li><li><strong>“handoff”</strong> generates the indexes <strong>9, 15, and 5</strong>, and those bits are also set to 1.</li></ul><p>When querying a key like <strong>“handheld”</strong>, the same process is applied.</p><ul><li>It generates the indexes <strong>6, 11, and 2</strong>.</li></ul><p>The system then checks the bits at these positions in the Bloom filter:</p><ul><li>If <strong>any bit is 0</strong>, the key definitely does <strong>not exist</strong>.</li><li>If <strong>all bits are 1</strong>, the key <strong>may exist</strong>.</li></ul><p>In this case, the bits at indexes <strong>6, 11, and 2</strong> are checked, and since at least one of them is 0, we can conclude that <strong>&quot;handheld&quot; is not present</strong>, without accessing the SSTable.</p><p>This avoids unnecessary disk reads and improves lookup performance.</p><p>This technique is not only used in databases, but also in many other use cases where we need to check whether an element belongs to a set. It helps reduce unnecessary disk reads and is widely used in systems such as search engines, CDNs, and Redis caching layers.</p><blockquote>To achieve a false-positive probability of <strong>1% </strong>when lookup a key, you need to allocate <strong>10 bits</strong> of Bloom filter space for every key in the SSTable.</blockquote><blockquote>For every additional <strong>5 bits per key</strong>, the false-positive probability is reduced by approximately <strong>tenfold</strong>.</blockquote><h4>2. B-Tree</h4><p>We have previously discussed B-Trees in detail in another article, so you may refer to it for a deeper look at the B-Tree structure section.</p><h4>LSM tree vs B-tree</h4><p>As a rule of thumb, LSM-trees are better suited for write-heavy applications, whereas B-trees are faster for reads</p><ol><li>B-tree updates actual values on writes. LSM tree appends only to the SSTable and updates values on merging in the background which makes it faster in write. Storage engines sometimes blend characteristics of both approaches — for example, by having multiple B-trees and merging them LSM-style.</li><li>In a B-tree, looking up a key involves reading one page at each level. Since the number of levels is usually quite small, reads from a B-tree are generally fast and have predictable performance. In an LSM storage engine, reads often have to check several SSTables at different stages of compaction, but Bloom filters help reduce the number of disk I/O operations required. Both approaches can perform well, and which is faster depends on the details of the storage engine and the workload.</li><li>Range queries are simple and fast on B-trees, as they can make use of the sorted structure of the tree. On LSM storage, range queries can also take advantage of the SSTable sorting, but they need to scan all the segments in parallel and combine the results. Bloom filters don’t help for range queries (since you would need to compute the hash of every possible key within the range, which is impractical), making range queries more expensive than point queries in the LSM approach.</li><li>High write throughput can cause latency spikes in a log-structured storage engine if the MemTable fills up. This happens if data can’t be written out to disk fast enough, perhaps because the compaction process cannot keep up with incoming writes. Many storage engines, including <em>RocksDB</em>, apply backpressure in this situation: they suspend all reads and writes until the <em>memtable</em> has been written out to disk</li></ol><p>Most of the NoSQL databases use the LSM tree strcutere while the relational databases such SQL databases uses the Btree structure.</p><blockquote>This can give an intuition for why NoSQL databases are often used in logging systems such as those in ride-hailing or food delivery platforms for tracking drivers. These systems require a flexible schema for logs, high write throughput, and horizontal scalability. NoSQL databases with LSM-tree storage engines are well-suited for this because they are optimized for write-intensive workloads and typically support sharding by default. This makes them a strong fit for handling millions of write operations per second in large-scale distributed systems.</blockquote><h3>Columnar Databases</h3><p>There is a general rule in database design: systems are typically optimized for either <strong>OLTP (Online Transaction Processing)</strong> or <strong>OLAP (Online Analytical Processing)</strong>.</p><p><strong>OLTP systems</strong> are designed to handle a large number of small, fast transactions concurrently. These are the systems we interact with daily, such as banking systems or HR platforms. In OLTP, operations usually involve reading or updating a small number of rows at a time.</p><p>In <strong>row-oriented databases</strong>, data is stored row by row in disk pages. This means that even when a query needs only a few columns, the system still reads entire rows across multiple pages. As a result, unnecessary data is loaded into memory.</p><p>For example, in an HR system, a query like <em>“find the highest salary per department”</em> touches only a small subset of columns (`department_name`, `salary`) but still scans many rows in a traditional row-based storage model.</p><p>This is illustrated in the diagram, where the required columns are highlighted in red and green, showing how multiple pages are still loaded even though only a small portion of the data is actually needed.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*4XqenxaU81Ziu54s3Wn6Aw.png" /><figcaption>row database stores rows of HR system into set of rows per pages</figcaption></figure><p>As shown in the diagram, we only need two columns across multiple pages to compute the salary for each row. This is where the idea of <strong>columnar databases</strong> emerges, especially as such analytical queries have become more common in the last decade due to the massive growth of data.</p><p>In <strong>columnar databases</strong>, data is stored column by column in disk pages instead of row by row. This storage model is particularly useful for analytical workloads that primarily operate on a subset of columns rather than entire rows.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*UwMr0SpNcE8jxY_UsMeUqg.png" /><figcaption>columns are stored in pages in columnar database pages</figcaption></figure><p>Now as shown in the diagram, for a query like <em>finding the maximum salary per department</em>, a columnar database only needs to access two pages: the <strong>department column page</strong> and the <strong>salary column page</strong>, making the operation significantly more efficient.</p><p>This is why columnar databases are not suitable for everyday OLTP workloads. A single row update would require modifying multiple column files across different pages, which becomes inefficient for frequent small transactions. Instead, they are mainly used in <strong>data warehouse systems</strong>, such as Google BigQuery and Snowflake, where analytical queries dominate.</p><h4>Star Model</h4><p>The <strong>star schema</strong> is a data model that organizes information into a central fact table connected to multiple dimension tables.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*l00gtk5vpnjB4ZBkJtvEsA.png" /><figcaption>star model — fact table at the middle and dimension tables</figcaption></figure><p>Snowflake uses this model internally to enable a “one big table” approach, but in a more advanced form. Instead of relying heavily on multiple dimension tables, it can work more directly with columns, since it is a columnar database.</p><p>There is much more to explore in columnar databases, as well as in other database types — they are large, deep topics with many details. Here, we only covered a high-level overview to help understand when and why to use each type when designing a system.</p><p>next in the series: Replication &amp; Sharding</p><p><strong><em>Resources</em></strong></p><ul><li><a href="https://www.oreilly.com/library/view/designing-data-intensive-applications/9781098119058/">Design Data Intensive Applications</a> by Martin Kleppmann &amp; Chris Riccomini</li><li>Amr ElHelw <a href="https://www.youtube.com/playlist?list=PLE8kQVoC67PzGwMMsSk3C8MvfAqcYjusF">Database Internals Series</a></li><li><a href="https://medium.com/@mohamed.shaaban.elbay/cracking-the-query-plan-indexes-6965617ab49b">Cracking The Query Plan</a> by Me</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e889b3c1fa9f" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Cracking The Query Plan (Indexes)]]></title>
            <link>https://medium.com/@mohamed.shaaban.elbay/cracking-the-query-plan-indexes-6965617ab49b?source=rss-163154ddb199------2</link>
            <guid isPermaLink="false">https://medium.com/p/6965617ab49b</guid>
            <category><![CDATA[query-optimization]]></category>
            <category><![CDATA[sql]]></category>
            <category><![CDATA[indexing]]></category>
            <category><![CDATA[database]]></category>
            <category><![CDATA[b-tree]]></category>
            <dc:creator><![CDATA[Mohamed Shaaban]]></dc:creator>
            <pubDate>Wed, 04 Dec 2024 20:22:55 GMT</pubDate>
            <atom:updated>2024-12-22T09:13:47.624Z</atom:updated>
            <content:encoded><![CDATA[<p>In this article, I will guide you through different types of the most commonly used indexes, helping you understand their effects on query enhancement and how they work internally. You may also want to check the introduction for an overview of database storage.</p><p>the intro: <a href="https://medium.com/@mohamed.shaaban.elbay/cracking-the-query-plan-intro-c24f5b9173f4">https://medium.com/@mohamed.shaaban.elbay/cracking-the-query-plan-intro-c24f5b9173f4</a></p><p>note that all examples are working on 5 million rows I generated before.</p><p><strong>Covered Topics:</strong></p><ul><li>B Tree Index</li><li>Composite Index</li><li>Hash Index</li><li>Covering Index</li><li>BitMap</li><li>Index Intersection</li><li>Index Union</li><li>Index Intersection using bitMap</li><li>Index Union using bitMap</li><li>General Tips</li><li>Tips for Index Usage in Joins</li><li>Tips for Index Usage in Sorting</li></ul><h3>B Trees Index</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/504/1*Lp03fZNbv7cjBRhzsRlshA.png" /><figcaption>figure 1.0 — B+ tree example</figcaption></figure><h4>B Tree Structure</h4><p>As shown in the above image figure 1.0 In a B+ tree, data is organized hierarchically, with each node acting as the midpoint (or separator) for the values of its child nodes.</p><ul><li><strong>Right Subtree:</strong> All values in the right subtree are greater than the value in the parent node.</li><li><strong>Left Subtree:</strong> All values in the left subtree are smaller than the value in the parent node.</li></ul><h4><strong>Leaf Nodes and Data Storage</strong></h4><p>The actual data is stored in the <strong>leaf nodes</strong>, which are organized as a sorted <strong>doubly linked list</strong>. This means each leaf node contains pointers to the next and previous nodes, maintaining the order of the data.</p><p>In our context, we use a B+ tree, which is a type of B trees. The key difference between a B-tree and a B+ tree is how the data is organized at the leaf nodes.</p><ul><li>In a <strong>B-tree</strong>, data is not necessarily sorted at the leaf nodes. This means searching for a range of values can be more effort-intensive because it requires moving up and down the tree to find the required range.</li><li>In a <strong>B+ tree</strong>, all data is sorted at the leaf nodes. This makes it easier to search for a range of values, as you can find them in a single pass through the leaf nodes without needing to traverse back up the tree.</li></ul><p>Within each leaf node:</p><ul><li>Data is sorted.</li><li>Each entry consists of:<br> — The cc <strong>column value</strong> in this node being indexed.<br> — A list of <strong>row IDs</strong>, which acts as a pointer to the physical location of the data on disk.</li></ul><h4>Understanding Row IDs</h4><p>You can think of row IDs as a structured reference that includes:</p><ol><li><strong>File </strong>reference.</li><li><strong>Page </strong>reference.</li><li><strong>Row </strong>reference (slot).</li></ol><p>This structure effectively maps the logical data to its physical location on disk.</p><h4>Random Page References</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/826/1*6Dr5HDvAd5vnQiXjXL8kAA.png" /><figcaption>figure 1.1 — B tree access pages on disk randomly</figcaption></figure><blockquote>It’s important to note that the leaf nodes reference pages randomly on the disk as shown in figure 1.1. This randomness introduces challenges, which we’ll explore later, including how the database engine optimizes or mitigates these issues.</blockquote><h3>B+ Tree Indexes</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/699/0*wKArDqTVXIh8xibr" /><figcaption>figure 1.2 — B+ tree example</figcaption></figure><p>Let’s consider <strong>Figure 1.2</strong>, which shows a B+ tree indexing a column called x that stores numbers. In this example, the value 25 is the median of all values in the table.</p><h4>Fetching a Specific Value: x = 20</h4><p>Suppose we want to find the row where x = 20. The B-tree traversal would work as follows:</p><ol><li><strong>Start at the root node</strong> (value 25). Since 20 is smaller than 25, move to the left sub-tree.</li><li><strong>Visit the left child node</strong> (value 15). Since 20 is larger than 15, move to the right sub-tree.</li><li><strong>Reach the leaf node</strong> containing the value 20.</li></ol><p>At this point, we find the row ID associated with 20 in the leaf node. The database engine uses this row ID to locate the corresponding page on disk, retrieve the row, and return it.</p><p>This demonstrates how B-trees efficiently support <strong>equality conditions</strong> (x = value).</p><h4>Fetching a Range of Values: x BETWEEN 20 AND 40</h4><p>Now, let’s consider a range query where x is between 20 and 40. The traversal process is as follows:</p><ol><li>Start at the root node (25) and navigate to the <strong>leaf node containing </strong><strong>20</strong>, as described above.</li><li>From the leaf node, follow the <strong>doubly linked list</strong> to move sequentially through the values (20, 25, 30, 35, 40).</li><li>For each value in the range, the database engine uses the associated row IDs to locate and fetch the relevant pages from disk.</li></ol><blockquote><strong>Challenges with Random Page Access</strong></blockquote><blockquote>— Because pages are stored randomly on the disk, the same page may need to be opened multiple times to fetch rows for different values within the range. This inefficiency becomes significant for large ranges.</blockquote><blockquote>— To address this issue, techniques like <strong>bitmap indexes</strong> can optimize the process. We’ll explore these solutions later in the same article.</blockquote><h4>A Real-World Examples with Query Plans</h4><p>Now, let’s look at a real query and its execution plan to better understand how the database handles these scenarios.</p><ul><li><strong>Equality query (example 1.0)</strong></li></ul><pre>CREATE INDEX idx_first_name_btree ON partners(first_name);<br>-------------------------------------------------------------------------------<br><br>explain analyze <br>select first_name, email<br>from partners <br>where first_name = &#39;first_name456789&#39;<br><br>------------------------------- Query Plan ------------------------------------<br><br>Index Scan using idx_first_name_btree on partners  (cost=0.43..8.45 rows=1 width=180) (actual time=0.040..0.041 rows=1 loops=1)<br>  Index Cond: ((first_name)::text = &#39;first_name435678&#39;::text)<br>Planning Time: 0.131 ms<br>Execution Time: 0.062 ms</pre><p>We created an index on the first_name column in the partners table. When we queried the table with a filter on first_name, the query optimizer chose to <strong>use the index</strong> instead of performing a sequential or parallel scan, as it did in the previous example in the intro.</p><ul><li>Range query <strong>(example 1.1)</strong></li></ul><pre>CREATE INDEX idx_age_btree ON age (age);<br>-------------------------------------------------------------------------------<br><br>explain<br>select * <br>from users <br>where age &gt;= 90<br><br>------------------------------- Query Plan ------------------------------------<br><br>Index Scan using idx_users_age on users  (cost=0.43..9736.31 rows=428107 width=4) (actual time=0.569..39.097 rows=437141 loops=1)<br>  Index Cond: (age &gt; 90)<br>Planning Time: 1.288 ms<br>Execution Time: 46.938 ms</pre><p>In this example, there is an index on the age column. When querying for a <strong>range of values</strong>, the optimizer chose to <strong>scan the index</strong> rather than performing a full table scan.</p><p><strong>Step 1:</strong> The database engine scans the B-tree index, starting at the root and moving through the tree until it reaches the value 90 in the leaf node, which marks the beginning of the range.</p><p><strong>Step 2:</strong> From there, it continues traversing sequentially through the leaf nodes until it reaches the end of the specified range, which is 100 in this case.</p><p><strong>Step 3:</strong> While traversing the leaf nodes, the database engine fetches the rows using the row IDs stored in the leaf nodes, retrieving the data from the table for the specified range.</p><ul><li>Index doesn’t cover the full conditions in where clause. <strong>(example 1.3)</strong></li></ul><pre>CREATE INDEX idx_last_name_btree ON partners(last_name);<br>-------------------------------------------------------------------------------<br><br>explain analyze<br>select * <br>from partners<br>where last_name = &#39;last_name456789&#39; and email = &#39;user435678@example.com&#39;<br><br>-------------------------------- Query Plan -----------------------------------<br><br>Index Scan using idx_partners_last_name on partners  (cost=0.29..8.30 rows=1 width=148) (actual time=0.049..0.049 rows=0 loops=1)<br>  Index Cond: ((last_name)::text = &#39;last_name456789&#39;::text)<br>  Filter: ((email)::text = &#39;user435678@example.com&#39;::text)<br>Planning Time: 0.281 ms<br>Execution Time: 0.077 ms</pre><p>in this case, there is an index on the last_name column, but the filter involves both last_name and email. the following steps happens:</p><ol><li>the optimizer makes an intelligent decision by first searching for last_name in the B-tree index.</li><li>After finding the leaf nodes that match last_name = &#39;last_name456789&#39;, the engine retrieves the corresponding <strong>row IDs</strong> and fetches the relevant rows from disk.</li><li>Then, it applies the second condition—checking whether the email is &#39;user435678@example.com&#39;—to filter out any non-matching rows. And this is clear in the word Filter which means that the filter is outside the index.</li></ol><p>This approach is efficient because the optimizer first narrows down the results using the indexed column (last_name) and then applies the secondary filter on the non-indexed column (email) only to the rows that were already fetched from the disk. This avoids scanning all rows which improves performance.</p><h3>Composite Index</h3><p>A composite index can be a B tree index where each node contains two or more columns. In a composite index, the values are sorted first by the first column, then by the second column, and so on. Since it is a B-tree index, it supports both equality and range queries.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*zcK_RyiE95YUOuMM" /><figcaption>figure 1.3 — Composite Index using B tree</figcaption></figure><h4>Fetching a Specific Value: x = 2, y &lt; c</h4><p>In the example in figure 1.3, the B-tree organizes values by sorting primarily on the first column (x), and then secondarily on the second column (y). This sorting order is maintained in both the internal nodes and the leaf nodes of the tree.</p><p>Consider a query with the condition x = 2 and y &lt; &#39;c&#39;. The B-tree will efficiently navigate through the index by first looking for x = 2. Once it reaches the leaf node with x = 2, it will then traverse the leaf nodes while the condition y &lt; &#39;c&#39; is valid. For instance, it will start at x = 2, y = &#39;a&#39; and continue to the next values x = 2, y = &#39;b&#39;, and stop before x = 2, y = &#39;c&#39;.</p><p>This efficient navigation and traversal through the B-tree allows for quick retrieval of the desired range of values.</p><h4>Optimizing Queries with Composite Indexes</h4><p>When using a composite index, the traversal of the leaf nodes starts when the first range condition of the prefix columns is encountered. This means:</p><ul><li>Index usage stops after the first range condition.</li><li>The rest of the conditions are applied as filters while traversing the leaf nodes.</li></ul><h4>Example: Index on (a, b, c)</h4><p>with a condition like a = 1, b &lt; &#39;c&#39;, c = 5:</p><ul><li>The index search begins at a = 1.</li><li>Traversal starts from the leaf node where a = 1 and b = &#39;a&#39; (the beginning of the b range).</li></ul><p>During traversal, the remaining conditions are applied which is c = 5.</p><p>with a condition like a &lt; 10, b = &#39;c&#39;, c = 3:</p><ol><li>Start at the beginning of the range for a = 0.</li><li>Scan through the leaf nodes for all a value between 0 and 9.</li><li>Apply the conditions b = &#39;c&#39; and c = 3 as filters during the traversal.</li></ol><p>Since the range condition a &lt; 10 is applied early, the engine must scan a larger number of leaf nodes. This makes the query less efficient because it has to traverse more nodes to find the matching rows.</p><blockquote><strong>To optimize index usage:</strong></blockquote><blockquote>- Place the most unique columns first in the index.</blockquote><blockquote>- Understand that the index usage stops at the first range condition, and the rest of the conditions serve as filters during leaf node traversal.</blockquote><ul><li>Composite Index (example 1.4)</li></ul><pre>index on last name and email;<br>-------------------------------------------------------------------------------<br><br>explain analyze<br>select * <br>from partners<br>where last_name = &#39;last_name456789&#39; and email = &#39;user435678@example.com&#39;<br><br>------------------------------- Query Plan ------------------------------------<br><br>Index Scan using idx_partners_last_name_email on partners  (cost=0.29..8.30 rows=1 width=148) (actual time=0.031..0.031 rows=0 loops=1)<br>  Index Cond: (((last_name)::text = &#39;last_name456789&#39;::text) AND ((email)::text = &#39;user435678@example.com&#39;::text))<br>Planning Time: 0.143 ms<br>Execution Time: 0.046 ms</pre><p>It’s now easy to notice the difference in the index scan behavior. In Example 1.3, the engine had to traverse the leaf nodes and apply additional filters. However, in this example with the improved index structure using composite index, the index scan is more efficient. The optimizer directly accesses the relevant rows without extra filtering or unnecessary leaf node traversal, making the query faster.</p><h3>Hash Index</h3><p>A hash index consists of a hash function and a hash table. The hash function maps the values of the indexed column to a specific location in the hash table.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*j9DaqUHeFwwWQguO" /><figcaption>figure 1.4 — Hash index</figcaption></figure><p>In our example in Figure 1.4, we want to search for the key Alice. The process works as follows:</p><ol><li>The key Alice is passed through a hash function.</li><li>The hash function calculates a value and maps it to a specific bucket in the hash table. For example, the hash function maps Alice to bucket 4.</li></ol><p>Inside each bucket, there are two things:</p><ul><li>The key (Alice in this case).</li><li>A list of row IDs, which point to the physical locations on the disk where rows with the value Alice can be found.</li></ul><p>This allows the database engine to quickly locate the data by looking up the corresponding bucket in the hash table and retrieving the rows based on the row IDs.</p><h4>Characteristics of Hash Indexes</h4><ul><li><strong>Supports only equality queries</strong>: Hash indexes are efficient for queries that use exact matches (e.g., column = value).</li><li><strong>No range queries</strong>: Since the data is not stored in any specific order, hash indexes do not support range queries (e.g., column BETWEEN x AND y).</li><li>Hash Index (example 1.5)</li></ul><pre>CREATE INDEX idx_last_name_hash ON partners USING HASH(last_name);<br>-------------------------------------------------------------------------------<br><br>explain analyze <br>select first_name<br>from partners <br>where last_name = &#39;last_name456789&#39;<br><br>------------------------------- Query Plan ------------------------------------<br><br>Index Scan using idx_last_name_hash on partners  (cost=0.00..8.02 rows=1 width=17)<br>Index Cond: ((last_name)::text = &#39;last_name456789&#39;::text)</pre><p>In this example, the optimizer selects the hash index created on the last_name column, which is more efficient than performing a full table scan.</p><blockquote>— Note: This example stands alone and does not rely on any previous B-tree indexes, as they have been dropped.</blockquote><blockquote>— In some databases, we can create a composite index using a hash index as well, but it is more common to use B-trees for this purpose.</blockquote><blockquote>— Remember, it’s all about trade-offs — no index type is universally better or worse in all cases.</blockquote><h3>Covering Index</h3><p>A covering index means that all selected columns values in the query existed in the index and no need to go to the disk to fetch more data.<br>By including all the query selected columns in the index, this reduces disk access which improves query performance.</p><ul><li>Covering Index (example 1.6)</li></ul><pre>CREATE INDEX idx_users_age_location ON users(age, location);<br>-------------------------------------------------------------------------------explain <br>SELECT location<br>FROM users<br>WHERE age = 30 and location = &#39;New York&#39;<br><br><br>------------------------------- Query Plan ------------------------------------ <br><br>Index Only Scan using idx_users_age_location on users  (cost=0.43..500.75 rows=21216 width=9)<br>Index Cond: ((age = 30) AND (location = &#39;New York&#39;::text))<br>  Heap Fetches: 0</pre><p>As seen in the query plan, the word “Only” indicates that the index is a covering index, and “Heap fetches: 0” means no data was fetched from the disk.</p><p>This means that all the selected columns, such as location in this case, are included in the idx_users_age_location index. Since the required data is available within the index itself, the database engine doesn&#39;t need to access the disk to fetch the full row. Instead, it can retrieve the values directly from the index, reducing disk I/O and improving query performance.</p><blockquote>Note: Including all the selected columns in the index does not always represent the best approach.</blockquote><blockquote>While it can improve query performance, it may negatively impact insert and update operations.</blockquote><blockquote>This is because every insert or update operation requires the index to be rebalanced and updated. As a result, more read and write operations are needed, which can degrade the performance of inserting and updating data.</blockquote><h3>Bitmap</h3><p>As mentioned earlier, regular indexes access pages randomly. When traversing the leaf nodes, the same page may be accessed multiple times if different index entries point to the same page. This becomes inefficient, especially when the query requests a large number of rows.</p><p>For example, if a query asks for all users with id &gt; 100, which is essentially all rows except for a small subset (say all pages except for one or two pages), using an index could lead to excessive random access. This process involves repeatedly loading the same pages, which is inefficient and can cause performance issues. In such cases, even a sequential scan of the full table might be more efficient despite its drawbacks.</p><p>To address this, PostgreSQL offers a smart solution using a Bitmap Index. Instead of directly accessing pages for each matching row, the following happens:</p><ul><li>The database uses a bitmap to mark the pages that need to be read.</li><li>Then, it reads all the needed pages at once.</li></ul><p>This way, the database can gather all the necessary pages in a single pass, avoiding repeated random access.</p><p>Consider the bitmap as an array of bit values: 1 and 0. 1 means the page with this index number needs to be read into memory, and 0 means this page does not need to be read.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/776/1*wQfuq79Qd5g_1qgp8XnLWg.png" /><figcaption>figure 1.5 — bitmap for pages 1, 2</figcaption></figure><p>As shown in Figure 1.5, suppose from the B-tree index, the engine understands that it needs to open pages 1, 2, 1, 1, and 2, respectively, to fetch 5 rows. Instead of repeatedly accessing the same pages, the database marks pages 1 and 2 in the bitmap, then reads each of them only once. This reduces redundant disk I/O and improves the overall query performance.</p><ul><li>Bitmap (example 1.7)</li></ul><pre>index on age<br>-------------------------------------------------------------------------------<br><br>explain analyze <br>select * from users where age &gt; 90<br><br>------------------------------- Query Plan ------------------------------------ <br><br>Bitmap Heap Scan on users  (cost=5544.64..69691.55 rows=425833 width=26) (actual time=20.904..138.330 rows=437141 loops=1)<br>  Recheck Cond: (age &gt; 90)<br>  Heap Blocks: exact=36766<br>  -&gt;  Bitmap Index Scan on idx_users_age  (cost=0.00..5438.18 rows=425833 width=0) (actual time=16.856..16.857 rows=437141 loops=1)<br>        Index Cond: (age &gt; 90)<br>Planning Time: 0.140 ms<br>Execution Time: 147.660 ms</pre><p>As seen in Example 1.7, the database engine uses the index to apply the filter age &gt; 90 by doing the following:</p><ul><li>The required pages are marked in the bitmap with a 1 (indicating the page should be read) and 0 (indicating the page should not be read).</li><li>The bitmap heap scan fetches the bitmap marked pages from the heap/disk.</li><li>The pages are read, and the condition is rechecked for all rows within those pages.</li></ul><p><strong>Note:</strong> While it may seem like additional effort to check all rows in each page, this method is more efficient than random access.</p><h3>Index Intersection</h3><p>Suppose you have two separate indexes: one on the name column and another on the age column. If your query is something like name = &#39;shaaban&#39; AND age &gt; 25, the database engine will typically prefer to use a composite index on both columns if it exists. However, in this case, we don&#39;t have such a composite index.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/685/0*uPRqYF51ix7ySJfc" /><figcaption>figure 1.6 — index intersection</figcaption></figure><p>As shown in figure 1.6, The optimizer aiming to make the best use of the available indexes, performs the following steps on the separated indexes:</p><ol><li>It retrieves all rows that match the first part of the condition (<em>ex:</em> name = &#39;john&#39;) from the name index.</li><li>It retrieves all rows that match the second part of the condition (<em>ex: </em>age &gt; 30) from the age index.</li><li>It then combines these results to find the intersection, which includes only the rows that satisfy both conditions (<em>ex: </em>name = &#39;john&#39; AND age &gt; 30).</li></ol><blockquote>Note: one index scan is always better than two. So Composite index on both columns is probably to perform better than index intersection</blockquote><h3>Index Union</h3><p>Similar to index intersection, <strong>index union</strong> is another optimization technique. In this case, the database engine merges the row IDs from two or more different indexes. This is the only type of index optimization that supports <strong>OR</strong> conditions in a query.</p><p>For example, if your query is something like name = &#39;john&#39; OR age &gt; 30, the engine will:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/685/0*hS3uPMtS2lyHrdEj" /></figure><ol><li>Retrieve all rows matching the name condition from the name index.</li><li>Retrieve all rows matching the age condition from the age index.</li><li>It then merges (unions) the row IDs from both indexes to get all the rows that match either of the conditions.</li></ol><h3>Index Intersection and Index Union using bitmap</h3><p>As shown in Figure 1.6, the intersection occurs between the row IDs retrieved from each separate index. Instead of directly reading all pages from the first index “name” and then reading all pages from the second index “age”, we only need the common pages that satisfy both conditions: name = &#39;john&#39; and age &gt; 30. We can use a bitmap to mark only the common pages identified by both index searches.</p><p>Let’s see a visual example to understand this more clearly.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*iMbGjS8meJVUsvD5" /><figcaption>figure 1.7 — pages from each index</figcaption></figure><p>As shown in Figure 1.7, suppose we want to get all rows matching the full condition name = &#39;john&#39; and age &gt; 30. The database has an index on age and another index on name. The following steps occur:</p><ol><li><strong>Index scan on the </strong><strong>name column</strong>: The bitmap marks pages 0 and 1 as relevant for the condition name = &#39;john&#39;.</li><li><strong>Index scan on the </strong><strong>age column</strong>: The bitmap marks pages 1 and 11 as relevant for the condition age &gt; 30.</li><li><strong>Apply AND operation between the two bitmaps</strong>: The result of the AND operation indicates that only page 1 satisfies both conditions.</li><li><strong>Fetch the result</strong>: Page 1 is the only page that needs to be read to fulfill the query condition.</li></ol><p>This process is exactly what happens in the query plan shown below example 1.8</p><pre>index on age, index on location<br>--------------------------------------------------------------------------------<br><br>explain<br>SELECT user_id<br>FROM users<br>WHERE age &gt; 30 and location = &#39;New York&#39;;<br><br>------------------------------- Query Plan ------------------------------------ <br><br>Bitmap Heap Scan on users<br>   Recheck Cond: ((age &gt; 30) AND (location = &#39;New York&#39;))<br>   -&gt; BitmapAnd<br>      -&gt; Bitmap Index Scan on idx_users_age<br>         Index Cond: (age &gt; 30)<br>      -&gt; Bitmap Index Scan on idx_users_location<br>         Index Cond: (location = &#39;New York&#39;)</pre><p>In Example 1.8, the index scan on the age column and the index scan on the locationcolumn each produce a bitmap marking the relevant pages to be read. The database then performs an AND operation between these two bitmaps to identify the common pages that match both conditions. It fetches these pages and rechecks the full condition on all the rows within the fetched pages.</p><p>In contrast, with index union, the engine obtains two bitmaps from each index and applies an OR operation between the bitmaps. This OR operation retrieves all pages that match any part of the condition, ensuring that all relevant pages are included.</p><p>let’s see index union example in the next example.</p><p>Example 1.8</p><pre>CREATE INDEX idx_users_age ON users(age);<br>CREATE INDEX idx_users_location ON users(location);<br>------------------------------------------------------------------------------<br><br>explain <br>SELECT user_id<br>FROM users <br>WHERE age &gt; 30 OR location = &#39;New York&#39;;<br><br>------------------------------- Query Plan ------------------------------------ <br><br>Bitmap Heap Scan on users  (cost=19270.03..81410.04 rows=1683333 width=4)<br>Recheck Cond: ((age &gt; 30) OR ((location)::text = &#39;New York&#39;::text))<br>  Heap Blocks: exact=36765<br>  -&gt;  BitmapOr  (cost=19270.03..19270.03 rows=1691667 width=0)<br>        -&gt;  Bitmap Index Scan on idx_users_age (cost=0.00..18152.43 rows=1666667 width=0)<br>              Index Cond: (age &gt; 30)<br>        -&gt;  Bitmap Index Scan on idx_users_location  (cost=0.00..275.93 rows=25000 width=0)<br>              Index Cond: ((location)::text = &#39;New York&#39;::text)</pre><p>The query plan shows that the database performs a BitmapOr operation to merge the results of two bitmap index scans on age and location columns. The merged bitmap identifies the relevant pages, which are then fetched and rechecked for the condition (age &gt; 30 OR location = &#39;New York&#39;).</p><h3>General Tips</h3><blockquote><strong>Isolate Columns</strong><br>a column shouldn’t be a part of an expression or function so the database engine can recognize the exact values it needs to extract from the index.</blockquote><blockquote>The engine cannot evaluate an expression or equation while scanning the index because expressions, functions, or equations do not yield deterministic result values that the engine can predict without calculation.</blockquote><p>let’s see some real scenarios:</p><pre>-- This query below will not use the index on user_id because the indexed column is part of an equation.<br>SELECT user_id FROM users WHERE user_id + 1 = 5;<br><br>-- We can enhance the query to isolate the user_id:<br>SELECT user_id FROM users WHERE user_id = 4;<br>-- Now user_id is isolated on the left side of the equation. This will use the index.</pre><pre>-- The query below will not use the index on last_name since it is part of a function:<br>SELECT ... WHERE last_name &gt;= UPPER(name);<br><br>-- You can solve this by converting the name parameter to uppercase before passing it to the query:<br>SELECT ... WHERE last_name &gt;= &#39;UPPERCASE_NAME&#39;;<br>-- This makes the value deterministic for the engine, allowing it to know the exact value to scan in the index.</pre><pre>-- The query below will not use the index on date_col because it is part of a function and part of an equation:<br>SELECT ... WHERE TO_DAYS(CURRENT_DATE) - TO_DAYS(date_col) &lt;= 10;<br><br>-- Additionally, using CURRENT_DATE or any constantly changing value prevents index usage due to its non-deterministic nature. <br>-- To solve this, pass the date as a parameter and rewrite the query to isolate date_col:<br>SELECT ... WHERE date_col &gt;= &#39;2024-11-10&#39;;</pre><p>Another approach is to create an index on expressions or functions:</p><pre>-- For example:<br>CREATE INDEX idx_user_id_plus_one ON users((user_id + 1));<br>CREATE INDEX idx_upper_name ON users((UPPER(name)));<br><br>-- These indexes will work if you use the same expressions or functions in the WHERE clause:<br>SELECT ... FROM users WHERE user_id + 1 = 5;<br>SELECT ... FROM users WHERE UPPER(name) = &#39;SOME_NAME&#39;;</pre><p>However, in my opinion, this is not a practical solution. It’s better to isolate your columns whenever possible for better index usage.</p><h3>Index in Joins</h3><p>Indexes play a crucial role in optimizing database joins. Let’s consider a basic nested loop join between two tables, customers and orders, both having a customer_id column.</p><h4>Basic Nested Loop Join</h4><p>Here’s how a typical nested loop join works:</p><pre>-- suppose having 2 tables, customers and orders <br>-- and both of them have a customer_id column<br><br>/*<br>  For each row in Customers (Outer Table):<br>    Lookup Orders (Inner Table) using Index on customer_id:<br>      If match found:<br>        Combine Orders and Customers row<br>*/</pre><p>We can enhance this nested loop join by creating an index on the joining column customer_id. This improvement replaces the inner loop lookup with an index lookup, which is significantly faster and more efficient than a full table scan.</p><h4>Example:</h4><pre>create index idx_customer_id on orders(customer_id)<br><br> - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -<br><br>SELECT *<br>FROM orders<br>JOIN customers ON orders.customer_id = customers.customer_id;<br><br> - - - - - - - - - - - - - - - - Query Plan - - - - - - - - - - - - - - - - - - <br><br>Nested Loop (cost=0.42..25.67 rows=10 width=128) (actual time=0.035..0.076 rows=5 loops=1)<br>-&gt; Seq Scan on orders (cost=0.00..12.00 rows=100 width=64)<br>-&gt; Index Scan using idx_customer_id on customers (cost=0.42..1.34 rows=1 width=64)<br>    Index Cond: (customer_id = orders.customer_id)<br><br>Planning Time: 0.123 ms<br>Execution Time: 0.147 ms</pre><p>Another example when having a filter on the outer table</p><pre>create index idx_customer_id on orders(order_date, customer_id)<br>- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -<br><br>SELECT *<br>FROM orders<br>JOIN customers ON orders.customer_id = customers.customer_id<br>WHERE orders.order_date = &#39;2023–01–01&#39;;<br><br>- - - - - - - - - - - - - - - - Query Plan - - - - - - - - - - - - - - - - - - <br><br>Nested Loop (cost=0.42..20.00 rows=5 width=128) (actual time=0.020..0.050 rows=3 loops=1)<br>-&gt; Index Scan using idx_customer_id on orders (cost=0.42..12.00 rows=5 width=64) (actual time=0.005..0.010 rows=3 loops=1)<br>    Index Cond: (order_date &gt;= &#39;2024–01–01&#39;)<br>-&gt; Index Scan using customers_pkey on customers (cost=0.42..1.34 rows=1 width=64) (actual time=0.010..0.012 rows=1 loops=3)<br>Index Cond: (customer_id = orders.customer_id)</pre><p>In this plan:</p><ul><li>The filter on order_date is applied first using the index idx_order_date_customer_id.</li><li>The database retrieves the filtered customer_id (it is a covering index for this case) from the orders table using an index scan.</li><li>For each filtered row in orders, an index scan on customers using customers_pkey (the primary key index) is performed or another index on that column.</li></ul><p>By applying the filter on the orders table before the join, the database reduces the number of rows to be joined, thereby improving the efficiency of the join operation. This demonstrates how creating and using indexes can enhance join query performance by minimizing the number of scanned rows and leveraging faster index lookups.</p><h3>Index in Sorting</h3><p>Data is already sorted in the index at the leaf node. To sort based on an indexed column, use a prefix of the index. If the index is composite, data is sorted first by the first column, then by the second column, and so on.</p><p>If you use a middle column in the index without the prefix, the engine cannot use the index to sort.</p><h4>Example 1:</h4><pre>// index on age<br><br>explain analyze<br>select * from users where age &gt; 90<br>order by age<br><br>- - - - - - - - - - - - - - - - - Query Plan - - - - - - - - - - - - - - - - -<br><br>Index Scan using idx_users_age on users (cost=0.43..8.45 rows=1 width=26) (actual time=0.021..0.021 rows=0 loops=1)<br> Index Cond: (age &gt; 99)<br>Planning Time: 0.126 ms<br>Execution Time: 0.044 ms</pre><p>Data is already sorted based on age in the age index, so no additional sorting effort is required after scanning the index.</p><pre>explain analyze<br><br>select * from users where age &gt; 90<br>order by age desc<br><br> - - - - - - - - - - - - - - - - Query Plan - - - - - - - - - - - - - - - - - -<br><br>Index Scan Backward using idx_users_age on users (cost=0.43..8.45 rows=1 width=26) (actual time=0.045..0.045 rows=0 loops=1)<br> Index Cond: (age &gt; 90)<br>Planning Time: 0.096 ms<br>Execution Time: 0.063 ms</pre><ul><li><em>The index is traversed in reverse to fetch data in descending order.</em></li></ul><h4>Example 2: Sorting with Composite Index</h4><p><strong>Index:</strong> idx_rentals on (rental_date, inventory_id, customer_id)</p><p>The following queries uses index in sorting:</p><pre>Index on (rental_date, inventory_id, customer_id) <br><br>WHERE rental_date = &#39;2005–05–25&#39; ORDER BY inventory_id ASC;<br>WHERE rental_date &gt; &#39;2005–05–25&#39; ORDER BY rental_date, inventory_id;</pre><p>Using a range in the <em>WHERE</em> clause requires appending the ranged column again in the <em>ORDER</em> <em>BY</em> clause to follow the index prefix to sort by the range then by the rest of the prefix.</p><p>the following queries will not use index for sorting:</p><pre>WHERE rental_date = &#39;2005–05–25&#39; ORDER BY inventory_id DESC, customer_id ASC; <br>-- Avoid different sort directions on indexed columns.<br><br>WHERE rental_date = &#39;2005–05–25&#39; ORDER BY inventory_id, staff_id; <br>-- staff_id is not in the index prefix.<br><br>WHERE rental_date &gt; &#39;2005–05–25&#39; ORDER BY inventory_id, customer_id; <br>-- should sort by rental_date first which is the first in the prefix .<br><br>WHERE rental_date = &#39;2005–05–25&#39; AND inventory_id IN (1,2) ORDER BY customer_id;<br>-- inventory_id uses an IN statement, which acts like a range condition in sorting. <br>-- Since it&#39;s not included in the ORDER BY clause, the index is only used in filtering.</pre><p>Example: index on string column:</p><pre>SELECT * FROM table WHERE name LIKE &#39;abc%&#39;;<br>-- this query can use index on the name column because it is a prefix.<br>-- but &#39;%abc&#39;, &#39;%abc%&#39; can&#39;t use index on name because they are not using a prefix. </pre><blockquote><strong>General Rule: Always watch your queries.</strong></blockquote><blockquote>Changes in data affect the query plan, so there is no fixed plan for each query. Query plans change with data changes, search criteria, and other factors. So, always monitor your queries.</blockquote><p>If you notice any errors or have suggestions, feel free to leave a comment or contact me on LinkedIn. Your feedback is greatly appreciated!</p><p>linkedin: <a href="https://www.linkedin.com/in/mohamed-shaaban-4b8019178/">https://www.linkedin.com/in/mohamed-shaaban-4b8019178/</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6965617ab49b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Cracking The Query Plan (Intro)]]></title>
            <link>https://medium.com/@mohamed.shaaban.elbay/cracking-the-query-plan-intro-c24f5b9173f4?source=rss-163154ddb199------2</link>
            <guid isPermaLink="false">https://medium.com/p/c24f5b9173f4</guid>
            <category><![CDATA[database-internals]]></category>
            <category><![CDATA[indexing]]></category>
            <category><![CDATA[postgresql]]></category>
            <category><![CDATA[b-tree]]></category>
            <category><![CDATA[sql]]></category>
            <dc:creator><![CDATA[Mohamed Shaaban]]></dc:creator>
            <pubDate>Wed, 04 Dec 2024 20:07:39 GMT</pubDate>
            <atom:updated>2024-12-08T05:44:27.016Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*CbK65FSQ8GUQeJW6cQ5IBw.png" /></figure><p>In this series of articles, I’ll guide you step by step to understand SQL query plans. To do this, we first need to learn the important terms used in database queries. By understanding how databases work internally, we can figure out why certain query plans are chosen and how to improve them when needed. Knowing how the query optimizer makes decisions helps you spot when a plan is not efficient and change it to make your queries run faster.</p><p>In this series of articles, we will discuss various database concepts, focusing specifically on PostgreSQL. While these concepts are broadly applicable across different types of databases, the examples and query plans provided will be in PostgreSQL.</p><h4>How Databases Store Tables on Disk</h4><p>Databases store tables as a collection of files, and each file consists of multiple pages. A page is the smallest unit the database can read from disk into memory. Throughout this journey, we’ll focus on the concept of pages as a core building block.</p><p>Pages are typically stored in random order within a file. They are not arranged in any specific sequence. (In some databases, pages can be sorted on the disk based on a specific column, usually the primary key. but we will talk generally based on postgresql)</p><p>To give you a better idea, imagine we have a table with 100,000 rows, spread across 1,000 pages. Each page contains 100 rows. Now, let’s say you want to retrieve a specific row from this table. How does the database engine find it?</p><p>The engine performs a full table scan, opening all the pages and checking each row to see if it matches the desired row. This approach becomes increasingly inefficient as the table size grows, taking more time to complete.</p><p>While the database engine may use multiple threads to read all the pages in a shorter time, the cost of reading the entire table remains the same.</p><h4>Parallel Scanning with Multiple Threads example</h4><pre>explain analyze <br>select *<br>from partners <br>where email = &#39;user435678@example.com&#39;<br><br>------------------------------- Query Plan ------------------------------------<br><br>Gather  (cost=1000.00..127895.77 rows=1 width=180) (actual time=136.131..140.386 rows=1 loops=1)<br>  Workers Planned: 2<br>  Workers Launched: 2<br>  -&gt;  Parallel Seq Scan on partners  (cost=0.00..126895.67 rows=1 width=180) (actual time=88.300..125.916 rows=0 loops=3)<br>        Filter: ((email)::text = &#39;user435678@example.com&#39;::text)<br>        Rows Removed by Filter: 1666666&quot;<br>Planning Time: 0.094 ms<br>JIT:<br>  Functions: 6&quot;<br>  Options: Inlining false, Optimization false, Expressions true, Deforming true<br>  Timing: Generation 0.513 ms, Inlining 0.000 ms, Optimization 0.418 ms, Emission 5.996 ms, Total 6.927 ms<br>Execution Time: 140.63</pre><p>In this example, database engine performs a parallel scan on the table using multiple threads. This means that instead of scanning the table sequentially with a single thread, multiple threads work together to scan different parts of the table simultaneously. This approach can significantly speed up the scanning process, especially for large tables, by leveraging the power of multi-core processors.</p><p>here is the idea of sorting the data in specific structure such as indexes can help in reaching to the required data faster.</p><p>References for all the articles<strong>:</strong></p><ul><li>Database Engineering Course: Hussein Nasser</li><li>High Performance MySQL Articles — Sayed Alesawy</li><li>Database Internals Course: Amr Elhelw</li><li><a href="https://use-the-index-luke.com/">https://use-the-index-luke.com</a></li><li>Database System Concepts: Book</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c24f5b9173f4" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>