This is how I do it - which uses Ivy. I use it in a currently 1.2 MB file containing the names of students and classes (I teach Business English online to Chinese professionals). I looked around for quite a while to find a way to efficiently insert internal links, the link completion didn't seem to work very well. This article contains the code for the technique I use. It does take a few seconds to find it given the size of the file but I can tolerate that.
http://pragmaticemacs.com/emacs/insert-internal-org-mode-links-the-ivy-way/
Edited to add code.
First, you need to install Ivy (I also installed the related tools Counsel and Swiper). I used Elpa to do this.
https://github.com/abo-abo/swiper
I also installed worf as this code uses it:
https://github.com/abo-abo/worf
Then based on the linked article, I added the following code to init.el:
(ivy-mode 1)
(counsel-mode 1)
(setq ivy-count-format "(%d/%d) ")
(global-set-key (kbd "C-s") 'swiper)
(require 'worf)
(defun bjm/worf-insert-internal-link ()
"Use ivy to insert a link to a heading in the current `org-mode' document. Code is based on `worf-goto'."
(interactive)
(let ((cands (worf--goto-candidates)))
(ivy-read "Heading: " cands
:action 'bjm/worf-insert-internal-link-action)))
(defun bjm/worf-insert-internal-link-action (x)
"Insert link for `bjm/worf-insert-internal-link'"
;; go to heading
(save-excursion
(goto-char (cdr x))
;; store link
(call-interactively 'org-store-link)
)
;; return to original point and insert link
(org-insert-last-stored-link 1)
;; org-insert-last-stored-link adds a newline so delete this
(delete-backward-char 1)
)
;; this is the key that I decided to use to call this function
(global-set-key (kbd "C-c v") (quote bjm/worf-insert-internal-link))