Given a table of employees and this query: SELECT first_name, last_name, date_of_birthFROM employeesWHERE date_of_birth >= ? AND date_of_birth <= ?AND subsidiary_id = ? Index(subsidiary_id, date_of_birth) is better than index(date_of_birth, subsidiary_id) because it visits fewer index leaf nodes. The difference is negligible if the date filter is very selective, but, otherwise, the larger the date range, the worse the performance.

Index for equality first, then for ranges

When using a LIKE filter on an indexed column, only the prefix before the wildcard (%) is used as an index condition; the remaining characters don't narrow the scanned index range. The longer the prefix, the more efficient the lookup.Consequently, a LIKE filter with a leading wildcard (e.g. "%ant") can't use an index and has to do a sequential scan over the whole table.

Use longer prefixes in LIKE filters

In general, queries are slow because they get too much data from the heap. To find the root cause, get the query's execution plan and look for:<ul><li class="ql-align-justify">Heap-table accesses → which means it's reading too much data from the heap</li><li class="ql-align-justify">Wide index range scans → which means the index scan is not very selective, resulting in many potential matches, which need to be fetched from heap to determine if they're good matches</li></ul>

How to debug a slow query that uses an index

The smallest unit of data that a database can read is a table block or a table page, which is usually 8KB. Depending on where that block is located, reading it takes different amounts of time:<ul><li class="ql-align-justify">From memory: 2μs</li><li class="ql-align-justify">From SSD: 100μs</li><li class="ql-align-justify">From HDD: 10ms</li></ul>There's an order of magnitude between them, making it important to have the indexes loaded into memory.

How long it takes to read a table block

If you need to join 5 tables, 2 are joined, then their result is joined with another table, and so on. It doesn't matter in which order you write the joins because the database evaluates all orders and chooses the most efficient one.Furthermore, depending on table statistics, available indexes, and system resources, the actual joining is done using one of these methods: nested loops join, hash join, or merge join.As a general guideline, to improve join performance, consider creating composite indexes that cover the columns in the WHERE clause, followed by the columns in the JOIN condition.

Only two tables are joined at a time

How: It iterates over all rows from one table and for each of them it searches the matching rows in the other table.When: It's used for small datasets when the overhead of a more advanced join method is not justified, or when one of the tables has an index on the JOIN condition.Tip: Ensure you have an index on the JOIN condition.Complexity:<ul><li class="ql-align-justify">without any indexes: O(M*N) time. O(1) space</li><li class="ql-align-justify">with indexes: O(M*logN) time. O(1) space</li></ul>

Nested loops join

How: First, it builds a hash table from the smaller table, where the key is the JOIN key and the value is the necessary tuple data. Then, it scans the other table, hashing the JOIN key of each row and emitting the rows that are also present in the hash table.When: It's used for joining large datasets with equality conditions, that can fit into the working memory (work_mem).Tip: Ensure you have enough working memory to avoid hash table spilling to disk.Complexity:<ul><li class="ql-align-justify">O(M+N) time. O(M) space</li><li class="ql-align-justify">O(M) to build the hash table + O(N) to scan the other table</li></ul>

Hash join

How: Sorts both tables by the join condition and merges the results like a zipper. For very large datasets, it splits the dataset into chunks, sorts each chunk in memory, writes each sorted chunk into a temporary file on disk, and finally does a multi-way merge of the sorted files on disk.When: It's used when at least one input dataset is pre-sorted or for datasets larger than the working memory.Tip: Ensure datasets are pre-sorted or can be sorted efficiently.Complexity:<ul><li class="ql-align-justify">for pre-sorted inputs: O(M+N) time. O(1) space</li><li class="ql-align-justify">otherwise: O(MlogM + NlogN) time. O(M+N) space</li></ul>

Merge join

The sorting operation of an ORDER BY is skipped if there's an index with the same ordering. Moreover, that index allows the ORDER BY to be executed in a pipelined manner i.e. if you request the Top-N results, the query won't need to read and sort the entire result set first.In contrast, non-pipelined ORDER BYs need to sort all rows, materialize the results, and then return the first N results. They take longer to execute as the table grows in size, whereas the pipelined ORDER BY is unaffected (it's affected by the depth of the index B-tree, but that grows much slower than the table size).

Use indexes to pipeline ORDER BY clauses

There are two ways: using a hash table or sorting and aggregating.<ol><li class="ql-align-justify">The database builds a hash table with the key being the grouped columns, and the value being the aggregated value. This hash table is built in a temporary table and then returned to the client as the result.</li><li class="ql-align-justify">The database sorts the rows by the grouped columns, stores them in a temporary table and then aggregates the results.</li></ol>1 uses less memory because 2 sorts the entire input set, but 2 can use an index to avoid the sorting step and as such it can be pipelined i.e. it can return results before reading the entire input set.

How a GROUP BY is executed

There are two ways to paginate results: offset and seek. The offset method uses the OFFSET keyword, whereas the seek method relies on a column filter to exclude the rows from the previous pages (in practice, this is usually the unique identifier of the last row from the previous page).In terms of performance, the seek method is better because it doesn't have to process all previously paginated rows (as offset has to do) and is good for infinite scrolling use cases. However, it doesn't allow for page skipping, which can only be achieved with the offset method.

Pagination methods

Tips to improve the performance of your SQL queries

computerscience

Computer Science

softwareengineering

Software Engineering

Markus Winand

SQL Performance Explained

Type checking is a process that verifies if a variable is compatible with a certain operation. Depending on when it happens, there are two paradigms:<ul><li class="ql-align-justify">Static typing → which happens at compile-time and doesn't allow a variable to be reassigned values of different types because types are bound to variables. (Java, Go, C++, Typescript)</li><li class="ql-align-justify">Dynamic typing → which happens at runtime and allows for variables to be reassigned values of different types because types are bound to values. (Python, Javascript, PHP, Perl)</li></ul>

When type checking happens

Depending on how the type checking is done, we have two paradigms:<ul><li class="ql-align-justify">Nominal typing → which determines compatibility based on a variable's type. (Java, C++, PHP, Perl)</li><li class="ql-align-justify">Structural typing / Duck typing → which determines compatibility based on the set of attributes and methods of a variable. (Python, Go, Javascript, Typescript)</li></ul>

How type checking is done

Type coercion is the implicit type conversion from one data type to another. Depending on whether the language does it, we have two paradigms:<ul><li class="ql-align-justify">Weak typing → where the language does type coercion (Javascript, PHP, C)</li><li class="ql-align-justify">Strong typing → where the language doesn't do type coercion and we must explicitly convert values from one data type to another. (Java, Go)</li></ul>

If type coercion is done

Typing paradigms in programming languages

Type Checking Paradigms

Postgres offers 3 textual data types, each with its own purpose, but offering the same query performance:<ul><li class="ql-align-justify">char(n) → when you expect your data to always be N characters long (if it's shorter, Postgres adds spaces at the end)</li><li class="ql-align-justify">varchar(n) → when you want to limit your data's length to N characters</li><li class="ql-align-justify">text → when you want to store texts of any length</li></ul>varchar and text can store strings that use up to 1GB, but if you want to change the limit of a varchar field, you have to rewrite the table. This process requires an exclusive lock on the table, meaning nobody can use it until the rewrite is complete.

Textual data types

The basic unit of storage in Postgres is a page (or block). Each table and index is organized in 8KB logical pages, which are grouped into 1GB segments on disk. Whenever Postgres has to read a row from disk, it reads its physical location from the ctid column and then loads its entire corresponding page from disk.

Table storage layout

Materialized views (MV) are views that persist the results of their underlying query, can be refreshed periodically and let you add indexes on them. They're useful when you want to speed up an expensive query and you're ok working with stale data.There are two ways to refresh a MV:<ol><li class="ql-align-justify">Blocking - which completes faster, but blocks all clients from querying the MV;</li><li class="ql-align-justify">Concurrently - which completes slower, but lets clients query the MV, although their queries take longer to run. This option works only if the MV has a unique index.</li></ol>E.g. Naming convention: [app]_vw_[mv_name]_materialized

Materialized views

The query planner looks at available indexes, cost settings, strategy settings, and distribution of data, in order to plan the most efficient way to execute a query.Stats about the distribution of data are stored in the pg_statistic table and presented in a more readable form in the pg_stats view. They are generated based on ~20% of the table data (less for large tables) and are constantly updated by the autovacuum daemon. You can also manually update them using ANALYZE or VACUUM ANALYZE, the later which is strongly recommended after inserting or deleting a large number of rows.

Table statistics are essential for optimal query plans

You can view a query plan using the EXPLAIN (ANALYZE, VERBOSE, BUFFERS) command. The plan is organized as a tree, where each node has these details:<ul><li class="ql-align-justify">operation e.g. Index Scan, Group Aggregate, Sort</li><li class="ql-align-justify">cost=startup cost..total cost → The startup is the time before retrieval of data and includes scanning of indexes, joins of tables, organizing additional parallel workers</li><li class="ql-align-justify">rows=N → estimated number of rows retrieved by the node</li><li class="ql-align-justify">width=W → estimated avg. size of rows produced by the node, in bytes</li><li class="ql-align-justify">buffers → number of pages read from cache (hit) and from disk (read)</li></ul>

How to read query plans

Thinking of migrating to PostgreSQL? This clear, fast-paced introduction helps you understand and use this open source database system. Not only will you learn about the enterprise class features in versions 9.2, 9.3, and 9.4, you’ll also discover that PostgeSQL is more than a database system—it’s also an impressive application platform.With examples throughout, this book shows you how to achieve tasks that are difficult or impossible in other databases. This second edition covers LATERAL queries, augmented JSON support, materialized views, and other key topics. If you’re a current PostgreSQL user, you’ll pick up gems you may have missed before.<ul><li>Learn basic administration tasks such as role management, database creation, backup, and restore</li><li>Apply the psql command-line utility and the pgAdmin graphical administration tool</li><li>Explore PostgreSQL tables, constraints, and indexes</li><li>Learn powerful SQL constructs not generally found in other databases</li><li>Use several different languages to write database functions</li><li>Tune your queries to run as fast as your hardware will allow</li><li>Query external and variegated data sources with foreign data wrappers</li><li>Learn how use built-in replication filters to replicate data</li></ul>

Regina O. Obe

Leo S. Hsu

PostgreSQL: Up and Running

The goal was not to create a new programming language, but to provide a better way to write software. Specifically, the Go team wanted to address the complexities that arise when building modern server software, such as:<ul><li>controlling dependencies</li><li>programming with large teams with changing personnel</li><li>ease of maintainability</li><li>effective use of multicore CPUs and networking</li><li>efficient testing</li></ul>

Why Go was created

<ul><li>Portability. It allowed programmers to work on whatever platform they liked, and compile for whatever platform was required.</li><li>Gofmt. It showed that autoformatting could be done well and it could save valuable time by not arguing over spaces and newlines.</li><li>Strong standard library. It kept the community working with the same toolkit and prevented variant libraries from arising.</li><li>Concurrency. It helped popularize concurrency as a way to structure server software by making concurrency a first-class component of the language.</li><li>Fast builds 😁</li></ul>

What Go got right

Reflections on Go's 14th Anniversary - Rob Pike

<ul><li>Primary → Server that can modify data.</li><li>Standby → Server that replicates the data changes on the primary server.</li><li>Warm standby → Standby server that doesn't accept connections until it's promoted to a primary server.</li><li>Hot standby → Standby server that accepts connections and serves read-only queries.</li></ul>

Server roles in a Postgres cluster

There are two ways in which data is synchronized from the primary server to the standby servers:<ol><li>Synchronous → Write transactions are not committed until all servers commit them.</li><li>Asynchronous → Write transactions are first committed on the primary server and then copied to the standby servers.</li></ol>See the image for pros and cons of each type.

How data is synchronized in a Postgres cluster

Postgres has two built-in asynchronous replication solutions:<ol><li>Streaming replication, which is a type of WAL Shipping that streams WAL records to standby servers as they are generated.</li><li>Logical replication, which constructs logical data modifications (<a href="https://www.postgresql.org/docs/current/logicaldecoding-example.html">SQL-like commands</a>) from the WAL and streams them to standby servers.</li></ol>

Built-in replication solutions

PostgreSQL Replication

Set the followings settings in /etc/postgresql/15/main/postgresql.conf:"Error Reporting and Logging"<ul><li>logging_collector = on</li><li>log_min_duration_statement = 1s</li><li>log_lock_waits = on</li></ul>"Run-time Statistics"<ul><li>track_activity_query_size = 8192</li></ul>

Enable slow query log

<ol><li>Download the log files on your computer. The default location is <code>/var/lib/postgresql/15/main/log/</code>.</li><li>Install <a href="https://pgbadger.darold.net/">pgBadger</a></li><li>Analyze the logs: <code>pgbadger -o stats.html --prefix '%m \[%p\] %q%u@%d' /dir\_with\_logs/\*.log</code></li><li>Open the HTML output file in your browser to review the results</li></ol>

Analyze slow query log

PostgreSQL - How to Configure Slow Query Log

The recommendation pipeline has four steps:<ol><li>Candidate sourcing - Fetch the best tweets from different recommendation sources</li><li>Ranking - Rank tweets such that the most relevant ones appear first in the feed.</li><li>Filtering - Apply heuristics and filters to create a balanced and diverse feed.</li><li>Mixing non-tweet content like Ads, Follow Recommendations, and Onboarding prompts.</li></ol>The recommendation pipeline runs 5 billion times per day and completes in under 1.5 seconds on average.

Recommendation algorithm

Gets the best 1,500 recent tweets:<ul><li>50% from people you follow (In-Network)</li><li>50% from people you don't follow (Out-of-Network)</li></ul>In-Network<ul><li>Uses a logistic regression model to rank the recent tweets of people you follow. The higher the likelihood of engagement between you and another user, the more of their tweets will be included.</li></ul>Out-of-network<ul><li>Uses a social graph of engagements to find tweets that people you follow have recently engaged with, and tweets liked by people who are similar to you.</li><li>Uses an embedding space of users and tweets to determine what tweets and users are similar to your interests.</li></ul>

Candidate sourcing

Ranking is achieved with a 48M parameter neural network that is continuously trained on tweet interactions to optimize for positive engagement (e.g. Likes, Retweets, and Replies). This ranking mechanism takes into account thousands of features and outputs ten labels to give each tweet a score, where each label represents the probability of an engagement.

Ranking

<ul><li>Visibility Filtering: Remove tweets from accounts you block or mute. </li><li>Author Diversity: Avoid too many consecutive tweets from a single author.</li><li>Content Balance: Deliver a fair balance of In-Network and Out-of-Network tweets.</li><li>Feedback-based Fatigue: Lower the score of tweets that you provided negative feedback around.</li><li>Social Proof: Exclude Out-of-Network tweets without a second degree connection to the tweet i.e. ensure someone you follow engaged with the tweet or follows the tweet’s author.</li><li>Co﻿nversations: Provide more context to a Reply by threading it together with the original tweet.</li></ul>

Apply heuristics and filters

Twitter aims to deliver you the best of what’s happening in the world right now. This blog is an introduction to how the algorithm selects Tweets for your timeline.

artificialintelligence

Artificial Intelligence

Twitter's Recommendation Algorithm

Cassandra stores columns on disk in the clustering order of your table. Therefore, to get the performance, your queries with ORDER BY should match the table's clustering order.
For example, if you often query the newest data in the table, then you should set your clustering order to be <code>(insertion_time DESC)</code>:
<code>CREATE TABLE timeseries ( event_type text, insertion_time timestamp, event blob, PRIMARY KEY (event_type, insertion_time) ) WITH CLUSTERING ORDER BY (insertion_time DESC);</code>

Match your query's ORDER BY to the clustering order

Cassandra allows you to sort your query results in reverse clustering order, but it comes at a cost. Cassandra has to read all partition rows/columns and sort them in-memory, making your queries slower and increasing load on the cluster.The slowdown is proportional to the number of rows and columns you have, and it can become a serious problem if your partitions grow to thousands of rows and dozens of columns.See more info on <a href="https://stackoverflow.com/questions/57931713/cost-of-order-by-in-cassandra">StackOverflow</a>.

Reversing clustering order at query time scans the entire partition

Ordering query results to make use of the on-disk sorting of columns.

Cassandra - Clustering Order

DROP COLUMN only makes the column invisible to SQL operations by setting attisdropped=True in the system catalog table <a href="https://www.postgresql.org/docs/current/catalog-pg-attribute.html">pg_attribute</a>. Existing rows keep the original value, while new rows will store NULL on that column.Thus, dropping a column is quick, but it doesn't reduce the disk size of your table. That space will be reclaimed over time as existing rows are updated. However, if you want to reclaim disk space immediatelly, you can execute VACUUM FULL to force a rewrite of the table.See more info on <a href="https://stackoverflow.com/a/15700213">StackOverflow</a>.

DROP COLUMN doesn't physically remove columns

PostgreSQL - DROP COLUMN doesn't physically remove columns

The XY problem is asking about your attempted solution rather than your actual problem . This leads to wasted time and energy for both the people asking for help and those providing help.<ol><li>User wants to do X.</li><li>User doesn't know how to do X, but thinks they can fumble their way to a solution by doing Y.</li><li>User doesn't know how to do Y either.</li><li>User asks for help with Y.</li><li>Others try to help with Y, but are confused because Y seems like a strange problem to solve.</li><li>Finally, after much interaction, it becomes clear that the user really wants help with X, and that Y wasn't even a suitable solution for X.</li></ol>

What is the XY problem?

<ol><li>Always include information about a broader picture along with any attempted solution.</li><li>If someone asks for more information, do provide details.</li><li>If there are other solutions you've already ruled out, share why you've ruled them out. This gives more information about your requirements.</li></ol>

SQL Performance Explained

Type Checking Paradigms

PostgreSQL: Up and Running

Reflections on Go's 14th Anniversary - Rob Pike

PostgreSQL Replication

Ovidiu Podariu (Tech)