Clickhouse: Slow order by primary key with small limit on big data

[gsmetal]

Hello. I have such table:

CREATE TABLE logs.logs ( timestamp DateTime,  nsec UInt32,  `string_fields.names` Array(String),  `string_fields.values` Array(String),  `number_fields.names` Array(String),  `number_fields.values` Array(Float64),  `boolean_fields.names` Array(String),  `boolean_fields.values` Array(Float64),  `null_fields.names` Array(String),  date Date MATERIALIZED toDate(timestamp)) ENGINE = MergeTree(date, (timestamp, nsec), 32768)

It has 4,3 billion records:

:) select count() from logs;

SELECT count()
FROM logs 

┌────count()─┐
│ 4277567828 │
└────────────┘

1 rows in set. Elapsed: 1.565 sec. Processed 4.28 billion rows, 17.11 GB (2.73 billion rows/s., 10.93 GB/s.) 

When I just select with small limit, everything works perfect:

:) select * from logs limit 5;

SELECT *
FROM logs 
LIMIT 5

...

5 rows in set. Elapsed: 0.034 sec. 

But it returns first five logs, but what if I want to get last five logs? I do this by ordering by primary key:

:) select * from logs order by timestamp desc, nsec desc limit 5;

SELECT *
FROM logs 
ORDER BY 
    timestamp DESC, 
    nsec DESC
LIMIT 5

↙ Progress: 111.15 million rows, 58.55 GB (8.27 million rows/s., 4.36 GB/s.) ██▍                                                                                             2%^← Progress: 111.97 million rows, 58.98 GB (8.27 million rows/s., 4.36 GB/s.) ██▍                                                                                             2%Cancelling query.
Ok.
Query was cancelled.

0 rows in set. Elapsed: 13.642 sec. Processed 111.97 million rows, 58.98 GB (8.21 million rows/s., 4.32 GB/s.) 

It starts processing all 4.3 billion rows, so it's slow.

Even if I use WHERE to reduce number of rows it's not so fast:

:) select count() from logs where timestamp > '2017-10-09 08:00:00';

SELECT count()
FROM logs 
WHERE timestamp > '2017-10-09 08:00:00'

┌──count()─┐
│ 43025631 │
└──────────┘

1 rows in set. Elapsed: 0.036 sec. Processed 44.83 million rows, 179.31 MB (1.26 billion rows/s., 5.04 GB/s.) 

:) select * from logs where timestamp > '2017-10-09 08:00:00' order by timestamp desc, nsec desc limit 5;

SELECT *
FROM logs 
WHERE timestamp > '2017-10-09 08:00:00'
ORDER BY 
    timestamp DESC, 
    nsec DESC
LIMIT 5

...

5 rows in set. Elapsed: 5.054 sec. Processed 44.83 million rows, 23.60 GB (8.87 million rows/s., 4.67 GB/s.) 

5 seconds on selecting 5 rows from 45 million rows when order by primary key looks slow.

Is this OK? What am I doing wrong in getting last N rows (by primary key)? Or maybe table is configured wrong?

PS. Versions is:

ClickHouse client version 1.1.54289.
Connecting to clickhouse:9000.
Connected to ClickHouse server version 1.1.54289.

[KochetovNicolai]

Hello.

ClickHouse don't have optimization which allows skipping rows while reading first (or last) N rows ordered by primary key. So, results you see are expected.

Even when you need to read first N rows, ordered by primary key, it's necessary to merge data from different parts, which is full scan if your query doesn't have limitation on date column or primary key.

However, it's possible to implement more efficiently: read first (or last) N rows from each block. (Also, there are some other technical details).

[distol]

Hi!

If you store (structured) logs, it's a frequent need to see "last logs". In this scenario, table primary key is timestamp (or, timestamp + nanoseconds, as shown above).

Time-to-time it could be "last logs" without any filter, or filtering by couple columns. But it always last logs. By last I mean last 500-1000 results, it's usually enough.

Will this optimisation be implemented in some near future? Or maybe you could suggest some workaround for this case?

[gsmetal]

If it's possible in clichouse internals to just get last N elements without full scan, maybe there shoud be special construction like LIMIT -10 or something like that? It always possible to make count first and then do LIMIT (COUNT - N), N, but this realisation seems a little weird.

[gsmetal]

Just tried, this limit-with-offset solution also does not work, it does full scan:

:) select count() from logs;

SELECT count()
FROM logs 

┌────count()─┐
│ 4277567828 │
└────────────┘

1 rows in set. Elapsed: 1.362 sec. Processed 4.28 billion rows, 17.11 GB (3.14 billion rows/s., 12.56 GB/s.) 

:) select * from logs limit 4277567818, 10;

SELECT *
FROM logs 
LIMIT 4277567818, 10

↖ Progress: 216.17 million rows, 113.77 GB (10.33 million rows/s., 5.44 GB/s.) ████▋                                                                                         4%^↑ Progress: 217.02 million rows, 114.22 GB (10.32 million rows/s., 5.43 GB/s.) ████▋                                                                                         5%Cancelling query.
Ok.
Query was cancelled.

0 rows in set. Elapsed: 21.151 sec. Processed 217.02 million rows, 114.22 GB (10.26 million rows/s., 5.40 GB/s.) 

:) 

[KochetovNicolai]

To improve performance, you can add limits on primary key. For example, use
SELECT * from logs where date = today()
or
SELECT * from logs where dateTime > now() - 60 * 60

[nvartolomei]

Hello, does the ClickHouse team have any plans regarding on improving this query pattern?

ps. Also, I'm interested in this optimisation to work together with where conditions.

[alexey-milovidov]

This is planned to do after more fundamental modifications in query pipeline.
These modifications are planned for Q4. You may look at the prototype here: https://github.com/yandex/ClickHouse/compare/processors#diff-d84e5dc28812accede7d6803ffb73be9R13

[alikrubin]

Yes, that will be a great feature, @alexey-milovidov, could you share when it will be available.

Meanwhile I came up with the following workaround:

```select * from rc where created_utc > (select max(created_utc) from rc) - 606024 and subreddit='programming' order by created_utc desc limit 10;

10 rows in set. Elapsed: 4.768 sec. Processed 3.05 million rows, 57.34 MB (638.84 thousand rows/s., 12.03 MB/s.)

It may require an iterative process -  

1.
SELECT count()
FROM rc
WHERE (created_utc > (
(
SELECT max(created_utc)
FROM rc
) - ((60 * 60) * 24))) AND (subreddit = 'programming')

┌─count()─┐
│ 1248 │
└─────────┘

1 rows in set. Elapsed: 4.510 sec. Processed 3.05 million rows, 56.83 MB (675.38 thousand rows/s., 12.60 MB/s.) ```

1. select * ...

[alexey-milovidov]

It will be fixed by this PR: #5042

[alexey-milovidov]

Fixed in master.

[alexey-milovidov]

Some optimizations still remain: exponential growth of read window from some small value.