0

I am trying to build a query partitioner for a distributed processing system. This system would work with databases that support JDBC.

The input of this partitioner would be the name of a table, and a column to use for partitioning. Let's assume that there is an index over this column. For example:

Table: customers
Partitioning column: customer_id

From there, I would build the following query:

select * from customers where customer_id >= ? and customer_id < ?

And then, I would like to divide the domain of customer_id into, say, 10 ranges of approximately the same size. I would like to issue a fast query to figure this out.

I found the percentile_cont function in ANSI SQL (good since a lot of databases will support this) - and I wrote this query, which seems to work:

SELECT 
  percentile_cont(customer_id, 0)  over(),
  percentile_cont(customer_id, 0.1)  over(),
  percentile_cont(customer_id, 0.2)  over(),
  percentile_cont(customer_id, 0.3)  over(),
  percentile_cont(customer_id, 0.4)  over(),
  percentile_cont(customer_id, 0.5)  over(),
  percentile_cont(customer_id, 0.6)  over(),
  percentile_cont(customer_id, 0.7)  over(),
  percentile_cont(customer_id, 0.8)  over(),
  percentile_cont(customer_id, 0.9)  over(),
  percentile_cont(customer_id, 1)  over()
FROM customers LIMIT 1

My questions are:

  1. If the column customer_id is indexed - will this query be reasonably fast to quickly generate ranges and then use them to parallelize 10 queries?
  2. Is there any other way of finding similarly-sized ranges for a given table using a partitioning column?
3
  • Parallelizing a query by yourself is probably a bad idea. Most DBMSs can parallelize anyway where appropriate, and doing it yourself will probably just slow things down more Oct 31 '21 at 10:56
  • thanks - I am working on a data processing framework, and our users want to be able to parallelize reading data out of their Jdbc database. This is why I'm looking to parallelize queries 'manually'
    – Pablo
    Nov 2 '21 at 1:20
  • Jdbc is not a database, it's a database API specification. And what do you mean "users want to be able to parallelize" why would the users care? Is this not just a possible performance optimization? I suggest you limit yourself to specific RDBMS products, which may have fast ways of reading existing histograms to get the data you want, for example sys.dm_db_stats_histogram on SQL Server Nov 2 '21 at 1:34
3

I have bad news for you. What you want to do is going to be a lot harder than you were anticipating.

Most databases implement much of the ANSI SQL standard, but they do not implement all parts of it, especially for something more advanced like window functions. Some database platforms don't even support the LIMIT construct that you used. You'll need to prepare for writing different code for each database platform that you support.

It is unlikely that the database that you connect to will have an index on every column of every table. You will need some kind of control over the schema of the database that you're querying to get a schema that allow for reasonable performance of the queries that you want to run. Even then, a standard b-tree index doesn't allow for fast computations of percentiles.

The query optimizers of each database platform work in significantly different ways. A query that is fast on one platform may be slow on another. Consider the following simple query against an indexed ID column:

SELECT MIN(ID), MAX(ID)
FROM table;

That query used to be extremely fast on SQL Server but would require two table scans on Oracle (newer versions of Oracle may have improved the query optimizer to no longer need the table scans). That query is significantly simpler than yours. I would not expect the approach that you used in the question to perform well on most platforms. I changed your syntax to one supported by SQL Server and the query didn't finish after six minutes against a table with about six million rows.

You should also consider relaxing the problem statement to allow for approximate results. If the goal is to split the data into parts and to process each part on a different system, then you probably don't need to send exactly 10% of the table to each system. Allowing for approximate results will greatly improve the performance of the query for some approaches, especially if the target tables are very large.

I suggest changing the question you asked to something resembling the following: "For database platform X, how can I compute fast (define fast) quantiles for a table with Y rows under Z isolation level?" With that type of question, a database expert for that platform may be able to help you. However, some platforms may not allow for an answer to be calculated as quickly as you'd like due to limitations of those platforms.

To give you an idea of what a well-performing solution would look like, I'll provide an example solution for the following question: "For database platform SQL Server, how can I compute quantiles for a table with 6.5 M rows under a SERIALIZABLE isolation level within 1 second?"

First I'll add 6.5 million rows to a table with a clustered columnstore index:

CREATE TABLE part_test (
    ID1 BIGINT NOT NULL,
    ID2 BIGINT NOT NULL,
    ID3 VARCHAR(3) NOT NULL,
    ID4 VARCHAR(10) NOT NULL,
    ID5 DATETIME NOT NULL,
    INDEX CCI CLUSTERED COLUMNSTORE
);

INSERT INTO part_test WITH (TABLOCK)
SELECT RN, RN % 100000, LEFT(CAST(NEWID() AS VARCHAR(40)), 3), REPLICATE(CHAR(RN % 60 + 10), 10), DATEADD(SECOND, RN, GETDATE())
FROM
(
    SELECT ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) RN
    FROM master..spt_values t1
    CROSS JOIN master..spt_values t2
) q
OPTION (MAXDOP 1);

The reason I specified the SERIALIZABLE isolation level is it allows me to split the query up into two parts. I found it to be much easier to write fast code to solve this problem by using two queries. While the queries are running, no other process will be able to modify the data in the table. You need to decide if that's acceptable or not. Here is one method of calculating the percentiles:

BEGIN TRANSACTION;
DECLARE @CNT BIGINT, @MIN BIGINT, @MAX BIGINT;

SELECT @CNT = COUNT_BIG(*), @MIN = MIN(ID1), @MAX = MAX(ID1)
FROM part_test WITH (TABLOCK, SERIALIZABLE);

SELECT ID1
FROM 
(
    SELECT TOP (9) ID1
    FROM
    (
        SELECT ID1, ROW_NUMBER() OVER (ORDER BY ID1) RN
        FROM part_test WITH (TABLOCK)
    ) q
    WHERE RN % (@CNT / 10) = (@CNT / 10) - 1 -- math may not be exactly right here, but it's just a proof of concept
    ORDER BY ID1
) q

UNION ALL SELECT @MIN

UNION ALL SELECT @MAX

ORDER BY ID1;

COMMIT TRANSACTION;

That query finishes in about 200 ms on my 8 CPU core desktop. It's important to understand that this approach does a sort. Performance will get worse as the table gets more rows, especially if the sort cannot be performed in memory. As the table size gets bigger, a completely different strategy may perform better. That's one of the reasons that I mentioned that allowing for approximate results may help you.

It's also important to understand that the approach that I used is very specific to SQL Server. It's great if something like this meets your needs for SQL Server, but the solution for other database platforms will likely look significantly different from it.

1

It's unclear why you want to partition the data in such a way. It seems you are only doing it "in order to parallelize queries", but most DBMSs have much better ways of parallelizing queries.

Either way, if you can customize your code to a specific DBMS, you may be able to query the histogram data very efficiently, instead of doing a massive scan on a huge table.

For example, in SQL Server, you could do something like this:

SELECT
  range_high_key,
  Centile = RunningRows * 100.0 / TotalRows
FROM (
    SELECT 
      RunningRows = SUM(range_rows) OVER (ORDER BY CAST(range_high_key AS int) ROWS UNBOUNDED PRECEDING),
      TotalRows = SUM(range_rows) OVER (),
      range_high_key = CAST(range_high_key AS int)
    FROM sys.tables t
    JOIN sys.stats s ON s.object_id = t.object_id
    CROSS APPLY sys.dm_db_stats_histogram(t.object_id, 1) h
    WHERE t.name = 't'
) h;

db<>fiddle

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.