Tarantool development patches archive
 help / color / mirror / Atom feed
From: Konstantin Osipov <kostja@tarantool.org>
To: tarantool-patches@freelists.org
Cc: Vladislav Shpilevoy <v.shpilevoy@tarantool.org>
Subject: [tarantool-patches] Re: [PATCH 1/2] space: add method to fetch next rowid
Date: Wed, 21 Nov 2018 21:58:42 +0300	[thread overview]
Message-ID: <20181121185842.GG18547@chai> (raw)
In-Reply-To: <C7337190-86D3-44B2-AC0A-259592E564E3@tarantool.org>

* n.pettik <korablev@tarantool.org> [18/11/12 16:12]:
> 
> It is true that 2^64 is likely to be quite huge number of tuples,
> but for instance JOIN uses nested-loop algorithm, so it requires
> n^2 memory for ephemeral table to comprise results.
> In this regard, to reach the limit we need 4-way join where each
> table contains 2^16 entries, which in turn doesn’t seem to be giant.
> 
> *It is only thoughts tho, I haven’t tested it since I suppose very likely
>  my pc would simply get stuck.*

intel 64 bit architecture can not address more than 48 bits.

Apart from the fact that you can multiply 4 numbers in a cross
join there is a question how much time this nested loop is going
to run. Imagine it runs 2^48 processor ticks. It's several weeks
by a conservative estimate.
> 
> I wanted to create long test as the easiest solution, but Alexander warned
> me that Travis may not survive such test due to lack of memory.
> 
> 

-- 
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov

  parent reply	other threads:[~2018-11-21 18:58 UTC|newest]

Thread overview: 12+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-10-29 19:02 [tarantool-patches] [PATCH 0/2] Re-implement rowid generation for ephemeral spaces Nikita Pettik
2018-10-29 19:02 ` [tarantool-patches] [PATCH 1/2] space: add method to fetch next rowid Nikita Pettik
2018-10-30  8:45   ` Vladimir Davydov
2018-10-30 10:32     ` n.pettik
2018-11-09  9:25   ` [tarantool-patches] " Vladislav Shpilevoy
2018-11-11 23:16     ` n.pettik
2018-11-11 23:22       ` Vladislav Shpilevoy
2018-11-14 23:11         ` n.pettik
2018-11-21 18:58       ` Konstantin Osipov [this message]
2018-10-29 19:02 ` [tarantool-patches] [PATCH 2/2] sql: use vtab::rowid_next() instead of index_max() Nikita Pettik
2018-11-09  9:25   ` [tarantool-patches] " Vladislav Shpilevoy
2018-11-15  4:54 ` [tarantool-patches] Re: [PATCH 0/2] Re-implement rowid generation for ephemeral spaces Kirill Yukhin

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20181121185842.GG18547@chai \
    --to=kostja@tarantool.org \
    --cc=tarantool-patches@freelists.org \
    --cc=v.shpilevoy@tarantool.org \
    --subject='[tarantool-patches] Re: [PATCH 1/2] space: add method to fetch next rowid' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox