- Introduction
- Concepts
- Architecture
- Key Features
- Horizontal Scalability
- MySQL Compatible Syntax
- Replicate from and to MySQL
- Distributed Transactions with Strong Consistency
- Cloud Native Architecture
- Minimize ETL with HTAP
- Fault Tolerance & Recovery with Raft
- Automatic Rebalancing
- Deployment and Orchestration with Ansible, Kubernetes, Docker
- JSON Support
- Spark Integration
- Read Historical Data Without Restoring from Backup
- Fast Import and Restore of Data
- Hybrid of Column and Row Storage
- SQL Plan Management
- Open Source
- Online Schema Changes
- How-to
- Get Started
- Deploy
- Hardware Recommendations
- From Binary Tarball
- Orchestrated Deployment
- Geographic Redundancy
- Data Migration with Ansible
- Configure
- Secure
- Transport Layer Security (TLS)
- Generate Self-signed Certificates
- Monitor
- Migrate
- Maintain
- Scale
- Upgrade
- Troubleshoot
- Reference
- SQL
- MySQL Compatibility
- SQL Language Structure
- Data Types
- Functions and Operators
- Function and Operator Reference
- Type Conversion in Expression Evaluation
- Operators
- Control Flow Functions
- String Functions
- Numeric Functions and Operators
- Date and Time Functions
- Bit Functions and Operators
- Cast Functions and Operators
- Encryption and Compression Functions
- Information Functions
- JSON Functions
- Aggregate (GROUP BY) Functions
- Miscellaneous Functions
- Precision Math
- SQL Statements
ADD COLUMN
ADD INDEX
ADMIN
ADMIN CANCEL DDL
ADMIN CHECKSUM TABLE
ADMIN CHECK [TABLE|INDEX]
ADMIN SHOW DDL [JOBS|QUERIES]
ALTER DATABASE
ALTER TABLE
ALTER USER
ANALYZE TABLE
BEGIN
CHANGE COLUMN
COMMIT
CREATE DATABASE
CREATE INDEX
CREATE TABLE LIKE
CREATE TABLE
CREATE USER
DEALLOCATE
DELETE
DESC
DESCRIBE
DO
DROP COLUMN
DROP DATABASE
DROP INDEX
DROP TABLE
DROP USER
EXECUTE
EXPLAIN ANALYZE
EXPLAIN
FLUSH PRIVILEGES
FLUSH STATUS
FLUSH TABLES
GRANT <privileges>
INSERT
KILL [TIDB]
LOAD DATA
LOAD STATS
MODIFY COLUMN
PREPARE
RENAME INDEX
RENAME TABLE
REPLACE
REVOKE <privileges>
ROLLBACK
SELECT
SET [NAMES|CHARACTER SET]
SET PASSWORD
SET TRANSACTION
SET [GLOBAL|SESSION] <variable>
SHOW CHARACTER SET
SHOW COLLATION
SHOW [FULL] COLUMNS FROM
SHOW CREATE TABLE
SHOW DATABASES
SHOW ENGINES
SHOW ERRORS
SHOW [FULL] FIELDS FROM
SHOW GRANTS
SHOW INDEXES [FROM|IN]
SHOW INDEX [FROM|IN]
SHOW KEYS [FROM|IN]
SHOW PRIVILEGES
SHOW [FULL] PROCESSSLIST
SHOW SCHEMAS
SHOW STATUS
SHOW [FULL] TABLES
SHOW TABLE STATUS
SHOW [GLOBAL|SESSION] VARIABLES
SHOW WARNINGS
START TRANSACTION
TRACE
TRUNCATE
UPDATE
USE
- Constraints
- Generated Columns
- Character Set
- Configuration
- Security
- Transactions
- System Databases
- Errors Codes
- Supported Client Drivers
- Garbage Collection (GC)
- Performance
- Key Monitoring Metrics
- Alert Rules
- Best Practices
- TiSpark
- TiDB Binlog
- Tools
- Overview
- Use Cases
- Download
- Mydumper
- Syncer
- Loader
- TiDB Data Migration
- TiDB Lightning
- sync-diff-inspector
- PD Control
- PD Recover
- TiKV Control
- TiDB Control
- FAQs
- Support
- Contribute
- Releases
- All Releases
- v2.1
- v2.0
- v1.0
- Glossary
You are viewing the documentation of an older version of the TiDB database (TiDB v2.1).
TopN and Limit Operator Push Down
This document describes the implementation of TopN and Limit operator pushdown.
In the TiDB execution plan tree, the LIMIT
clause in SQL corresponds to the Limit operator node, and the ORDER BY
clause corresponds to the Sort operator node. The adjacent Limit operator and Sort operator are combined as the TopN operator node, which means that the top N records are returned according to a certain sorting rule. That is to say, a Limit operator is equivalent to a TopN operator node with a null sorting rule.
Similar to predicate pushdown, TopN and Limit are pushed down in the execution plan tree to a position as close to the data source as possible so that the required data is filtered at an early stage. In this way, the pushdown significantly reduces the overhead of data transmission and calculation.
Examples
This section illustrates TopN pushdown through some examples.
Example 1: Push down to the Coprocessors in the storage layer
create table t(id int primary key, a int not null);
explain select * from t order by a limit 10;
+----------------------------+----------+-----------+---------------+--------------------------------+
| id | estRows | task | access object | operator info |
+----------------------------+----------+-----------+---------------+--------------------------------+
| TopN_7 | 10.00 | root | | test.t.a, offset:0, count:10 |
| └─TableReader_15 | 10.00 | root | | data:TopN_14 |
| └─TopN_14 | 10.00 | cop[tikv] | | test.t.a, offset:0, count:10 |
| └─TableFullScan_13 | 10000.00 | cop[tikv] | table:t | keep order:false, stats:pseudo |
+----------------------------+----------+-----------+---------------+--------------------------------+
4 rows in set (0.00 sec)
In this query, the TopN operator node is pushed down to TiKV for data filtering, and each Coprocessor returns only 10 records to TiDB. After TiDB aggregates the data, the final filtering is performed.
Example 2: TopN can be pushed down into Join (the sorting rule only depends on the columns in the outer table)
create table t(id int primary key, a int not null);
create table s(id int primary key, a int not null);
explain select * from t left join s on t.a = s.a order by t.a limit 10;
+----------------------------------+----------+-----------+---------------+-------------------------------------------------+
| id | estRows | task | access object | operator info |
+----------------------------------+----------+-----------+---------------+-------------------------------------------------+
| TopN_12 | 10.00 | root | | test.t.a, offset:0, count:10 |
| └─HashJoin_17 | 12.50 | root | | left outer join, equal:[eq(test.t.a, test.s.a)] |
| ├─TopN_18(Build) | 10.00 | root | | test.t.a, offset:0, count:10 |
| │ └─TableReader_26 | 10.00 | root | | data:TopN_25 |
| │ └─TopN_25 | 10.00 | cop[tikv] | | test.t.a, offset:0, count:10 |
| │ └─TableFullScan_24 | 10000.00 | cop[tikv] | table:t | keep order:false, stats:pseudo |
| └─TableReader_30(Probe) | 10000.00 | root | | data:TableFullScan_29 |
| └─TableFullScan_29 | 10000.00 | cop[tikv] | table:s | keep order:false, stats:pseudo |
+----------------------------------+----------+-----------+---------------+-------------------------------------------------+
8 rows in set (0.01 sec)
In this query, the sorting rule of the TopN operator only depends on the columns in the outer table t
, so a calculation can be performed before pushing down TopN to Join, to reduce the calculation cost of the Join operation. Besides, TiDB also pushes TopN down to the storage layer.
Example 3: TopN cannot be pushed down before Join
create table t(id int primary key, a int not null);
create table s(id int primary key, a int not null);
explain select * from t join s on t.a = s.a order by t.id limit 10;
+-------------------------------+----------+-----------+---------------+--------------------------------------------+
| id | estRows | task | access object | operator info |
+-------------------------------+----------+-----------+---------------+--------------------------------------------+
| TopN_12 | 10.00 | root | | test.t.id, offset:0, count:10 |
| └─HashJoin_16 | 12500.00 | root | | inner join, equal:[eq(test.t.a, test.s.a)] |
| ├─TableReader_21(Build) | 10000.00 | root | | data:TableFullScan_20 |
| │ └─TableFullScan_20 | 10000.00 | cop[tikv] | table:s | keep order:false, stats:pseudo |
| └─TableReader_19(Probe) | 10000.00 | root | | data:TableFullScan_18 |
| └─TableFullScan_18 | 10000.00 | cop[tikv] | table:t | keep order:false, stats:pseudo |
+-------------------------------+----------+-----------+---------------+--------------------------------------------+
6 rows in set (0.00 sec)
TopN cannot be pushed down before Inner Join
. Taking the query above as an example, if you get 100 records after Join, then you can have 10 records left after TopN. However, if TopN is performed first to get 10 records, only 5 records are left after Join. In such cases, the pushdown results in different results.
Similarly, TopN can neither be pushed down to the inner table of Outer Join, nor can it be pushed down when its sorting rule is related to columns on multiple tables, such as t.a+s.a
. Only when the sorting rule of TopN exclusively depends on columns on the outer table, can TopN be pushed down.
Example 4: Convert TopN to Limit
create table t(id int primary key, a int not null);
create table s(id int primary key, a int not null);
explain select * from t left join s on t.a = s.a order by t.id limit 10;
+----------------------------------+----------+-----------+---------------+-------------------------------------------------+
| id | estRows | task | access object | operator info |
+----------------------------------+----------+-----------+---------------+-------------------------------------------------+
| TopN_12 | 10.00 | root | | test.t.id, offset:0, count:10 |
| └─HashJoin_17 | 12.50 | root | | left outer join, equal:[eq(test.t.a, test.s.a)] |
| ├─Limit_21(Build) | 10.00 | root | | offset:0, count:10 |
| │ └─TableReader_31 | 10.00 | root | | data:Limit_30 |
| │ └─Limit_30 | 10.00 | cop[tikv] | | offset:0, count:10 |
| │ └─TableFullScan_29 | 10.00 | cop[tikv] | table:t | keep order:true, stats:pseudo |
| └─TableReader_35(Probe) | 10000.00 | root | | data:TableFullScan_34 |
| └─TableFullScan_34 | 10000.00 | cop[tikv] | table:s | keep order:false, stats:pseudo |
+----------------------------------+----------+-----------+---------------+-------------------------------------------------+
8 rows in set (0.00 sec)
In the query above, TopN is first pushed to the outer table t
. TopN needs to sort by t.id
, which is the primary key and can be directly read in order (keep order: true
) without extra sorting in TopN. Therefore, TopN is simplified as Limit.